School of Computer Science, Tel Aviv University
Spring 2011, 0368-4147-01

Homomorphic Encryption and Lattices

Thursdays 10am-1pm, Ornstein 110
Instructor: Shai Halevi

This class will cover several results in cryptography (many from the last few years) that I found interesting, loosely related to homomorphic encryption schemes and lattice-based schemes. The format may be a mix of a regular class and a seminar: I plan to give most of the lectures myself, but some of the lectures may also be given by students (see below).

Schedule

February 24 Fully-homomorphic encryption over the integers [vDGHV, Eurocrypt 2010]. Slides in PPTX or PDF.
March 3 Introduction to Lattices. Lecture notes from Oded Regev's course
March 10 • The Hermite normal form. Material contained in notes of lecture 4 and lecture 5 from Gennady Shmonin's course in EPFL.
• The LLL algorithm, lecture notes from Oded Regev's course.
March 17 Lattice-Based Cryptanalysis. Specifically:
• Simultaneous Diophantine Approximations (SDA) and application to the approximate-GCD problem (hand-written notes - 2MB).
• Coppersmith's Method (hand-written notes - 1.7MB).
Most of the material can be found in Chapter 20 of Steven Galbraith's book on Mathematics of Public Key Cryptography.
March 24 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.
April 7
Lecture Notes 		Lattice Trapdoor Constructions: Ajtai, Alwen-Peikert, Micciancio-Peikert.
April 28 Learning with Errors (LWE). Based on [Regev, JACM 2009] and [Peikert, STOC 2009]. See also Oded Regev's survey. (Hand-written class notes, 5.2MB).
May 5
Lecture Notes
Lecture Notes 		More Learning with Errors:
• Regev's main average-case to worst-case lemma.
• The GHV quadratic-homomorphic encryption scheme based on LWE.
May 12
Lecture Notes 		Ideal lattices. Background: rings, ideals, and ideal-lattices. The collision-resistant hashing from [PR, TCC 2006] and [LM, ICALP 2006]. Material mostly from Vadim Lyubashevsky's PhD thesis, Chapters 2(C-F) and 3.
May 19
Lecture Notes 		The somewhat-homomorphic encryption scheme from [Gentry 2009] (material mostly from Craig Gentry's PhD thesis).
May 26 The Smart-Vercauteren/Gentry-Halevi variants of Gentry's SWHE, and optimizations. Material mostly from the Gentry-Halevi EUROCRYPT 2011 paper. (See also this printout.)
June 2
Lecture Notes 		• The somewhat-to-fully homomorphic transformation, as applied specifically to the Gentry-Halevi variant.
• FHE without squashing using the new "Chimeric scheme" of Gentry-Halevi.
June 9
Lecture Notes 		• The Brakerski-Vaikuntanathan SWHE/FHE scheme from LWE, and Gentry's "leveled-FHE" without bootstrapping. Material taken from Gentry's manuscript.

Homework

  1. Problem-set #1 and solutions.
  2. Problem-set #2 and solutions.
  3. Problem-set #3 and solutions.
  4. Problem-set #4 and solutions.
  5. Problem-set #5, due June 16.

PRE-REQUISITES:

The main pre-requisite for this class is general familiarity with modern theory of cryptography, such as obtained by taking the class Foundation of Cryptography (0368-4162-01). For example, I assume that students are familiar with the notion of semantic-security of encryption schemes (CPA-security), know about standard hardness assumptions (e.g., factoring), and are comfortable with reduction- based proofs of security. I also assume good command of linear algebra (e.g., matrices and their rank, the determinant, Gaussian elimination, 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, scribe notes, and optionally also presentation of a paper. I also plan to give out a few homework sets, but it is not clear if they will be graded.

Scribe notes: each student must scribe at least one lecture, or more if the need arises. The scribe notes should be a cleaned-up summary of the lecture (possibly with some additional details that were omitted in class).

Paper Presentation: I am considering having 3-4 of the lectures given by students, on recent papers related to the general topic of the class. Students who want to present a paper in class should contact me.

SYLLABUS:

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

  1. Prelude: The somewhat-homomorphic encryption scheme "over the integers" from (van Dijk et al. EUROCRYPT 2010), and a reduction to the approximate-GCD problem.

  2. Introduction to lattices and lattice reduction. Lattices, bases, duality, Hermite-normal-form. The problems (Gap-)SVP, SIVP, BDD. Known approximation algorithms for SVP/SIVP/BDD. (This may or may not include describing the LLL algorithm itself.)

    Using SVP approximation to solve simultaneous Diophantine-approximation (SDA), and using SDA to solve approximate-GCD. Assessing the security of the van Dijk et al. scheme.

  3. Lattice-based crypto, part 1. The Short-Integer-Solution problem (SIS), using it to get collision-resistant hashing, Ajtai's reduction of SIVP-approximation to SIS. Maybe Ajtai/Peikert-Alwen trapdoor construction.

  4. Lattice-based crypto, part 2: The Learning-With-Errors problem (LWE), Regev's LWE-based encryption scheme. Peikert's reduction of Gap-SVP to LWE (STOC 2009). Maybe GPV signatures and the dual Regev cryptosystem (Gentry-Peikert-Vaikuntanathan STOC 2008).

  5. LWE-based encryption that supports quadratic formulas over encrypted data (Gentry-Halevi-Vaikuntanathan, EUROCRYPT 2010). Maybe extending it to higher degrees using "d-operand multiplication" (Aguilar-Gaborit-Herranz CRYPTO 2010).

  6. Ideal lattices: Micciancio's reduction of Ideal-SIVP to Ideal-SIS (FOCS 2002), maybe hashing from ideal-SIS (Peikert-Rosen TCC 2006, Lyubashevsky-Micciancio ICALP 2006), maybe Ideal-LWE (Lyubashevsky-Peikert-Regev EUROCRYPT 2010). Maybe an attack on Ideal-SIVP (Gentry-Szydlo EUROCRYPT 2002).

  7. Somewhat-homomorphic encryption from Ideal lattices (Gentry STOC 2009). Variants and implementations (Smart-Vercauteren PKC 2010, Gentry-Halevi 2010).

  8. Worst-case to average-case reduction for Gentry's somewhat homomorphic cryptosystem (Gentry CRYPTO 2010).

  9. From somewhat- to fully-homomorphic encryption (Gentry STOC 2009).

  10. Other methods for computing on encrypted data: Yao circuits, branching programs (Ishai-Pasking TCC 2007). Re-randomizable Yao circuits (Gentry-Halevi-Vaikuntanathan CRYPTO 2010)