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 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 computations: theoretical lower bounds are large whereas the precision actually needed on average is much lower. IALatRed is a proof-of-concept of an adaptive precision version of LLL, one of its variant Potential-LLL and the BKZ reduction. 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.

| Features

  • Lightweight and fast library for Interval Arithmetic.
  • Implementation of several lattice redcution algorithms ( LLL, Potential-LLL, BKZ ) with interval arithmetic.
  • Support early abort of reductions (using standard signal interuption ctrl+c

| Download

IALatRed requires: Download latest version

| Exemples

  • LLL reduction:
    latred < matrix_file
  • Potential-LLL reduction:
    latred -p < matrix-file
  • 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 LLL-delta 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 ERC-669891 and ICT-644209.