Paper 2014/591

Compact and Side Channel Secure Discrete Gaussian Sampling

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

Abstract

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.

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

BibTeX

@misc{cryptoeprint:2014/591,
      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{https://eprint.iacr.org/2014/591}},
      url = {https://eprint.iacr.org/2014/591}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.