Schedule

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+)
---------------------------------------------------------------------