Sparse Pseudorandom Distributions

Pseudorandom distributions on n-bit strings are ones which cannot be effi- ciently distinguished from the uniform distribution on strings of the same length. Namely, the expected behavior of any polynomial-time algorithm on a pseudorandom input is (almost) the same as on a random (i.e. uniformly chosen) input. Clearly, the uni- form distribution is a pseudorandom one. But do such trivial cases exhaust the notion of pseudorandomness? Under certain intractability assumptions the existence of pseudoran- dom generators was proven, which in turn implies the existence of non-trivial pseudoran- dom distributions. In this paper we investigate the existence of pseudorandom distribu- tions, using no unproven assumptions.We show that sparse pseudorandom distributions do exist. A probability distribu- tion is called sparse if it is concentrated on a negligible fraction of the set of all strings (of the same length). It is shown that sparse pseudorandom distributions can be gen- erated by probabilistic (non-polynomial time) algorithms, and some of them are not sta- tistically close to any distribution induced by probabilistic polynomial-time algorithms.Finally, we show the existence of probabilistic algorithms which induce pseudoran- dom distributions with polynomial-time evasive support. Any polynomial-time algorithm trying to find a string in their support will succeed with negligible probability. A conse- quence of this result is a proof that the original definition of zero-knowledge is not robust under sequential composition. (This was claimed before, leading to the introduction of more robust formulations of zero-knowledge.)