Paper 2016/151

Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN

Yu Yu and John Steinberger

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\) and TC\(^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\) and TC\(^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}\) (for any constant 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)\), where \(\omega(1)\) can be any small super-constant (e.g., \(\log\log\log{n}\) 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\)(MOD\(_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: (1) A PRF on a weak key of sublinear entropy (or equivalently, a uniform key that leaks any \((1 - o(1))\)-fraction) has comparable security to the underlying LPN on a linear size secret. (2) A PRF with key length \(\lambda\) can have security up to \(2^{O(\lambda/\log\lambda)}\), which goes much beyond the security level of the underlying low-noise LPN. where adversary makes up to certain super-polynomial amount of queries.