COL 872: Cryptography for the Cloud

In Semester 2, 2014-2015, I will be teaching C0L 872: Cryptography for the Cloud.

Course Description

The course will cover some exciting recent progress in cryptography in the field of computing on encrypted data. The course will be entirely mathematical in nature, as was my version of 759. The focus will be on identifying interesting directions for future research.

Administrative Information

When and Where.

Mondays and Thursdays, 3:30-5:00 pm in Bharti 204. The slot for the class has been changed to X to avoid any conflicts. Please register!

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 CSL 759 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. Knowing about PRFs and Oblivious Transfer may be useful for later classes. 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 : 30%
• One or two scribes : 20%
• Assignments : 15%. Assignments will be open ended in nature and collaboration is encouraged.
• Midterm :20%
• Class Participation: 15%

There will be extra credit problems/questions throughout the course.

Resources

The course will have several commonalities with this course at MIT and this course at Columbia.

Project Ideas

Some project ideas are available here. PROJECT REPORTS ARE DUE ON APRIL 30th END OF DAY BY EMAIL.

Scribes

Below are the scribes for the class. The scribes are only accessible from within the IITD network.

Part 1: Lattice Based Cryptography and Fully Homomorphic encryption

• Lec 1: Jan 8th. The scribe 1 is by Dhiraj.
• Lec 2 and 3: Jan 12 and 15th: The scribe 2 and 3 is by Ishaan.
• Lec 4 and 5: Jan 19 and 22 : scribe 4 and scribe 5 is by Gajraj.
For lectures 1-5, please refer to first 4 lectures of this course.
• Jan 26 holiday. Happy Republic day.
• Lec 6 and 7: Jan 28 and Feb 2 : Background on lattices. Useful notes are Regev's course notes or Daniele's slides . Scribe 6 and scribe 7 are by Jatin. Scribe 7 is incorrect -- it is actually a scribe of the following lecture. Please refer to Regev's course notes or Daniele's notes to study this material.
• Lec 8 (Feb 5): Computational problems in lattices and hardness of LWE. The scribe is by Abhay, available here.
• Lec 9 (Feb 9): Student Presentation: Sai Praneeth Reddy on Worst case to Average case reductions for Lattices. The notes followed were by Regev.
• Lec 10 (Feb 12): Student Presentation: Jatin Batra on "New Algorithms for Learning in the prescence of errors". The paper is here.
• Feb 17 and 19: No class due to Minor 1 on Feb 17th and Instructor unwell on Feb 19th.
• Lec 11 and Lec 12 (Feb 23 and Feb 26 ) Scribes are by Nishant, available here and here.

Part 2: Functional Encryption

• Lec 13 (March 9th): Introduction to Functional Encryption. Motivation and definition of FE, different relaxations of FE, Indistinguishability based security. Scribe by Abhay. Notes are here.
• Lec 14 (March 12th): Simulation based security for Functional Encryption. Impossibility for SIM secure IBE described by BSW11. Scribe by Dhiraj, available here. (temporarily in handwritten format). The texed up version is here.
• Lec 15 and 16 (March 16th and March 23rd): Detailed discussion of BSW Impossibility. Definition of Garbled circuits. Construction of inner product garbled circuit scheme. Construction of Single Key functional encryption scheme using Garbled circuits. Scribe by Bharadwaj available here.
• (March 19th): No class due to Minor 2.
• Lec 17 (March 25th) (makeup class for Feb 19th) : Construction of Yao's Garbled circuits from checkable symmetric key encryption. Scribe by Kunal available here.
• Lec 18 (March 26th) : Towards FE from LWE: Ajtai lattices, facts about Ajtai lattices, discrete Gaussians and their properties, generating trapdoors. Two equivalent methods to generate the (A, e, u) distribution, where A, u are random and e is a discrete Gaussian. Much of this material is discussed in the preliminaries of GPV08. Scribe by Tapas available here.
• Lec 19 (March 30) : Construction of Inner product functional encryption from LWE. Paper is available here. Scribe by Tapas available here.
• Lec 20 (April 1) : Discussion on SIM based versus IND based FE. Discussed a hypothetical trivial simulator that seemingly always succeeds and analyzed why it fails. Completed construction of inner produce FE and began discussion of security. Security notion achieved by construction is "weak attribute hiding in the selective case". Discussion of this definition. Scribe by Kunal available here.
• Lec 21 (April 2) : Discussion of insufficiencies of IND based definition, described in BSW11. Scribe by Surbhi available here.
• Lec 22 (April 8) : This class is a makeup for April 6th, when I was unwell. Complete the security proof of AFV11. Scribe by Surbhi available here.
• Lec 23 (April 9) : Reusable Garbled Circuits construction. The paper is here. Scribe by Dravyansh.

Part 3: Miscellaneous Topics on Popular Demand.

• Lec 24 (April 13): Cryptographic puzzles to combat denial of service and to implement bitcoins. Slides for DoS attacks are here and slides for Bitcoins (though I did not use them) are here.
• Lec 25 (April 16): Guest Lecture by Dr Amit Pande on location privacy. Slides are here.
• Lec 26 (April 20): Student Presentations.
• Lec 27 (April 23): Student Presentations.