On Sparse Pseudorandom Distributions

Webpage for a paper by Oded Goldreich and Hugo Krawczyk


Pseudorandom distributions (on strings) are ones which cannot be efficiently distinguished from the uniform distribution on strings of the same length. Namely, the expected behaviour of any polynomial-time algorithm on a pseudorandom input is (almost) the same as on a random (i.e. uniformly chosen) input. Clearly, the uniform distribution is a pseudorandom one. But do such trivial cases exhaust the notion of pseudorandomness? Under reasonable intractability assumptions the existence of pseudorandom generators was proven, which in turn implies the existence of non-trivial pseudorandom distributions. In this paper we investigate the existence of pseudorandom distributions, making no intractability (or other) assumptions.

We show that sparse pseudorandom distributions do exist. These distributions are concentrated on a negligible fraction of the set of all strings (of the same length). Sparse pseudorandom distributions can be induced by (non-polynomial time) probabilistic algorithms, and some of them are not statistically close to any distributions induced by polynomial-time probabilistic algorithms.

Finaly, we show the existence of probabilistic algorithms which induce distributions with polynomial-time evasive support in the sense that any polynomial-time algorithm trying to find a string in the support will succeed with negligible probability. A consequence of this result is a proof that the original definition of zero-knowledge is not robust under sequential composition. (This was argued before, leading to the introduction of more robust formulations of zero-knwledge.)

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.