Paper 2025/1176

A Practical Randomized Nearest-Colattice Framework for Arbitrary Norms

Abstract

The approximate Closest Vector Problem $\mathsf{CVP}$ with large approximation factors, such as a polynomial approximation, arises in the concrete cryptanalysis of lattice-based signatures, yet it is commonly estimated indirectly through $\mathsf{SVP}$ after Kannan's embedding (Wang et al, PQC2025). Such reductions may return short vectors that do not encode valid $\mathsf{CVP}$ solutions and are less suited to reusable preprocessing, batched targets, and list output. We give, to our knowledge, the first practical instantiation of the Nearest-Colattice framework (Espitau et al, ANTS2020). Our $\texttt{RandNColattice}$ algorithm realizes quotient-lattice $\mathsf{CVP}$ calls on explicitly projected basis blocks using randomized slicer oracles (Ducas et al, PKC2020), and therefore naturally propagates multiple candidate branches for batches of targets. We further extend the randomized slicer with dimensions for free for both $\mathsf{BDD}$ and approximate $\mathsf{CVP}$/$\mathsf{ListCVP}$, and introduce $\texttt{HybridRandNColattice}$, which replaces the oracle on the final block with Klein's sampler to generate diverse randomized residual targets efficiently. The final candidate-filtering interface is norm-generic, while our concrete analysis focuses on the Euclidean and infinity norms. We derive blockwise distance and runtime models and construct an estimator over 4 strategy models: $\mathsf{D4f}\text{-}{CVP}$, $\mathsf{Prob}\text{-}\mathsf{BDD}$, $\mathsf{CVP}_{\gamma_2}$, and $\mathsf{Flexd4f}\text{-}\mathsf{CVP}_{\gamma_2}$ with $1\leq \gamma_2\leq \sqrt{4/3}$. The estimator instantiates costs under a theoretical model and the AGPS20 and MATZOV22 gate-count models, and we apply it to non-amortized forgery estimates for Dilithium, HuFu, and one-more-ISIS. Finally, we implement $\texttt{HybridRandNColattice}$ by extending the G6K-CPU based randomized slicer (Alexander et al, AsiaCrypt 2025). Our experiments support the Euclidean distancemodel, while showing that the spherical approximation used for infinity-norm filtering is optimistic because the actual blockwise error distribution is anisotropic. These results provide a concrete foundation for direct approximate-$\mathsf{CVP}$ cryptanalysis and identify tighter infinity-norm modeling as an important open problem.

Note: We updated our model to a Randomized Nearest Colattice Algorithm, which can solve the approximate batch-cvp problems.