**Certified lattice reduction**

*Thomas Espitau and Antoine Joux*

**Abstract: **Quadratic form reduction and lattice reduction are fundamental tools in
computational number theory and in computer science, especially in
cryptography. The celebrated Lenstra-Lenstra-Lovász reduction algorithm
(so-called LLL) has been improved in many ways through the past decades and
remains one of the central methods used for reducing integral lattice basis. In
particular, its floating-point variants-where the rational arithmetic required
by Gram-Schmidt orthogonalization is replaced by floating-point arithmetic-are
now the fastest known. However, the systematic study of the reduction theory of
real quadratic forms or, more generally, of real lattices is not widely
represented in the literature. When the problem arises, the lattice is usually
replaced by an integral approximation of (a multiple of) the original lattice,
which is then reduced. While practically useful and proven in some special
cases, this method doesn't offer any guarantee of success in general. In this
work, we present an adaptive-precision version of a generalized LLL algorithm
that covers this case in all generality. In particular, we replace
floating-point arithmetic by Interval Arithmetic to certify the behavior of the
algorithm. We conclude by giving a typical application of the result in
algebraic number theory for the reduction of ideal lattices in number fields.

**Category / Keywords: **foundations / Lattice reduction, lattice techniques

**Date: **received 28 May 2016, last revised 28 May 2019

**Contact author: **Thomas Espitau at lip6 fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20190528:112107 (All versions of this report)

**Short URL: **ia.cr/2016/528

[ Cryptology ePrint archive ]