CS101abc Introduction to Theoretical Cryptography
Term: Spring 2016
Lectures: MW 10:3012, 213 Annenberg
Instructor: Thomas Vidick
Office hours: Monday 23pm, 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: oneway functions, pseudorandom generators, public and privatekey 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, latticebased cryptography and quantumproof 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 23: Computational hardness. Oneway functions, hardness amplification.
 Week 4: Authentication
 Weeks 56: Indistinguishability and pseudrandomness. Pseudorandom generators, the GoldreichLevin theorem, pseudorandom permutations.
 Week 7: Symmetrickey encryption. Stream and block ciphers.
 Week 8: Publickey encryption.
 Week 9: Zeroknowledge.
 Week 10: Latticebased 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 onetime pad, Shannon's theorem.
Reading: KatzLindell sections 1, 2, 3.1, 3.2. 
March 30th.
Oneway functions. Rabin's function.
Reading: KatzLindell sections 7.1, 8.1, 8.2.1, 8.4.1. 
April 4th.
Weak OWF, strong OWF, hardness amplification.
Computational indistinguishability. Pseudorandom generators.
Reading: KatzLindell section 3.3.1. 
April 6th.
Length extension theorem for PRG. Encryption from PRG. Hardcore bits.
Reading: KatzLindell sections 7.4.2, 3.3.3, 7.1.3. 
April 11th.
GolreichLevin theorem.
Reading: KatzLindell section 7.3. 
April 13th.
Pseudorandom functions. INDCPA security.
Reading: KatzLindell sections 3.5 and 7.5. 
April 18th.
Publickey encryption. Trapdoor OWP, DDH and ElGamal PKC.
Reading: KatzLindell sections 10.3, 11.1, 11.4.1, 13.1. 
April 20th.
Authentication. MAC. INDCCA scehemes from MAC.
Reading: KatzLindell sections 4.1, 4.2, 4.3, 4.5, 4.6. 
April 25th.
Digital signatures. Collisionresitant hash functions, signatures from CRHF.
Reading: KatzLindell 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: KatzLindell section 5.5 
May 2nd.
Symmetrickey encryption in practice: block ciphers, AES.
Reading: KatzLindell section 5. 
May 4th.
Publickkey encryption in practice: Attacks on plain RSA, padded RSA.
Reading: KatzLindell section 11.5. 
May 9th.
Zeroknowledge, Interactive proofs.
Reading: PassShelat sections 4.14.6. 
May 11th.
Commitment schemes. Construction from OWP+hardcore bit.
Reading: PassShelat sections 4.74.9. 
May 16th.
Zeroknowledge proofs for NP. Intro to multiparty computation.
Reading: PassShelat section 4.7. 
May 18th.
Oblivious transfer: definitions, constructions.
Reading: PassShelat section 6.2.4. 
May 20th.
Yao's garbled circuits: secure computation of any twoparty function against semihonest adversaries.
Reading: PassShelat sections 6.2.16.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 Turingaward winning paper inventing publickey 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 GoldwasserMicaliRackoff paper proposing a definition of interactive proofs and inventing ZeroKnowledge (another Turingaward 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: