## Modern Cryptography, Probabilistic Proofs and PseudorandomnessYou can start by putting the DO NOT DISTURB sign. Cay, in Desert Hearts (1985). The interplay between randomness and computation is one of the most fas cinating scientific phenomena uncovered in the last couple of decades. This interplay is at the heart of modern cryptography and plays a fundamental role in complexity theory at large. Specifically, the interplay of randomness and computation is pivotal to several intriguing notions of probabilistic proof systems and is the focal of the computational approach to randomness. This book provides an introduction to these three, somewhat interwoven domains (i.e., cryptography, proofs and randomness). Modern Cryptography. Whereas classical cryptography was confined to the art of designing and breaking encryption schemes (or "secrecy codes"), Modern Cryptography is concerned with the rigorous analysis of any system which should withstand malicious attempts to abuse it. We emphasize two aspects of the transition from classical to modern cryptography: ( 1) the wide ning of scope from one specific task to an utmost wide general class of tasks; and (2) the move from an engineering-art which strives on ad-hoc tricks to a scientific discipline based on rigorous approaches and techniques. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

The Foundations of Modern Cryptography | 1 |

12 Central Paradigms | 5 |

13 Pseudorandomness | 9 |

14 ZeroKnowledge | 12 |

15 Encryption | 15 |

16 Signatures | 20 |

17 Cryptographic Protocols | 24 |

18 Some Notes | 26 |

33 The Archetypical Case | 77 |

34 Derandomization of Timecomplexity Classes | 87 |

35 Space Pseudorandom Generators | 88 |

36 Special Purpose Generators | 92 |

37 Concluding Remarks | 103 |

A Background on Randomness and Computation | 107 |

A2 Computational Models and Complexity Classes | 110 |

A3 Complexity Classes Glossary | 118 |

19 Historical Perspective | 33 |

110 Two Suggestions for Future Research | 35 |

111 Some Suggestions for Further Reading | 36 |

Probabilistic Proof Systems | 39 |

22 Interactive Proof Systems | 41 |

23 ZeroKnowledge Proof Systems | 49 |

24 Probabilistically Checkable Proof Systems | 53 |

25 Other Probabilistic Proof Systems | 61 |

26 Concluding Remarks | 65 |

Pseudorandom Generators | 73 |

32 The General Paradigm | 75 |

### Other editions - View all

Modern Cryptography, Probabilistic Proofs and Pseudorandomness Oded Goldreich No preview available - 2010 |

Modern Cryptography, Probabilistic Proofs and Pseudorandomness Oded Goldreich No preview available - 2014 |

### Common terms and phrases

ACM Symposium adversary application approximation Bellare bits Boolean bounded ciphertext circuits coin tosses common input computationally computationally indistinguishable Computer Science Computer Science Vol consider construction cryptographic protocols Cryptography CS-proofs defined definition denoted derandomization deterministic distinguisher distribution efficient ensemble exists formula Foundations of Computer given Goldreich Goldwasser graph hard-core predicate IEEE Symposium infeasible integer interactive proof system intractability assumptions Lecture Notes length logarithmic Loosely speaking Micali non-interactive Notes in Computer notion NP-proof obtain one-way functions oracle machine output pairwise independent paradigm parties permutation plaintext polynomial polynomial-time algorithm private-key probabilistic polynomial-time probabilistically checkable proofs probability at least problem processors prover pseudorandom functions queries query complexity random variable random walk randomized algorithm resp sample sampler Section seed sequence signature schemes specific strategy stretch function string Symposium on Foundations Theorem Theory of Computing uniformly chosen uniformly selects verifier zero-knowledge proofs

### Popular passages

Page 177 - U. Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the 9th Annual ACMSIAM Symposium on Discrete Algorithms, San Francisco, California, pages 201-210, 1998.

Page 175 - A. Shamir, How to Share a Secret, Communications of the ACM, Vol. 22, No. 11, pp.