CSE206A: Lattices Algorithms and Applications (Winter 2004)

Istructor: Daniele Micciancio

Schedule: MWF 4:00-4:50pm in WLH 2110

Announcements

• Lecture notes from the first part of the course are available.
• Most of the page below is recycled from a previous version of the course and will be updated soon. So, some of the links below might be broken, and will be fixed as the page gets updated.

Course Description

Point 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 gives a general introduction to the theory of lattices, and covers the main applications of lattices to cryptography, cryptanalysis and various other selected areas. The course is 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. Specific topics include lattice approximations algorithms (eg. LLL basis reduction), computational complexity of lattice problems (including NP-hardness results and Ajtai's worst-case / average-case connection), and various applications of lattices both from cryptography and other areas of computer science.

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 will be the source of many applications in this course.

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.

Assignments

Students will receive a grade based on a homework assignment and either a presentation or a project. The homework assignment is due on Monday February 10.

Presentations will based on 2 or 3 closely related papers. Students are expected to submit a short report summarizing the contributions of the papers, and give a 50 minutes presentation to the class. See below for possible topics and paper links.

Projects involve the experimentation with lattice reduction algorithms to solve some cryptanalysis problem. If you are interested in performing a project, talk to Daniele to decide on a possible topic

Here are some ideas for possible presentation topics:

• Chinese Reminder Codes: using lattices to decode error correcting codes based on CRT.
  • Guruswami, Sahai, Sudan, Soft-decision Decoding of Chinese Remainder Codes, FOCS 2000
  • Boneh, Finding Smooth Integers in Short Intervals Using CRT Decoding, JCSS 64:768-784, 2002. (Prelim. STOC 2000)
  • Goldreich, Ron, Sudan, Chinese Remaindering with Errors, IEEE Trans. on IT 46(4):1330-1338, 2000. (Prelim. STOC 1999)
• Faster randomized algorithms for SVP and CVP. These are the fastest known algorithms to find (almost) exact solutions to lattice problems
  • Schnorr, Lattice Reduction by Random Sampling and Birthday Methods, STACS 2003
  • Ajtai, Kumar, Sivakumar, A sieve algorithm for the shortest lattice vector problem, STOC 2001
  • Ajtai, Kumar, Sivakumar, Sampling Short Lattice Vectors and the Closest Lattice Vector Problem, CCC 2002
• Improving the LLL approximation factor
  • Ajtai, The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice, STOC 2003
  • Schnorr, A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms, TCS 53(2-3):201-224, 1987
  • Schnorr, Block reduced lattice bases and successive minima, Combinatorics, Probability and Computing, 3:507-522, 1994
• Speeding up LLL reduction:
  • Koy, Schnorr, Segment and Strong Segment LLL-Reduction of Lattice Bases, Manuscript, 2002(Prelim. CaLC 2001)
  • Storjohann, Faster Algorithms for Integer Lattice Basis Reduction. TR 249, Departement Informatik, ETH Zurich, 1996.
• HNF algorithms
  • Micciancio, Warinschi, A linear space algorithm for computing the Hermite normal form , ISSAC 2001
  • Storjohan, Computing Hermite and Smith normal forms of triangular integer matrices, Linear Algebra and its Applications, 282(1-3):25-45, 1998
  • Storjohan, Labahn, Asymptotically fast computation of Hermite normal forms of integer matrices, ISSAC 1996.
• Cryptanalysis of DSS under various attack scenarios:
  • Bellare, Goldwasser, Micciancio, "Pseudo-random" generators within cryptographic applications: the DSS case, Crypto 1997
  • Nguyen, Shparlinski, The insecurity of the Digital Signature Algorithms with partially known nonces, J. Cryptology 15(3):151-176, 2001

You can find many other links to papers related to lattice algorithms and applications at the following sites.

• Damien Stehle' links on Algorithmics and Lattices
• Helger Lipmaa's links on Lattice Cryptography and Reduction

Projects tipically involve an experimental component, where you use lattice reduction algorithms to attack a cryptanalitic problem. Lattices are routinely used to attack various kind of cryptographic functions. To get an idea of what can be done using lattices, read some of the papers below. If you want to work on a project, let me know.

Lattice attacks to various kind of cryptographic functions are routinely discovered. The following are two survey papers describing many applications of lattices:

• The Two Faces of Lattices in Cryptology, CaLC 2001
• Lattice Reduction: a Toolbox for the Cryptanalyst, J.Crypto 11(3), 1998

Below is a list of papers describing lattice attacks that appeared in conferences like Crypto, Eurocrypt, Asiacrypt, PKC, SAC, etc. The papers are listed in reverse chronological order, so some of the papers at the bottom of the list contain among the simplest lattice based attacks..

• The Insecurity of Esign in Practical Implementation
• Analysis of the Insecurity of ECMQV with Partially Known Nonces
• Attacking Unbalanced RSA-CRT Using SPA
• Key Recovery Attacks on NTRU without Ciphertext Validation Routine
• New Partial Key Exposure Attacks on RSA
• The Impact of Decryption Failures on the Security of NTRU Encryption
• Hypercubic Lattice Reduction and Analysis of GGH and NTRU Signatures
• On the Security of RDSA
• Enhancing Simple Power-Analysis Attacks on Elliptic Curve Cryptosystems
• Cryptanalysis of Unbalanced RSA with Small CRT-Exponent
• Cryptanalysis of the Revised NTRU Signature Scheme
• Lattice Attacks on RSA-Encrypted IP and TCP
• On the Insecurity of a Server-Aided RSA Protocol
• Cryptanalysis of the NTRU Signature Scheme (NSS) from Eurocrypt 2001
• The Two Faces of Lattices in Cryptology
• Low Secret Exponent RSA Revisited
• Approximate Integer Common Divisors
• The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces
• Information Leakage Attacks against Smart Card Implementations of the Elliptic Curve Digital Signature Algorith
• Key Recovery and Message Attacks on NTRU-Composite
• A Chosen-Ciphertext Attack against NTRU
• Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto'97
• Factoring N = p^r q for Large r
• Cryptanalysis of RSA with Private Key d Less than N^0.292
• The Effectiveness of Lattice Attacks Against Low-Exponent RSA
• Cryptanalysis of a Fast Public Key Cryptosystem Presented at SAC '97
• The Beguin-Quisquater Server-Aided RSA Protocol from Crypto '95 is Not Secure
• An Attack on RSA Given a Small Fraction of the Private Key Bits
• Cryptanalysis of the Ajtai-Dwork Cryptosystem
• Cryptanalysis of the Chor-Rivest Cryptosystem
• Lattices and Cryptography: An Overview
• Speeding up Discrete Log and Factoring Based Schemes via Precomputations
• Merkle-Hellman Revisited: A Cryptanalysis of the Qu-Vanstone Cryptosystem Based on Group Factorizations
• A Multiplicative Attack Using LLL Algorithm on RSA Signatures with Redundancy
• Low-Exponent RSA with Related Messages
• The Cryptanalysis of a New Public-Key Cryptosystem Based on Modular Knapsacks
• Cryptanalysis of a Public-Key Cryptosystem Based on Approximations by Rational Numbers
• Cryptanalysis of Short RSA Secret Exponents
• How to Break Okamoto's Cryptosystem by Reducing Lattice Bases

Here are a few more papers about lattice algorithms of applications:

• A Lattice Based General Blind Watermark Scheme
• The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm
• An Advantage of Low-Exponent RSA with Modulus Primes Sharing Least Significant Bits
• A Faster Lattice Reduction Method Using Quantum Search
• Computing the M = U U t Integer Matrix Decomposition

Some papers related to the projects discussed in class:

• Statistical zero-knowledge proofs with efficient provers: lattice problems and more
• The inapproximability of lattice and coding problems with preprocessing
• Generalized compact knapsaks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions
• Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor

Additional links to random papers related to lattices:

• Heuristics on lattice basis reduction in practice, Backes, Wetzel, JEA 7(1), 2002

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: January 16th, 2004