Modern cryptography, probabilistic proofs and pseudo-randomness
type: Item
instance of: scholarly article
title: Modern cryptography, probabilistic proofs and pseudo-randomness
zbMATH Open document ID: 0907.94002
author: Oded Goldreich
published in: Algorithms and Combinatorics
publication date: 1999-01-06T00:00:00Z
review text: 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 Ra…
Mathematics Subject Classification ID: 94-01
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68-01
Mathematics Subject Classification ID: 68P25
Mathematics Subject Classification ID: 65C10
zbMATH DE Number: 1236224
zbMATH Keywords: cryptography
zbMATH Keywords: probabilistic proof systems
zbMATH Keywords: zero-knowledge
zbMATH Keywords: pseudorandomness
reviewed by: Ian Blake
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1236224