Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with AC0 o MOD2:
TR14-033 | 10th March 2014
Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$

Revisions: 1

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 >>>

TR18-069 | 14th April 2018
Oded Goldreich, Guy Rothblum

Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint