The Short Integer Solution (SIS) problem plays an important role in lattice-based cryptography. In this paper, we construct a natural and simple provable algorithm that solves the SIS problem for any norm when the norm bound $\ell$ is less than half the modulus $q$. The algorithm consists of using a discrete Gaussian sampler on the SIS $q$-ary lattice to obtain many lattice vectors, and requires estimating the probability that one of them is nonzero and falls into a ball of radius $\ell$ in the given norm. For the latter, we improve upon previous analysis of a random $q$-ary lattice by obtaining tight bounds on the expected value and variance of the Gaussian mass of the entire lattice and of an $\ell_p$-norm ball, for any $p\in(0,\infty]$. These bounds require new technical results on the discrete Gaussian distribution and on the ratio of two Gaussian mass functions of $\mathbb{Z}$. This allows us to show that the proposed algorithm is provably correct. When instantiated with a Markov chain Monte Carlo (MCMC)-based discrete Gaussian sampler, the complexity of the algorithm can be estimated precisely. In particular, we show that its performance is at least 50 bits faster than the version of Wagner's algorithm of Ducas, Engelberts, and Loyer (Crypto 2025) for solving SIS with the infinity norm across all security levels of Dilithium, but still far from heuristic estimates underlying the security of this scheme.
Amaury Pouly is researcher scientist at the National Centre for Scientific Research (CNRS) in France. His current research focuses on mathematical aspects of cryptography, with a particular interest for lattices.