2015 · 30 citations · 12 references
ComputingComputer EngineeringComputer ScienceAlgorithmsCryptographyReconfigurable ComputingLattice-based CryptographyLookup TablesLow-power Fpga DesignRandom Number GenerationBlock RamBlock Ram ArchitectureComparatorsDiscrete Gaussian DistributionsGaussian DistributionsHardware Acceleration For CryptographyHit RateLookup Table Design
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.
12
Algorithms for quantum computation: discrete logarithms and factoring
Peter W. Shor · 2002 · 8.5K citations
Computing, Computer Science, Physics +12
Fully homomorphic encryption using ideal lattices
Craig Gentry · 2009 · 6.6K citations
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2005 · 2.2K citations