RT Generic
T1 Efficient polynomial evaluations with preprocessing and applications to cryptography
A1 Carrillo Redondo, Mario
AB 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.
YR 2024
FD 2024
LK https://hdl.handle.net/20.500.14352/107970
UL https://hdl.handle.net/20.500.14352/107970
LA eng
NO Trabajo de Fin de Máster en Métodos Formales, Facultad de Informática UCM, Departamento de Sistemas Informáticos y Computación, Curso 2023/2024.
DS Docta Complutense
RD 5 abr 2025