Faces of Modern Cryptography

2009

 

Fiat and Naor, building on ideas of Hellmand, show that for every efficiently computable one-way function $f: \{0,1 \}^n \rightarrow \{0,1 \}^n$ there is a circuit of size about $2^{3n/4}$ that inverts $f$ everywhere. This result "relativizes" in the sense that such a circuit can be constructed for every function $f$ provided that "$f$-gates" are available. In such a setting, Yao showed that there are functions for which inversion cannot be performed by circuits of size less than about  2^{n/2}. It remains open to bridge the gap between the Fiat-Naor construction and Yao's lower bound.


We consider the complexity of inverting a one-way function on an $\epsilon$ fraction of inputs. In such a setting, Gennaro, Trevisan and Wee show that Yao's lower bound scales as $(\epsilon 2^n)^{1/2}$. We show how to invert any function $f$ on an $\epsilon$ fraction of inputs with circuits of size about $\max \{ (\epsilon 2^n)^{1/2}, \epsilon^{5/4} 2^{3n/4} \}$, which is tight for $\epsilon$ smaller than $2^{-n/3}$.


We also provide a distinguishing attack against arbitrary length-increasing psedorandom generators $G: \{ 0,1\}^n \rightarrow \{ 0,1 \}^{n+1}$. We show that distinguishing probability $\epsilon$ can be achieved by a circuit of size about $\epsilon^2 2^n$, regardless of the complexity of the generator. (The distinguishing circuit does not require "G-gates".) This is tight for distinguishing attacks against arbitrary generators.


Joint work with Anindya De and Madhur Tulsiani

Generic Attacks Against One-Way Functions and Pseudorandom Generators

Luca Trevisan

Professor

University of California Berkeley

Computer Science Division