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").