Paper 2015/660

A Hybrid Gaussian Sampler for Lattices over Rings

Léo Ducas and Thomas Prest

Abstract

Gaussian sampling over lattices is a cornerstone of lattice-based cryptography as it allows to build numerous cryptographic primitives. There are two main algorithms performing this task. The first one is due to Klein (SODA 2000) and Gentry, Peikert and Vaikuntanathan (STOC 2008), and outputs vectors of good quality but runs rather slowly, in quadratic time. The second one is due to Peikert (CRYPTO 2010) and outputs vectors of slightly worse quality, but can be made to run in quasilinear time in the ring setting. We present a Gaussian Sampler optimized for lattices over the ring of integer of a cyclotomic number field. At a high-level it works as Klein's sampler but uses an efficient variant of Peikert's sampler as a subroutine. The result is a new sampler that samples vectors with a quality close to Klein's sampler and achieves the same quasilinear complexity as Peikert's sampler. In practice, we get close to the best of both worlds.

Note: This pre-print is super-seeded by https://eprint.iacr.org/2015/1014. It also contains a bug: Section 3.2 is incorrect. It is unclear how to repair it while keeping quasi-linear complexity (except in the power-of-2 case).

Metadata
Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Lattice-based CryptographyGaussian SamplingIdeal Lattices
Contact author(s)
thomas prest @ ens fr
History
2016-08-12: withdrawn
2015-07-02: received
See all versions
Short URL
https://ia.cr/2015/660
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.