International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 02 July 2015

Léo Ducas, Thomas Prest
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.