In Semester 1, 2019-2020, 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 3:30- 4:45 pm and Fridays, 2:00-3:30 pm in CSB 34. 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%
- Scribe: 15%
Resources
The course will have several commonalities with
this course at MIT,
this course at ENS Lyon and
this course at Berkeley.
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: Basics of lattice based cryptography.
- Introduction to SIS and LWE. Basic properties and cryptographic applications: public and private-key encryption and collision-resistant hashing. Reference is here.
More references: For more background on lattices, useful notes are
Regev's course notes or
Daniele's slides. See also
Daniele's talk,
Chris Peikert's expository talks and Regev's survey.
Part 2: Fully Homomorphic encryption
A nice survey is
here.
- FHE of BV11 and Brakerski 12: References are here and here. The modulus reduction trick from BGV12 is described in these notes.
- FHE of GSW13 and (possibly) the improvement of BV14. Some useful notes are here.
- Multi-key FHE. The multi-key FHE scheme of CG14 and its simplification MW15. We will use MW15 as our main reference.
Part 3: Bilinear Maps and Applications
- Identity Based Encryption: Notes are here and here.
- Broadcast Encryption.
Part 4: Multilinear Maps and Indistinguishability Obfuscation
- Witness Encryption. Some notes are here.
- Introduction to obfuscation and impossibility of strongest definition. Some reading is here and the paper is here.
- "Best possible Obfuscation" and its usefulness. We will refer to notes from UCB: notes 1, notes 2 and notes 3. For additional reading, see the SW14 paper.
- Current constructions of iO.