Announcements

• [25 Nov] All the draft scribe notes until Lecture 7 are posted now. A cautionary note: they are lightly proof-checked and edited and I do not vouch for the correctness of all the material therein.
• [23 Sep] Draft scribe notes for Lecture 1 are posted now.

Course Information

INSTRUCTOR	Vinod Vaikuntanathan Office: 32-G696 E-mail: vinodv at mit
LOCATION	34-304
TIME	Monday 12:30 - 2:30pm (Note new time), Office Hours by appointment
TEXTBOOK	There are no required textbooks. Instead, we will use material from a number of current research papers listed below.
GRADING	Based on Scribing 1-2 Lectures and a Final Project. The final project could be either: (a) a clear exposition of a new result on the topic of computing on encrypted data; (b) the solution to an open problem; or (c) the design and implementation of a new application that uses encrypted computation.

The course counts for Grad-H Credit as well as the M.Eng. Theory of Computation Concentration.

Course Description

We will study both classical and modern technologies for computing on encrypted data including:

1. Secure Multi-party Computation Protocols;
2. Fully Homomorphic Encryption;
3. Functional Encryption; and
4. Program Obfuscation.

We will discuss the recent exciting developments in these areas, as well as a number of open problems.

Prerequisites: We will assume knowledge of basic cryptography and mathematical maturity. 6.875 or 6.857 is a plus.

• Template for scribe notes: the style file and a sample tex file.
• Some Project Ideas.

Schedule (subject to change)

Lecture	Topic	Scribe Notes
Lecture 1 (Sep 09)	Introduction: Private Outsourcing of Computation. Homomorphic Encryption Schemes: RSA, El Gamal, Goldwasser-Micali, Paillier. The Learning with Errors Problem.	Madars Virza Draft Scribe Notes [ pdf ]
Lecture 2 (Sep 16)	The Learning with Errors Problem (decision and search versions), Search to decision reductions, Lattices, Worst-case to Average-case Reduction for LWE, Private-key and Public-key Encryption Schemes based on LWE, Basic Additive and Multiplicative Homomorphisms.	William Cyr Draft Scribe Notes [pdf ]
Lecture 3 (Sep 23)	Dimension Switching and Somewhat Homomorphic Encryption.	Chiraag Juvekar Draft Scribe Notes [pdf ]
Lecture 4 (Sep 30)	Modulus Switching, Leveled FHE Bootstrapping Theorem and FHE, Circular security of encryption schemes	Cheng Chen Draft Scribe Notes [pdf ]
Lecture 5 (Oct 7)	Verifiable Outsourcing of Computation. Kilian's Efficient Arguments and Micali's CS proofs. The Goldwasser-Kalai-Rothblum interactive proof for poly-time computations. Lecturer: Yael Kalai.	Justin Holmgren Draft Scribe Notes [pdf ]
	No Class: Columbus Day
Lecture 6 (Oct 21)	Functional Encryption. Yao's Garbled Circuits and Single-key Functional Encryption.	Aakanksha Sarda and Yilei Chen Draft Scribe Notes [pdf ]
Lecture 7 (Oct 28)	Garbled Circuits (contd.), dual Regev encryption.	Prashant Vasudevan Draft Scribe Notes [pdf ]
Lecture 8 (Nov 4)	Lattices, Trapdoors for Lattices and Identity-based Encryption.	Sunoo Park Draft Scribe Notes [pdf ]
	No Class: Veteran's Day
Lecture 10 (Nov 18)	Gaussian Sampling and IBE.	Ioana Ivan Draft Scribe Notes [pdf ]
Lecture 11 (Nov 25)	Constructions of Attribute-based Encryption and Functional Encryption	Adin Schmahmann Draft Scribe Notes [pdf ]
Lecture 12 (Dec 2)	Advanced Topics: Program Obfuscation	Aloni Cohen
Lecture 13 (Dec 9)	Advanced Topics: Oblivious RAM	Nathan Rittenhouse Draft Scribe Notes [pdf ]

References

General References.

• homomorphic encryption course at Tel Aviv University.

Lecture 1.

• Dana Angluin's number theory primer.
• The Rivest-Adleman-Dertouzos paper.
• Gentry's CACM paper on "Computing on Encrypted Data". [pdf]
• Regev's paper on the learning with errors problem and the associated cryptosystem. See Section 5. [pdf]

Lecture 2.

• Regev's Survey of the Learning with Errors problem and Applications, CCC 2010. [pdf]
  (Note that although this survey is a great resource for basic facts about and applications of LWE, it is a little dated. In particular, some of the open problems mentioned therein -- most notably, constructing pseudorandom functions and fully homomorphic encryption schemes based on LWE -- have since been solved.)
• Regev's paper on the learning with errors problem, the worst-case to average-case reduction for LWE and the associated private- and public-key cryptosystems. [pdf]
• Brakerski-Vaikuntanathan [pdf] and Brakerski-Gentry-Vaikuntanathan [pdf] and Brakerski [link to crypto eprint] on LWE-based fully homomorphic encryption schemes.
  
  
• Additional Reading: Rothblum's paper: How to go from Private key to Public key Homomorphic Encryption. [pdf]
• Additional Reading: Micciancio-Mol on sample-preserving reductions from search to decision LWE. [link to crypto eprint]
• Additional Reading: Brakerski et al. on a search to decision reduction for LWE with arbitrary modulus (among a number of other results) [link to arxiv]
• Additional Reading: Micciancio-Peikert with more results on the hardness of LWE with small errors. [link to crypto eprint]

Lecture 3.

• Brakerski-Vaikuntanathan [pdf] and Brakerski-Gentry-Vaikuntanathan [pdf] and Brakerski [link to crypto eprint] on LWE-based fully homomorphic encryption schemes.
• Gentry's Ph.D. thesis, Chapter 4 for a proof of the bootstrapping theorem. [link]
• How to add in log depth [pdf]
• Applebaum-Cash-Peikert-Sahai [pdf] for circular security of LWE-based encryption and a proof of equivalence between LWE with uniform secrets and LWE with "short" secrets.
  
  
• Additional Reading: Brakerski et al. on a search to decision reduction for LWE using modulus reduction [link to arxiv]
• Additional Reading: The Lindner-Peikert paper [link to crypto eprint] on parameters for LWE-based encryption schemes.

Lecture 5.

• Efficient Arguments. [pdf]
• Micali's CS proofs. [pdf]
• Goldwasser-Kalai-Rothblum interactive proofs for "muggles" [pdf]

Lecture 6.

• Boneh, Sahai and Waters. Functional Encryption: Definitions and Challenges. [ link to eprint ]
• Lindell and Pinkas. A Proof of Security of Yao's Protocol for Secure Two-Party Computation [ link to eprint ]

Lecture 7.

• Lindell and Pinkas. A Proof of Security of Yao's Protocol for Secure Two-Party Computation [ link to eprint ]
• Gentry, Peikert, Vaikuntanathan. Trapdoors for Hard Lattices and Cryptographic Applications [link to eprint]
• Micciancio, Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. [link to eprint]

---