Name
Abstract | ||
|---|---|---|
Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class AC0 (MOD2). 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 We conjecture that the function family FA(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. We study the class AC0 ○ MOD2 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 MOD2 function is typical. We investigate the relation between the hardness of learning noisy parities and the existence of weak PRFs in AC0 ○ MOD2. We argue that such a complexity-driven approach can play a role in bridging the gap between the theory and practice of cryptography. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2554797.2554821 | ITCS |
Keywords | DocType | Volume |
class AC0,weak PRFs,weak pseudorandom function,weak PRF,candidate weak pseudorandom function,minimal complexity requirement,fixed Boolean function family,MOD2 function,function family FA,Pseudorandom function,complexity limitation | Journal | 21 |
Citations | PageRank | References |
1 | 0.35 | 16 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adi Akavia | 1 | 395 | 15.47 |
| Andrej Bogdanov | 2 | 458 | 31.53 |
| Siyao Guo | 3 | 50 | 5.01 |
| Akshay Kamath | 4 | 1 | 1.02 |
| Alon Rosen | 5 | 1360 | 60.54 |