6.892 (Fall 2013)
Seminar: Computing on Encrypted Data



Announcements

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.

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.
  • Lecture 1.
  • Lecture 2.
  • Lecture 3.
  • Lecture 5.
  • Lecture 6.
  • Lecture 7.