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. We find that asymptotically the input distribution only affects the total reduction probability, not the shape of the output length distribution. We show that the reduction probability advantages of our models over the sphere model range from $\times 1.5$ up to $\times 8$.