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) |
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.
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.
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.