Fast infinity norm reduction method for two vector lattices
Fast \(\ell_\infty\)-Reduction of Rank-2 Lattices in $\mathbb{R}^n$ via a New Reduced-Basis Notion
Computational GeometryCryptography and Security
Summary
Lattices are grids of points important in areas like cryptography, where finding the shortest lattice point under certain norms is a key problem. Most methods look for short points using the usual distance measure (Euclidean norm), but some applications require using the infinity norm, which measures largest coordinate size. The authors introduce a new way to simplify two-dimensional lattices using this infinity norm and design a fast algorithm to find short vectors more efficiently. Their algorithm guarantees steady progress, runs with similar complexity as classical methods, uses fewer multiplications, and performs better in practice.
What this means in practice
- •For post-quantum cryptography engineers: Speed up lattice basis reduction under infinity norm to analyze signature schemes like ML-DSA with tighter security guarantees.
- •For numerical optimization developers: Use a new efficient lattice reduction method to simplify rank-two lattice problems constrained by infinity norms in geometric computations.
Authors
Bo Pang, Shaojing Zhang, Chengliang Tian
Abstract
The shortest vector problem (SVP) under the infinity norm ($\ell_\infty$-norm) is an important lattice problem with applications in lattice-based cryptography. In particular, the security analysis of the post-quantum signature standard ML-DSA highlights the importance of finding short solutions satisfying infinity-norm constraints, rather than only Euclidean norm bounds. However, most existing lattice reduction algorithms are developed for the Euclidean norm, while dedicated studies under the infinity norm remain limited. In this work, we focus on rank-two lattices in $\mathbb{R}^n$ and introduce a new notion of reduced basis under the infinity norm. Based on this definition, we propose an efficient lattice basis reduction algorithm that performs a multi-dimensional analogue of Euclidean division using a dominant coordinate of the basis vectors. Each non-terminal iteration guarantees a factor-two decrease of the maximum infinity norm of the basis vectors. We prove that the algorithm terminates and achieves a bit complexity of $O(nT^2)$, matching the asymptotic complexity order of the classical Lagrange--Gauss reduction. Moreover, the proposed algorithm saves at least $2n$ multiplications per iteration compared with the classical approach. Experiments demonstrate significant runtime improvements, especially for high-dimensional lattices. This work provides a foundation for developing lattice reduction techniques under the infinity norm.