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. |
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.
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.
Below is a very tentative course plan. There are likely to be significant changes to this plan as the semester goes on.