Paper 2007/458
Saving Private Randomness in OneWay Functions and Pseudorandom Generators
Nenad Dedic, Danny Harnik, and Leonid Reyzin
Abstract
Can a oneway 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 blackbox 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 higherlevel primitives to oneway 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 pairwiseindependent hash functions results in a new oneway 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 blackbox reduction cannot, for a general f, reduce the secretinput length, even given the knowledge that security of f is only $2^{k}$; nor can a blackbox reduction use fewer than k secret input bits when f has $2^k$ distinct outputs. Our second main result is an application of the publicrandomness approach: we show a construction of a pseudorandom generator based on any regular oneway 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 oneway function input.
Note: PDF rendering problems corrected. Affiliations updated.
Metadata
 Available format(s)
 PDF PS
 Category
 Foundations
 Publication info
 Published elsewhere. This is the full version of TCC 2008 paper.
 Keywords
 pseudorandomnessoneway functionrandomized iteratepseudorandom generatorregular oneway function
 Contact author(s)
 nenad dedic @ gmail com
 History
 20071210: last of 2 revisions
 20071210: received
 See all versions
 Short URL
 https://ia.cr/2007/458
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/458, author = {Nenad Dedic and Danny Harnik and Leonid Reyzin}, title = {Saving Private Randomness in OneWay Functions and Pseudorandom Generators}, howpublished = {Cryptology ePrint Archive, Paper 2007/458}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/458}}, url = {https://eprint.iacr.org/2007/458} }