Technical Report CS0553

Title: Sparse and Evasive Pseudorandom Distributions
Authors: O. Goldreich and H. Krawczyk
Abstract: Pseudorandom distributions on n-bit strings are ones which cannot be efficiently 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 uniform distribution is a pseudorandom one. But do such trivial cases exhaust the notion of pseudorandomness? Under certain 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, using no unproven assumptions.

We show that sparse pseudorandom distributions do exist. A probability distribution 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 generated by probabilistic (non-polynomial time) algorithms, and some of them are not statistically close to any distribution induced-by probabilistic polynomial-time algorithms.

Finally, we show the existence of probabilistic algorithms which induce pseudorandom distributions with polynomial-time evasive support. Any polynomial-time algorithm trying to find a string in their support will succeed with negligible probability. Furthermore, we present a construction of collections of pseudorandom sets which are also evasive for non-uniform polynomial-time algorithms. This means that such an algorithm cannot find, for most sets in the collection, an element in that set, except fot a negligible probability.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion