Paper 2025/1176

Solve Approximate CVP via Variants of Nearest-Colattice

Wenwen Xia, Shanghai Jiao Tong University
Geng Wang, Shanghai Jiao Tong University
Dawu Gu
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 queries. (6) We integrate a slicer and Colattice into G6K-CPU, leveraging the Locality-Sensitive Hashing (LSH) technqiue for nearest neighbors search (NNS). This is the first practical implementation of an NNS-accelerated slicer. Our results demonstrate the practical efficiency of approximate CVP and batch-CVP attacks, highlighting the need for more accurate security estimation. These findings underscore the practical importance of accurate approximate CVP modeling and call for a reassessment of current parameter sets in post-quantum signature schemes.

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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.