Pseudorandomness and Cryptographic Applications (Princeton Computer Science Notes)

Rating:
Summary: Definitely worth studying
Review: Walking into a colleague's office and noticing papers scattered all over her desk and shelves, I remarked on the apparent disorganization. She explained that from her standpoint everything was organized and easy to find. Randomness, she said, is observer dependent.

This is the theme taken in this book, namely tha a proper concept of randomness is not an intrinsic property of a collection or a distribution, but rather is dependent of the tools and computing capabilities of the observer. The concept of a pseudorandom distribution is introduced as a distribution where no efficient procedure or program can distinguish it from a uniform distribution. Pseudorandom generators are polynomial-time deterministic programs that take a randomly selected seed and expand it into a pseudorandom bit sequence.

The preliminaries/introduction gives an overview of sets, set functions, big-O, little-o notation, and most importantly from the author's standpoint, function and probability ensembles. He defines what it means to have a source of random bits, but does not give algorithms on how to produce them. Complexity classes are also discussed for both the deterministic and probabilistic cases, along with a very brief review of probability.

Private key cryptosystems begin the next chapter with an example of a one-time-pad private key cryptosystems. Pseudorandom generators are introduced as a solution to the problem of sending secure messages that are longer than the private key.

The author does a good job of defining computational and statistical indistinguishability, and the connection between 1-way functions and pseudorandom generators. What is interesting about all of these constructions is that they are based on sequences of probability distributions (called ensembles in the book) instead of a single probability distribution. The author defines ensembles as being different and close in the statistical sense and then uniform and pseudorandom.

The approach he takes is helpful because he gives informal definitions to develop the reader's intuition and then moves on to the formal definitions. After reading the book, one takes away an appreciation of what pseudorandomness is all about and how it applies to cryptography.