Non-uniform attacks against one-way functions and PRGs.
Anindya De, Luca Trevisan, Madhur Tulsiani · 2009
We study the power of non-uniform attacks against one-way functions and pseudorandom generators. Fiat and Naor [FN99] show that for every function f: [N] → [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{ɛ 5 4 N 3 4, √ ɛN} exists that inverts f on at least an ɛ fraction of inputs. A lower bound of ˜ Ω ( √ ɛN) also holds, making our result tight in the “low end ” of ɛ ≤ 3 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.)