Paper 2026/1465

On Reduction Probability Models in Lattice Sieving

Marc Stevens, Centrum Wiskunde & Informatica
Michael Yonli, Centrum Wiskunde & Informatica
Abstract

In lattice sieving, the sphere model assumes that sieving elements are distributed close to or on a sphere with uniformly distributed direction. It is extensively used to predict how lattice sieving behaves. In the sphere model the probability that a random pair of vectors reduces is asymptotically $p_n={(3/4)}^{n/2}/\sqrt{3\pi n/8}$. In practice sieving algorithms have been observed to perform better than predicted by the sphere model. It is an open question how this gap behaves asymptotically: does the gap vanish or grow as the dimension grows? Our work answers this question by showing that it is asymptotically constant. We generalise the sphere model to uniform ball and non-uniform ball models and analyse reduction probability distributions. The reduction probability advantages of our models over the sphere model range from $\times 1.5$ up to $\times 8$. Moreover, we examine scaled depth distributions (defined for dimension $n$ as $w=-n \ln \|x\|$) in the asymptotic setting. Under global reductions the output scaled depth distribution converges to $\text{Exp}(2/3)$ for any converging family of scaled depth distributions that is dominated by a suitable integrable function. The input scaled depth distribution only affects the total reduction probability. Compared to (the scaled depth distribution $\text{Exp}(1)$ induced by) the uniform ball as input distribution, using this stable limit distribution as input distribution results in an increased reduction probability ($\times 4.5$ versus $\times 8$).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
lattice sievingreduction probabilitysphere modelball model
Contact author(s)
stevens @ cwi nl
michael yonli @ cwi nl
History
2026-10-23: revised
2026-07-17: received
See all versions
Short URL
https://ia.cr/2026/1465
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2026/1465,
      author = {Marc Stevens and Michael Yonli},
      title = {On Reduction Probability Models in Lattice Sieving},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1465},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1465}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.