Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Lattice-based Cryptography, Gaussian Sampling, Ideal Lattices

Date: received 1 Jul 2015, withdrawn 12 Aug 2016

Contact author: thomas prest at ens fr

Available format(s): (-- withdrawn --)

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

Version: 20160812:144916 (All versions of this report)

Short URL: ia.cr/2015/660

Discussion forum: Show discussion | Start new discussion