Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NC0 CRYPTOGRAPHY:
Reports tagged with NC0 Cryptography:
TR25-030 | 15th March 2025
Oliver Korten, Toniann Pitassi, Russell Impagliazzo

Stronger Cell Probe Lower Bounds via Local PRGs

Revisions: 1

In this work we observe a tight connection between three topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement ... more >>>


TR26-228 | 4th October 2026
Benny Applebaum

Bitwise-Optimal Cryptography: From One-Wayness to Pseudorandomness and Target Collision Resistance

We study cryptographic primitives that are both locally computable (i.e., in $\mathrm{NC}^0$) and exponentially secure. For pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs), we further require linear stretch and linear compression, respectively, which is essentially the best one can hope for in this setting. Such primitives simultaneously achieve ... more >>>




ISSN 1433-8092 | Imprint