Saving Private Randomness in One-Way Functions and Pseudorandom Generators

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+{\mathcal O}(k {\rm log} k)$

bits (as opposed to

${\mathcal 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.