Post-Quantum Discrete Gaussian Noise Samplers
Background
At the heart of lattice-based cryptography is noise sampling, generally from discrete Gaussian distributions. These small noise samples play a crucial role in hiding information during both the key generation and encryption phases in lattice-based cryptosystems. Moreover, it has been shown that the bounded distance decoding problem underlying the Gaussian Sampling can be reduced to the Shortest Vector Problem (SVP) or Closest Vector Problem (CVP). The security reductions from these problems, i.e., SVP and CVP, form the theoretical foundation of lattice-based cryptography.
Although noise sampling could be performed using simpler distributions, e.g., uniform or binomial distributions, this would require increasing the noise levels significantly. Higher noise levels increase the complexity and lower the performance of these cryptosystems. Furthermore, many simpler distributions suffer from information leakage and weaker security guarantees. Hence, the Gaussian distribution represents a highly desirable choice for noise sampling with optimal performance and security trade-offs. Obtaining discrete Gaussian samples with high precision is challenging and non-trivial. It represents one of the main hurdles in the effort to implement a secure scheme and poses a serious bottleneck to achieving good performance in practice. High-precision floating-point arithmetic operations are required to perform a high-precision Gaussian sampling with negligible statistical distance.
Furthermore, achieving security against side-channel attacks has been recognized as an important problem. This is because developing a constant time implementation of Gaussian sampling without incurring major performance penalties is still largely an unsolved problem. Moreover, an efficient implementation of a Gaussian noise sampler without security losses remains elusive. It requires careful timing analysis of the underlying sampling algorithm so that the resulting implementation is constant-time and resistant to side-channel attacks.
Discrete Gaussian Distribution
The continuous Gaussian distribution with standard deviation σ > 0 and mean c ∈ R is defined as follows:
Let E be a random variable on R, then for x ∈ R, we have
x = height of the curve’s peak
c = position of the curve’s peak
σ = standard deviation, control’s the width of the bell
σ2 = variance
Note: Smaller the width of the bell curve, narrower will be the Gaussian distribution. This has two advantages: better proof of security and small signatures in signature schemes.
Let E be a random variable on R, then for x ∈ R, we have
Pr(E = x) =
Here,
1
σ√ 2 π
e -(x-c)2/2σ2
x = height of the curve’s peak
c = position of the curve’s peak
σ = standard deviation, control’s the width of the bell
σ2 = variance
Note: Smaller the width of the bell curve, narrower will be the Gaussian distribution. This has two advantages: better proof of security and small signatures in signature schemes.
The discrete version of the Gaussian distribution over Z with mean 0 and standard deviation σ > 0 is denoted by DZ,σ and is defined as follows:
1. Let E be a random variable on Z, then
2. Let E be a random variable on Z, then
The discrete Gaussian distribution DL,σ over a Lattice L with standard deviation σ > 0 assigns a probability proportional to as follows:
Let E be a random variable on L, then
Tail bound of the Discrete Gaussian distribution
Tail of the Gaussian distribution is infinitely long and cannot be covered by any sampling algorithm. We need to sample up to a bound known as the tail bound. A finite tail-bound introduces a statistical difference with the true Gaussian difference. So, the tail bound will depend on the maximum statistical distance allowed by the security parameters.
For any c > 1, the probability of sampling v from DZm,σ satisfies the following inequality
Precision Bound (Why true discrete Gaussian distribution is not feasible?)
The probabilities in a discrete Gaussian distribution have infinitely long binary representations and hence no algorithm can sample according to the true discrete Gaussian distribution. Secure applications require sampling with high precision to maintain negligible statistical distance from actual distribution.
Let ρz denote the true probability of sampling z ∈ Z according to the distribution Dz,σ
Assume that the sampler selects z with probability pz where |pz - ρz| < ε for some error constant ε > 0.
The statistical distance Δ to the true distribution DZm,σ is given by
Here,
ĎZm,σ is approximate discrete Gaussian distribution corresponding to the finite-precision probabilities pzover m independent samples.
Also,
Summary: Probability distribution function for discrete Gaussian distribution is given by
c = 0, i.e., Gaussian distribution centered around 0.
The advantage of assuming c = 0 is that there will be symmetry of probability density function and it is sufficient to generate samples over Z+ and use a random bit to determine the sign.
For practicality, generate samples in the interval [0, τσ] where τ is positive constant or tail-cut factor. Also, for practical reasons, the probabilities Dσ(x) are calculated only upto n-bit precision and can be denoted by Dnσ.
Sampling Algorithm: A sampling method is required to generate samples from discrete Gaussian distributions. Below are several sampling algorithms and their efficient hardware implementations.
1. Let E be a random variable on Z, then
Pr(E = Z) =
1
S
e -Z2/2σ2
Where
S = 1 + 2 ∑ ∞ Z=1
e -Z2/2σ2
and S is the normalization factor & approximately equals σ√ 2 π 2. Let E be a random variable on Z, then
Pr(E = Z) =
e -πz2/s2
Here, s > 0, s is the parameter of distribution.The discrete Gaussian distribution DL,σ over a Lattice L with standard deviation σ > 0 assigns a probability proportional to as follows:
Let E be a random variable on L, then
Pr(E = x) =
e -|x|2/2σ2
Specifically, when L = Zm, the discrete Gaussian distribution is the product distribution of m independent copies of DZ,σ.Tail bound of the Discrete Gaussian distribution
Tail of the Gaussian distribution is infinitely long and cannot be covered by any sampling algorithm. We need to sample up to a bound known as the tail bound. A finite tail-bound introduces a statistical difference with the true Gaussian difference. So, the tail bound will depend on the maximum statistical distance allowed by the security parameters.
For any c > 1, the probability of sampling v from DZm,σ satisfies the following inequality
Pr(|v| > cσ√m) =
cme (m/2)(1-c)2
Precision Bound (Why true discrete Gaussian distribution is not feasible?)
The probabilities in a discrete Gaussian distribution have infinitely long binary representations and hence no algorithm can sample according to the true discrete Gaussian distribution. Secure applications require sampling with high precision to maintain negligible statistical distance from actual distribution.
Let ρz denote the true probability of sampling z ∈ Z according to the distribution Dz,σ
Assume that the sampler selects z with probability pz where |pz - ρz| < ε for some error constant ε > 0.
The statistical distance Δ to the true distribution DZm,σ is given by
Δ(ĎZm,σ, DZm,σ) < 2-k + 2mzt∊
Here,
ĎZm,σ is approximate discrete Gaussian distribution corresponding to the finite-precision probabilities pzover m independent samples.
Also,
Pr(|v| > zt : v ← DZm,σ) < 2-k represents the tail bound and k is the security parameter (cryptographic scheme will be k-1 bit secure).
Summary: Probability distribution function for discrete Gaussian distribution is given by
Dσ(x = z) =
Here, x = random variable defined over Z
1
σ√ 2 π
e -(z-c)2/2σ2
c = 0, i.e., Gaussian distribution centered around 0.
The advantage of assuming c = 0 is that there will be symmetry of probability density function and it is sufficient to generate samples over Z+ and use a random bit to determine the sign.
For practicality, generate samples in the interval [0, τσ] where τ is positive constant or tail-cut factor. Also, for practical reasons, the probabilities Dσ(x) are calculated only upto n-bit precision and can be denoted by Dnσ.
Sampling Algorithm: A sampling method is required to generate samples from discrete Gaussian distributions. Below are several sampling algorithms and their efficient hardware implementations.
Box-Muller Sampling
The Box-Muller sampling method is based on the BoxMuller transform proposed by Box and Muller. A basic form of Box-Muller transform takes two samples from the uniform distribution on the interval [0, 1] and maps them to two standard Gaussian distributed samples. The first algorithm shows how the Box-Muller sampling works. Input to the algorithm is the standard deviation σ for desired probability distribution. Steps 1 and 2 generate two samples uniformly at random from the interval [0, 1]. In step 4 and 5, the required computations are performed to map the samples from the uniform distribution to the required Gaussian distribution. At every iteration, the algorithm generates two samples x and y as an output.
Rejection Sampling
Rejection sampling is a basic technique used to generate samples from a given probability distribution. It is also called an “acceptance-rejection” method or “accept-reject algorithm”. The principle behind rejection sampling is based on the observation that to sample a random variable in one dimension, a uniformly random sampling from the interval [0, 1] can be performed and the samples that fall under the required density function graph can be retained. Rejection sampling algorithm works as shown in algorithm below.
Ziggurat Sampling
Marsaglia and Tsang developed the Ziggurat transform method for sampling from decreasing densities. The method is based on covering the target density with a set of horizontal equal-area rectangles, a cap and a tail. The Ziggurat title came from the appearance of the layered rectangles. Ziggurats are ancient Mesopotamian terraced temple mounds that, mathematically, are two-dimensional step functions. A one-dimensional ziggurat underlies Marsaglia’s algorithm.
Hardware Implementation Notes
We are also providing the highly optimized and efficient hardware implementation of Box-Muller, rejection, and Ziggurat sampling algorithms over a Gaussian probability distribution. The design implementation is constant-time with high-precision sampling making it post-quantum secure and resistant to side-channel attacks.
A parameterized design implementation of all three sampling algorithms provides an opportunity to plug them in easily to any existing or future cryptosystems. Evaluation of hardware cost, sampling efficiency, and throughput provided useful insights on the best sampling algorithm to use for practical purposes.
A parameterized design implementation of all three sampling algorithms provides an opportunity to plug them in easily to any existing or future cryptosystems. Evaluation of hardware cost, sampling efficiency, and throughput provided useful insights on the best sampling algorithm to use for practical purposes.
Community Note
Based on the evaluations and the associated observations, we are making the following recommendations:
Based on the evaluations and the associated observations, we are making the following recommendations:
- Box-Muller sampling has the highest sampling efficiency and throughput but also has the highest resource utilization. Thus, use of Box-Muller sampling is the best choice when there is no resource constraint and sampling efficiency is the main criterion for an application.
- Rejection sampling has the lowest resource utilization and can be used in applications where resource (memory/area) is a constraint and only a few samples need to generated. Although, a trade off on sampling efficiency and throughput will have to be made if large number of samples are required.
- The Ziggurat sampling method is optimal in terms of both the resource utilization and sampling efficiency. The choice of using Ziggurat sampling can be made irrespective of the resource utilization or sampling efficiency trade-offs. The research community, at large, can benefit from these useful insights and in turn will be able to make an appropriate choice of Gaussian Noise Sample for their own applications.
Hardware Downloads
A zip file of the source code for this project is available for download by clicking on the download sign on the right. First, we would like to thank our sponsors who have generously supported these efforts for multiple years now. Second, many thanks to the STAM Center researchers and students, both present and former, who have contributed to the code base. These are open-source projects provided under the MIT License.
One can also access the project code through the github directory by clicking on the github icon.
