CSE207C: Lattices in Cryptography and Cryptanalysis (Winter 2002)

Istructor: Daniele Micciancio

Schedule: Tue/Thu 5:30-6:50pm in HSS 2321

Announcements

• Homework 2 is ready. See below.
• Homework 1 is ready. See below.
• First day of classes: Tuesday January 8th
• Class on Thursday Jan 10th is cancelled because of Contemporary Methods in Cryptography workshop at (UCLA) IPAM. Check out the lattices and cryptography session on Thusday afternoon.

Course Description

Lattices are powerful mathematical objects that have been used to efficiently solve many important problems in computer science, including integer programming with constant number of variables, polynomial factorization over the rationals, Diophantine approximation, etc.

Lattices have also been extensively used in cryptology. Quite peculiarly, lattices have been used both in cryptanalysis (using lattice approximation algorithms to break cryptosystems) and in cryptography (using computationally hard lattice problems to design robust cryptographic functions).

This course will give a general introduction to the theory of (point) lattices, and cover the main applications of lattices to both cryptography and cryptanalysis. The course will be primarily focused on the algorithmic aspects of the theory: which lattice problem can be solved in polynomial time, and which problems seems to be intractable. In presenting the solution to various cryptographic problems, we will cover the essentials of lattice approximations algorithms (eg. LLL basis reduction), present the current state of knowledge on the computational complexity of lattice problems (including NP-hardness results and Ajtai's worst-case / average-case connection), and study practical cryptosystems based on the hardness of lattice problem (e.g., the NTRU cryptosystem).

If you want to get a flavour of some of the topics covered in this course, read the notes for lecture one below. The examples in these notes are all from cryptanalysis (how to break cryptosystems using lattices) which is the topic covered in the first half of the course. In the second half of the course, we'll get more into complexity theory and the design of provably secure cryptographic functions based on lattices.

Prerequisites

Knowledge of computer algorithms, probability theory, linear algebra and basic complexity theory (P, NP, coNP, NP-hardness) is required. Some basic knowledge of cryptography (RSA function, probabilistic encryption, etc.) is recommended, but not strictly necessary. If you are interested in this course, but you are not sure if you have the necessary prerequisites, consult the instructor.

Papers

Below are references to papers related to material covered in class, and covered in the lecture notes below. Some of them pertain extentions or refinements of results presented in class, and are given as hints for further study.

• Schroeppel, Shamir. "A ts^2 = O(2^n) time/space tradeoff for certain NP-complete problems". SIAM Journal on Computing, 10(3):456-464, 1981.
• Lagarias, Odlyzko. "Solving low density subsetsum problems". Journal of the ACM, 32(1):229-246. 1985. (This paper contains the original lattice based attack to subsetsum.)
• Frieze. "On the Lagarias-Odlyzko algorithm for the subset sum problem. SIAM Journal on computing, 15(2):536-539. 1986. (This paper contains a simpler analysis that the LLL algorithm can be used to solve subsetsum with density O(1/n))
• Coster, Joux, LaMacchia, Odlyzko, Schnorr, Stern. "Improved low-density subset-sum algorithms". Computational Complexity 2(2):111-128, 1992. (This paper shows that an exact SVP oracle can be used to solve most subsetsum problems with densitiy up to 0.9...)
• Micciancio. "The hardness of the closest vector problem with preprocessing". IEEE Transactions on Information Theory, 47 (3): 1212-1215, 2001. (The simple proof of NP hardness of the closest vector problem can be found here. This result was originally proved by van Emde Boas in 1981.)

Homeworks

Yes! The first homework is finally available. Have fun! For the programming part you can you the implementation of LLL from Victor Shoup's Number Theory Library (NTL). The library is a pretty easy install. If you have any problem getting the library to work, let me know.

• Homework 2 (ps) (pdf)
• Homework 1 (ps) (pdf). If you have problem dowloading the files, try to reaload the class webpage clicking on this link.

Links

This is a very preliminary list of related links. I will keep adding links with time. If you know of any relevant link that is not already on the list, please send me email.

• Bibilography on Lattices and Cryptography
• Daniele Micciancio and Shafi Goldwasser's Complexity of Lattice problems: a cryptographic perspective. A book on the computational complexity of lattices, and their use in the construction of provably secure cryptographic functions. The material contained in this book is somehow the complement of what is covered by the lecture notes.
• Cynthia Dwork's Lecture Notes on Lattices and their Applications to Cryptography.
• David Molnar's page on Parallel Lattice Basis Reduction.
• NTRU webpage. A very efficient commercial cryptosystem based on lattices.
• Victor Shoup's Number Theory Library (NTL). A C++ library for lattice basis reduction that has been widely used in cryptanalysis.

Lecture Notes (Fall 1999)

Below are the lecture notes of a prelinimary version of this course, taught as CSE291 in Fall 1999. Most of the topics in the syllabus are covered by the lecture notes.

• Lecture 1 (Oct 21): Introduction, Some problems in cryptanalysis, Lattices and linear algebra. (ps)
• Lecture 2 (Oct 26): Orthogonal bases, Hermite normal form and determinant. (ps)
• Lecture 3 (Oct 28): Polynomial time HNF algorithm. (ps)
• Lecture 4 (Nov 2): Shortest vector problem (SVP), Minkowski's convex body theorem. (ps)
• Lecture 5 (Nov 4): Applications of Minkowski's theorem. Successive minima. Reduced basis for 2-dimensional lattices. (ps)
• Lecture 6 (Nov 9): Solving SVP in 2-dimensional lattices: the generalized Gauss algorithm. (ps)
• Lecture 7 (Nov 11): Approximating SVP in n-dimensional lattices: the LLL algorithm. (ps)
• Lecture 8 (Nov 16): Finding small solutions to univariate polynomial equations. (ps)
• Lecture 9 (Nov 18): Finding small solutions to multivariate linear equations. (ps)
• Lecture 10 (Nov 23): The Closest Vector Problem (CVP): algorithms and complexity. (ps)
• Problem Set (Nov 23, Due Dec 7). (ps)
• Lecture 11 (Nov 30): Private key cryptosystems based on subset-sum (ps)
• Lecture 12 (Dec 2): The dual lattice. (ps)
• Lecture 13 (Dec 7): Embedding trapdoors in the subset sum function (ps)
• Lecture 14 (Dec 9): Conclusion
• Bibliography (ps)

Daniele Micciancio
Last Midified: December 10th, 2001