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
Jump to:
Course description
Cryptography 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 outline
Here 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.
Prerequisites
A 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 workload
There 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.Lectures
-
March 28th.
Introduction. Perfect secrecy, the one-time pad, Shannon's theorem.
Reading: Katz-Lindell sections 1, 2, 3.1, 3.2. -
March 30th.
One-way functions. Rabin's function.
Reading: Katz-Lindell sections 7.1, 8.1, 8.2.1, 8.4.1. -
April 4th.
Weak OWF, strong OWF, hardness amplification.
Computational indistinguishability. Pseudo-random generators.
Reading: Katz-Lindell section 3.3.1. -
April 6th.
Length extension theorem for PRG. Encryption from PRG. Hard-core bits.
Reading: Katz-Lindell sections 7.4.2, 3.3.3, 7.1.3. -
April 11th.
Golreich-Levin theorem.
Reading: Katz-Lindell section 7.3. -
April 13th.
Pseudo-random functions. IND-CPA security.
Reading: Katz-Lindell sections 3.5 and 7.5. -
April 18th.
Public-key encryption. Trapdoor OWP, DDH and El-Gamal PKC.
Reading: Katz-Lindell sections 10.3, 11.1, 11.4.1, 13.1. -
April 20th.
Authentication. MAC. IND-CCA scehemes from MAC.
Reading: Katz-Lindell sections 4.1, 4.2, 4.3, 4.5, 4.6. -
April 25th.
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. -
April 27th.
The random oracle model. Signatures in the RO model.
Reading: Katz-Lindell section 5.5 -
May 2nd.
Symmetric-key encryption in practice: block ciphers, AES.
Reading: Katz-Lindell section 5. -
May 4th.
Publick-key encryption in practice: Attacks on plain RSA, padded RSA.
Reading: Katz-Lindell section 11.5. -
May 9th.
Zero-knowledge, Interactive proofs.
Reading: Pass-Shelat sections 4.1-4.6. -
May 11th.
Commitment schemes. Construction from OWP+hardcore bit.
Reading: Pass-Shelat sections 4.7-4.9. -
May 16th.
Zero-knowledge proofs for NP. Intro to multiparty computation.
Reading: Pass-Shelat section 4.7. -
May 18th.
Oblivious transfer: definitions, constructions.
Reading: Pass-Shelat section 6.2.4. -
May 20th.
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 -
May 23rd.
General multiparty computation; malicious adversaries. The GMW compiler.
Reading: Chapter 7 in the survey by Goldreich. -
May 25th.
The learning with errors problem (LWE)
Reading: Boaz Barak's lecture notes.
Reading assignments
- 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.
Resources
The course textbook is Introduction to modern cryptography (second edition), by Katz and Lindell.Background on number theory:
Links to similar classes: