Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

Pseudorandom 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 ... more >>>

Oded Goldreich, Guy Rothblum

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.

Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than

the work of Reingold, Rothblum, and Rothblum (STOC, 2016).

Our proof system for AC0[2] supports a more ...
more >>>