Paper 2007/458

Saving Private Randomness in One-Way Functions and Pseudorandom Generators

Nenad Dedic, Danny Harnik, and Leonid Reyzin


Can a one-way function f on n input bits be used with fewer than $n$ bits while retaining comparable hardness of inversion? We show that the answer to this fundamental question is negative, if one is limited black-box reductions. Instead, we ask whether one can save on secret random bits at the expense of more public random bits. Using a shorter secret input is highly desirable, not only because it saves resources, but also because it can yield tighter reductions from higher-level primitives to one-way functions. Our first main result shows that if the number of output elements of f is at most $2^k$, then a simple construction using pairwise-independent hash functions results in a new one-way function that uses only k secret bits. We also demonstrate that it is not the knowledge of security of f, but rather of its structure, that enables the savings: a black-box reduction cannot, for a general f, reduce the secret-input length, even given the knowledge that security of f is only $2^{-k}$; nor can a black-box reduction use fewer than k secret input bits when f has $2^k$ distinct outputs. Our second main result is an application of the public-randomness approach: we show a construction of a pseudorandom generator based on any regular one-way function with output range of known size $2^k$. The construction requires a seed of only 2n+O(k\log k) bits (as opposed to O(n \log n) in previous constructions); the savings come from the reusability of public randomness. The secret part of the seed is of length only k (as opposed to n in previous constructions), less than the length of the one-way function input.

Note: PDF rendering problems corrected. Affiliations updated.

Available format(s)
Publication info
Published elsewhere. This is the full version of TCC 2008 paper.
pseudorandomnessone-way functionrandomized iteratepseudorandom generatorregular one-way function
Contact author(s)
nenad dedic @ gmail com
2007-12-10: last of 2 revisions
2007-12-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nenad Dedic and Danny Harnik and Leonid Reyzin},
      title = {Saving Private Randomness in One-Way Functions and Pseudorandom Generators},
      howpublished = {Cryptology ePrint Archive, Paper 2007/458},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.