Approximate Voronoi cells for lattices, revisited
Pith reviewed 2026-05-24 23:36 UTC · model grok-4.3
The pith
The volumes of approximate Voronoi cells for high-dimensional lattices follow precise asymptotics under the Gaussian heuristic, settling an open problem and improving CVPP algorithms.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We settle the open problem of determining exact asymptotics on the volume of approximate Voronoi cells under the Gaussian heuristic. As a result, we obtain improved upper bounds on the time complexity of the randomized iterative slicer when using less than 2^{0.076d + o(d)} memory, and we show how to obtain time-memory trade-offs even when using less than 2^{0.048d + o(d)} memory. We also settle the open problem of obtaining a continuous trade-off between the size of the advice and the query time complexity, as the time complexity with subexponential advice in our approach scales as d^{d/2 + o(d)}, matching worst-case enumeration bounds.
What carries the argument
The approximate Voronoi cell construction for CVPP, whose volume is analyzed via the Gaussian heuristic to derive complexity bounds for the randomized iterative slicer.
If this is right
- Improved upper bounds on time complexity of the randomized iterative slicer with memory less than 2^{0.076d + o(d)}
- Time-memory trade-offs are possible even with memory less than 2^{0.048d + o(d)}
- Continuous trade-off between advice size and query time complexity
- With subexponential advice the query time scales as d^{d/2 + o(d)}, matching worst-case enumeration bounds
Where Pith is reading between the lines
- The continuous trade-off may allow tuning preprocessing resources to specific memory constraints in applications
- The matching to enumeration bounds suggests the method saturates known scaling in the subexponential-advice regime
Load-bearing premise
The Gaussian heuristic accurately predicts the volume of approximate Voronoi cells in high-dimensional lattices.
What would settle it
An exact computation or simulation of the volume of an approximate Voronoi cell for a concrete lattice in dimension 80-120 that deviates from the asymptotic formula derived under the Gaussian heuristic.
Figures
read the original abstract
We revisit the approximate Voronoi cells approach for solving the closest vector problem with preprocessing (CVPP) on high-dimensional lattices, and settle the open problem of Doulgerakis-Laarhoven-De Weger [PQCrypto, 2019] of determining exact asymptotics on the volume of these Voronoi cells under the Gaussian heuristic. As a result, we obtain improved upper bounds on the time complexity of the randomized iterative slicer when using less than $2^{0.076d + o(d)}$ memory, and we show how to obtain time-memory trade-offs even when using less than $2^{0.048d + o(d)}$ memory. We also settle the open problem of obtaining a continuous trade-off between the size of the advice and the query time complexity, as the time complexity with subexponential advice in our approach scales as $d^{d/2 + o(d)}$, matching worst-case enumeration bounds, and achieving the same asymptotic scaling as average-case enumeration algorithms for the closest vector problem.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript revisits approximate Voronoi cells for the closest vector problem with preprocessing (CVPP) on high-dimensional lattices. It settles the open problem of Doulgerakis-Laarhoven-De Weger by deriving exact asymptotics for the volume of these cells under the Gaussian heuristic. This yields improved upper bounds on the time complexity of the randomized iterative slicer for memory budgets below 2^{0.076d + o(d)}, time-memory trade-offs below 2^{0.048d + o(d)}, and a continuous trade-off in which subexponential advice produces query time d^{d/2 + o(d)}, matching worst-case enumeration bounds.
Significance. If the derivations hold, the work improves the best known asymptotic bounds for CVPP algorithms under the standard Gaussian heuristic and resolves two open questions in the area. The explicit, parameter-free character of the volume asymptotics (resting only on the external heuristic rather than fitted constants) and the matching of enumeration scaling are concrete strengths.
minor comments (3)
- [§4] §4 (volume asymptotics): the transition from the Gaussian heuristic to the claimed exact leading-term expression should include an explicit statement of the o(·) error term and the dimension range in which the approximation is asserted to become exact.
- [§5] The time-memory trade-off curves in §5 are presented only asymptotically; a short table or plot of the concrete exponents for d = 100…200 would help readers assess practical relevance.
- Notation: the symbol V_approx is introduced without an immediate forward reference to its precise definition in terms of the covering radius and the number of lattice points; a one-line reminder in the introduction would improve readability.
Simulated Author's Rebuttal
We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. The report contains no enumerated major comments, so we have no specific points to address point-by-point. We are pleased that the work is viewed as settling the open problems from Doulgerakis-Laarhoven-De Weger and improving the CVPP bounds under the Gaussian heuristic.
Circularity Check
No significant circularity
full rationale
The central claim settles an open problem by deriving exact volume asymptotics explicitly under the external Gaussian heuristic (a standard lattice assumption, not fitted or defined inside the paper). No load-bearing step reduces a prediction to a self-defined parameter, fitted input, or self-citation chain; the derivation chain remains independent of the target result. The provided abstract and context show no equations that equate outputs to inputs by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Gaussian heuristic holds for the distribution of lattice points and thus for the volume of approximate Voronoi cells
Reference graph
Works this paper leans on
-
[1]
Dorit Aharonov and Oded Regev, Lattice problems in NP∩ coNP, in: FOCS, pp. 362–371, 2004
work page 2004
-
[2]
Miklós Ajtai and Cynthia Dwork, A public-key cryptosyst em with worst- case/average-case equivalence, in: STOC, pp. 284–293, 1997
work page 1997
-
[3]
Miklós Ajtai, Ravi Kumar and Dandapani Sivakumar, A siev e algorithm for the shortest lattice vector problem, in: STOC, pp. 601–610, 2001
work page 2001
-
[4]
Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena K irshanova, Eamonn Postlethwaite and Marc Stevens, The general sieve kernel an d new records in lat- tice reduction, in: EUROCRYPT, pp. 717–746, 2019
work page 2019
-
[5]
Nguyên, Random sampling revi sited: lattice enumer- ation with discrete pruning, in: EUROCRYPT, pp
Y oshinori Aono and Phong Q. Nguyên, Random sampling revi sited: lattice enumer- ation with discrete pruning, in: EUROCRYPT, pp. 65–102, 2017
work page 2017
-
[6]
Nguyen and Yixin Shen, Quantum l attice enumeration and tweaking discrete pruning, in: ASIACRYPT, pp
Y oshinori Aono, Phong Q. Nguyen and Yixin Shen, Quantum l attice enumeration and tweaking discrete pruning, in: ASIACRYPT, pp. 405–434, 2018
work page 2018
-
[7]
Anja Becker, Léo Ducas, Nicolas Gama and Thijs Laarhoven , New directions in nearest neighbor searching with applications to lattice si eving, in: SODA, pp. 10–24, 2016
work page 2016
-
[8]
Bernstein, Johannes Buchmann and Erik Dahmen ( eds.), Post-quantum cryptography, Springer, 2009
Daniel J. Bernstein, Johannes Buchmann and Erik Dahmen ( eds.), Post-quantum cryptography, Springer, 2009
work page 2009
-
[9]
Ward Beullens, Thorsten Kleinjung and Frederik V ercaut eren, CSI-FiSh: Effi- cient isogeny based signatures through class group computa tions, Cryptology ePrint Archive, Report 2019/498 (2019)
work page 2019
-
[10]
Nicolas Bonifas and Daniel Dadush, Short paths on the Vo ronoi graph and the closest vector problem with preprocessing, in: SODA, pp. 295–314, 2015
work page 2015
-
[11]
Daniel Dadush, Oded Regev and Noah Stephens-Davidowit z, On the closest vector problem with a distance guarantee, in: CCC, pp. 98–109, 2014
work page 2014
-
[12]
Emmanouil Doulgerakis, Thijs Laarhoven and Benne de We ger, Finding closest lat- tice vectors using approximate Voronoi cells, in: PQCrypto, 2019
work page 2019
-
[13]
Léo Ducas, Shortest vector from lattice sieving: a few d imensions for free, in: EU- ROCRYPT, pp. 125–145, 2018
work page 2018
-
[14]
The European Telecommunications Standards Institute (ETSI), Quantum-Safe Cryp- tography, 2019
work page 2019
-
[15]
Ulrich Fincke and Michael Pohst, Improved methods for c alculating vectors of short length in a lattice, Mathematics of Computation 44 (1985), 463–471
work page 1985
-
[16]
Nguyên and Oded Regev, Lattice en umeration using ex- treme pruning, in: EUROCRYPT, pp
Nicolas Gama, Phong Q. Nguyên and Oded Regev, Lattice en umeration using ex- treme pruning, in: EUROCRYPT, pp. 257–278, 2010. 14 T. Laarhoven
work page 2010
-
[17]
Guillaume Hanrot and Damien Stehlé, Improved analysis of Kannan’s shortest lattice vector algorithm, in: CRYPTO, pp. 170–186, 2007
work page 2007
-
[18]
Gottfried Herold, Elena Kirshanova and Thijs Laarhove n, Speed-ups and time- memory trade-offs for tuple lattice sieving, in: PKC, pp. 407–436, 2018
work page 2018
-
[19]
Ravi Kannan, Improved algorithms for integer programm ing and related lattice prob- lems, in: STOC, pp. 193–206, 1983
work page 1983
-
[20]
Thijs Laarhoven, Sieving for shortest vectors in latti ces using angular locality- sensitive hashing, in: CRYPTO, pp. 3–22, 2015
work page 2015
-
[21]
Thijs Laarhoven, Sieving for closest lattice vectors ( with preprocessing), in: SAC, pp. 523–542, 2016
work page 2016
-
[22]
Thijs Laarhoven and Artur Mariano, Progressive lattic e sieving, in: PQCrypto, pp. 292–311, 2018
work page 2018
-
[23]
Thijs Laarhoven, Michele Mosca and Joop van de Pol, Find ing shortest lattice vec- tors faster using quantum search, Designs, Codes and Cryptography 77 (2015), 375– 400
work page 2015
-
[24]
Daniele Micciancio, The hardness of the closest vector problem with preprocessing, IEEE Transactions on Information Theory 47 (2001), 1212–1215
work page 2001
-
[25]
Daniele Micciancio and Panagiotis V oulgaris, A determ inistic single exponential time algorithm for most lattice problems based on Voronoi ce ll computations, in: STOC, pp. 351–358, 2010
work page 2010
-
[26]
Daniele Micciancio and Panagiotis V oulgaris, Faster e xponential time algorithms for the shortest vector problem, in: SODA, pp. 1468–1480, 2010
work page 2010
-
[27]
Daniele Micciancio and Michael Walter, Fast lattice po int enumeration with minimal overhead, in: SODA, pp. 276–294, 2015
work page 2015
-
[28]
Phong Q. Nguyên and Thomas Vidick, Sieve algorithms for the shortest vector prob- lem are practical, Journal of Mathematical Cryptology 2 (2008), 181–207
work page 2008
-
[29]
The National Institute of Standards and Technology (NI ST), Post-Quantum Cryp- tography, 2017
work page 2017
-
[30]
Alice Pellet-Mary, Guillaume Hanrot and Damien Stehlé , Approx-SVP in ideal lat- tices with pre-processing, in: EUROCRYPT, pp. 685–716, 2019
work page 2019
-
[31]
Peter Pivovarov, V olume thresholds for Gaussian and sp herical random polytopes and their duals, Studia Mathematica 183 (2007), 15–34
work page 2007
-
[32]
Peter Pivovarov, V olume distribution and the geometry of high-dimensional r andom polytopes, Ph.D. thesis, 2010
work page 2010
-
[33]
Oded Regev, On lattices, learning with errors, random l inear codes, and cryptogra- phy, in: STOC, pp. 84–93, 2005. Approximate V oronoi cells for lattices, revisited 15
work page 2005
-
[34]
Claude E. Shannon, Probability of error for optimal cod es in a Gaussian channel, Bell System Technical Journal 38 (1959), 611–656
work page 1959
-
[35]
Maria Shcherbina and Brunello Tirozzi, On the volume of the intersection of a sphere with random half spaces, Comptes Rendus Mathematique 334 (2002), 803–806
work page 2002
-
[36]
Shor, Algorithms for quantum computation: dis crete logarithms and factor- ing, in: FOCS, pp
Peter W. Shor, Algorithms for quantum computation: dis crete logarithms and factor- ing, in: FOCS, pp. 124–134, 1994
work page 1994
-
[37]
Naftali Sommer, Meir Feder and Ofir Shalvi, Finding the c losest lattice point by iterative slicing, SIAM Journal of Discrete Mathematics 23 (2009), 715–731
work page 2009
-
[38]
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa, Efficient public key encryption based on ideal lattices, in: ASIACRYPT, pp. 617–635, 2009
work page 2009
-
[39]
Noah Stephens-Davidowitz, A time-distance trade-off for GDD with preprocessing - Instantiating the DLW heuristic, in: CCC, 2019
work page 2019
-
[40]
Michel Talagrand, Intersecting random half-spaces: t oward the Gardner–Derrida for- mula, The Annals of Probability 28 (2000), 725–758
work page 2000
-
[41]
Nicola Turchi, High-dimensional asymptotics for random polytopes , Ph.D. thesis, 2019
work page 2019
-
[42]
J. G. Wendel, A problem in geometric probability, Mathematica Scandinavica 11 (1962), 109–112. A The Sommer–Feder–Shalvi iterative slicer We briefly describe some more details on previous, related wo rk in these appen- dices, starting with the iterative slicer of Sommer–Feder– Shalvi [37]. This algo- rithm provides an elementary, greedy strategy to attempt...
work page 1962
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.