|
|
1 | (10) |
|
1.1 Encryption and Secrecy |
|
|
1 | (1) |
|
1.2 The Objectives of Cryptography |
|
|
2 | (2) |
|
|
4 | (1) |
|
1.4 Cryptographic Protocols |
|
|
5 | (1) |
|
|
6 | (5) |
|
2 Symmetric-Key Cryptography |
|
|
11 | (38) |
|
2.1 Symmetric-Key Encryption |
|
|
11 | (19) |
|
|
12 | (3) |
|
|
15 | (1) |
|
|
16 | (3) |
|
|
19 | (6) |
|
|
25 | (5) |
|
2.2 Cryptographic Hash Functions |
|
|
30 | (19) |
|
2.2.1 Security Requirements for Hash Functions |
|
|
30 | (2) |
|
2.2.2 Construction of Hash Functions |
|
|
32 | (10) |
|
2.2.3 Data Integrity and Message Authentication |
|
|
42 | (2) |
|
2.2.4 Hash Functions as Random Functions |
|
|
44 | (5) |
|
3 Public-Key Cryptography |
|
|
49 | (58) |
|
3.1 The Concept of Public-Key Cryptography |
|
|
49 | (2) |
|
|
51 | (7) |
|
|
51 | (2) |
|
3.2.2 The Integers Modulo n |
|
|
53 | (5) |
|
|
58 | (19) |
|
3.3.1 Key Generation and Encryption |
|
|
58 | (4) |
|
3.3.2 Attacks Against RSA Encryption |
|
|
62 | (5) |
|
3.3.3 Probabilistic RSA Encryption |
|
|
67 | (3) |
|
3.3.4 Digital Signatures --- The Basic Scheme |
|
|
70 | (1) |
|
3.3.5 Signatures with Hash Functions |
|
|
71 | (6) |
|
3.4 The Discrete Logarithm |
|
|
77 | (8) |
|
|
77 | (1) |
|
|
78 | (2) |
|
3.4.3 Digital Signature Algorithm |
|
|
80 | (2) |
|
3.4.4 ElGamal Encryption in a Prime-Order Subgroup |
|
|
82 | (3) |
|
|
85 | (2) |
|
|
85 | (1) |
|
3.5.2 Rabin's Signature Scheme |
|
|
86 | (1) |
|
3.6 Homomorphic Encryption Algorithms |
|
|
87 | (3) |
|
|
87 | (1) |
|
3.6.2 Paillier Encryption |
|
|
88 | (1) |
|
3.6.3 Re-encryption of Ciphertexts |
|
|
89 | (1) |
|
3.7 Elliptic Curve Cryptography |
|
|
90 | (17) |
|
3.7.1 Selecting the Curve and the Base Point |
|
|
93 | (5) |
|
3.7.2 Diffie-Hellman Key Exchange |
|
|
98 | (2) |
|
|
100 | (2) |
|
3.7.4 Elliptic Curve Digital Signature Algorithm |
|
|
102 | (5) |
|
4 Cryptographic Protocols |
|
|
107 | (96) |
|
4.1 Key Exchange and Entity Authentication |
|
|
107 | (10) |
|
|
108 | (3) |
|
4.1.2 Diffie--Hellman Key Agreement |
|
|
111 | (1) |
|
4.1.3 Key Exchange and Mutual Authentication |
|
|
112 | (2) |
|
4.1.4 Station-to-Station Protocol |
|
|
114 | (1) |
|
4.1.5 Public-Key Management Techniques |
|
|
115 | (2) |
|
4.2 Identification Schemes |
|
|
117 | (9) |
|
4.2.1 Interactive Proof Systems |
|
|
117 | (2) |
|
4.2.2 Simplified Fiat-Shamir Identification Scheme |
|
|
119 | (2) |
|
|
121 | (2) |
|
4.2.4 Fiat--Shamir Identification Scheme |
|
|
123 | (2) |
|
4.2.5 Fiat--Shamir Signature Scheme |
|
|
125 | (1) |
|
|
126 | (4) |
|
4.3.1 A Commitment Scheme Based on Quadratic Residues |
|
|
127 | (1) |
|
4.3.2 A Commitment Scheme Based on Discrete Logarithms |
|
|
128 | (1) |
|
4.3.3 Homomorphic Commitments |
|
|
129 | (1) |
|
|
130 | (3) |
|
4.5 Verifiable Electronic Elections |
|
|
133 | (13) |
|
4.5.1 A Multi-authority Election Scheme |
|
|
135 | (3) |
|
4.5.2 Proofs of Knowledge |
|
|
138 | (4) |
|
4.5.3 Non-interactive Proofs of Knowledge |
|
|
142 | (1) |
|
4.5.4 Extension to Multi-way Elections |
|
|
143 | (1) |
|
4.5.5 Eliminating the Trusted Center |
|
|
144 | (2) |
|
4.6 Mix Nets and Shuffles |
|
|
146 | (22) |
|
4.6.1 Decryption Mix Nets |
|
|
147 | (3) |
|
4.6.2 Re-encryption Mix Nets |
|
|
150 | (3) |
|
4.6.3 Proving Knowledge of the Plaintext |
|
|
153 | (1) |
|
4.6.4 Zero-Knowledge Proofs of Shuffles |
|
|
154 | (14) |
|
4.7 Receipt-Free and Coercion-Resistant Elections |
|
|
168 | (16) |
|
4.7.1 Receipt-Freeness by Randomized Re-encryption |
|
|
169 | (7) |
|
4.7.2 A Coercion-Resistant Protocol |
|
|
176 | (8) |
|
|
184 | (19) |
|
4.8.1 Blindly Issued Proofs |
|
|
186 | (6) |
|
4.8.2 A Fair Electronic Cash System |
|
|
192 | (5) |
|
4.8.3 Underlying Problems |
|
|
197 | (6) |
|
5 Probabilistic Algorithms |
|
|
203 | (12) |
|
5.1 Coin-Tossing Algorithms |
|
|
203 | (5) |
|
5.2 Monte Carlo and Las Vegas Algorithms |
|
|
208 | (7) |
|
6 One-Way Functions and the Basic Assumptions |
|
|
215 | (28) |
|
6.1 A Notation for Probabilities |
|
|
216 | (1) |
|
6.2 Discrete Exponential Function |
|
|
217 | (6) |
|
6.3 Uniform Sampling Algorithms |
|
|
223 | (3) |
|
|
226 | (3) |
|
|
229 | (1) |
|
6.6 Quadratic Residuosity Property |
|
|
230 | (1) |
|
6.7 Formal Definition of One-Way Functions |
|
|
231 | (4) |
|
|
235 | (8) |
|
7 Bit Security of One-Way Functions |
|
|
243 | (24) |
|
7.1 Bit Security of the Exp Family |
|
|
243 | (7) |
|
7.2 Bit Security of the RSA Family |
|
|
250 | (8) |
|
7.3 Bit Security of the Square Family |
|
|
258 | (9) |
|
8 One-Way Functions and Pseudorandomness |
|
|
267 | (16) |
|
8.1 Computationally Perfect Pseudorandom Bit Generators |
|
|
267 | (8) |
|
|
275 | (8) |
|
9 Provably Secure Encryption |
|
|
283 | (38) |
|
9.1 Classical Information-Theoretic Security |
|
|
284 | (4) |
|
9.2 Perfect Secrecy and Probabilistic Attacks |
|
|
288 | (4) |
|
9.3 Public-Key One-Time Pads |
|
|
292 | (2) |
|
9.4 Passive Eavesdroppers |
|
|
294 | (7) |
|
9.5 Chosen-Ciphertext Attacks |
|
|
301 | (20) |
|
9.5.1 A Security Proof in the Random Oracle Model |
|
|
304 | (9) |
|
9.5.2 Security Under Standard Assumptions |
|
|
313 | (8) |
|
10 Unconditional Security of Cryptosystems |
|
|
321 | (52) |
|
10.1 The Bounded Storage Model |
|
|
322 | (10) |
|
10.2 The Noisy Channel Model |
|
|
332 | (1) |
|
10.3 Unconditionally Secure Message Authentication |
|
|
333 | (4) |
|
10.3.1 Almost Universal Classes of Hash Functions |
|
|
333 | (2) |
|
10.3.2 Message Authentication with Universal Hash Families |
|
|
335 | (1) |
|
10.3.3 Authenticating Multiple Messages |
|
|
336 | (1) |
|
10.4 Collision Entropy and Privacy Amplification |
|
|
337 | (6) |
|
|
338 | (2) |
|
10.4.2 Privacy Amplification |
|
|
340 | (1) |
|
10.4.3 Extraction of a Secret Key |
|
|
341 | (2) |
|
10.5 Quantum Key Distribution |
|
|
343 | (30) |
|
10.5.1 Quantum Bits and Quantum Measurements |
|
|
344 | (6) |
|
|
350 | (3) |
|
10.5.3 Estimation of the Error Rate |
|
|
353 | (1) |
|
10.5.4 Intercept-and-Resend Attacks |
|
|
354 | (8) |
|
10.5.5 Information Reconciliation |
|
|
362 | (5) |
|
10.5.6 Exchanging a Secure Key -- An Example |
|
|
367 | (1) |
|
10.5.7 General Attacks and Security Proofs |
|
|
368 | (5) |
|
11 Provably Secure Digital Signatures |
|
|
373 | (24) |
|
11.1 Attacks and Levels of Security |
|
|
373 | (3) |
|
11.2 Claw-Free Pairs and Collision-Resistant Hash Functions |
|
|
376 | (3) |
|
11.3 Authentication-Tree-Based Signatures |
|
|
379 | (2) |
|
11.4 A State-Free Signature Scheme |
|
|
381 | (16) |
|
A Algebra and Number Theory |
|
|
397 | (62) |
|
|
397 | (6) |
|
|
403 | (4) |
|
A.3 The Chinese Remainder Theorem |
|
|
407 | (2) |
|
A.4 Primitive Roots and the Discrete Logarithm |
|
|
409 | (4) |
|
A.5 Polynomials and Finite Fields |
|
|
413 | (6) |
|
A.5.1 The Ring of Polynomials |
|
|
413 | (2) |
|
A.5.2 Residue Class Rings |
|
|
415 | (2) |
|
|
417 | (2) |
|
A.6 Solving Quadratic Equations in Binary Fields |
|
|
419 | (2) |
|
|
421 | (5) |
|
|
426 | (4) |
|
|
430 | (2) |
|
A.10 Primes and Primality Tests |
|
|
432 | (5) |
|
|
437 | (22) |
|
|
438 | (8) |
|
A.11.2 Normal Forms of Elliptic Curves |
|
|
446 | (3) |
|
A.11.3 Point Addition on Elliptic Curves |
|
|
449 | (6) |
|
A.11.4 Group Order and Group Structure of Elliptic Curves |
|
|
455 | (4) |
|
B Probabilities and Information Theory |
|
|
459 | (24) |
|
B.1 Finite Probability Spaces and Random Variables |
|
|
459 | (8) |
|
B.2 Some Useful and Important Inequalities |
|
|
467 | (3) |
|
B.3 The Weak Law of Large Numbers |
|
|
470 | (2) |
|
|
472 | (4) |
|
B.5 Basic Concepts of Information Theory |
|
|
476 | (7) |
References |
|
483 | (18) |
Index |
|
501 | |