## On Sparse Pseudorandom Distributions

#### Webpage for a paper by Oded Goldreich and Hugo Krawczyk

#### Abstract

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.