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 NO~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 "derandom-ization" technique for the learning with errors (LWE) problem which, in effect, generates the error terms deterministically.
展开▼
