(2020) Certified Lattice Reduction.

Text
LLLintervalAIMC.pdf Download (609kB)  Preview 
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 (socalled 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 floatingpoint variants—where the rational arithmetic required by Gram–Schmidt orthogonalization is replaced by floatingpoint 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 adaptiveprecision version of a generalized lll algorithm that covers this case in all generality. In particular, we replace floatingpoint 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.
Item Type:  Article 

Divisions:  Antoine Joux (AJ) 
Depositing User:  Antoine Joux 
Date Deposited:  16 Dec 2020 09:02 
Last Modified:  16 Dec 2020 09:02 
Primary Research Area:  NRA1: Trustworthy Information Processing 
URI:  https://publications.cispa.saarland/id/eprint/3311 
Actions
Actions (login required)
View Item 