Columbia University, Computer Science
Spring 2013, COMS E6261
Homomorphic Encryption and Lattices
This is a three-credit advanced graduate level course. The course
is one of the electives for MS students in the Foundations of Computer
Science Track and the Computer Security Track, and for undergraduates
in the Foundations of Computer Science Track. It also serves as a
general elective for the PhD program in computer science.
The class will focus around a different topic, possibly with a
different format, every time it is taught. The class can be repeated
for credit. Auditing the class is allowed but requires instructor
approval. CVN students should contact the instructor before registering.
Instructor: Shai Halevi,
co-instructor: Tal Malkin
TA: Fernando Krell
- Tal Malkin: Thursdays 2:00 - 4:00 (CSB 514, e-mail: tal AT cs ...)
- Shai Halevi: By appointment (e-mail: shaih AT alum DOT mit DOT edu)
- Fernando Krell: By appointment (e-mail: fernando AT cs ...)
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).
- Thursday Apr 11th. Prof. Malkin office hours changed. 1:00-3:00pm
- Extra class Friday Apr 12th. Mudd Building Room 1024, 9:30am.
- Extra office hour (Fernando). Monday Apr 15th CSB 516, 11am.
||Introduction to Lattices.
Lecture notes from Oded Regev's course
||The Hermite normal form.
Material containded 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.
||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.
||• Discrete Gaussians, Smoothing Parameter, Lecture notes from Oded Regev's course|
• Leftover Hash Lemma, Lecture notes from Ronitt Rubinfeld's course in MIT.
|The Learning with Errors problem (LWE), random-self reducability, search-to-decision reduction, the Regev'05 cryptosystem.
|The Gentry-Peikert-Vaikuntanathan SIS-based signatures [GPV08]
|The lattice trapdoor construction of Micciciancio-Peikert [MP12]
||Yao Garbled Circuits. See the Lindel-Pinkas exposition and proof [LP09].
|The Gorbunov-Vaikuntanathan-Wee LWE-based Attribute-Based Encryption Scheme [GVW13]
|• Continue with [GVW13] Attribute-Based Ecnryption|
• LWE-based homomorphic encryption
|Continue LWE-based homomorphic encryption
|Ideal Lattices, The NTRU cryptosystem,
||• Continue with the NTRU cryptosystem,
• Multilinear maps from ideal lattices
- Problem-set #1 due Feb 5.
- Problem-set #2 due Feb 19.
- Problem-set #3 due Mar 12.
- Problem-set #4 due Mar 26.
- Problem-set #5 due Apr 23.
- Problem-set #6 due May 7.
The main pre-requisite is general familiarity with modern theory of
cryptography, such as obtained by taking the class 4261 introduction
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.
- Weeks 1-2.
Introduction and course plan. Lattice basics: definitions, bases,
duality, etc. Hard problems in lattices (Gap-)SVP, SIVP, BDD, etc.
Basic lattice algorithms: Hermite-normal-form, the LLL algorithm
and approximation of SVP/SIVP/BDD.
- Weeks 3-4.
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. The Micciancio-Peikert trapdoor
construction (EUROCRYPT 2012).
- Weeks 5-7.
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).
- Week 8.
A short detour: Secure computation and Yao garbled circuits.
- Week 9.
More LWE-based crypto: Attribute-based encryption, functional
encryption, reusable garbled circuits (the new works of Gorbunov et al. and
Goldwasser et al.)
- Week 10.
LWE-based homomorphic encryption: Based on
(Gentry STOC 2009), (Brakerski-Vaikuntanathan FOCS 2011),
(Brakerski-Gentry-Vaikuntanathan ITCS 2012),
(Brakerski CRYPTO 2012).
- Weeks 11-12.
Ideal lattices: Introduction, definitions, properties.
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 some
- Week 13.
Homomorphic encryption from ideal lattices: efficiency with packed
ciphertexts (Smart-Vercauteren 2011), (Gentry-Halevi-Smart
EUROCRYPT/CRYPTO 2012), NTRU-based (multi-key) homomorphic
encryption (López-Alt, Tromer, Vaikuntanathan STOC 2012).
- Week 14.
Multi-linear maps from ideal lattices (Garg-Gentry-Halevi 2012),
and applications for attribute-based encryption and similar
(Garg-Gentry-Halevi 2012, Sahai-Waters 2012).