CSE206A: Lattices Algorithms and Applications (Winter 2016)

Schedule: Tue,Thu 12:30pm-1:50pm in WLH 2112
Section ID: 861032
Instructor: Daniele Micciancio
Office hour: Tuesday 2-3pm

Course description

Point lattices are powerful mathematical objects that can be used to efficiently solve many important problems in computer science, most notably in the areas of cryptography and combinatorial optimization. This course gives a general introduction to the theory of point lattices, their algorithms, computational complexity, mathematical techniques, and applications to cryptography. Specific topics touched by the course include:

• Lattice Based Cryptography: the design of cryptographic functions that are as hard to break as solving hard lattice problems. From basic public key encryption and digital signature schemes, to advanced applications like identity based encryption and fully homomorphic encryption, i.e., encryption schemes that allow to compute on encrypted data without decrypting.
• Algorithms: approximation algorithms for the efficient solution of lattice approximation problems, exponential time algorithms for the exact solution of NP-hard lattice problems.
• Computational Complexity: connection between average-case and worst-case complexity, reductions, NP-hardness, interactive proof systems.
• Advanced mathematical techniques: Fourier/Harmonic analysis methods for the study of lattice problems. Lattice problems from Algebraic Number Theory and their application to the design of very efficient cryptographic functions.
• Other Applications: If time permits, applications to lattices in coding theory (error correction), combinatorial optimization (integer programming), and more.

Prerequisites and Coursework

The main prerequisites for the course are general mathematical maturity, knowledge of basic mathematics (good linear algebra and probability theory, basic abstract algebra, and a little bit of calculus) and introductory level algorithms and complexity theory (mathematical models of computation, analysis of algorithms, polynomial time solvability, NP-hardness, etc.) Some prior knowledge of cryptography is useful, but not strictly required. No prior knowledge of advanced complexity theory, Fourier analysis, or algebraic number theory is assumed, but you should be prepared to learn a bit about all this through the course.

Coursework for students enrolled in the course will include a substantial amount of reading, a number of individual homework assignments (say 4), a team project to be executed in groups of 2 or 3 students, and perhaps scribing some lecture notes. Projects should be discussed with the instructor during the 6th week of classes, and each group should submit a written report and deliver a short presentation.

Homework Assignments

• Homework 1, due Thursday January 4, 2016. Submission instructions will be posted soon.

• Homework 2, due Thursday January 28, 2016 A revised homework containing guidelines on how to run lattice reductions algorithms has been posted.

• Homework 3, due Friday February 12, 2016

• Project guidelines

Reading Assignments

The course will be based on a combination of lecture notes, research papers and other online material as posted below. Links will be added to the following list as the course moves forward.

• Point Lattices: Lattices, Bases, Gram-Schmidt orthogonalization, and Lattice determinant.
• Minkowski's Theorem: The Shortest Vector Problem (SVP), Shortest Independent Vectors Problem (SIVP), and Minkowski's Theorems.
• Cryptanalysis: Pseudorandom generators, Truncated Linear Congruential Generator, Subset-sum generator, Closest Vector Problem and Bounded Distance Decoding, Lattice attacks on LCG and SubsetSum generators.
• Basis reduction and the LLL algorithm, with applications to the approximate solution of SVP and SIVP.
• Pseudorandomness of subset-sum function: See original paper Efficient Cryptographic Schemes Provably as Secure as Subset Sum (R. Impagliazzo & M. Naor, J. Cryptology 1996)
• Duality: The dual lattice and the Closest Vector Problem (CVP)
• Basic Algorithms for Gram-Schmidt orthogonalization, Hermite Normal Form computation, Nearest plane approximation algorithm, and Enumeration algorithms for exact CVP computation.
• Lattice Cryptography: Random lattices, their properties, and construction of basic cryptographic primitives, like one-way functions and public key encryption.
• Better Key Sizes (and Attacks) for LWE-Based Encryption (Lindner & Peikert, CT-RSA 2011). The encryption scheme presented in class is almost identical to the one in section 3 of the paper. There are also some preliminary lecture notes covering the part the lecture on relating different variants of LWE.
• Fourier analsysis: the discrete gaussian distribution, possion summation formula, tail bounds, the smoothing parameter, etc.

External Links

Introductory chapters and surveys on lattice cryptography:

• Introductory chapter on lattices from "Complexity of Lattice problems: a cryptographic perspective" (2002). The rest of the book is a bit out of date, but still a good introduction to the subject.
• Survey chapter on Lattice-Based Cryptography from "Post Quantum Cryptography" (2009)
• Survey chapter on Cryptographic functions from worst-case complexity assumptions from "The LLL Algorithm: Survey and Applications" (2009). The book has many other interesting chapters covering more applications of lattices in computer science and mathematics.
• Tutorial on The Geometry of Lattice Cryptography from FOSAD 2011.
• Survey on The Learning With Errors Problem from CCC 2010.
• A Decade of Lattice Cryptography (ePrint 2015). A survey of the most recent uses of lattices in the construction of advanced cryptographic primitives.

Other courses' webpages:

• Previous editions of this course: Winter 2002, Spring 2007, Winter 2010, Winter 2012, Spring 2014,
• Oded Regev's couorse on Lattices in Computer Science at Tel Aviv university.
• Chris Peikert's course on Lattices in Cryptography at U. Michigan.
• Vinod Vaikuntanathan's course on Advanced Topics in Cryptography: Lattices at MIT

Implementations:

• fpLLL: state of the art impementation of lattice reduction and related algorithms using fast floating point arithmetics.
• Number Theory Library (NTL). A C++ library for lattice basis reduction, polynomial arithmetics and other algebraic problems.
• Lambda o lambda (Lol). A high level Haskell library for lattice based cryptography. See also paper.
• RingLWE C++ library: A C++implementation of the RingLWE Toolkit of Lyubashevsky, Peikert and Regev, as described in the MS Thesis.