Columbia University, Computer Science
Spring 2013, COMS E6261

Homomorphic Encryption and Lattices

Tuesdays 2:10-4:00pm, Mudd 1024
Instructor: Shai Halevi, co-instructor: Tal Malkin, TA: Fernando Krell
Office hours: Tal on Thursdays 2-4pm, Shai & Fernando by request

This class will cover results in cryptography, mostly from the last few years, related to homomorphic encryption schemes and other lattice-based cryptosystems. The format will mostly be regular lectures, but some lectures may also be given by students (if there is interest).

Schedule

January 22 Introduction to Lattices. Lecture notes from Oded Regev's course in Tel-Aviv.
Januray 29 The Hermite normal form. Material contained in notes of lecture 4 and lecture 5 from Gennady Shmonin's course in EPFL.
February 5 The LLL algorithm, lecture notes from Oded Regev's course.
February 12 Ajtai's worst-case/average-case connection. The Small Integer Solution problem (SIS), Relation to worst-case SVP, SIVP, SIS-based collision-resistant hashing. Lecture notes from Oded Regev's course.
February 19 • Discrete Gaussians, Smoothing Parameter, Lecture notes from Oded Regev's course
• Leftover Hash Lemma, Lecture notes from Ronitt Rubinfeld's course in MIT.
February 26
Class notes		 The Learning with Errors problem (LWE), random-self reducability, search-to-decision reduction, the Regev'05 cryptosystem.
March 12
Class notes		 The Gentry-Peikert-Vaikuntanathan SIS-based signatures [GPV08]
March 26
Class notes		 The lattice trapdoor construction of Micciancio-Peikert [MP12]
April 2 Yao garbled circuits. See the Lindel-Pinkas exposition and proof [LP09].
April 9
Class notes		 The Gorbunov-Vaikuntanathan-Wee LWE-based Delegation & Attribute-Based Ecnryption Scheme [GVW13]
April 12
Class notes		 • Continue with [GVW13] Attribute-Based Ecnryption
• LWE-based homomorphic encryption
April 16
Class notes		 Continue LWE-based homomorphic encryption [BV11, BGV12, B12]
April 23
Class notes		 Ideal Lattices, The NTRU cryptosystem, [SS11]
April 30 • Continue with the NTRU cryptosystem, [LTV12]
• Multilinear maps from ideal lattices [GGH13] (slides)

Homework

  1. Problem-set #1, due Feb 5.
  2. Problem-set #2, due Feb 19.
  3. Problem-set #3, due Mar 12.
  4. Problem-set #4, due Mar 26.
  5. Problem-set #5, due Apr 23.
  6. Problem-set #6, due May 7.

Handouts

PRE-REQUISITES:

The main pre-requisite is general familiarity with modern theory of cryptography, such as obtained by taking the class 4261 introduction to cryptography.

For example, students are assumed to be familiar with the notion of semantic-security of encryption schemes (CPA-security), know about standard hardness assumptions (e.g., factoring), and be comfortable with reduction-based proofs of security. We also assume good command of linear algebra (e.g., matrices and their rank, the determinant, Gaussian elimination, Gram-Schmidt orthogonalization, etc.) To the extent that we need more advanced algebra, we will cover it in class.

GRADING:

Grade will be based on a combination of class participation, homework, scribe notes, and maybe also a project or presentation of a paper.

Scribe notes: We will need scribes for each lecture, the scribe notes should be a cleaned-up summary of the lecture (possibly with some additional details that were omitted in class).

Project: In the second half of the class we may assign small projects instead of regular problem-sets, for example reading a recent paper and summarizing it in a report.

Paper Presentation: We may have a few of the lectures given by students, on recent papers related to the general topic of the class. (No more than 3-4 of the classes.) Students who want to present a paper in class should contact the lecturer.

SYLLABUS:

Below is a very tentative course plan. There are likely to be changes to this plan as the semester goes on, especially toward the end.