CISPA
Browse
cispa_all_3311.pdf (595.29 kB)

Certified Lattice Reduction

Download (595.29 kB)
journal contribution
posted on 2023-11-29, 18:06 authored by Antoine JouxAntoine Joux, Thomas Espitau
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.

History

Preferred Citation

Antoine Joux and Thomas Espitau. Certified Lattice Reduction. In: Advances in Mathematics of Communications. 2020.

Primary Research Area

  • Algorithmic Foundations and Cryptography

CISPA Affiliation

  • No

Legacy Posted Date

2020-12-16

Journal

Advances in Mathematics of Communications

Open Access Type

  • Green

Sub Type

  • Article

BibTeX

@article{cispa_all_3311, title = "Certified Lattice Reduction", author = "Joux, Antoine and Espitau, Thomas", journal="{Advances in Mathematics of Communications}", year="2020", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC