Cryptography (2019-II)

(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.

Lecture schedule and overview

Lecture 1 (2019-08-19, Monday)
Introduction, one-time pads, basics of provable security, an example of secure computation of AND
Lecture 2 (2019-08-22, Thursday)
Shamir’s Secret Sharing Scheme, introduction to cryptography from intractability
Lecture 3 (2019-08-26, Monday)
Computational indistinguishability, revisiting hybrid arguments, introduction to pseudorandom generators
Lecture 4 (2019-08-29, Thursday)
Pseudorandom functions, building PRGs from PRFs, the Goldreich-Goldwasser-Micali construction of building PRFs from PRGs

(2019-09-02 is a holiday (Ganesh Chaturthi))

Lecture 5 (2019-09-05, Thursday)
Proof of correctness of the GGM construction, PRPs and block ciphers, security under Chosen Plaintext Attacks, some block cipher modes and padding schemes
Lecture 6 (2019-09-09, 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 (2019-09-12, Thursday)
CCA security via strong PRPs, introduction to MACs, PRFs are MACs, brief description of CCA-MAC and ECBC-MAC
Lecture 8 (2019-09-19, Thursday)
CCA-security of Encrypt-Then-MAC, collision-resistant hash functions

(End of Part 1 of the course. Part 2 of the course begins)

Lecture 9 (2019-09-23, Monday)
Minimal assumptions for crypto, introduction to one-way functions (OWFs), weak OWFs imply strong OWFs
Lecture 10 (2019-09-26, Thursday)
The universal OWF, one-way permutations, trapdoor permutations, towards building PRGs
Lecture 11 (2019-09-30, Monday)
Next-Bit-Unpredictability implies PRG, hardcore predicate for DL, hardcore predicates for OWPs, towards the Goldreich-Levin theorem
Lecture 12 (2019-10-04, Friday)
The proof of the Goldreich-Levin theorem
Lecture 13 (2019-10-09, Wednesday, tentative)
(tentative) Public key cryptography, theoretical constructions, descriptions of practical implementations of DDH, RSA, ElGamal, Cramer-Shoup
Lecture 14 (2019-10-14, Monday)
Some nuances about the DDH, digital signature schemes
Lecture 15 (2019-10-16, Wednesday)
(tentative) Signature schemes for multiple messages
Lecture 16 (2019-10-18, Friday)
Wrapping up digital signature schemes. Introduction to zero knowledge
Lecture 17 (2019-10-22, Tuesday)
Zero knowledge protocols for graph isomorphism and quadratic reciprocity
Lecture 18 (2019-10-23, Wednesday)
Commitment schemes via OWPs, zero knowledge protocols for NP
Lecture 19 (2019-10-28, Monday)
Zero knowledge protocols for NP (finished proof), introduction to ZK Proofs of Knowledge
Lecture 20 (2019-11-01, Friday)
More on proofs of knowledge, and non-interactive zero knowledge in the random-oracle-model, brief sketch of zero knowledge for IP

(End of Part 2 of the course. Part 3 of the course begins)

Lecture 21 (2019-11-04, Monday)
Homomorphisms in encryption, introduction to lattices, the shortest vector problem
Lecture 22 (2019-11-18, Monday)
The LLL algorithm for a 2O(n)-approximation for SVP
Lecture 23 (2019-11-21, 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 (2019-11-25, Monday)
Learning with errors (LWE): basic properties and cryptosystems based on it
Lecture 25 (2019-11-28, Thursday)
Fully homomorphic encryption: [Gentry-Sahai-Waters] scheme for levelled FHE, sketch of bootstrapping