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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2016
Keywords
Symmetric CryptographyLow-depth PRFsLearning Parity with Noise
Contact author(s)
yuyuathk @ gmail com
History
2016-02-25: last of 4 revisions
2016-02-18: received
See all versions
Short URL
https://ia.cr/2016/151
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/151,
      author = {Yu Yu and John Steinberger},
      title = {Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN},
      howpublished = {Cryptology ePrint Archive, Paper 2016/151},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/151}},
      url = {https://eprint.iacr.org/2016/151}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.