Paper 2016/528
Adaptive precision LLL and Potential-LLL reductions with Interval arithmetic
Thomas Espitau and Antoine Joux
Abstract
Lattice reduction is fundamental in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra–Lenstra–Lovász reduction algorithm (called LLL or L3) has been improved in many ways through the past decades and remains one of the central tool for reducing lattice basis. In particular, its floating-point variants — where the long-integer arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic — are now the fastest known. Yet, the running time of these floating-point versions is mostly determined by the precision needed to perform sound computa- tions: theoretical lower bounds are large whereas the precision actually needed on average is much lower. In this article4, we present an adaptive precision version of LLL and one of its variant Potential-LLL. In these algorithms, floating-point arithmetic is replaced by Interval Arithmetic. The certification property of interval arithmetic enables runtime detection of precision defects in numerical computations and accordingly, makes it possible to run the reduction algorithms with guaranteed nearly optimal precision. As such, these adaptive reduction algorithms run faster than the state-of-the-art implementations, while still being provable.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- Lattice reductionlattice techniques
- Contact author(s)
- Thomas Espitau @ lip6 fr
- History
- 2019-05-28: last of 3 revisions
- 2016-05-29: received
- See all versions
- Short URL
- https://ia.cr/2016/528
- License
-
CC BY