Paper 2026/1465
On Reduction Probability Models in Lattice Sieving
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
-
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}
}