CSE206A: Lattices Algorithms and Applications (Fall 2019)

Schedule: Tue,Thu 9:30am-10:50am in CSE 4258
Instructor: Daniele Micciancio (CSE4214)
TA: Jessica Sorrell (CSE4242)

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, 2 or 3 individual homework assignments, and a team project to be executed in groups of 2 or 3 students. Projects should be discussed with the instructor by the end of the 5th week of classes, and will be due during the 10th week. Each group should submit a written report, and possibly deliver a short presentation.

Homework Assignments

The course will be based on a combination of lecture notes, research papers and other online material as posted below. Links below the line are reading material from the last offering of the course. The list will be updated as the course moves forward.

If you are scribing lecture notes, you can use this template.tex

• Point Lattices: Lattices, Bases, Gram-Schmidt orthogonalization, and Lattice determinant.
• Duality: The dual lattice and the Closest Vector Problem (CVP)
• Minkowski’s Theorem: The Shortest Vector Problem (SVP), Shortest Independent Vectors Problem (SIVP), and Minkowski’s Theorems.
• Random Lattices and Lattice Cryptography: Random lattices, the SIS and LWE problems, and construction of basic cryptographic primitives, like one-way functions and collision resistant hashing.

• FHE: Fully Homomorphic Encryption
• Basis reduction and the LLL algorithm, with applications to the approximate solution of SVP and SIVP.
• Fourier analsysis: the discrete gaussian distribution, possion summation formula, tail bounds, the smoothing parameter, etc.

A collection of Links to papers and other resources on lattice cryptography and algorithms (not very actively) maintained by Daniele Micciancio, mostly for his own personal use.

Implementations and Libraries:

• 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.
• PALISADE. A general purpose C++ library for lattice cryptography.
• Lambda o lambda (Lol). A high level Haskell library for lattice based cryptography. See also paper.
• NFLlib. An NTT-based Fast Lattice Library for computations in power-of-two cyclotomic rings.
• HElib. A library for Fully Homomorphic Encryption.
• RingLWE C++ library: A C++implementation of the RingLWE Toolkit of Lyubashevsky, Peikert and Regev, as described in the MS Thesis.