IALatRed
Interval Arithmetic Lattice Reduction
 What is IALatRed?
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 floatingpoint variants — where the longinteger arithmetic required by Gram–Schmidt orthogonalization is replaced by floatingpoint arithmetic — are now the fastest known. Yet, the running time of these floatingpoint versions is mostly determined by the precision needed to perform sound computations: theoretical lower bounds are large whereas the precision actually needed on average is much lower. IALatRed is a proofofconcept of an adaptive precision version of LLL, one of its variant PotentialLLL and the BKZ reduction. In these algorithms, floatingpoint 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 stateoftheart implementations, while still being provable.
 Features
 Lightweight and fast library for Interval Arithmetic.
 Implementation of several lattice redcution algorithms ( LLL, PotentialLLL, BKZ ) with interval arithmetic.
 Support early abort of reductions (using standard signal
interuption
ctrl+c
 Download
IALatRed requires: GNU MP 4.2.0 or higher
 GCC 4.7 or higher
 Exemples
 LLL reduction:
latred < matrix_file
 PotentialLLL reduction:
latred p < matrixfile

LLL reduction with delta set to 0.8:
latred d 0.8 < matrix_file

BKZ blocksize 20:
latred B 20 < matrix_file

BKZ reduction blocksize 20 with LLLdelta set to 0.8,
early precision defect heuristic:
latred d 0.8 B 20 e < matrix_file

LLL with external scalar product:
latred S < lattice_file < scalprod_file
This project is maintained by Antoine Joux and Thomas Espitau. It is supported by the European Union's H2020 Program me under grant agreement number ERC669891 and ICT644209.