Cryptography Reference
In-Depth Information
3
Pseudorandomness
In practice “pseudorandom” sequences are often used instead of truly
random sequences. The underlying belief is that if an (ecient) appli-
cation performs well when using a truly random sequence then it will
perform essentially as well when using a “pseudorandom” sequence.
However, this belief is not supported by ad-hoc notions of “pseudoran-
domness” such as passing the statistical tests in (92) or having large
linear-complexity (as in (83)). In contrast, the above belief is an easy
corollary of defining pseudorandom distributions as ones that are com-
putationally indistinguishable from uniform distributions.
Loosely speaking, pseudorandom generators are ecient procedures
for creating long “random-looking” sequences based on few truly ran-
dom bits (i.e., a short random seed). The relevance of such constructs
to cryptography is in the ability of legitimate users that share short
random seeds to create large objects that look random to any feasible
adversary (which does not know the said seed).
