Complexity Theory and Cryptology. An Introduction to Cryptocomplexity

Cover......Page 1
Series: Texts in Theoretical Computer Science - An EATCS Series......Page 2
Complexity Theory and Cryptology: An Introduction to Cryptocomplexity......Page 4
Copyright......Page 5
Preface......Page 8
Contents......Page 10
About This Book......Page 14
How to Use This Book......Page 16
Overview of the Book Chapters......Page 17
2.1 Algorithmics......Page 22
2.2 Formal Languages and Recursive Function Theory......Page 29
2.3.1 Propositional Logic......Page 42
2.3.2 Predicate Logic......Page 47
2.4.1 Algebra and Number Theory......Page 50
2.4.2 Permutation Groups......Page 54
2.4.3 Graph Theory......Page 56
2.5 Probability Theory......Page 59
2.6 Exercises and Problems......Page 60
2.7 Summary and Bibliographic Remarks......Page 64
3.1 Tasks and Aims of Complexity Theory......Page 66
3.2 Complexity Measures and Classes......Page 69
3.3 Speed-Up, Compression, and Hierarchy Theorems......Page 76
3.4 Between Logarithmic and Polynomial Space......Page 85
3.5.1 Many-One Reducibilities, Hardness, and Completeness......Page 90
3.5.2 NL-Completeness......Page 94
3.5.3 NP-Completeness......Page 101
3.6.1 P versus NP and the Graph Isomorphism Problem......Page 119
3.6.2 The Berman–Hartmanis Isomorphism Conjecture and One-Way Functions......Page 121
3.7 Exercises and Problems......Page 127
3.8 Summary and Bibliographic Remarks......Page 131
4.1 Tasks and Aims of Cryptology......Page 140
4.2.1 Substitution and Permutation Ciphers......Page 143
4.2.2 Affine Linear Block Ciphers......Page 148
4.2.3 Block and Stream Ciphers......Page 158
4.3.1 Shannon’s Theorem and Vernam’s One-Time Pad......Page 164
4.3.2 Entropy and Key Equivocation......Page 168
4.4 Exercises and Problems......Page 174
4.5 Summary and Bibliographic Remarks......Page 181
5. Hierarchies Based on NP......Page 184
5.1 Boolean Hierarchy over NP......Page 185
5.2 Polynomial Hierarchy......Page 203
5.3 Parallel Access to NP......Page 214
5.3.1 A Brief Digression to Social Choice Theory......Page 219
5.3.2 Determining Young Winners Is Complete for Parallel Access to NP......Page 221
5.4 Query Hierarchies over NP......Page 225
5.5 The Boolean Hierarchy Collapsing the Polynomial Hierarchy......Page 230
5.6 Alternating Turing Machines......Page 234
5.7 The Low and the High Hierarchy within NP......Page 245
5.8 Exercises and Problems......Page 254
5.9 Summary and Bibliographic Remarks......Page 261
6. Randomized Algorithms and Complexity Classes......Page 274
6.1 The Satisfiability Problem of Propositional Logic......Page 275
6.1.1 Deterministic Time Complexity......Page 276
6.1.2 Probabilistic Time Complexity......Page 278
6.2.1 PP, RP, and ZPP: Monte Carlo and Las Vegas Algorithms......Page 281
6.2.2 BPP: Bounded-Error Probabilistic Polynomial Time......Page 288
6.3.1 Quantifiers and BPP......Page 292
6.3.2 Arthur-Merlin Hierarchy......Page 299
6.4 Counting Classes......Page 303
6.5.1 Graph Isomorphism Is in the Low Hierarchy......Page 307
6.5.2 Graph Isomorphism Is in SPP......Page 311
6.6 Exercises and Problems......Page 315
6.7 Summary and Bibliographic Remarks......Page 319
7. RSA Cryptosystem, Primality, and Factoring......Page 324
7.1.1 RSA Public-Key Cryptosystem......Page 325
7.1.2 RSA Digital Signature Scheme......Page 329
7.2 Primality Tests......Page 330
7.2.1 Fermat Test......Page 332
7.2.2 Miller–Rabin Test......Page 336
7.2.3 Solovay–Strassen Test......Page 342
7.3 Factoring......Page 348
7.3.1 Trial Division......Page 349
7.3.2 Pollard’s Algorithm......Page 350
7.3.3 Quadratic Sieve......Page 351
7.3.4 Other Factoring Methods......Page 356
7.4 Security of RSA: Possible Attacks and Countermeasures......Page 358
7.5 Exercises and Problems......Page 366
7.6 Summary and Bibliographic Remarks......Page 370
8. Other Public-Key Cryptosystems and Protocols......Page 374
8.1.1 Diffie and Hellman’s Secret-Key Agreement Protocol......Page 375
8.1.2 Discrete Logarithm and the Diffie–Hellman Problem......Page 379
8.2.1 ElGamal’s Public-Key Cryptosystem......Page 382
8.2.2 ElGamal’s Digital Signature Scheme......Page 384
8.2.3 Security of ElGamal’s Protocols......Page 386
8.3 Rabin’s Public-Key Cryptosystem......Page 393
8.3.1 Rabin’s Cryptosystem......Page 394
8.3.2 Security of Rabin’s System......Page 396
8.4 Arthur-Merlin Games and Zero-Knowledge......Page 399
8.5 Merkle and Hellman’s Public-Key Cryptosystem......Page 406
8.6 Rabi, Rivest, and Sherman’s Protocols......Page 409
8.7 Exercises and Problems......Page 415
8.8 Summary and Bibliographic Remarks......Page 421
List of Figures......Page 426
List of Tables......Page 428
References......Page 430
Symbols......Page 457
A......Page 458
B......Page 460
C......Page 461
D......Page 465
E......Page 466
F......Page 468
G......Page 470
H......Page 471
I, J, K......Page 473
L......Page 474
M......Page 476
N......Page 477
O......Page 478
P......Page 479
Q, R......Page 482
S......Page 484
T......Page 487
U......Page 489
V, W......Page 490
X, Y, Z......Page 491