2012 | OriginalPaper | Buchkapitel
Pseudorandom Functions and Lattices
verfasst von : Abhishek Banerjee, Chris Peikert, Alon Rosen
Erschienen in: Advances in Cryptology – EUROCRYPT 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We give direct constructions of pseudorandom function (PRF) families based on conjectured hard lattice problems and learning problems. Our constructions are asymptotically efficient and highly parallelizable in a practical sense, i.e., they can be computed by simple, relatively
small
low-depth arithmetic or boolean circuits (e.g., in NC
1
or even TC
0
). In addition, they are the first low-depth PRFs that have no known attack by efficient quantum algorithms. Central to our results is a new “derandomization” technique for the learning with errors (
LWE
) problem which, in effect, generates the error terms deterministically.