Computer Science/Discrete Mathematics Seminar II
Bitwise-Optimal Cryptography: From One-Wayness to Pseudorandomness and Target Collision Resistance
We study bitwise-optimal cryptographic primitives: functions in NC⁰ (where each output bit depends on only a constant number of input bits) that achieve exponential security, together with linear stretch for pseudorandom generators (PRGs) and linear compression for universal one-way hash functions (UOWHFs).
We show that any exponentially secure one-way function in NC⁰ implies bitwise-optimal PRGs and UOWHFs, establishing an equivalence between these three primitives in this highly efficient regime. Interestingly, such an equivalence is not known for general, unrestricted cryptographic primitives in the exponential-security regime without additional regularity assumptions.
Our proof relies on new structural results on locally computable functions that allow us to remove the regularity assumption required by previous constructions. Along the way, we also establish a projection-based compression theorem for locally samplable sources.