TY - GEN

T1 - Time space tradeoffs for attacks against one-way functions and PRGs

AU - De, Anindya

AU - Trevisan, Luca

AU - Tulsiani, Madhur

N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - 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 N 3/4. We show that an algorithm using time, space and advice at most max {ε5/4N3/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 logN) time and with advice and space O(ε 2 •NlogN). We prove a lower bound of S•TΩ(ε 2 N) 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.

AB - 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 N 3/4. We show that an algorithm using time, space and advice at most max {ε5/4N3/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 logN) time and with advice and space O(ε 2 •NlogN). We prove a lower bound of S•TΩ(ε 2 N) 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.

KW - One-way functions

KW - pseudorandom generators

KW - random permutations

KW - time-space tradeoffs

UR - http://www.scopus.com/inward/record.url?scp=77956997411&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956997411&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14623-7_35

DO - 10.1007/978-3-642-14623-7_35

M3 - Conference contribution

AN - SCOPUS:77956997411

SN - 3642146228

SN - 9783642146220

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 649

EP - 665

BT - Advances in Cryptology - CRYPTO 2010 - 30th Annual Cryptology Conference, Proceedings

T2 - 30th Annual International Cryptology Conference, CRYPTO 2010

Y2 - 15 August 2010 through 19 August 2010

ER -