Sampling from Discrete Distributions in Combinational Hardware with Application to Post-Quantum Cryptography
Michael X. Lyonsa and Kris Gajb
Cryptographic Engineering Research Group George Mason University Fairfax, Virginia, U.S.A.
amlyons3@gmu.edu
bkgaj@gmu.edu
ABSTRACT
Random values from discrete distributions are typically generated from uniformly-random samples. A common technique is to use a cumulative distribution table (CDT) lookup for inversion sampling, but it is also possible to use Boolean functions to map a uniformly-random bit sequence into a value from a discrete distribution. This work presents a methodology for deriving such functions for any discrete distribution, encoding them in VHDL for implementation in combinational hardware, and (for moderate precision and sample space size) confirming the correctness of the produced distribution. The process is demonstrated using a discrete Gaussian distribution with a small sample space, but it is applicable to any discrete distribution with fixed parameters. Results are presented for sampling schemes from several submissions to the NIST PQC standardization process, comparing this method to CDT lookups on a Xilinx Artix-7 FPGA. The process produces compact solutions for distributions up to moderate size and precision.
Keywords: Boolean Functions, Centered binomial, Combinational Logic, Constant time, DDG-tree, Discrete Gaussian, FPGA, logic Minimization.
