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.
Category / Keywords: secret-key cryptography / Symmetric Cryptography, Low-depth PRFs, Learning Parity with Noise Original Publication (with minor differences): IACR-EUROCRYPT-2016 Date: received 17 Feb 2016, last revised 25 Feb 2016 Contact author: yuyuathk at gmail com Available format(s): PDF | BibTeX Citation Version: 20160225:135646 (All versions of this report) Short URL: ia.cr/2016/151 Discussion forum: Show discussion | Start new discussion