Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
6 Pseudorandom Numbers
6 Pseudorandom Numbers
Pages 65-86
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 65... ...
A pseudorandom bit generator is a deterministic method to produce from a small set of "random" bits called the seed a larger set of random-Iooking bits called pseudorandom bits. There are several reasons for using pseudorandom bits.
|
From page 66... ...
A third reason arises from cryptography: the existence of secure pseudorandom bit generators is essentially equivalent to the existence of secure private-key cryptosystems. For Monte CarIo simulations, one often wants pseudorandom numbers, which are numbers simulating either independent draws from a fixed probability distribution on the real line R
|
From page 67... ...
reference for pseudorandom number generators is Knuth (1981, Chapter 3~. 6.2 Explicit Constructions of Pseucloranclom Bit Generators Where might pseudorandom number generators come from?
|
From page 68... ...
. The computational complexity principle leads to pseudorandom number generators having provably good properties with respect to some level of computational resources, but most of these are not of use in practice because one must use more than the allowed bound on computation to find them in the first place.
|
From page 69... ...
Blum and Micali (1982) gave a method for generating a set of pseudorandom bits whose security rests on the difficulty of solving the discrete logarithm problem.
|
From page 70... ...
Sets of good hash functions play an important role in the theory of pseudorandom generators, where they are used to convert highly nonuniform probability distributions on k inputs into nearly uniform distributions on I inputs; see, for instance, Goldreich et al.
|
From page 71... ...
proposed some simple generators that have extremely long periods; whether they have good statistical properties remains to be determined. 6.3 Computational Information Theory and Cryptography In the last few years, there has been extensive development of a theoretical basis of secure pseudorandom number generators.
|
From page 72... ...
What is a pseudorandom number generator? The basic idea of pseudo randomness is to take a small amount of randomness described by a seed drawn from a given source probability distribution and to produce determ~nisticaDy from the seed a larger number of apparently random bits that simulate a sample drawn from another target probability distribution on a range space.
|
From page 73... ...
is ~i-indistinguishable from Q for aD the statistical tests Hi drawn from if. To make these ideas clearer, we allow as source distribution the uniform distribution Uk on the set {0, 13k of binary strings of length k, and for target distributions we allow either Us for some e, or else U(tO, lit)
|
From page 74... ...
< km + m, for some fixed integer m > 1. We say that 5 is a nonuniform secure pseudorandom bit generator (abbreviated N-PRG)
|
From page 75... ...
This condition may be rephrased as, "5 passes ad polynomial time statistical tests." Since PTIME C PSIZE, an N-PRG is always a U-PRG. These definitions of N-PRG and U-PRG form the basis of a nice theory, whose purpose is to reduce the existence question for apparently very complicated objects (N-PRGs)
|
From page 76... ...
~. The one-way property embodied in this definition is weaker than that required of an N-PRG in several ways: a function fk can have an extremely nonuniform probability distribution on its range {0, Make, it iS required to
|
From page 77... ...
~ (1) , it suffices by theorem 6.1 to enlarge a set of Q random bits to obtain e + ~ pseudorandom bits, for an infinite set of e.
|
From page 78... ...
showed how to construct a secure authentication scheme based on a one-way function. Finally, we mention that probabilistic algorithms play a fundamental role in the theoretical foundations of modern cryptography, as indicated in Goldwasser and Micali (1984~.
|
From page 79... ...
Then Zen -1 < n < km + m) are the pseudorandom bits generated fro to the seed no of length 2k bits.
|
From page 80... ...
for fixed positive ~ < 2; i.e., 0~(X) = { O if Y ~ ~ Define t~]
|
From page 81... ...
coin flips. One can extract several pseudorandom bits from each of the iterates an of the RSA generator.
|
From page 82... ...
, How to generate cryptographically strong versions of pseudorandom bits, in Proc. 22nd Annual Symposium on Foundations of Computer Science, {EKE Computer Society Press, Los Alamitos, Calif., 112-117.
|
From page 83... ...
29th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, Calif., 1224. Goldwasser, S., and S
|
From page 84... ...
No. 42, American Mathematical Society, Providence, R.~., 115-143.
|
From page 85... ...
, in Proc. 23rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CaTif., 80-91.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.