CSE206A: Lattices Algorithms and Applications (Spring 2014)
Schedule: Tue,Thu 11:00am-12:20pm in EBU3B (CSE) 4217 Section ID: 809063 Instructor:Daniele Micciancio Office hour: by appointment
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:
Algorithms: approximation algorithms for the efficient solution of lattice approximation problems, exponential time algorithms for the exact solution of NP-hard lattice problems.
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.
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 very efficient cryptographic functions.
Other Applications: If time permits, applications to lattices in coding theory (error correction), combinatorial optimization (integer programming), and more.
Prerequisites: The main prerequisites for the course are general mathematical maturity, knowledge of basic mathematics (mostly linear algebra, probability theory, and a little bit of calculus) and introductory level algorithms and complexity theory (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 will learn a little bit about all this through the course.
Lectures Notes
Revised lecture notes and pointers to research papers and other reading material will be posted here as we cover the material in class. As a reference, see pointers to previous lecture notes and other courses in the external links section below.
Introduction: 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.
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.
Basis reduction and the LLL algorithm, with applications to the approximate solution of SVP and SIVP.
Lattice Cryptography: Random lattices, their properties, and construction of basic cryptographic primitives, like one-way functions and public key encryption.
Coursework
Coursework for students enrolled in the course will include a small number of individual homework assignments (say, 3), and a group project to be executed in groups of 2 or 3 students. Projects should be discussed with the instructor during the 6th week of classes.