ECCC-Report TR14-033https://eccc.weizmann.ac.il/report/2014/033Comments and Revisions published for TR14-033en-usMon, 16 Jun 2014 05:09:24 +0300
Revision 1
| Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$ |
Siyao Guo,
Adi Akavia,
Andrej Bogdanov,
Alon Rosen,
Akshay Kamath
https://eccc.weizmann.ac.il/report/2014/033#revision1Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for constructing weak PRFs. To this end
1. We conjecture that the function family $F_A(x) = g(Ax)$, where $A$ is a random square $GF(2)$ matrix and $g$ is a carefully chosen function of constant depth, is a weak PRF. In support of our conjecture, we show that functions in this family are inapproximable by $GF(2)$ polynomials and do not correlate with any fixed Boolean function family of subexponential size.
2. We study the class $\mathrm{AC}0 \circ \mathrm{MOD}_2$ that captures the complexity of our construction. We conjecture that all functions in this class have a Fourier coefficient of magnitude $\exp(- \poly \log n)$ and prove this conjecture in the case when the $\mathrm{MOD}_2$ function is typical.
3. We investigate the relation between the hardness of learning noisy parities and the existence of weak PRFs in $\mathrm{AC}0 \circ \mathrm{MOD}_2$.
We argue that such a complexity-driven approach can play a role in bridging the gap between the theory and practice of cryptography.Mon, 16 Jun 2014 05:09:24 +0300https://eccc.weizmann.ac.il/report/2014/033#revision1
Paper TR14-033
| Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$ |
Siyao Guo,
Adi Akavia,
Andrej Bogdanov,
Alon Rosen,
Akshay Kamath
https://eccc.weizmann.ac.il/report/2014/033Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for constructing weak PRFs. To this end
1. We conjecture that the function family $F_A(x) = g(Ax)$, where $A$ is a random square $GF(2)$ matrix and $g$ is a carefully chosen function of constant depth, is a weak PRF. In support of our conjecture, we show that functions in this family are inapproximable by $GF(2)$ polynomials of low degree and do not correlate with any fixed Boolean function family of subexponential size.
2. We study the class $\mathrm{AC}0 \circ \mathrm{MOD}_2$ that captures the complexity of our construction. We conjecture that all functions in this class have a Fourier coefficient of magnitude $\exp(- \poly \log n)$ and prove this conjecture in the case when the $\mathrm{MOD}_2$ function is typical.
3. We investigate the relation between the hardness of learning noisy parities and the existence of weak PRFs in $\mathrm{AC}0 \circ \mathrm{MOD}_2$.
We argue that such a complexity-driven approach can play a role in bridging the gap between the theory and practice of cryptography.Mon, 10 Mar 2014 07:51:11 +0200https://eccc.weizmann.ac.il/report/2014/033