Pseudorandom Generators
A fresh view at the question of randomness was taken in the theory of computing: It has been postulated that a distribution is pseudorandom if it cannot be told apart from the uniform distribution by an efficient procedure. The paradigm, originally associ
- PDF / 4,105,874 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 101 Downloads / 254 Views
If two objects are indistinguishable, in what sense are they different?
The author, failing to recall a suitable quote (1997).
Summary- A fresh view at the question of randomness was taken in the theory of computing: It has been postulated that a distribution is pseudorandom if it cannot be told apart from the uniform distribution by an efficient procedure. The paradigm, originally associating efficient procedures with polynomial-time algorithms, has been applied also with respect to a variety of limited classes of such distinguishing procedures. Starting with the general paradigm, we survey the archetypical case of pseudorandom generators (withstanding any polynomial-time distinguisher), as well as generators withstanding space-bounded distinguishers, the derandomization of complexity classes such as BPP, and some special-purpose generators.
3.1 Introduction The second half of this century has witnessed the development of three theories of randomness, a notion which has been puzzling thinkers for ages. The first theory (cf., [109]), initiated by Shannon [322], is rooted in probability theory and is focused at distributions which are not perfectly random. Shannon's Information Theory characterizes perfect randomness as the extreme case in which the information contents is maximized (and there is no redundancy at all). Thus, perfect randomness is associated with a unique distribution - the uniform one. In particular, by definition, one cannot generate such perfect random strings from shorter random seeds. The second theory (cf., [243, 246]), due to Solomonov [333], Kolmogorov [235] and Chaitin [93], is rooted in computability theory and specifically in the notion of a universal language (equiv., universal machine or computing device). It measures the complexity of objects in terms of the shortest program (for a fixed universal machine) which generates the object. Like O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness © Springer-Verlag Berlin Heidelberg 1999
74
3. Pseudorandom Generators
Shannon's theory, Kolmogorov Complexity is quantitative and perfect random objects appear as an extreme case. However, in this approach one may say that a single object, rather than a distribution over objects, is perfectly random. Still, Kolmogorov's approach is inherently intractable (i.e., Kolmogorov Complexity is uncomputable), and- by definition- one cannot generate strings of high Kolmogorov Complexity from short random seeds. The third theory, initiated by Blum, Goldwasser, Micali and Yao [198, 71, 351), is rooted in complexity theory and is the focus of this chapter. This approach is explicitly aimed at providing a notion of perfect randomness which nevertheless allows to efficiently generate perfect random strings from shorter random seeds. The heart of this approach is the suggestion to view objects as equal if they cannot be told apart by any efficient procedure. Consequently a distribution which cannot be efficiently distinguished from the uniform distribution will be considered as being
Data Loading...
