Cryptology ePrint Archive: Report 2011/401

Pseudorandom Functions and Lattices

Abhishek Banerjee and 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$^{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.

Category / Keywords: foundations / pseudorandom functions, lattices

Date: received 26 Jul 2011, last revised 10 Aug 2011

Contact author: cpeikert at cc gatech edu

Available formats: PDF | BibTeX Citation

Note: Minor changes to ring-LWE background.

Version: 20110810:123632 (All versions of this report)

Discussion forum: Show discussion | Start new discussion