nach oben

2010 | Buch

Kapitel lesen Erstes Kapitel lesen

The LLL Algorithm

Survey and Applications

herausgegeben von: Phong Q. Nguyen, Brigitte Vallée

Verlag: Springer Berlin Heidelberg

Buchreihe : Information Security and Cryptography

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Inhaltsverzeichnis

Frontmatter

Chapter 1. The History of the LLL-Algorithm

Abstract

The 25th birthday of the LLL-algorithm was celebrated in Caen from 29th June to 1st July 2007. The three day conference kicked off with a historical session of four talks about the origins of the algorithm. The speakers were the three L’s and close bystander Peter van Emde Boas. These were the titles of their talks.

A tale of two papers – Peter van Emde Boas.
The early history of LLL – Hendrik Lenstra.
The ellipsoid method and basis reduction – László Lovász.
Polynomial factorization and lattices in the very early 1980s – Arjen Lenstra.

This chapter is based on those talks, conversations with these four historic characters, the notes that Peter van Emde Boas and Arjen Lenstra wrote for the preproceedings, and many artifacts from the phenomenal archive of Van Emde Boas.

Ionica Smeets, Arjen Lenstra, Hendrik Lenstra, László Lovász, Peter van Emde Boas

Chapter 2. Hermite’s Constant and Lattice Algorithms

Abstract

We introduce lattices and survey the main provable algorithms for solving the shortest vector problem (SVP), either exactly or approximately. In doing so, we emphasize a surprising connection between lattice algorithms and the historical problem of bounding a well-known constant introduced by Hermite in 1850, which is related to sphere packings. For instance, we present Lenstra–Lenstra–Lovász (LLL) as an (efficient) algorithmic version of Hermite’s inequality on Hermite’s constant. Similarly, we present blockwise generalizations of LLL as (more or less tight) algorithmic versions of Mordell’s inequality.

Phong Q. Nguyen

Chapter 3. Probabilistic Analyses of Lattice Reduction Algorithms

Abstract

The general behavior of lattice reduction algorithms is far from being well understood. Indeed, many experimental observations, regarding the execution of the algorithms and the geometry of their outputs, pose challenging questions, which remain unanswered and lead to natural conjectures yet to be settled. This survey describes complementary approaches which can be adopted for analyzing these algorithms, namely, dedicated modeling, probabilistic methods, and a dynamical systems approach. We explain how a mixed methodology has already proved fruitful for small dimensions p, corresponding to the variety of Euclidean algorithms (p = 1) and to the Gauss algorithm (p = 2). Such small dimensions constitute an important step in the analysis of lattice reduction in any (high) dimension, since the celebrated LLL algorithm, due to Lenstra, Lenstra, and Lovász, precisely involves a sequence of Gauss reduction steps on sublattices of a large lattice.

Brigitte Vallée, Antonio Vera

Chapter 4. Progress on LLL and Lattice Reduction

Abstract

We review variants and extensions of the LLL-algorithm of Lenstra, Lenstra Lovász, extensions to quadratic indefinite forms and to faster and stronger reduction algorithms. The LLL-algorithm with Householder orthogonalisation in floating-point arithmetic is very efficient and highly accurate. We review approximations of the shortest lattice vector by feasible lattice reduction, in particular by block reduction, primal–dual reduction and random sampling reduction. Segment reduction performs LLL-reduction in high dimension, mostly working with a few local coordinates.

Claus Peter Schnorr

Chapter 5. Floating-Point LLL: Theoretical and Practical Aspects

Abstract

The text-book LLL algorithm can be sped up considerably by replacing the underlying rational arithmetic used for the Gram–Schmidt orthogonalisation by floating-point approximations. We review how this modification has been and is currently implemented, both in theory and in practice. Using floating-point approximations seems to be natural for LLL even from the theoretical point of view: it is the key to reach a bit-complexity which is quadratic with respect to the bit-length of the input vectors entries, without fast integer multiplication. The latter bit-complexity strengthens the connection between LLL and Euclid’s gcd algorithm. On the practical side, the LLL implementer may weaken the provable variants in order to further improve their efficiency: we emphasise on these techniques. We also consider the practical behaviour of the floating-point LLL algorithms, in particular their output distribution, their running-time and their numerical behaviour. After 25 years of implementation, many questions motivated by the practical side of LLL remain open.

Damien Stehlé

Chapter 6. LLL: A Tool for Effective Diophantine Approximation

Abstract

The purpose of this paper is to survey in a unified setting some of the results in diophantine approximation that the LLL algorithm can make effective in an efficient way. We mostly study the problems of finding good rational approximations to vectors of real and p-adic numbers, and of finding approximate linear relations between vectors of real numbers. We also discuss classical applications of those effective versions, among which Mertens’ conjecture and the effective solution of diophantine equations.

Guillaume Hanrot

Chapter 7. Selected Applications of LLL in Number Theory

Abstract

In this survey, I describe some applications of LLL in number theory.I show in particular how it can be used to solve many different linear problems and quadratic equations and to compute efficiently in number fields.

Denis Simon

Chapter 8. The van Hoeij Algorithm for Factoring Polynomials

Abstract

In this survey, we report about a new algorithm for factoring polynomials due to Mark van Hoeij. The main idea is that the combinatorial problem that occurs in the Zassenhaus algorithm is reduced to a very special knapsack problem. In case of rational polynomials, this knapsack problem can be very efficiently solved by the LLL algorithm. This gives a polynomial time algorithm, which also works very well in practice.

Jürgen Klüners

Chapter 9. The LLL Algorithm and Integer Programming

Abstract

The LLL algorithm has proven to be a powerful theoretical and practical tool in many areas of discrete mathematics. In this chapter, we review some structural and algorithmic results involving basis reduction and integer programming.

Karen Aardal, Friedrich Eisenbrand

Chapter 10. Using LLL-Reduction for Solving RSA and Factorization Problems

Abstract

Twenty five years ago, Lenstra, Lenstra and Lovász presented their celebrated LLL lattice reduction algorithm. Among the various applications of the LLL algorithm is a method due to Coppersmith for finding small roots of polynomial equations. We give a survey of the applications of this root finding method to the problem of inverting the RSA function and the factorization problem. As we will see, most of the results are of a dual nature, they can either be interpreted as cryptanalytic results or as hardness/security results.

Alexander May

Chapter 11. Practical Lattice-Based Cryptography: NTRUEncrypt and NTRUSign

Abstract

We provide a brief history and overview of lattice based cryptography and cryptanalysis: shortest vector problems, closest vector problems, subset sum problem and knapsack systems, GGH, Ajtai-Dwork and NTRU. A detailed discussion of the algorithms NTRUEncrypt and NTRUSign follows. These algorithms have attractive operating speed and keysize and are based on hard problems that are seemingly intractable. We discuss the state of current knowledge about the security of both algorithms and identify areas for further research.

Jeff Hoffstein, Nick Howgrave-Graham, Jill Pipher, William Whyte

Chapter 12. The Geometry of Provable Security: Some Proofs of Security in Which Lattices Make a Surprise Appearance

Abstract

We highlight some uses of lattice reduction in security proofs of nonlattice-based cryptosystems. In particular, we focus on RSA-OAEP, the Rabin partial-domain hash signature scheme, techniques to compress Rabin signatures and ciphertexts, the relationship between the RSA and Paillier problems and Hensel lifting, and the hardness of the most significant bits of a Diffie–Hellman secret.

Craig Gentry

Chapter 13. Cryptographic Functions from Worst-Case Complexity Assumptions

Abstract

Lattice problems have been suggested as a potential source of computational hardness to be used in the construction of cryptographic functions that are provably hard to break. A remarkable feature of lattice-based cryptographic functions is that they can be proved secure (that is, hard to break on the average) based on the assumption that the underlying lattice problems are computationally hard in the worst-case. In this paper we give a survey of the constructions and proof techniques used in this area, explain the importance of basing cryptographic functions on the worst-case complexity of lattice problems, and discuss how this affects the traditional approach to cryptanalysis based on random challenges.

Daniele Micciancio

Chapter 14. Inapproximability Results for Computational Problems on Lattices

Abstract

In this article, we present a survey of known inapproximability results for computational problems on lattices, viz. the Shortest Vector Problem (SVP), the Closest Vector Problem (CVP), the Closest Vector Problem with Preprocessing (CVPP), the Covering Radius Problem (CRP), the Shortest Independent Vectors Problem (SIVP), and the Shortest Basis Problem (SBP).

Subhash Khot

Chapter 15. On the Complexity of Lattice Problems with Polynomial Approximation Factors

Abstract

Lattice problems are known to be hard to approximate to withinsub-polynomial factors. For larger approximation factors, such as \(\sqrt{n}\), lattice problems are known to be in complexity classes, such as NP ∩ coNP, and are hence unlikely to be NP-hard. Here, we survey known results in this area. We also discuss some related zero-knowledge protocols for lattice problems.

Oded Regev

Backmatter

Titel: The LLL Algorithm
herausgegeben von: Phong Q. Nguyen
Brigitte Vallée
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-02295-1
Print ISBN: 978-3-642-02294-4
DOI: https://doi.org/10.1007/978-3-642-02295-1