Fiore, DarioCascudo, IgnacioCarrillo Redondo, Mario2024-09-052024-09-052024https://hdl.handle.net/20.500.14352/107970Trabajo 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.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.engmaster thesisopen access004(043.3)CryptographyPolynomial CommitmentsVector CommitmentsFast PolynomialEvaluationDEPIRCriptografíaCompromisos de PolinomioCompromisos VectorialesEvaluación Rápida de PolinomiosInformática (Informática)33 Ciencias Tecnológicas