Columbia University, Computer Science
Spring 2013, COMS E6261
ADVANCED CRYPTOGRAPHY:
Homomorphic Encryption and Lattices
GENERAL INFORMATION:
This is a threecredit 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.
Tuesdays 2:104:00pm,
Instructor: Shai Halevi,
coinstructor: Tal Malkin
TA: Fernando Krell
Office Hours
 Tal Malkin: Thursdays 2:00  4:00 (CSB 514, email: tal AT cs ...)
 Shai Halevi: By appointment (email: shaih AT alum DOT mit DOT edu)
 Fernando Krell: By appointment (email: fernando AT cs ...)
Announcements
 Thursday Apr 11th. Prof. Malkin office hours changed. 1:003:00pm
(CSB 514).
 Extra class Friday Apr 12th. Mudd Building Room 1024, 9:30am.
 Extra office hour (Fernando). Monday Apr 15th CSB 516, 11am.
This class will cover results in cryptography,
mostly from the last few years, related to homomorphic encryption
schemes and other latticebased 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

January 29 
The Hermite normal form.
Material containded 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 worstcase/averagecase connection.
The Small Integer Solution problem (SIS), Relation to worstcase
SVP, SIVP, SISbased collisionresistant 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), randomself reducability, searchtodecision reduction, the Regev'05 cryptosystem.

March 12 Class notes 
The GentryPeikertVaikuntanathan SISbased signatures [GPV08]

March 26 Class notes 
The lattice trapdoor construction of MicciciancioPeikert [MP12]

April 2

Yao Garbled Circuits. See the LindelPinkas exposition and proof [LP09].

April 9 Class notes 
The GorbunovVaikuntanathanWee LWEbased AttributeBased Encryption Scheme [GVW13]

April 12
Class notes 
• Continue with [GVW13] AttributeBased Ecnryption
• LWEbased homomorphic encryption

April 16
Class notes 
Continue LWEbased 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
 Problemset #1 due Feb 5.
 Problemset #2 due Feb 19.
 Problemset #3 due Mar 12.
 Problemset #4 due Mar 26.
 Problemset #5 due Apr 23.
 Problemset #6 due May 7.
Handouts
PREREQUISITES:
The main prerequisite 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
semanticsecurity of encryption schemes
(CPAsecurity), know about standard hardness assumptions (e.g.,
factoring), and be comfortable with reductionbased proofs of security.
We also assume good command of linear algebra (e.g., matrices and
their rank, the determinant, Gaussian elimination, GramSchmidt
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 cleanedup 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 problemsets, 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 34 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.
 Weeks 12.
Introduction and course plan. Lattice basics: definitions, bases,
duality, etc. Hard problems in lattices (Gap)SVP, SIVP, BDD, etc.
Basic lattice algorithms: Hermitenormalform, the LLL algorithm
and approximation of SVP/SIVP/BDD.
 Weeks 34.
Latticebased crypto, part 1: The ShortIntegerSolution problem
(SIS), using it to get collisionresistant hashing, Ajtai's reduction
of SIVPapproximation to SIS. The MicciancioPeikert trapdoor
construction (EUROCRYPT 2012).
 Weeks 57.
Latticebased crypto, part 2: The LearningWithErrors problem
(LWE), Regev's LWEbased encryption scheme. Peikert's reduction of
GapSVP to LWE (STOC 2009). Maybe GPV signatures and the dual Regev
cryptosystem (GentryPeikertVaikuntanathan STOC 2008).
 Week 8.
A short detour: Secure computation and Yao garbled circuits.
 Week 9.
More LWEbased crypto: Attributebased encryption, functional
encryption, reusable garbled circuits (the new works of Gorbunov et al. and
Goldwasser et al.)
 Week 10.
LWEbased homomorphic encryption: Based on
(Gentry STOC 2009), (BrakerskiVaikuntanathan FOCS 2011),
(BrakerskiGentryVaikuntanathan ITCS 2012),
(Brakerski CRYPTO 2012).
 Weeks 1112.
Ideal lattices: Introduction, definitions, properties.
Micciancio's reduction of IdealSIVP to IdealSIS
(FOCS 2002), maybe hashing from idealSIS (PeikertRosen TCC 2006,
LyubashevskyMicciancio ICALP 2006), maybe IdealLWE
(LyubashevskyPeikertRegev EUROCRYPT 2010). Maybe some
ideallattice cryptanalysis
 Week 13.
Homomorphic encryption from ideal lattices: efficiency with packed
ciphertexts (SmartVercauteren 2011), (GentryHaleviSmart
EUROCRYPT/CRYPTO 2012), NTRUbased (multikey) homomorphic
encryption (LópezAlt, Tromer, Vaikuntanathan STOC 2012).
 Week 14.
Multilinear maps from ideal lattices (GargGentryHalevi 2012),
and applications for attributebased encryption and similar
(GargGentryHalevi 2012, SahaiWaters 2012).