Paper 2023/1654

On Gaussian sampling, smoothing parameter and application to signatures

Abstract

We present a general framework for polynomial-time lattice Gaussian sampling. It revolves around a systematic study of the discrete Gaussian measure and its samplers under extensions of lattices; we first show that given lattices $\Lambda'\subset \Lambda$ we can sample efficiently in $\Lambda$ if we know how to do so in $\Lambda'$ and the quotient $\Lambda/\Lambda'$, \emph{regardless} of the primitivity of $\Lambda'$. As a direct application, we tackle the problem of domain extension and restriction for sampling and propose a sampler tailored for lattice \emph{filtrations}, which can be seen as a broad generalization of the celebrated Klein's sampler. Then, we demonstrate how to sample using a change of bases, or even switching the ambient space, even when the target lattice is not represented as full-rank in the ambient space. We show how to correct the induced distortion with the ``convolution-like'' technique of Peikert (Crypto 2010) (which we encompass as a byproduct). Since our framework aims at modularity and leverage the combinations of smaller samplers to build new ones, we also propose ad-hoc samplers for the so-called \emph{root lattices} $\mathsf{A}_n, \mathsf{D}_n, \mathsf{E}_n$ as base cases, extending the state-of-the-art for root lattice sampling, which was limited to $\mathbb{Z}^n$. We also show how our framework blends with the so-called $k$ing construction and provides a sampler for the remarkable Leech and Barnes-Wall lattices. As a by-product, we obtain novel, quasi-linear samplers for prime and smooth conductor (as $2^\ell 3^k$) cyclotomic rings, achieving essentially optimal Gaussian width. In a practice-oriented application, we showcase the impact of our work on hash-and-sign signatures over \textsc{ntru} lattices. In the best case, we can gain around 200 bytes (which corresponds to an improvement greater than 20\%) on the signature size. We also improve the new gadget-based constructions (Yu, Jia, Wang, Crypto 2023) and gain up to 110 bytes for the resulting signatures. Lastly, we sprinkle our exposition with several new estimates for the smoothing parameter of lattices, stemming from our algorithmic constructions and by novel methods based on series reversion.