Saving Private Randomness in One-Way Functions and Pseudorandom Generators
Nenad Dedic, Danny Harnik, and Leonid Reyzin
Abstract
Can a one-way function f on n input bits be used
with fewer than 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
, 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 ; nor can a black-box reduction use fewer than k secret input bits when f has 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 . 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.
@misc{cryptoeprint:2007/458,
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},
url = {https://eprint.iacr.org/2007/458}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.