Pseudorandom Functions and Lattices

Abhishek Banerjee; Chris Peikert; Alon Rosen

Paper 2011/401

Pseudorandom Functions and Lattices

Abhishek Banerjee, Chris Peikert, and Alon Rosen

Abstract

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 \emph{small} low-depth arithmetic or boolean circuits (e.g., in NC or even TC). 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.

Note: Minor changes to ring-LWE background.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: pseudorandom functions lattices
Contact author(s): cpeikert @ cc gatech edu
History: 2011-08-10: last of 2 revisions; 2011-07-28: received; See all versions
Short URL: https://ia.cr/2011/401
License: CC BY

BibTeX

@misc{cryptoeprint:2011/401,
      author = {Abhishek Banerjee and Chris Peikert and Alon Rosen},
      title = {Pseudorandom Functions and Lattices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/401},
      year = {2011},
      url = {https://eprint.iacr.org/2011/401}
}