SELF-LEARNING CRYPTOGRAPHY by Alptekin Küpçü Supported by two Teaching Innovation Grants (2014 & 2016) from the Koç University Office of Learning and Teaching (KOLT)WEEKLY SCHEDULE: (last update 2017.02.26)Weekly load expected 10 hours. See Resources for Books and Videos. See Homeworks for HW# and Suggested Exercises for the textbook. --------------------------------------------------------------------- 1. Introduction, Historical Ciphers and Probability Background. --------------------------------------------------------------------- Use these resources: - Read book Chapter 1 (both editions). - Read book Appendix A (both editions). - Watch Boneh 1.4 & 1.5 discrete probability crash course & 6.2 birthday bound. - Watch NPTEL 4 (starting at 11:45) basic probability, birthday bound, entropy. - Watch Boneh 1.3 historical ciphers and Katz 3.7 historical ciphers. - Watch Katz 3.5 modern principles & 3.6 security definitions. Learn these topics really well: - Principles of *modern* cryptography. - Importance of formal definitions, proofs, and assumptions. - Kerckhoff's principle. - Probability, conditional probability, entropy. - Birthday bound. Solve these exercises: - Solve suggested Exercises for Ch1. - Do HW1. * Week 1 is long, week 2 is shorter. Aim to finish both in two weeks total. --------------------------------------------------------------------- --------------------------------------------------------------------- 2. Perfect Secrecy and One Time Pad. --------------------------------------------------------------------- Use these resources: - Read book Chapter 2 (both editions). - Watch NPTEL 7 Perfect secrecy. - Watch Boneh 2.1 one time pad. - Watch Udacity Unit 1: 23 to 31 one time pad. Learn these topics really well: - Formal definition of perfect secrecy. - Implications of Shannon's theorem. Solve these exercises: - Solve suggested Exercises for Ch2. - Udacity Problem Set 1: 8 Malleability of one time pad. 16 One time pad key reuse. - Do HW2. --------------------------------------------------------------------- --------------------------------------------------------------------- 3. Computational Semantic Security, Encryption. --------------------------------------------------------------------- Use these resources: Part 1) - Read book Chapters 3.1 and 3.2 (both editions). - Watch Katz 4.2 & 4.3 computational secrecy. - Watch Boneh 2.6 semantic security & 2.7 PRG-based encryption. - Watch Katz 4.7 PRG-based encryption security proof. - Watch Küpçü 1 to 6 encryption scheme definition, reduction proofs, PRG-based encryption security proof. - Watch NPTEL 22 (starting 42:00) RSA bit PRG, Blum Blum Shub bit PRG. Part 2) - Read book: ED1: 3.3 to 3.4 ED2: 3.3 to 3.4.1 - Watch Katz 5.2 PRFs. - Watch Boneh 4.2 PRF/PRP & 4.3 multi-message many-time key security. Learn these topics really well: - Formal definitions of computational security. - Formal definition of a symmetric key encryption scheme and its correctness. - The PRG-based encryption security proof. - Reduction based proof technique. Solve these exercises: - Solve suggested Exercises for Ch3. - Udacity Unit 2: 2 to 11 randomness. - Do HW3 after part 1 & HW4 after part 2. --------------------------------------------------------------------- --------------------------------------------------------------------- 4. Pseudorandomness, Block Cipher modes of operation, CPA security. --------------------------------------------------------------------- Use these resources: - Read book: ED1: 3.5 to 3.6.4 ED2: 3.4.2 to 3.6 - Watch Küpçü 7 PRF-based encryption security proof. - Watch Katz 5.3 PRF-based encryption security proof. - Watch NPTEL 18 block cipher modes of operation, ECB, CBC, OFB, CTR. - Watch Boneh 4.4 & 4.5 on block cipher modes of operation CBC and CTR. Learn these topics really well: - Formal definitions of PRG, PRF, PRP. - The PRF-based encryption security proof. - Important considerations for block cipher modes of operation. - Formal definition of CPA secure encryption. Solve these exercises: - Solve suggested Exercises for Ch3. - Udacity Unit 2: 19 to 25 modes of operation. - Udacity Problem Set 2: 3 Modes of operation. - Do HW5. --------------------------------------------------------------------- --------------------------------------------------------------------- 5. MAC, CCA security, Hash functions. --------------------------------------------------------------------- Use these resources: Part 1) - Read book: ED1: 4.1 to 4.4 ED2: 4.1 to 4.3 - Watch Boneh 5.1 & 5.2 message authentication codes. - Watch Katz 6.1 & 6.2 message authentication codes. - Read book: ED1: 4.5 ED2: 4.4 - Watch Boneh 5.3 & 5.4 CBC-MAC. - Read book: ED1: 3.7 , 4.8 , 4.9 ED2: 3.7 , 4.5 - Watch Boneh 7.1 & 7.2 & 7.3 & 7.4 CCA-security. - CCA-Security is equivalent to non-malleability. Read "Non-malleable cryptography", by Dolev & Dwork & Naor, published in SIAM Journal of Computing, in 1998. Part 2) - Read book: ED1: 4.6 ED2: 5.1 to 5.4 - There are other security definitions for hash functions. Read "Cryptographic Hash-Function Basics", by Rogaway and Shrimpton, published in FSE, in 2004. (also appears as IACR ePrint 2004/035) - Watch NPTEL 23 hash functions, hash and sign, preimage resistance, second preimage resistance, collision resistance, random oracle model (starting 18:00), non-ideal hash functions (between 18:00 and 22:00), reduction. - Watch NPTEL 24 reduction between hash function security properties, Merkle Damgard construction and its proof. - Watch Boneh 6.3 Merkle-Damgard hash function construction. - Watch NPTEL 1 Coin toss, one way functions, collision resistance. - Watch Udacity Unit 2: 40 to 52 Passwords and dictionary attacks. - Read book: ED2: 4.6 & 5.6 in your free time (pay close attention to 5.6.2). [Do not exist in ED1] Learn these topics really well: - Difference between security guarantees of encryption and MACs. - Formal definition of unforgeable MAC. Strong vs. Weak MAC definition. - Formal definition of CCA secure encryption. - How to achieve CCA secure encryption properly. - Different flavors of security for hash functions. - Relationship between hash function security definitions. Which one is stronger, which one is weaker. Solve these exercises: - Solve suggested Exercises for: ED1: Ch4. ED2: Ch4 and Ch5. - Do HW6 after part 1 & HW7 after part 2. * Week 5 is long, week 6 is shorter. Aim to finish both in two weeks total. --------------------------------------------------------------------- --------------------------------------------------------------------- 6. One way functions. Reductions. --------------------------------------------------------------------- Use these resources: - Read book: ED1: 6 ED2: 7 - Watch Küpçü 8 to 10 PRG output expansion and Hybrid proofs. Learn these topics really well: - Definitions of OWF, OWP and computational indistinguishability. - Hardcore predicates and functions. - Hybrid security proofs. - Focus on the proofs more than the constructions. Solve these exercises: - Solve suggested Exercises for: ED1: Ch6. ED2: Ch7. - Do HW8. --------------------------------------------------------------------- --------------------------------------------------------------------- 7. Number Theory. --------------------------------------------------------------------- Use these resources: - Read book: ED1: 7 , Appendix B ED2: 8 , Appendix B - Watch UW Week 1 (between 0:49 - 1:08 and 1:13 - 1:40) Modular arithmetic. - Watch UW Week 2 (between 1:01 - 1:35) Number theory (primes). - Watch UW Week 1 (between 1:09 - 1:13) Fundamental equation (Z = Y^X mod N). - Watch Paar 7 Finite fields, groups, polynomial arithmetic. - Watch NPTEL 27 (between 24:30 and 39:30) Chinese Remainder Theorem. - Watch NPTEL 28 (starting 39:40) quadratic residue. - Watch NPTEL 29 (until 9:45) Legendre, Jacobi. Learn these topics really well: - Modular arithmetic, (extended) Euclidean algorithm, CRT. Solve these exercises: - Solve suggested Exercises for: ED1: Ch7. ED2: Ch8. --------------------------------------------------------------------- --------------------------------------------------------------------- 8. Number Theory. --------------------------------------------------------------------- Use these resources: - Read HAC Chapters 2 and 3 (you may skip the algorithms in Chapter 3, and only read about the problems) - Watch Boneh 10.1 to 10.5 number theory. - Watch Katz 7.1 to 7.5 Number Theory. - Watch Udacity Unit 3: 18 to 32 Brief number theory. Learn these topics really well: - Groups, Fields, Rings, their relations and differences, formal definitions. - Generators, factoring assumption, quadratic residues, discrete logarithm problem, finding (square) roots. Solve these exercises: - Solve suggested Exercises for: ED1: Ch7. ED2: Ch8. * If you were slow, catch up now till the end of week 8. --------------------------------------------------------------------- --------------------------------------------------------------------- 9. Key management and Key exchange. --------------------------------------------------------------------- Use these resources: - Read book: ED1: 9 ED2: 10 - Watch Boneh 9.1 trusted third parties. - Watch NPTEL 38 (until 43:00) How to use cryptographic primitives in a network properly, Kerberos. - Watch Paar 23 Key establishment, key distribution problem, Kerberos & 13 Groups, Diffie-Hellman key exchange & 24 (until 42:00) Diffie-Hellman man-in-the-middle attack. - Watch Katz 8.2 Diffie-Hellman key exchange & 8.4 hybrid encryption. - Watch Udacity Unit 3: 8 to 17 & 33 to 35 Diffie-Hellman. Learn these topics really well: - Symmetric key distribution, Kerberos. - Diffie-Hellman key exchange and the man-in-the-middle attack. - Decisional Diffie-Hellman assumption, Computational Diffie-Hellman assumption. - Security definition of a key exchange scheme and the reduction proof of Diffie-Hellman key exchange against passive eavesdropper. Solve these exercises: - Solve suggested Exercises for: ED1: Ch9. ED2: Ch10. - Udacity Unit 3: 1 to 7 key distribution and Merkle puzzles. - Udacity Problem Set 3: 1 Diffie-Hellman. - Do HW9. --------------------------------------------------------------------- --------------------------------------------------------------------- 10. Public Key Encryption, RSA, ElGamal. --------------------------------------------------------------------- Use these resources: - Read book: ED1: 10 ED2: 11 (except 11.4.3 , 11.4.4 , 11.5.4 , 11.5.5) & 13.1 - Watch Udacity Unit 4: 7-37 RSA encryption. - Watch Katz 8.6 RSA encryption. - Watch Boneh 11.1 to 11.6 RSA encryption. - Watch Boneh 12.1 & 12.2 ElGamal encryption. - Watch Katz 8.5 ElGamal encryption. Learn these topics really well: - Security definitions of public key encryption (CPA and CCA). - RSA and ElGamal encryption schemes. - Trapdoor functions and their relation to one way functions. - Why textbook RSA encryption is insecure and how to fix that. Solve these exercises: - Solve suggested Exercises for: ED1: Ch10. ED2: Ch11. - Udacity Problem Set 4: 1 How to use PKC. - Do HW10. --------------------------------------------------------------------- --------------------------------------------------------------------- 11. Signatures, RSA, hash-and-sign, certificates, PKI. --------------------------------------------------------------------- Use these resources: - Read book: ED1: 12 ED2: 12 (except 12.4.2) - Watch Katz 9.1 to 9.4 signatures. - Watch Katz 9.5 PKI. - Watch Paar 24 (starting 42:00), PKI, certificates. - Watch Udacity Unit 5: 3 to 36 Encrypted key exchange (EKE), SSH, TLS, Certificates. - Watch UW Week 4 (starting 1:56) Certificates. (if you have time) Learn these topics really well: - Security definitions of digital signature schemes. - The hash-and-sign paradigm. - Certificates, public key infrastructure. Solve these exercises: - Solve suggested Exercises for Ch12. - Udacity Problem Set 5: 5 Certificates. --------------------------------------------------------------------- --------------------------------------------------------------------- 12. Random Oracle Model and Zero Knowledge Proofs. --------------------------------------------------------------------- Use these resources: - Read book: ED1: 13 ED2: 5.5 , 11.4.3 , 11.4.4 , 11.5.4 , 11.5.5 , 12.4.2 - Watch Küpçü 11 to 15 ROM. - Re-watch NPTEL 23 (starting 18:00) random oracle model, non-ideal hash functions, reduction. - Re-watch NPTEL 1 Coin toss, one way functions, collision resistance. (Tie this to random oracles.) - Watch Udacity Unit 2: 26 to 36 Coin toss and Random Oracle. - Watch Bar-Ilan 1st winter school 5 sigma protocols and zero knowledge proofs. Learn these topics really well: - Reduction proofs in the random oracle model. - RSA signatures. Solve these exercises: - Solve suggested Exercises for: ED1: Ch13. - Do HW11. --------------------------------------------------------------------- --------------------------------------------------------------------- 13. GM, Rabin, Paillier. --------------------------------------------------------------------- Use these resources: - Read book: ED1: 11 ED2: 13 (except 13.1) Learn these topics really well: - How to use interesting number theoretic assumptions for security properly. - Quadratic residuosity, modular square roots, group isomorphism. Solve these exercises: - Solve suggested Exercises for: ED1: Ch11. ED2: Ch13. --------------------------------------------------------------------- --------------------------------------------------------------------- 14. Elliptic Curves, Bilinear Maps and applications. --------------------------------------------------------------------- Use these resources: - Read MC Chapters 5.1 to 5.5 - Watch UW Week 2 (starting 1:54) Elliptic curves. - Watch Bar-Ilan 3rd winter school 6 & 9 bilinear maps (pairings) and example applications. Learn these topics really well: - What are elliptic curves (do not worry about their implementation details). - What are bilinear maps and their usage examples. - Properties of bilinear maps: efficiency, bilinearity, non-degeneracy. - How are elliptic curve groups similar to the number theoretic groups you have seen before. Solve these exercises: - Solve suggested Exercises for Ch5 of MC book. (3*, 9, 14+, 15.a, 16.a+, 17.a+*, 19**, 20**, 21**, 22**, 23**, 25**, 26+, 27**, 28**, 31, 32**, 34*, 35+, 36, 37*, 38**, 39**, 43+) --------------------------------------------------------------------- |