Paper 2017/308

Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus

Nicholas Genise and Daniele Micciancio

Abstract

We present improved algorithms for gaussian preimage sampling using the lattice trapdoors of (Micciancio and Peikert, CRYPTO 2012). The MP12 work only offered a highly optimized algorithm for the on-line stage of the computation in the special case when the lattice modulus $q$ is a power of two. For arbitrary modulus $q$, the MP12 preimage sampling procedure resorted to general lattice algorithms with complexity cubic in the bitsize of the modulus (or quadratic, but with substantial preprocessing and storage overheads.) Our new preimage sampling algorithm (for any modulus $q$) achieves linear complexity, and has very modest storage requirements. As an additional contribution, we give a new off-line quasi-linear time perturbation sampling algorithm, with performance similar to the (expected) running time of an efficient method proposed by (Ducas and Nguyen, Asiacrypt 2012) for power-of-two cyclotomics, but without the (matrix factorization) preprocessing and (lattice rounding) postprocessing required by that algorithm. All our algorithms are fairly simple, with small hidden constants, and offer a practical alternative to use the MP12 trapdoor lattices in a broad range of cryptographic applications.

Note: Fixed typo in SampleD ("c = c - z_{k-1}*d" to "c = c + z_{k-1}*d").

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
Keywords
Lattice-Based CryptographyDiscrete Gaussian SamplingLattice Trapdoors
Contact author(s)
ngenise @ eng ucsd edu
History
2022-04-25: last of 7 revisions
2017-04-10: received
See all versions
Short URL
https://ia.cr/2017/308
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/308,
      author = {Nicholas Genise and Daniele Micciancio},
      title = {Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus},
      howpublished = {Cryptology ePrint Archive, Paper 2017/308},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/308}},
      url = {https://eprint.iacr.org/2017/308}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.