+612 9045 4394
Modern Cryptography, Probalistic Proofs and Pseudorandomness : Algorithms and Combinatorics - Oded Goldreich

Modern Cryptography, Probalistic Proofs and Pseudorandomness

Algorithms and Combinatorics

Hardcover Published: December 1998
ISBN: 9783540647669
Number Of Pages: 183

Share This Book:


RRP $331.99
or 4 easy payments of $57.44 with Learn more
Ships in 15 business days

This book focuses on cryptography along with two related areas: the study of probabilistic proof systems, and the theory of computational pseudorandomness. Following a common theme that explores the interplay between randomness and computation, the important notions in each field are covered, as well as novel ideas and insights.

From the reviews:

"This book is intended for a reader with some knowledge of the theory of computing. It is divided into three chapters, each a survey of one of the topics mentioned in the title. The chapters may be read independently, and are somewhat different in nature. ...The book ends with four appendices. The first summarises the probability theory, complexity theory and cryptography that is used in the body of the book. The second gives examples of randomisation in algorithmic problems, complexity theory and distributed computing. The third contains two proofs, not to be found in the literature, of well-known results. The last appendix lists other surveys by the author." (Simon R. Blackburn, Mathematical Reviews)

"Modern cryptography, probabilistic proofs and pseudorandomness are three areas in theoretical computer science that demonstrate the interplay between randomness and computations. ... This book is informative and rich in content. ... the most appealing feature of this book is that it leans toward the intuition and historical motivations around these topics. ... it is an excellent resource for students and researchers ... . this book will probably give you a good collection of background motivations and nice discussions as well." (Andrew C. Lee, SIGACT News, Vol. 34 (4), 2003)

The Foundations of Modern Cryptography
Basic Tools
Central Paradigms
Computational Difficulty
Computational Indistinguishability
The Simulation Paradigm
The Basics
Pseudorandom Functions
The Basics
Some Variants
Basic Utilities
Beyond eavesdropping security
Two variants
Cryptographic Protocols
Concluding Comments
Some Notes
General notes
Specific notes
Historical Perspective
Two Suggestions for Future Research
Some Suggestions for Further Reading
Probabilistic Proof Systems
Interactive Proof Systems
The Role of Randomness
The Power of Interactive Proofs
The Interactive Proof System Hierarchy
How Powerful Should the Prover be?
Zero-Knowledge Proof Systems
A Sample Definition
The Power of Zero-Knowledge
The Role of Randomness
Probabilistically Checkable Proof Systems
The Power of Probabilistically Checkable Proofs
PCP and Approximation
More on PCP itself
The Role of Randomness
Other Probabilistic Proof Systems
Restricting the Provers Strategy
Non-Interactive Probabilistic Proofs
Proofs of Knowledge
Refereed Games
Concluding Remarks
Comparison among the various systems
The Story
Open Problems
Pseudorandom Generators
The General Paradigm
The Archetypical Case
A Short Discussion
Some Basic Observations
Pseudorandom Functions
Derandomization of time-complexity classes
Space Pseudorandom Generators
Special Purpose Generators
Pairwise-Independence Generators
Small-Bias Generators
Random Walks on Expanders
Dispersers, Extractors and Weak Random Sources
Concluding Remarks
Historical Perspective
Open Problems
Background on Randomness and Computation
Probability Theory -- Three Inequalities
Computational Models and Complexity classes
P, NP, and more
Probabilistic Polynomial-Time
Non-Uniform Polynomial-Time
Oracle Machines
Space Bounded Machines
Average-Case Complexity
Complexity classes
Some Basic Cryptographic Settings
Encryption Schemes
Digital Signatures and Message Authentication
The RSA and Rabin Functions
Randomized Computations
Randomized Algorithms
Approx Counting of DNF satisfying assignments
Finding a perfect matching
Testing whether polynomials are identical
Randomized Rounding applied to MaxSAT
Primality Testing
Testing Graph Connectivity via a random walk
Finding minimum cuts in graphs
Randomness in Complexity Theory
Reducing (Approximate) Counting to Deciding
Two-sided error versus one-sided error
The permanent: Worst-Case vs Average Case
Randomness in Distributed Computing
Testing String Equality
Routing in networks
Byzantine Agreement
Bibliographic Notes
Notes on two proofs
Parallel repetition of interactive proofs
A generic Hard-Core Predicate
A motivating discussion
Back to the formal argument
Improved Implementation of Algorithm $A
Related Surveys by the Author Bibliography (over 300 entries) '
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9783540647669
ISBN-10: 354064766X
Series: Algorithms and Combinatorics
Audience: Professional
Format: Hardcover
Language: English
Number Of Pages: 183
Published: December 1998
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.5 x 15.5  x 1.27
Weight (kg): 0.41