Paper 2025/1176
Solve Approximate CVP via Variants of Nearest-Colattice
Abstract
The approximate Closest Vector Problem (CVP) is a core computational problem underlying many post-quantum lattice-based signature schemes, including Dilithium, one-more-ISIS, and HuFu. While the security of these schemes is typically expressed in terms of the Inhomogeneous Short Integer Solution (ISIS) problem, it is well-known that ISIS can be efficiently reduced to approximate CVP. Despite its foundational role, approximate CVP with non-negligible approximation factors remains far less explored than other lattice problems such as SVP or LWE, creating a critical gap in both theory and practice.
In this work, we bridge this gap by advancing the Colattice framework for solving approximate CVP with large approximation factors. More concretely, (1) We define a practical version of the Colattice algorithm and propose a randomized Nearest Colattice for generating more than one approximate closest vector. (2) Define a formal strategy space for blockwise approximate CVP. (3) Propose a polynomial-time strategy selection algorithm and prove its correctness under standard lattice heuristics. (4) Building on this, we design an efficient security estimator for approximate CVP in both Euclidean and Infinity norms, and extend it to approximate batch-CVP attack settings. (5) By applying this estimator, we perform concrete security evaluations of Dilithium, HuFu, and one-more-ISIS. Our results reveal that almost none of the evaluated schemes withstand approximate batch-CVP attacks with
Note: We compute the wrong volume for Dilithium, so we correct the result.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- cryptanalysisapproximate CVPNearest-Colatticedimension for freesieveslicer
- Contact author(s)
-
xww_summer @ sjtu edu cn
wanggxx @ sjtu edu cn
dwgu @ sjtu edu cn - History
- 2025-07-08: last of 5 revisions
- 2025-06-23: received
- See all versions
- Short URL
- https://ia.cr/2025/1176
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1176, author = {Wenwen Xia and Geng Wang and Dawu Gu}, title = {Solve Approximate {CVP} via Variants of Nearest-Colattice}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/1176}, year = {2025}, url = {https://eprint.iacr.org/2025/1176} }