In Semester 2, 2016-2017, I will be teaching CS7111: Topics in Cryptography.
Course Description
The course will cover some exciting recent progress in cryptography in the field of computing on encrypted data. In the age of cloud computing, everyone agrees on the benefits of outsourcing data storage and computation to some server, such as Google or Amazon. In the age of wikileaks and Snowden, everyone also agrees that the server cannot be trusted and the data should be stored encrypted. But these are conflicting objectives. On the one hand, data must be encrypted, on the other, the point of cloud computing is to compute on this data. As you know, encryption hides all information about the underlying message, thus encrypted data should appear random. Computation performed on random junk will be random junk. How then, do we extract structure from this random looking encryption to compute functions on the underlying plaintext? How do we argue that data privacy was maintained? Recent years in crypto have seen some beautiful solutions to this problem ranging from fully homomorphic encryption to functional encryption to witness encryption to obfuscation to outsourcing computation. In CS7111, we will study some of these advances. The course will be entirely mathematical in nature. The focus will be on identifying interesting directions for future research.
Administrative Information
Lectures are Wednesdays and Fridays, 2:00-3:30 pm in CSB 36. Office hours are by appointment: just send me an email and drop in!
Pre-requisites.
This course requires mathematical maturity, you should be comfortable with the language of proofs. Knowledge of algorithms, theory of computing (i.e. familiarity with reductions), some algebra and probability theory is required. The course will be self contained for the most part but you should be familiar with the tools and techniques used in theoretical computer science. It is really useful if you have done CS 6111 (Foundations of Cryptography) but this is not absolutely essential.
In terms of background reading,
here are some good notes. Read chapter 3 and as much of 2 as you can. You should understand public key encryption well for now. The MOOC https://www.coursera.org/course/crypto is very useful, as is Katz Lindell's "Introduction to Modern Cryptography" (available on flipkart, you can borrow my copy for some time if you like).
Requirements.
- Class presentation : 25%
- Assignments : 20%. Assignments will be open ended in nature and collaboration is encouraged.
- Midterm :20%
- Final :20%
- Class Participation: 15%
Resources
The course will have several commonalities with
this course at MIT,
this course at Columbia and
this course at ENS Lyon.
For background on lattices, useful notes are
Regev's course notes or
Daniele's slides. See also
Daniele's talk and
Chris Peikert's expository talks.
Topics
Below are the topics we will discuss in class. We'll cover some subset or superset of these, depending on time. Suggestions for other topics are also welcome!
Part 1: Fully Homomorphic encryption
- The scheme of BGV12 , see this for some useful notes. For details about LWE, see this survey and the original paper.
- The scheme of GSW13 and (possibly) the improvement of BV14. Some useful notes are here.
- The multi-key FHE scheme of CG14 and its simplification MW15.
Part 2: Functional Encryption
- Introduction to Functional Encryption. Motivation and definition of FE, different relaxations of FE, Indistinguishability based security. Useful notes are here.
- Dual Regev Public Key Encryption, see GPV08. and trapdoors for lattices by MP12. Useful notes are here.
- Attribute based encryption of BGG+14. Notes are here.
- Construction of Yao's Garbled circuits from checkable symmetric key encryption.
- Reusable Garbled Circuits, relevant papers are here and here.
Part 3: Indistinguishability Obfuscation
- Introduction to obfuscation and impossibility of strongest definition. Some reading is here and the paper is here.
- "Best possible Obfuscation" and its usefulness, see SW14.
- Strong notions of FE imply obfuscation.
Assignments