International Association for Cryptologic Research

International Association
for Cryptologic Research


Nenad Dedic


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+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.
Upper and Lower Bounds on Black-Box Steganography
We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver).
An Improved Pseudorandom Generator Based on Hardness of Factoring
We present a simple to implement and efficient pseudorandom generator based on the factoring assumption. It outputs more than pn/2 pseudorandom bits per p exponentiations, each with the same base and an exponent shorter than n/2 bits. Our generator is based on results by Hastad, Schrift and Shamir [HSS93], but unlike their generator and its improvement by Goldreich and Rosen [GR00], it does not use hashing or extractors, and is thus simpler and somewhat more efficient. In addition, we present a general technique that can be used to speed up pseudorandom generators based on iterating one-way permutations. We construct our generator by applying this technique to results of [HSS93]. We also show how the generator given by Gennaro [Gen00] can be simply derived from results of Patel and Sundaram [PS98] using our technique.