Paper Info
Title
Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN.
Abstract
Pseudorandom functions PRFs play a central role in symmetric cryptography. While in principle they can be built from any one-way functions by going through the generic HILL SICOMP 1999 and GGM JACM 1986 transforms, some of these steps are inherently sequential and far from practical. Naor, Reingold FOCS 1997 and Rosen SICOMP 2002 gave parallelizable constructions of PRFs in NC$$^2$$2 and TC$$^0$$0 based on concrete number-theoretic assumptions such as DDH, RSA, and factoring. Banerjee, Peikert, and Rosen Eurocrypt 2012 constructed relatively more efficient PRFs in NC$$^1$$1 and TC$$^0$$0 based on \"learning with errors\" LWE for certain range of parameters. It remains an open problem whether parallelizable PRFs can be based on the \"learning parity with noise\" LPN problem for both theoretical interests and efficiency reasons as the many modular multiplications and additions in LWE would then be simplified to AND and XOR operations under LPN. In this paper, we give more efficient and parallelizable constructions of randomized PRFs from LPN under noise rate $$n^{-c}$$n-c for any constant $$0<c<1$$0<c<1 and they can be implemented with a family of polynomial-size circuits with unbounded fan-in AND, OR and XOR gates of depth $$\\omega 1$$ω1, where $$\\omega 1$$ω1 can be any small super-constant e.g., $$\\log \\log \\log {n}$$logloglogn or even less. Our work complements the lower bound results by Razborov and Rudich STOC 1994 that PRFs of beyond quasi-polynomial security are not contained in AC$$^0$$0MOD$$_2$$2, i.e., the class of polynomial-size, constant-depth circuit families with unbounded fan-in AND, OR, and XOR gates. Furthermore, our constructions are security-lifting by exploiting the redundancy of low-noise LPN. We show that in addition to parallelizability in almost constant depth the PRF enjoys either of or any tradeoff between the following:A PRF on a weak key of sublinear entropy or equivalently, a uniform key that leaks any $$1 - o1$$1-o1-fraction has comparable security to the underlying LPN on a linear size secret.A PRF with key length $$\\lambda $$λ can have security up﾿to $$2^{O\\lambda /\\log \\lambda }$$2Oλ/logλ, which goes much beyond the security level of the underlying low-noise LPN. where adversary makes up﾿to certain super-polynomial amount of queries.
Year
DOI
Venue
2016
10.1007/978-3-662-49896-5_6
IACR Cryptology ePrint Archive
Field
DocType
Volume
Weak key,Parallelizable manifold,Sublinear function,Discrete mathematics,Combinatorics,Upper and lower bounds,XOR gate,Key size,Mathematics,Learning with errors,Pseudorandom number generator
Journal
2016
ISSN
Citations 
PageRank 
0302-9743
3
0.37
References 
Authors
34
2
Name
Order
Citations
PageRank
Yu Yu121930.37
John P. Steinberger232918.30