CS101abc Introduction to Theoretical Cryptography
Term: Spring 2016
Lectures: MW 10:30-12, 213 Annenberg
Instructor: Thomas Vidick
Office hours: Monday 2-3pm, 207 Annenberg
Course descriptionCryptography is the art, or science, of secret writing. This course will introduce you to the definition, construction and analysis of the major building blocks of modern cryptography: one-way functions, pseudo-random generators, public and private-key encryption schemes, digital signature schemes, message authentication codes, and others. Time permitting we will consider some recent topics of interest such as homomorphic encryption, indistinguishability obfuscation, lattice-based cryptography and quantum-proof schemes.
Course outlineHere is an indicative list of topics to be covered in the course:
- Week 1: Introduction to the paradigm of modern cryptography. Perfect secrecy and Shannon's theorem.
- Weeks 2-3: Computational hardness. One-way functions, hardness amplification.
- Week 4: Authentication
- Weeks 5-6: Indistinguishability and pseudrandomness. Pseudorandom generators, the Goldreich-Levin theorem, pseudorandom permutations.
- Week 7: Symmetric-key encryption. Stream and block ciphers.
- Week 8: Public-key encryption.
- Week 9: Zero-knowledge.
- Week 10: Lattice-based cryptography.
PrerequisitesA major focus of the course will be on definitions and proofs of security. As such, the most important prerequisite is mathematical maturity. Students are expected to be comfortable reading and writing mathematical proofs, be at ease with algorithmic concepts, and have elementary knowledge of discrete math, number theory (modular arithmetic), and discrete probability.
No programming will be required for the course.
Evaluation and workloadThere will be a biweekly problem set. In addition, you will be asked to read and write short reports on some classic papers in the field of cryptography. There will be a final exam.
Introduction. Perfect secrecy, the one-time pad, Shannon's theorem.
Reading: Katz-Lindell sections 1, 2, 3.1, 3.2.
One-way functions. Rabin's function.
Reading: Katz-Lindell sections 7.1, 8.1, 8.2.1, 8.4.1.
Weak OWF, strong OWF, hardness amplification.
Computational indistinguishability. Pseudo-random generators.
Reading: Katz-Lindell section 3.3.1.
Length extension theorem for PRG. Encryption from PRG. Hard-core bits.
Reading: Katz-Lindell sections 7.4.2, 3.3.3, 7.1.3.
Reading: Katz-Lindell section 7.3.
Pseudo-random functions. IND-CPA security.
Reading: Katz-Lindell sections 3.5 and 7.5.
Public-key encryption. Trapdoor OWP, DDH and El-Gamal PKC.
Reading: Katz-Lindell sections 10.3, 11.1, 11.4.1, 13.1.
Authentication. MAC. IND-CCA scehemes from MAC.
Reading: Katz-Lindell sections 4.1, 4.2, 4.3, 4.5, 4.6.
Digital signatures. Collision-resitant hash functions, signatures from CRHF.
Reading: Katz-Lindell sections 12.1, 12.2, 12.3, 12.5.1, 12.6.1.
The random oracle model. Signatures in the RO model.
Reading: Katz-Lindell section 5.5
Symmetric-key encryption in practice: block ciphers, AES.
Reading: Katz-Lindell section 5.
Publick-key encryption in practice: Attacks on plain RSA, padded RSA.
Reading: Katz-Lindell section 11.5.
Zero-knowledge, Interactive proofs.
Reading: Pass-Shelat sections 4.1-4.6.
Commitment schemes. Construction from OWP+hardcore bit.
Reading: Pass-Shelat sections 4.7-4.9.
Zero-knowledge proofs for NP. Intro to multiparty computation.
Reading: Pass-Shelat section 4.7.
Oblivious transfer: definitions, constructions.
Reading: Pass-Shelat section 6.2.4.
Yao's garbled circuits: secure computation of any two-party function against semi-honest adversaries.
Reading: Pass-Shelat sections 6.2.1-6.2.3 and 6.2.5
General multiparty computation; malicious adversaries. The GMW compiler.
Reading: Chapter 7 in the survey by Goldreich.
The learning with errors problem (LWE)
Reading: Boaz Barak's lecture notes.
- Due April 13th: Kerckhoffs' 1883 desiderata for military cryptography, and Shannon's 1949 paper on the Communication Theory of Secrecy Systems.
- Due April 27th: Diffie and Hellman's 1976 Turing-award winning paper inventing public-key cryptography, and Merkle's 1978 paper proposing Merkle puzzles as a way to achieve computationally secure key distribution.
- Due May 11th: The RSA paper, and the Goldwasser-Micali-Rackoff paper proposing a definition of interactive proofs and inventing Zero-Knowledge (another Turing-award winning paper!).
- Due May 25th: Manuel Blum on Coin Flipping and Adi Shamir on How to Share a Secret.
ResourcesThe course textbook is Introduction to modern cryptography (second edition), by Katz and Lindell.
Background on number theory:
Links to similar classes: