Efficient polynomial evaluations with preprocessing and applications to cryptography

Abstract

In [20], Kedlaya and Umans proposed an algorithm that, after doing some preprocessing, enables fast evaluation of a multivariate polynomial. Recently, this algorithm has been used to achieve a breakthrough in cryptography, building an unkeyed DEPIR (Doubly Efficient Private Information Retrieval) in [22]. This construction allows, only after one run of a preprocessing algorithm on a database, efficient private access to it for any client. The goal of this TFM is to realize an implementation (the first one to the best of our knowledge) of the algorithm by Kedlaya and Umans in order to understand its practical performance and also, to build a new polynomial commitment based on it. Our new polynomial commitment scheme allows the prover to compute proofs for evaluations in time sublinear in the size of the polynomial. We achieve this by committing to the data structure resulting from preprocessing the polynomial using a vector commitment scheme with logarithmic opening run-time. We also analyze the efficiency and the security of this construction, discuss its limitations and possible strenghtenings.