Information Security and Cryptography Research Group

Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness

Thomas Holenstein

Theory of Cryptography Conference — TCC 2006, Lecture Notes in Computer Science, Springer-Verlag, pp. 443–461, Mar 2006.

In a seminal paper, Hastad, Impagliazzo, Levin, and Luby showed that pseudorandom generators exist if and only if one-way functions exist. The construction they propose to obtain a pseudorandom generator from an n-bit one-way function uses O(n^8) random bits in the input (which is the most important complexity measure of such a construction). In this work we study how much this can be reduced if the one-way function satisfies a stronger security requirement. For example, we show how to obtain a pseudorandom generator which satisfies a standard notion of security using only O(n^4 log^2(n)) bits of randomness if a one-way function with exponential security is given, i.e., a one-way function for which no polynomial time algorithm has probability higher than 2^(-cn) in inverting for some constant c. Using the uniform variant of Impagliazzo's hard-core lemma given in [Hol05] our constructions and proofs are self-contained within this paper, and as a special case of our main theorem, we give the first explicit description of the most efficient construction from [HILL99].

BibTeX Citation

    author       = {Thomas Holenstein},
    title        = {Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness},
    editor       = {Shai Halevi and Tal Rabin},
    booktitle    = {Theory of Cryptography Conference --- TCC 2006},
    pages        = 443--461,
    series       = {Lecture Notes in Computer Science},
    year         = 2006,
    month        = 3,
    publisher    = {Springer-Verlag},

Files and Links