You are looking at a specific version 20110810:123632 of this paper. See the latest version.

Paper 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.

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 functionslattices
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.