Modern cryptography, probabilistic proofs and pseudo-randomness (Q1273742)

The book gives an introduction and extensive survey to the three areas of: modern cryptography, probabilistic proof systems and pseudo-randomness. From the preface of the book: `The goal is to provide the reader with 1. A clear and structured overview of each of these areas. 2. Knowledge of the most important notions, ideas, techniques and results in each area. 3. Some new insights into each of these areas.' The first chapter introduces the basic notions of computational difficulty, pseudorandomness and zero-knowledge systems. In addition it gives a fairly comprehensive survey of the cryptographic utilities of encryption, signatures, including hash functions, and protocols. More discursive than a theorem and proof approach, it gives insight into the fundamentals of the subject. The second chapter concentrates on the three proof systems of interactive proofs, zero knowledge proofs and probabilistic checkable proofs. In particular, the role of randomness is viewed as a unifying theme for these discussions. Other interactive proof systems are also reviewed, including models in which the prover is restricted in its choice of strategy, a model in which the prover-verifier interaction is restricted and a model in which one proves knowledge of facts rather than their validity. Some open problems are also described. The third chapter focuses on the theory of randomness rooted in complexity theory. Here, objects are considered equal if they cannot be distinguished by any efficient procedure. The notions of stretching functions which take short strings and output longer ones, and computational indistinguishability, are fundamental to the approach. The book contains three appendices. The first contains background on probability theory assumed throughout the book and includes a discussion on computational models and complexity classes. It concludes with a review of four basic problems of cryptography, encryption schemes, digital signatures, message authentication and RSA and Rabin functions. The Appendix B demonstrates the usage of randomness in a variety of computational settings, including discussions on randomized algorithms, the role of randomness in complexity theory and randomness in distributed computing. The last appendix provides proofs of two basic results concerning, respectively, the behaviour of the error in parallel repetition of interactive proofs, with the number of repetitions, and the existence of a generic hard core predicate, used in chapter three.