Cryptography (2019II)
(Monday & Thursday 1130 — 1300) @ A 201
Course Calendar (.ical)
The course would deal with the foundations of crytography, largely from a theoretical standpoint.
References
There are plenty of wonderful references available online and we’ll pick and choose depending on the topic that is being covered.
 [Rosulek]: The Joy of Cryptography (by Mike Rosulek)
 [KatzLindell]: Introduction to Modern Cryptography (by Katz and Lindell)
 [VinodV]: Advanced Topics in Cryptography: Lattices (Fall 2015, by Vinod Vaikuntanathan) @ MIT
 [Barak]: An Intensive Introduction to Cryptography (by Boaz Barak)
 [Trevisan]: CS276Cryptography (by Luca Trevisan) @ Berkeley
 [PassShellat]: Introduction to Cryptography (by Rafael Pass and Abhi Shelat)
 [Goldreich]: The Foundations of Cryptography I and II (by Oded Goldreich)
Lecture schedule and overview
 Lecture 1 (20190819, Monday)
 Introduction, onetime pads, basics of provable security, an example of secure computation of AND

 [Rosulek]: Chapters 1, 2

 [PassShelat]: Chapter 1
 Lecture 2 (20190822, Thursday)
 Shamir’s Secret Sharing Scheme, introduction to cryptography from intractability

 [Rosulek]: Chapters 3,4
 Lecture 3 (20190826, Monday)
 Computational indistinguishability, revisiting hybrid arguments, introduction to pseudorandom generators

 [Rosulek]: Chapter 5
 Lecture 4 (20190829, Thursday)
 Pseudorandom functions, building PRGs from PRFs, the GoldreichGoldwasserMicali construction of building PRFs from PRGs

 [Rosulek]: Chapter 6
(20190902 is a holiday (Ganesh Chaturthi))
 Lecture 5 (20190905, Thursday)
 Proof of correctness of the GGM construction, PRPs and block ciphers, security under Chosen Plaintext Attacks, some block cipher modes and padding schemes

 [Rosulek]: Parts of Chapter 6 and 7
 Lecture 6 (20190909, Monday)
 brief description of Bleichenbacher’s attack on SSL V1.0, attacks based on padding oracles with CBC, motivation for security under Chosen Ciphertext Attacks, definition of CCA security, secure PRPs

 [Blei98]: “Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1”, CRYPTO 98

 [Rosulek]: Parts of Chapter 8 and Chapter 9
 Coded up Bleichenbacher attack: [.html] [.py] [.ipynb (for Jupyter notebook)]
 Lecture 7 (20190912, Thursday)
 CCA security via strong PRPs, introduction to MACs, PRFs are MACs, brief description of CCAMAC and ECBCMAC

 [Rosulek]: Parts of Chapter 9 and 10
 Lecture 8 (20190919, Thursday)
 CCAsecurity of EncryptThenMAC, collisionresistant hash functions

 [Rosulek]: Parts of Chapter 10 and 11
(End of Part 1 of the course. Part 2 of the course begins)
 Lecture 9 (20190923, Monday)
 Minimal assumptions for crypto, introduction to oneway functions (OWFs), weak OWFs imply strong OWFs

 [PassShelat]: Parts of Chapter 2
 Lecture 10 (20190926, Thursday)
 The universal OWF, oneway permutations, trapdoor permutations, towards building PRGs

 [PassShelat]: Parts of Chapter 2 and 3
 Lecture 11 (20190930, Monday)
 NextBitUnpredictability implies PRG, hardcore predicate for DL, hardcore predicates for OWPs, towards the GoldreichLevin theorem

 [PassShelat]: Parts of Chapter 3
 Lecture 12 (20191004, Friday)
 The proof of the GoldreichLevin theorem

 [PassShelat]: Chapter 3
 Lecture 13 (20191009, Wednesday, tentative)
 (tentative) Public key cryptography, theoretical constructions, descriptions of practical implementations of DDH, RSA, ElGamal, CramerShoup

 [PassShelat]: Chapter 3
 Lecture 14 (20191014, Monday)
 Some nuances about the DDH, digital signature schemes

 [PassShelat]: Chapter 3 and Chapter 5
 Lecture 15 (20191016, Wednesday)
 (tentative) Signature schemes for multiple messages

 [PassShelat]: Chapter 5

 [Trevisan]: Lecture 21
 Lecture 16 (20191018, Friday)
 Wrapping up digital signature schemes. Introduction to zero knowledge

 [Trevisan]: Lecture 21

 [PassShelat]: Chapter 4
 Lecture 17 (20191022, Tuesday)
 Zero knowledge protocols for graph isomorphism and quadratic reciprocity

 [Trevisan]: Lecture 25
 Lecture 18 (20191023, Wednesday)
 Commitment schemes via OWPs, zero knowledge protocols for NP

 [Trevisan]: Lecture 27
 Lecture 19 (20191028, Monday)
 Zero knowledge protocols for NP (finished proof), introduction to ZK Proofs of Knowledge

 [Trevisan]: Lecture 28, 26
 Lecture 20 (20191101, Friday)
 More on proofs of knowledge, and noninteractive zero knowledge in the randomoraclemodel, brief sketch of zero knowledge for IP
(End of Part 2 of the course. Part 3 of the course begins)
 Lecture 21 (20191104, Monday)
 Homomorphisms in encryption, introduction to lattices, the shortest vector problem

 [VinodV]: Parts of Lecture 1 and 2
 Lecture 22 (20191118, Monday)
 The LLL algorithm for a 2^{O(n)}approximation for SVP
 Lecture 23 (20191121, Thursday)
 SIVP and SIS, Gaussian smoothening, worst case to average case hardness, CRHF based on SIS

 [VinodV]: Lecture 11, and parts of Lecture 12
 Lecture 24 (20191125, Monday)
 Learning with errors (LWE): basic properties and cryptosystems based on it

 [VinodV]: Lecture 13
 Lecture 25 (20191128, Thursday)
 Fully homomorphic encryption: [GentrySahaiWaters] scheme for levelled FHE, sketch of bootstrapping

 [VinodV]: Lecture 13

 Lecture 23 and Lecture 24 of Daniel Wichs’ course Foundations of Cryptography

 “Computing arbitrary functions of encrypted data” by Craig Gentry