TY - GEN
T1 - Pseudorandom functions in almost constant depth from low-noise LPN
AU - Yu, Yu
AU - Steinberger, John
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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 NC2 and TC0 based on concrete number-theoretic assumptions such as DDH, RSA, and factoring. Banerjee, Peikert, and Rosen (Eurocrypt 2012) constructed relatively more efficient PRFs in NC1 and TC0 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 polynomialsize circuits with unbounded fan-in AND, OR and XOR gates of depth ω(1), where ω(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 AC0(MOD2), 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 − o(1))-fraction) has comparable security to the underlying LPN on a linear size secret. – A PRF with key length λ can have security up to 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.
AB - 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 NC2 and TC0 based on concrete number-theoretic assumptions such as DDH, RSA, and factoring. Banerjee, Peikert, and Rosen (Eurocrypt 2012) constructed relatively more efficient PRFs in NC1 and TC0 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 polynomialsize circuits with unbounded fan-in AND, OR and XOR gates of depth ω(1), where ω(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 AC0(MOD2), 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 − o(1))-fraction) has comparable security to the underlying LPN on a linear size secret. – A PRF with key length λ can have security up to 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.
UR - https://www.scopus.com/pages/publications/84964939473
U2 - 10.1007/978-3-662-49896-5_6
DO - 10.1007/978-3-662-49896-5_6
M3 - 会议稿件
AN - SCOPUS:84964939473
SN - 9783662498958
T3 - Lecture Notes in Computer Science
SP - 154
EP - 183
BT - Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
A2 - Fischlin, Marc
A2 - Coron, Jean-Sebastien
PB - Springer Verlag
T2 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016
Y2 - 8 May 2016 through 12 May 2016
ER -