Paper Info
Title
Time space tradeoffs for attacks against one-way functions and PRGs
Abstract
We study time space tradeoffs in the complexity of attacks against one-way functions and pseudorandom generators. Fiat and Naor [7] 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 N3/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√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] → [2N] there is a algorithm that achieves distinguishing probability ε 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(ε2 ċ N log N). We prove a lower bound of S ċ T ≥ Ω(ε2N) where T is the time used by the algorithm and S is the amount of advice. This lower bound applies even when the distinguisher has oracle access to G. We prove stronger lower bounds in the common random string model, for families of one-way permutations and of pseudorandom generators.
Year
DOI
Venue
2010
10.1007/978-3-642-14623-7_35
CRYPTO
Keywords
Field
DocType
one-way function,n log,log n,stronger lower bound,time space tradeoffs,advice length,lower order factor,pseudorandom generator,one-way permutation,space o,uniform distribution,one way functions,lower bound,one way function
Discrete mathematics,Binary logarithm,Combinatorics,Polynomial,Upper and lower bounds,Permutation,One-way function,Time complexity,A* search algorithm,Mathematics,Pseudorandom number generator
Conference
Volume
ISSN
ISBN
6223
0302-9743
3-642-14622-8
Citations 
PageRank 
References 
18
0.70
17
Authors
3
Name
Order
Citations
PageRank
Anindya De123924.77
Luca Trevisan22995232.34
Madhur Tulsiani335824.60