TR09-113 Authors: Anindya De, Luca Trevisan, Madhur Tulsiani

Publication: 9th November 2009 00:34

Downloads: 3009

Keywords:

We study the power of non-uniform attacks against one-way

functions and pseudorandom generators.

Fiat and Naor show that for every function

$f: [N]\to [N]$

there is an algorithm that inverts $f$ everywhere using

(ignoring lower order factors)

time, space and advice at most $N^{3/4}$.

We show that an algorithm using time, space and advice at most

\[ \max \{ \epsilon^{\frac 54} N^{\frac 34} \ , \ \sqrt{\epsilon N} \} \]

exists that inverts $f$ on at least an $\epsilon$ fraction of inputs.

A lower bound of $\tilde \Omega(\sqrt { \epsilon N })$ also holds,

making our result tight in the ``low end'' of

$\epsilon \leq \sqrt[3]{\frac{1}{N}}$.

(Both the results of Fiat and Naor and ours

are formulated as more general trade-offs between the time

and the space and advice length of the algorithm. The results quoted

above correspond to the interesting special case in which time

equals space and advice length.)

We also show that for every length-increasing generator

$G:[N] \to [2N]$ there is a algorithm that achieves distinguishing

probability $\epsilon$ between the output of $G$ and

the uniform distribution and that can be implemented in

polynomial (in $\log N$)

time and with advice and space $O(\epsilon^2 \cdot N\log N)$.

Alternatively, it can be implemented as a circuit

of size $O(\epsilon^2 \cdot N)$. We prove

a lower bound of $S\cdot T\geq \Omega(\epsilon^2 N)$ where

$T$ is the time used by the algorithm and $S$ is the amount of advice.

We prove stronger lower bounds in the {\em common random string}

model, for families of one-way permutations and of pseudorandom generators.