Paper 2023/1654

On Gaussian sampling, smoothing parameter and application to signatures

Abstract

We present a general framework for polynomial-time lattice Gaussian sampling. Its principles revolve around a systematic study of the discrete Gaussian measure and its samplers under \emph{extensions} of lattices, a setting encompassing that of nested lattices $\Lat'\subset \Lat$. A fundamental result for Gaussian sampling is that we can sample efficiently in $\Lat$ if we know how to do so in $\Lat'$ and the quotient $\Lat/\Lat'$. This is often presented in a context-dependent manner. Our formalism provides general and unifying foundations for this idea, and also shows that this can be done \emph{regardless} of the primitivity of $\Lat'$. As direct illustrations of this unifying theme, we formally recover and extend several methods from the literature: domain restriction and extension (as, efficient sampling in a larger or smaller lattice); a lattice \emph{filtration} based sampler, 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 leverages the combinations of smaller samplers to build new ones, we also propose ad-hoc samplers for the so-called \emph{root lattices} $\An_n, \Dn_n, \mathsf{E}_n$ as base cases, extending the state-of-the-art for root lattice sampling, which was limited to $\ZZ^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 concrete applications of our methods, 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 decrease their sizes by around 200 bytes (which corresponds to an improvement greater than 20\%). 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.