Welcome to the resource topic for 2023/1654
Title:
On Gaussian sampling, smoothing parameter and application to signatures
Authors: Thomas Espitau, Alexandre Wallet, Yang Yu
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.
ePrint: https://eprint.iacr.org/2023/1654
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .