An Efficient Algorithm for Integer Lattice Reduction

DOI10.1137/23M1557933MaRDI QIDQ6154950zbMATH OpenWikidataFDO

Authors Kristin Lauter, Cathy Li, Mark Tygert

Publication date 16 February 2024

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.02226

zbMATH Keywords

cryptographymatrixnumber theoryoptimizationorthogonalizationprojection

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Orthogonalization in numerical linear algebra (65F25) Numerical optimization and variational techniques (65K10)

Abstract: A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper proposes simple, efficient iterations for lattice reduction which are guaranteed to reduce the Euclidean norms of the basis vectors (the vectors in the subset) monotonically during every iteration. Each iteration selects the basis vector for which projecting off (with integer coefficients) the components of the other basis vectors along the selected vector minimizes the Euclidean norms of the reduced basis vectors. Each iteration projects off the components along the selected basis vector and efficiently updates all information required for the next iteration to select its best basis vector and perform the associated projections.

Recommendations

• scientific article; zbMATH DE number 3958726
• A hierarchy of polynomial time lattice basis reduction algorithms
• Random lattices, threshold phenomena and efficient reduction algorithms.
• scientific article; zbMATH DE number 4029654
• Reduction of lattice bases for arbitrary norms

Cites work

• A decade of lattice cryptography
• An introduction to the geometry of numbers.
• An updated set of basic linear algebra subprograms (BLAS)
• Basic Linear Algebra Subprograms for Fortran Usage
• Factoring polynomials with rational coefficients
• Floating-Point LLL: Theoretical and Practical Aspects
• Gram-Schmidt orthogonalization: 100 years and more
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice basis reduction. An introduction to the LLL algorithm and its applications
• New bounds in some transference theorems in the geometry of numbers
• On lattices, learning with errors, random linear codes, and cryptography
• The LLL algorithm. Survey and applications

Cited in

(2)

• The cool and the cruel: separating hard parts of LWE secrets
• Cool + cruel = dual, and new benchmarks for sparse LWE

This page was built for publication: An Efficient Algorithm for Integer Lattice Reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154950)