Paper 2026/2833
The Closest Vector Problem on Gadget Lattices: Efficient Algorithms and Voronoi Geometry
Abstract
Gadget lattices are a prominent family of lattices widely used in lattice-based cryptography, error-correcting codes, and computational complexity. We present efficient algorithms for the Closest Vector Problem (CVP) on power and CRT gadget lattices and their duals, handling arbitrary real-valued target vectors. For the parity-check power gadget lattice, we give a practical, deterministic O(n) linear-time exact CVP solver based on a new, specialized "deferred greedy" graph-cut technique. Through an explicit characterization of the Voronoi cell, we provide a comprehensive analysis of existing decoders: we prove that the standard BDD algorithm of Micciancio and Peikert (2012) unexpectedly solves CVP exactly for odd base b and integer targets, but degrades to a worst-case approximation factor of n^0.5 for binary base b=2 and continuous targets. Furthermore, we prove that standard pruned sphere decoding requires exponential time exp(Omega(n)) even when using a geometrically optimal basis. For the dual (generator) power gadget lattice, we construct an obtuse superbasis---proving for the first time that it is a lattice of "Voronoi's first kind"---which yields a polynomial-time O(n^3) exact CVP algorithm via graph min-cut reductions. Geometrically, we determine all successive minima and enumerate the facets of their Voronoi cells. In particular, we show that while the parity-check lattice has a sparse Voronoi cell with n^2+n facets, the generator lattice reaches the theoretical upper bound of 2(2^n-1) facets. Finally, we observe that CRT gadget lattices and their duals admit an orthogonal basis, yielding trivial linear-time CVP algorithms.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- lattice-based cryptographyCVPgadget latticesVoronoi cellBDDmin-cutpower gadgetCRT gadgetRNS
- Contact author(s)
- daniele @ cs ucsd edu
- History
- 2026-11-11: approved
- 2026-11-08: received
- See all versions
- Short URL
- https://ia.cr/2026/2833
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2833,
author = {Daniele Micciancio},
title = {The Closest Vector Problem on Gadget Lattices: Efficient Algorithms and Voronoi Geometry},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2833},
year = {2026},
url = {https://eprint.iacr.org/2026/2833}
}