Understanding LLL

• Maybe the best reference to understand how LLL works is the original paper itself : it describes in great details the principle of the algorithm.
  A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovàsz, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982)
• Antoine Joux's thesis is a good introduction to the lattice theory. It also provides an intuitive presentation of LLL which can be helpfull.
  A. Joux, La Reduction de Reseaux en Cryptographie, Thesis available at the ENS server
• Henri Cohen gives a very formal and rigorous presentation of LLL and its main variants
  H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1995 (Second edition)

LLL as a Tool

• It is not necessary to understand how LLL performs a lattice basis reduction in order to actually use it. LLL can be simply seen as a black box which reduces bases. This is the approach adopted by Antoine Joux and Jacques Stern; their paper gives a really good introduction to the use and capabilities of LLL as a toolbox.
  A. Joux and J. Stern, Lattice Reduction: a Toolbox for the Cryptanalyst, available at the ENS server
• An impressively simple and efficient application of LLL to break a cryptosystem is given by
  J. Stern and P. Toffin, Cryptanalysis of a Public-key Cryptosystem Based on Approximations by Rationnal Numbers, Advances in Cryptology - Eurocrypt'90, Springer-Verlag
• A well-explained use of LLL to solve modular equations is
  J. Hastad, Solving Simultaneous Modular Equations of Low Degree, Siam J. Computing, 1988
• The Hastad attack was extended to the multivariate case by Takagi and Naito
  T. Takagi and S. Naito, The multi-variable modular polynomial and its applications to cryptography , 7th International Symposium on Algorithm and Computation, ISAAC'96, Lecture Notes in Computer Science, vol. 1178, Springer-Verlag, 1996, pp.386-396.
• In fact, Takagi-Naito's result is not optimal. We were able to significantly simplify the proof and improve the result. See
  M. Joye, F. Koeune and J.-J. Quisquater, Takagi/Naito's algorithm revisited, Tech. Report CG-1997/3, UCL Crypto Group, Louvain-la-Neuve, March 1997

Other interesting papers are

• B. Vallée, Une approche géometrique de la réduction des réseaux en petite dimension, PhD Thesis
• B. Vallée, M.Girault and P. Toffin, How to Break Okamoto's Cryptosystems by Reducing Lattices Bases, Advances in Cryptology - Eurocrypt'87
• B. Vallée, M.Girault, P. Toffin, How to guess L-th roots modulo n by reducing lattice bases, Proc. of Conference of ISSAC-88 and AAECC-6, Jul.88
• Don Coppersmith, Finding a Small Root of a Univariate Modular Equation, Advances in Cryptology - Eurocrypt'96, Springer-Verlag
• Don Coppersmith, Finding a Small Root of a Bivariate Modular Equation; Factoring with High Bits Known, Advances in Cryptology - Eurocrypt'96, Springer-Verlag

Lattice-based Cryptosystems

• Lattice reduction is not only used on a "destructive" way. Recently, some public-key cryptosystems have been proposed, whose security is based on the assumption that finding a "very" short vector of a given lattice is difficult . One of those cryptosystem is NTRU
  J. Hoffstein, J. Pipher, J.H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem
  More info on NTRU is available at the NTRU Cryptosystems Home Page
• A first version of NTRU was broken (using LLL !) by Coppersmith and Shamir
  D. Coppersmith and A. Shamir, Lattice Attack on NTRU, Advances in Cryptology - Eurocrypt'97, Springer-Verlag
• Another PKCS based on the lattice reduction problem is the following. This paper is very detailed, very intuitive and, in my opinion, readable even by a non-specialist.
  O. Goldreich, S. Goldwasser and S. Halevi, Public-Key Cryptosystems from Lattice Reduction Problems, May 1997.
  The site also contains some other interesting paper (construction of a lattice-based hash function, ...).
• Last but not least, Ajtai and Dwork recently proposed a PKCS for which they can prove that breaking the cryptosystem is equivalent to solving the hardest instance of some short-vector problem.
  M. Ajtai and C. Dwork, A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence ECCC Report TR96-065, Dec 13, 1996 (revision in May, 1997).

Refinements and Variants of LLL

• C.P. Schnorr, A Hierarchy of Polynomial Time Basis Reduction Algorithms, Journal of Theoretical Computer Science, 1987
• C.P. Schnorr, A More Efficient Algorithm for Lattice Basis Reduction, Journal of Algorithms, 1988
• J.C. Lagarias, A.K. Lenstra and C.P. Schnorr, Korkine-Zolotarev Bases and Successive Minima of a Lattice and its Reciprocal Lattice, Combinatorica, 1990
• C. P. Schnorr and M. Euchner, Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, Proceedings of Fundamentals of Computation Theory 91, Springer-Verlag

Interesting links

• Many Links Related to Number Theory
• Implementations of extended LLL
• Lattice Basis Reduction, t-Designs