A Hierarchical Parallel Discrete Gaussian Sampler for Lattice-Based Cryptography

• Discrete Gaussian sampling is one of the important components in lattice-based cryptosystems which are promising candidates for post-quantum cryptographic algorithms. For sufficient security and satisfactory performance, the Knuth-Yao algorithm is an efficient way to implement discrete Gaussian samplers. Nevertheless, most polynomials in lattice-based cryptography have 256 coefficients or more, which suffers from long latency to complete the sample generation. In this paper, the first parallel discrete Gaussian sampler with hierarchical structure is proposed, while keeping statistical distance to the actual distribution. Based on the imbalanced visiting frequency of the probability matrix, a three-stage generation strategy is adopted with hierarchical bit search units (BSUs) that can greatly reduce area consumption of the repeated costly lookup tables. Besides the architecture improvement, a lowest-set-bit scanning scheme is introduced to BSUs. Moreover, the parallelism of our design provides obfuscation ability against side-channel attacks (SCAs). A practical hardware implementation of discrete Gaussian distributions with sigma = 3.33 on the Xilinx Virtex-5 XC5VLX30 FPGA device spends 26.12 ns on average to generate 256 samples, consuming 994 slices. Results have verified its advantages of area efficiency over the state-of-the-arts (SOAs).

Subject headings

NATURVETENSKAP  -- Matematik -- Sannolikhetsteori och statistik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Probability Theory and Statistics (hsv//eng)

Keyword

Lattice-based cryptography

discrete Gaussian sampler

Knuth-Yao algorithm

FPGA implementation

Publication and Content Type

ref (subject category)

kon (subject category)