Modern Cryptography, Probabilistic Proofs and Pseudorandomness

Front Cover
Springer Science & Business Media, Nov 24, 1998 - Mathematics - 183 pages
You 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
A4 Some Basic Cryptographic Settings
119
B Randomized Computations
125
B2 Randomness in Complexity Theory
135
B3 Randomness in Distributed Computing
139
B4 Bibliographic Notes
143
C Two Proofs
145
C2 A Generic HardCore Predicate
149
D Related Surveys by the Author
157
Bibliography
159
Index
179
Copyright

Other editions - View all

Common terms and phrases

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.

Bibliographic information