Paper 2026/225

Solving SIS in any norm via Gaussian sampling

Abstract

The Short Integer Solution (SIS) problem plays an important role in lattice-based cryptography. In this paper, we construct a natural and simple algorithm that allows us to solve the SIS problem for any norm in the case where the norm bound $\ell$ is smaller than half the modulus $q$. The algorithm consists in using a discrete Gaussian sampler on the SIS $q$-ary lattice to obtain many lattice vectors, and requires to estimate the probability that one of them is non-zero and falls into a ball of radius $\ell$ in the given norm. For the latter, we improve upon previous analysis of 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. Although our algorithm does not break Dilithium, it is at least 50 bits faster than the recent algorithm of Ducas, Engelberts and Loyer \cite{DEJ25} in Crypto 2025 for all security levels.