You are looking at a specific version 20160530:054632 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.