Cryptology ePrint Archive: Report 2014/591

Compact and Side Channel Secure Discrete Gaussian Sampling

Sujoy Sinha Roy and Oscar Reparaz and 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.

Category / Keywords: Lattice-based cryptography, Discrete Gaussian Sampler, Hardware implementation, Knuth-Yao algorithm, Discrete distribution generating (DDG) tree, Side channel analysis

Date: received 30 Jul 2014, last revised 1 Oct 2014

Contact author: sujoy sinharoy at esat kuleuven be

Available format(s): PDF | BibTeX Citation

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

Version: 20141001:063822 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]