[Resource Topic] 2023/1654: On Gaussian sampling, smoothing parameter and application to signatures

Welcome to the resource topic for 2023/1654

On Gaussian sampling, smoothing parameter and application to signatures

Authors: Thomas Espitau, Alexandre Wallet, Yang Yu


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 .