Towards efficient discrete Gaussian sampling for lattice-based cryptography

Abstract

Modern lattice-based public key cryptosystems usually require sampling from discrete Gaussian distributions. In this paper, we propose a novel implementation of cumulative distribution function (CDF) inversion sampler with high precision and large tail bound. It has maximum statistical distance of 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−90</sup> to a theoretical discrete Gaussian distribution. Our CDF inversion sampler exploits piecewise comparison to save more than 90% random bits and reduce the required large comparators to two small comparators. We speed up the sampler by using a small lookup table, and the hit rate of the lookup table is as high as 94%. With these optimizations, our sampler takes on average 9.44 random bits and 2.28 clock cycles to generate a sample. It consumes 1 block RAM and 17 slices on a Spartan-6 FPGA. With additional 13 slices, our sampler is able to generate n samples within around 1.14n clock cycles.