Cryptology ePrint Archive: Report 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.

Category / Keywords: Lattice reduction, lattice techniques

Date: received 28 May 2016, last revised 29 May 2016

Contact author: Thomas Espitau at lip6 fr

Available format(s): PDF | BibTeX Citation

Version: 20160530:054632 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]