Paper 2014/591

Compact and Side Channel Secure Discrete Gaussian Sampling

Sujoy Sinha Roy, Oscar Reparaz, Frederik Vercauteren, and Ingrid Verbauwhede


Discrete Gaussian sampling is an integral part of many lattice based cryptosystems such as public-key encryption, digital signature schemes and homomorphic encryption schemes. In this paper we propose a compact and fast Knuth-Yao sampler for sampling from a narrow discrete Gaussian distribution with very high precision. The designed samplers have a maximum statistical distance of $2^{-90}$ to a true discrete Gaussian distribution. In this paper we investigate various optimization techniques to achieve minimum area and cycle requirement. For the standard deviation 3.33, the most area-optimal implementation of the bit-scan operation based Knuth-Yao sampler consumes 30 slices on the Xilinx Virtex 5 FPGAs, and requires on average 17 cycles to generate a sample. We improve the speed of the sampler by using a precomputed table that directly maps the initial random bits into samples with very high probability. The fast sampler consumes 35 slices and spends on average 2.5 cycles to generate a sample. However the sampler architectures are not secure against timing and power analysis based attacks. In this paper we propose a random shuffle method to protect the Gaussian distributed polynomial against such attacks. The side channel attack resistant sampler architecture consumes 52 slices and spends on average 420 cycles to generate a polynomial of 256 coefficients.

Note: Some corrections in the text and in the title of the paper.

Available format(s)
Publication info
Preprint. MINOR revision.
Lattice-based cryptographyDiscrete Gaussian SamplerHardware implementationKnuth-Yao algorithmDiscrete distribution generating (DDG) treeSide channel analysis
Contact author(s)
sujoy sinharoy @ esat kuleuven be
2014-10-01: last of 2 revisions
2014-07-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sujoy Sinha Roy and Oscar Reparaz and Frederik Vercauteren and Ingrid Verbauwhede},
      title = {Compact and Side Channel Secure Discrete Gaussian Sampling},
      howpublished = {Cryptology ePrint Archive, Paper 2014/591},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.