Arbitrary-Centered Discrete Gaussian Sampling over the Integers

Abstract

Discrete Gaussian sampling over the integers, which is to sample from a discrete Gaussian distribution $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ over the integers $\mathbb {Z}$ with parameter $\sigma >0$ and center $\mu \in \mathbb {R}$, is one of fundamental operations in lattice-based cryptography. The sampling algorithm should support a varying center $\mu$ and even a varying parameter $\sigma$, when it is used as one of the subroutines in an algorithm for sampling trapdoor lattices, or sampling from Gaussian distributions over a general n-dimensional lattice $\varLambda$. In this paper, combining the techniques in Karney’s algorithm for exactly sampling the standard normal distribution, we present an exact sampling algorithm for $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ with an integer-valued parameter $\sigma$. This algorithm requires no pre-computation storage, uses no floating-point arithmetic, supports centers of arbitrary precision, and does not have any statistical discrepancy. Applying the convolution-like property of discrete Gaussian distributions, we also present an approximated sampling algorithm for $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ with a real-valued parameter $\sigma$. It also supports centers of arbitrary precision, and we show that the distribution it produces has a smaller max-log distance to the ideal distribution, as compared to Micciancio-Walter sampling algorithm, which was introduced by Micciancio et al. in Crypto 2017 for discrete Gaussian distributions with varying $\sigma$ and $\mu$ over the integers.

This work was supported by National Key R&D Program of China (2017YFB0802500), National Natural Science Foundations of China (Grant Nos. 61672550, 61972431), Guangdong Major Project of Basic and Applied Research (2019B030302008), Guangdong Basic and Applied Basic Research Foundation (No. 2020A1515010687) and the Fundamental Research Funds for the Central Universities (Grant No. 19lgpy217).

1 Introduction

Lattice-based cryptography has been accepted as a promising candidate for public key cryptography in the age of quantum computing. Discrete Gaussian sampling, which is to sample from a discrete Gaussian distribution $\mathcal {D}_{\varLambda ,\sigma ,\mathbf {c}}$ with parameter $\sigma >0$ and center $\mathbf {c}\in \mathbb {R}^n$ over an n-dimensional lattice $\varLambda$, plays a fundamental role in lattice-based cryptography. Discrete Gaussian sampling is not only one of the fundamental operations in many lattice-based cryptosystems but is also at the core of security proofs of these cryptosystems [10, 18, 21]. It has been considered by the cryptography research community as one of the fundamental building blocks of lattice-based cryptography [19, 20, 22, 24].

An important sub-problem of discrete Gaussian sampling, which is denoted by $\mathrm {Sample}\mathbb {Z}$, is to sample from a discrete Gaussian distribution $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ over the integers $\mathbb {Z}$ with parameter $\sigma >0$ and center $\mu \in \mathbb {R}$. Since $\mathrm {Sample}\mathbb {Z}$ is much more efficient and simpler than sampling from discrete Gaussian sampling over a general lattice, the operations involving discrete Gaussian sampling in some lattice-based cryptosystems such as [6, 23, 27] are nothing but $\mathrm {Sample}\mathbb {Z}$. A good sampling algorithm for a discrete Gaussian distribution (not necessarily over the integers $\mathbb {Z}$) should not only be efficient, but also have a negligible statistical discrepancy with the target distribution. Therefore, how to design and implement good sampling algorithms for discrete Gaussian distributions over the integers has received a lot of attentions in recent years.

The commonly used methods (techniques) for $\mathrm {Sample}\mathbb {Z}$ are the inversion sampling (using a cumulative distribution table, CDT) [24], the Knuth-Yao method (using a discrete distribution generating (DDG) tree) [7, 28], the rejection sampling [6, 10, 16], and the convolution technique [22, 25] (based on the convolution-like properties of discrete Gaussian distributions developed by Peikert in [24]).

The first $\mathrm {Sample}\mathbb {Z}$ algorithm, which was given by Gentry et al. in [10], uses rejection sampling. Although this algorithm supports varying parameters (including $\mu$ and $\sigma$), it is not very efficient, since it requires about 10 trials on average before outputting an integer in order to get a negligible statistical distance to the target discrete Gaussian distribution.¹

Most of improved $\mathrm {Sample}\mathbb {Z}$ algorithms are designed only for the case where center $\mu$ is fixed in advance, such as [6, 11, 14, 15, 28, 29]. It is necessary to consider generic $\mathrm {Sample}\mathbb {Z}$ algorithms that support varying parameters. Sampling from discrete Gaussian distributions over the integers is also usually one of the subroutines in discrete Gaussian sampling algorithms for distributions over a general n-dimensional lattice $\varLambda$. Examples include the $\mathrm {Sample}\mathbb {D}$ algorithm [10] for distributions over an n-dimensional lattice of a basis $\mathbf {B}\in \mathbb {R}^n$, Peikert’s algorithm for distributions over a q-ary integer lattice $\varLambda \subseteq \mathbb {Z}^n$ [24], and Gaussian sampling algorithms for trapdoor lattices [9, 20]. A $\mathrm {Sample}\mathbb {Z}$ algorithm should support a varying center $\mu$, and even a varying parameter $\sigma$, if it is used in these cases.

1.1 Related Work

In 2016, Karney proposed an algorithm for sampling exactly (without statistical discrepancy) from a discrete Gaussian distribution over the integers $\mathbb {Z}$ [16]. This algorithm uses no floating-point arithmetic and does not need any precomputation storage. It allows the parameters (including $\sigma$ and $\mu$) to be arbitrary rational numbers of finite precision. This may be the second generic $\mathrm {Sample}\mathbb {Z}$ algorithm since the one given by Gentry et al. in [10].

In 2017, Micciancio and Walter developed a new $\mathrm {Sample}\mathbb {Z}$ algorithm [22]. We call this algorithm Micciancio-Walter sampling algorithm. It extends and generalizes the techniques that were used in the sampler proposed by Pöeppelmann et al. [25]. Micciancio-Walter algorithm is also generic, i.e., it can be used to sample from discrete Gaussian distributions with arbitrary and varying parameters of specified (finite) precision. Moreover, Aguilar-Melchor et al. also designed a non-centered CDT algorithm with reduced size of precomputation tables [1].

More recently, it was suggested that the Bernoulli sampling, introduced by Ducas et al. in [6] for centered discrete Gaussian distributions over the integers, could be improved by using the polynomial approximation technique. Specifically, the rejection operation in the Bernoulli sampling can be performed very efficiently by using an approximated polynomial [3, 32]. The polynomial (its coefficients) can be determined in advance, and it also allows us to sample from Gaussian distributions with a varying center $\mu \in [0,1)$. Combining the convolution-like property of discrete Gaussian distributions [22, 24, 25], a non-centered Bernoulli sampling could be further extended to a generic sampling algorithm for any discrete Gaussian distribution over the integers. Howe et al. further presented a modular framework [12] for generating discrete Gaussians with arbitrary and varying parameters, which incorporates rejection sampling, the polynomial approximation technique, and the sampling technique used in Falcon signature [27].

Another alternative method of discrete Gaussian sampling over the integers is to sample from the (continuous) standard normal distribution, and then obtain the samples of discrete Gaussian distributions by rejection sampling [31]. This method is very efficient and supports discrete Gaussian distributions with arbitrary and varying parameters, although it relies on floating-point arithmetic (even involving logarithmic function and trigonometric function due to sampling from the standard normal distribution). In fact, a more simple and efficient method is to replace discrete Gaussians with rounded Gaussians [13], which are the nearest integers of sample values from the continuous normal distribution, but the security analysis of rounded Gaussians is only confined to the cryptosystems like Bliss signature.

Except Karney’s sampling algorithm, the existing algorithms for sampling from $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ with varying parameters, either rely on floating-point arithmetic, such as the algorithms in [10, 32], or require a large amount of precomputation storage, such as Micciancio-Walter sampling algorithm [22] and the one given by Aguilar-Melchor et al. [1]. The sampler presented by Barthe et al. in [3] supports a varying $\mu \in \mathbb {R}$ but not a varying parameters $\sigma$. It needs to perform another polynomial approximation procedure for the new $\sigma$.

Furthermore, except Karney’s sampling algorithm, those algorithms mentioned above are all the approximated algorithms, which only produce samples approximately from the target distribution. They usually involve complicated and careful security analysis based on statistical measures (e.g. Rényi divergence [2, 26], max-log distance [22], relative error [30]), since attaining a negligible statistical measure to the ideal Gaussian distribution may be crucial for lattice-based cryptography, especially for signatures [17] and lattice trapdoors [10], to provide zero-knowledgeness. Therefore, it is interesting to consider exact sampling algorithms in lattice-based cryptography. The security analysis based on statistical measures for exact algorithms can be simplified or even be omitted.

1.2 Our Contribution

On one hand, we note that Karney’s sampling algorithm [16] is exact sampling algorithm, but it allows only the case where $\sigma$ and $\mu$ are rational numbers of specified (finite) precision. In this paper, for an integer-valued parameter $\sigma$, we present an exact sampling algorithm for $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$. This algorithm requires no pre-computation storage, uses no floating-point arithmetic and supports a varying $\mu$ of arbitrary precision. On the other hand, although Micciancio-Walter sampling algorithm [22] supports varying parameters (including $\mu$ and $\sigma$) with specified (finite) precision, its base sampler requires a large amount of precomputation storage. Based on our proposed exact algorithm, applying the convolution-like property of discrete Gaussian distributions we give an approximated sampling algorithm for $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ with a real-valued parameter $\sigma$. It requires no pre-computation storage, and supports a varying $\mu$ of arbitrary precision. We show that the distribution it produces has a smaller max-log distance to the ideal distribution $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$, as compared to the distribution produced by Micciancio-Walter sampling algorithm.

1.3 Techniques

Let $\sigma$ be a positive integer, $\mu \in [0,1)$ be a real number of arbitrary precision, and x be a non-negative integer. We give an algorithm for exactly generating a Bernoulli random value which is true with probability

$$\exp \left( -t\frac{2x+t}{2x+2}\right) ,$$

where t is in the form of $(y-s\mu )/{\sigma }$, $s\in \{-1,1\}$, and y is an integer taken uniformly from $[(1+s)/2,\sigma +(1+s)/2)$. In our exact sampling algorithm for discrete Gaussian distributions, which is based on the rejection sampling, we show that the rejection operation can be performed by repeatedly using this algorithm of generating the Bernoulli random value.

In fact, this algorithm is adapted from Karney’s algorithm for exactly generating the Bernoulli random value (see Algorithm B in [16]). Karney also used it as the rejection operation in his algorithm for standard normal distribution as well as discrete Gaussian distributions over the integers. However, t is only regarded as a random deviate from [0, 1) in Karney’s algorithm. The value of t corresponds exactly to the fraction part of the prospective output and can be obtained directly as a random number in case of standard normal distribution, while the determination of the value of t in the case of discrete Gaussian distributions needs the computation with respect to the parameters $\sigma$ and $\mu$. In order to maintain the exactness, $\mu$ is only allowed to be a rational number for sampling from discrete Gaussian distributions, which limits the functionality of Karney’s algorithm.

2 Preliminaries

2.1 Notation

We denote the set of real numbers by $\mathbb {R}$, the set of integers by $\mathbb {Z}$, and the set of non-negative integers by $\mathbb {Z}^{+}$. We extend any real function $f(\cdot )$ to a countable set A by defining $f(A)=\sum _{x\in A}f(x)$ if it exists. The Gaussian function on $\mathbb {R}$ with parameter $\sigma >0$ and $\mu \in \mathbb {R}$ evaluated at $x\in \mathbb {R}$ can be defined by $\rho _{\sigma ,\mu }(x)=\exp {\left( -\frac{(x-\mu )^2}{2\sigma ^2}\right) }$. For real $\sigma >0$ and $\mu \in \mathbb {R}$, the discrete Gaussian distribution over $\mathbb {Z}$ is defined by $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }(x)={\rho _{\sigma ,\mu }(x)}/{\rho _{\sigma ,\mu }(\mathbb {Z})}$ for $x\in \mathbb {Z}$. Similarly, a discrete Gaussian distribution over $\mathbb {Z}^+$ is defined by $\mathcal {D}_{\mathbb {Z}^+,\sigma }(x)={\rho _{\sigma ,\mu }(x)}/{\rho _{\sigma ,\mu }(\mathbb {Z}^+)}$. By convention, the subscript $\mu$ is omitted when it is taken to be 0.

2.2 Rejection Sampling

Rejection sampling is a basic method (technique) used to generate observations from a distribution [5]. It generates sampling values from a target distribution X with arbitrary probability density function f(x) by using a proposal distribution Y with probability density function g(x). The basic idea is that one generates a sample value from X by instead sampling from Y and accepting the sample from Y with probability

$$f(x)/Mg(x),$$

repeating the draws from Y until a value is accepted, where M is a constant such that $f(x)\le Mg(x)$ for all values of x in the support of X. If $f(x)\le Mg(x)$ for all x then the rejection sampling procedure produces exactly, with enough replicates, the distribution of X. In fact, f(x) is allowed to be only a relative probability density function. Rejection sampling can be used to sample from a distribution X whose normalizing constant is unknown as long as the support of Y includes the support of x.

2.3 Karney’s Algorithm

Karney’s exact sampling algorithm for discrete Gaussian distributions, which is described as Algorithm 1, uses rejection sampling, and it is a discretization of his algorithm for sampling exactly from the normal distribution. Here, parameter $\sigma$ and $\mu$ are in the set of rational numbers $\mathbb {Q}$.

From the perspective of rejection sampling, in Algorithm 1, we can see that step 1 and step 2 together form a rejection sampling procedure, which generates $k\in \mathbb {Z}^+$ according to

$$\mathcal {D}_{\mathbb {Z}^+,1}(k)={\rho _{1}(k)}/{\rho _{1}(\mathbb {Z}^+)},$$

which is a discrete Gaussian distribution over the set of non-negative integers $\mathbb {Z}^+$. Then, the proposal distribution for the whole algorithm can be written as

$$g(z)=g(s(\lceil k\sigma +s\mu \rceil +j))=\rho _1(k)/(2\lceil \sigma \rceil \rho _1(\mathbb {Z}^{+}))$$

with $z=s(\lceil k\sigma +s\mu \rceil +j)$. The algorithm accepts z as the returned value with probability $e^{-\frac{1}{2}x(2k+x)}$, where $x=(\lceil k\sigma +s\mu \rceil -(k\sigma +s\mu )+j)/\sigma <1$. It is not hard to see that

$$\rho _1(k)\cdot \exp (-\frac{1}{2}x(2k+x))=\exp (-\frac{(\lceil k\sigma +s\mu \rceil +j-s\mu )^2}{2\sigma ^2})=\rho _{\sigma ,\mu }(z),$$

which guarantees the correctness of Algorithm 1.

In Algorithm 1, in order to exactly sample $k\in \mathbb {Z}^{+}$ with (relative) probability density $\rho _{1}(k)=\exp ({-k^2}/{2})$, Karney also gave an algorithm for exactly generating a Bernoulli random value which is true with probability $1/\sqrt{e}$. Specifically, one needs $(k+1)$ Bernoulli random values from $\mathcal {B}_{1/\sqrt{e}}$ to select an integer $k\ge 0$ with probability $\exp (-k/2)\cdot (1-\exp (-1/2))$ (step 1), then continues to generate $k(k-1)$ Bernoulli random values from $\mathcal {B}_{1/\sqrt{e}}$ to accept k with probability $\exp \left( -\frac{1}{2}k(k-1)\right)$ (step 2). Karney’s algorithm for exactly generating a Bernoulli random value which is true with probability $1/\sqrt{e}$ is adapted from Von Neummann’s algorithm for exactly sampling from the exponential distribution $e^{-x}$ for real $x > 0$ (see Algorithm V and Algorihtm H in [16]).

In Algorithm 1, step 8 is implemented by using a specifically designed algorithm so that it produces no any statistical discrepancy, and we will discuss this algorithm in Sect. 3.

3 Sampling from Arbitrary-Centered Discrete Gaussians

Algorithm 2 is our proposed algorithm for sampling from arbitrary-centered discrete Gaussian distributions. We give the proof of its correctness.

Theorem 1

The integer $z\in \mathbb {Z}$ output by Algorithm 2 is exactly from the discrete Gaussian distribution $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ with an integer-valued $\sigma$ and a real-valued $\mu$ of arbitrary precision, if the probability

$$\exp \left( -\frac{(y-s\mu )^2+2\sigma x(y-s\mu )}{2\sigma ^2}\right) $$

can be calculated exactly.

Proof

From the perspective of rejection sampling, following Karney’s approach (step 1 and 2 in Algorithm 1), we generate an integer x exactly from $\mathcal {D}_{\mathbb {Z}^+,1}(x)=\rho _{1}(x)/\rho _{1}(\mathbb {Z}^+)$, and use $\mathcal {D}_{\mathbb {Z}^+,1}$ as the proposal distribution. For a given positive integer $\sigma$, any $z\in \mathbb {Z}$ can be uniquely written as

$$z=s\left( \sigma x+y+\frac{1+s}{2}\right) ,$$

where $s\in \{-1,1\}$, and x, y are integers such that $x\ge 0$ and $y\in [0,\sigma )$. This guarantees that the support of the distribution produced by Algorithm 2 is the set of all the integers. For simplicity, we set $y\leftarrow y+1$ if $s=1$. Then, $z=s(\sigma x+y)$ and the target distribution density function f(z) for $z\in \mathbb {Z}$ can be written as

$$f(z)=f(s(\sigma x+y))=\frac{\rho _{\sigma ,\mu }(s(\sigma x+y))}{\rho _{\sigma ,\mu }(\mathbb {Z})}.$$

In Algorithm 2, for a given integer x exactly from $\mathcal {D}_{\mathbb {Z}^+,1}$, we sample $s\leftarrow \pm 1$ with equal probabilities, take $z=s(\sigma x+y)$, and then accept the value of z as the returned value with probability $\exp \left( -((y-s\mu )^2+2\sigma x(y-s\mu ))/(2\sigma ^2)\right)$. It is not hard to see that

$$\begin{aligned} \rho _{1}(x)\cdot \exp \left( -\frac{(y-s\mu )^2+2\sigma x(y-s\mu )}{2\sigma ^2}\right)= & {} \exp \left( -\frac{(\sigma x+y-s\mu )^2}{2\sigma ^2}\right) \\= & {} \exp \left( -\frac{(s(\sigma x+y)-\mu )^2}{2\sigma ^2}\right) \\= & {} \rho _{\sigma ,\mu }(s(\sigma x+y)), \end{aligned}$$

which is proportional to the desired (relative) probability density. This implies that the probability of Algorithm 2 going back to step 1 is equal to a constant,

$$1-\left( 1-\exp (-1/2)\right) \sum _{z=-\infty }^{+\infty }\rho _{\sigma ,\mu }(z)=1-\left( 1-\exp (-1/2)\right) \rho _{\sigma ,\mu }(\mathbb {Z}).$$

We denote by $Q_\infty$ this constant and let $q(z)=(1-\exp (-1/2))\cdot \rho _{\sigma ,\mu }(z)$. Then, the probability that Algorithm 2 outputs an integer $z\in \mathbb {Z}$ can be given by

$$q(z)+q(z)Q_{\infty }+\ldots +q(z)Q_{\infty }^i+\ldots ={q(z)}\cdot \sum _{i=0}^\infty {Q_{\infty }^i}=\frac{\rho _{\sigma ,\mu }(z)}{\rho _{\sigma ,\mu }(\mathbb {Z})},$$

which shows the correctness of Algorithm 2. Since all the operations, including computing the value of probability

$$\exp \left( -\frac{(y-s\mu )^2+2\sigma x(y-s\mu )}{2\sigma ^2}\right) ,$$

can be performed without any statistical discrepancy, and thus Algorithm 2 produces exactly the discrete Gaussian distribution $\mathcal {D}_{\mathbb {Z},\sigma , \mu }$.    $\square$

The most important problem of Algorithm 2 is to compute exaclty the value of the exponential function for a real-valued $\mu$ of arbitrary precision, and get a Bernoulli random value which is true with probability of this value. Addressing this problem is based on the following observation.

$$\begin{aligned}&{\exp \left( -\frac{(y-s\mu )^2+2\sigma x(y-s\mu )}{2\sigma ^2}\right) } \\&\qquad \qquad =\exp \left( -\frac{1}{2}\left( \frac{y-s\mu }{\sigma }\right) \left( 2x+\frac{y-s\mu }{\sigma }\right) \right) \\&\qquad \qquad =\left( \exp \left( -\frac{1}{2}\left( \frac{y-s\mu }{\sigma }\right) \left( \frac{2x+(y-s\mu )/\sigma }{x+1}\right) \right) \right) ^{x+1}\\&\qquad \qquad =\left( \exp \left( -\left( \frac{y-s\mu }{\sigma }\right) \left( \frac{2x+(y-s\mu )/\sigma }{2x+2}\right) \right) \right) ^{x+1}\\&\qquad \qquad =\left( \exp \left( -\tilde{y}\left( \frac{2x+\tilde{y}}{2x+2}\right) \right) \right) ^{x+1},\\ \end{aligned}$$

where $\tilde{y}=(y-s\mu )/\sigma$ and $0\le \tilde{y}<1$. Therefore, we can repeatedly sample from the Bernoulli distribution $\mathcal {B}_p$ a total of $x+1$ times to obtain a Bernoulli random value which is true with our desired probability, where

$$p=\exp \left( -\tilde{y}\left( \frac{2x+\tilde{y}}{2x+2}\right) \right) .$$

Sampling the Bernoulli distribution $\mathcal {B}_p$ can be accomplished by using Algorithm 3, which was proposed by Karney in [16]. The function C(m) with $m=2x+2$ in Algorithm 3 is a random selector that outputs $-1$, 0 and 1 with probability 1/m, 1/m and $1-2/m$ respectively.

The main idea is to sample two sets of uniform deviates $v_1, v_2, \ldots$ and $w_1, w_2, \ldots$ from [0, 1), and to determine the maximum value $n\ge 0$ such that

$$t>v_1>v_2>\ldots >v_n \quad \text{ and }\quad w_i<(2x+t)/(2x+2)\quad \text{ for } i=1,2,\ldots ,n.$$

If n is even, it returns true, and the probability is exactly equal to

$$1-t\left( \frac{2x+t}{2x+2}\right) +\frac{t^2}{2!}\left( \frac{2x+t}{2x+2}\right) ^2-\frac{t^3}{3!}\left( \frac{2x+t}{2x+2}\right) ^3+\ldots =\exp \left( -t\frac{2x+t}{2x+2}\right) .$$

This follows from the Taylor expansion of the exponential function. Then, applying this procedure at most $k+1$ times, one can obtain a Bernoulli random value which is true with probability $\exp \left( -\frac{1}{2}t(2x+t)\right)$ for given x and t. Taking

$$t=\tilde{y}=\frac{y-s\mu }{\sigma }$$

and applying Algorithm 3, we can sample from the Bernoulli distribution $\mathcal {B}_{p}$ with $p=\exp \left( -\tilde{y}\left( (2x+\tilde{y})/(2x+2)\right) \right)$.

The remaining issue is that we need to compare $\tilde{y}$ with a randomly generated deviate in [0, 1), but do not use floating-point arithmetic. This can guarantee the exactness. We observe that any real $u\in [0,1)$ of arbitrary precision can be represented by

$$u=\frac{j-sr}{\sigma }$$

with given $\sigma$ and s, where j is an integer from $[(1+s)/2,\sigma +(1+s)/2)$ and $r\in [0,1)$ is a real number of arbitrary precision. Then, we can do the comparison as follows.

Fig. 1.

Comparing $u=(j-r)/\sigma$ with $(y-\mu )/\sigma$

To obtain a randomly generated deviate in the form of $u=(j-sr)/\sigma \in [0,1)$, we sample j uniformly in $\{0,1,2,\cdots ,\sigma -1\}$, sample a uniform deviate $r\in [0,1)$ and set $j=j+1$ if $s=1$. To compare a randomly generated deviate $u=(j-sr)/\sigma$ with a given $(y-s\mu )/\sigma$, we compare j with y firstly and return the result if they are not equal. Otherwise, we compare r with $\mu$ to complete the whole procedure. Figure 1 shows the above idea in the case of $s=1$. We summarize the whole procedure of comparison in Algorithm 4.

Note that comparing r with $\mu$ can be realized without floating-point arithmetic through bitwise operations. This implies that Algorithm 4 allows $\mu$ to be a real number of arbitrary precision and there is no case where $r=\mu$. Specifically, following the implementation of Karney’s algorithm for random numbers of arbitrary precision, the comparison of two deviates is realized digit-by-digit, and each digit of a deviate is generated online according to the actual needs. To determine the relation between r and $\mu$, we take the first digit of r and $\mu$, respectively, denoted by $r_{1}$ and $\mu _{1}$. If $r_{1}$ or $\mu _{1}$ does not exist, then we generate it uniformly online. If $r_{1}$ and $\mu _{1}$ are equal, then we take the second digit of r and $\mu$, namely $r_{2}$ and $\mu _{2}$, and continue to compare them. In fact, one digit could consist of only one bit or a small number of bits, such as 4 bits, 8 bits or 16 bits. We call the number of bits in each digit the digit size, which can be specified in the source code in advance.

Finally, if each random deviate in [0, 1) used in Algorithm 3 is handled in the form of $u=(j-sr)/\sigma$, then Algorithm 3 allows $\mu$ to be a real number of arbitrary precision, and we can implement it without floating-point arithmetic.

4 Applying the Convolution-Like Property

In this section, we try to extend Algorithm 2 to the case of discrete Gaussian distributions with arbitrary parameters (including $\sigma$ and $\mu$) by using the convolution-like property of discrete Gaussian distributions.

Informally, for a Gaussian distribution with a relatively large standard deviation $\sigma$, we compute two samples $x_1$ and $x_2$ with smaller variances $\sigma _1^2$ and $\sigma _2^2$. We hope that their combination $x_1+c\cdot x_2$ with a constant c is Gaussian with variance $\sigma _1^2+c\cdot \sigma _2^2$. Although this is not generally the case for discrete Gaussian distributions, Peikert showed that the distribution of $x_1+c\cdot x_2$ is statistically close to discrete Gaussian distribution with variance $\sigma _1^2+c\cdot \sigma _2^2$ under certain conditions with respect to the smoothing parameter of lattices [24]. This observation was called by Peikert the convolution-like property of discrete Gaussian distributions.

Definition 1

(a special case of [21], Definition 3.1). Let $\epsilon >0$ be a positive real. The smoothing parameter of lattice $\mathbb {Z}$, denoted by $\eta _\epsilon (\mathbb {Z})$, is defined to be the smallest real s such that $\rho _{1/s}(\mathbb {Z}\setminus \{0\})\le \epsilon$.

Lemma 1

(Adapted from Lemma 3.3 [21]). For any real $\epsilon >0$, the smoothing parameter of lattice $\mathbb {Z}$ satisfies² $\eta _\epsilon (\mathbb {Z})\le \sqrt{\ln (2(1+1/\epsilon ))/2}/\pi$.

Here, we apply the conclusion described by Micciancio and Walter in [22] about the convolution-like property, since it deals with non-centered discrete Gaussian over the integers $\mathbb {Z}$ and uses a more cryptographically efficient measure of closeness between probability distributions, named the max-log distance.

Definition 2

[22]. The max-log distance between two distributions $\mathcal {P}$ and $\mathcal {Q}$ over the same support S is $\varDelta _\mathrm {ML}(\mathcal {P},\mathcal {Q})=\max _{x\in S}|\ln \mathcal {P}(x)-\ln \mathcal {Q}(x)|$.

Lemma 2

(Corollary 4.2 in [22]). Let $\sigma _1, \sigma _2>0$, $\sigma ^2=\sigma _1^2+\sigma _2^2$ and $\sigma _3^{-2}=\sigma _1^{-2}+\sigma _2^{-2}$. Let $\varLambda =h\cdot \mathbb {Z}$ be a copy of the integer lattice $\mathbb {Z}$ scaled by a constant h. For any $\mu _1$ and $\mu _2\in \mathbb {R}$, we denote by $\tilde{\mathcal {D}}_{\mu _1+\mathbb {Z},\sigma }$ the distribution of

$$x_1\leftarrow x_2+\tilde{\mathcal {D}}_{\mu _1-x_2+\mathbb {Z},\sigma _1}\quad \text{ with }\quad x_2\leftarrow \tilde{\mathcal {D}}_{\mu _2+\varLambda ,\sigma _2}.$$

If $\sigma _1\ge \eta _\epsilon (\mathbb {Z})$, $\sigma _3\ge \eta _\epsilon (\varLambda )=h\cdot \eta _\epsilon (\mathbb {Z})$, $\varDelta _\mathrm {ML}(\mathcal {D}_{\mu _2+\varLambda ,\sigma _2},\tilde{\mathcal {D}}_{\mu _2+\varLambda ,\sigma _2})\le \epsilon _2$ and $\varDelta _\mathrm {ML}(\mathcal {D}_{\mu +\mathbb {Z},\sigma _1},\tilde{\mathcal {D}}_{\mu +\mathbb {Z},\sigma _1})\le \epsilon _1$ for any $\mu \in \mathbb {R}$, then

$$\varDelta _\mathrm {ML}(\mathcal {D}_{\mu _1+\mathbb {Z},\sigma },\tilde{\mathcal {D}}_{\mu _1+\mathbb {Z},\sigma })\le 4\epsilon +\epsilon _1+\epsilon _2,$$

where $\epsilon _1$ and $\epsilon _2$ are positive real numbers.

Definition 3

(Randomized rounding operator $\lfloor \cdot \rceil _\lambda$ [22]). For $\mu \in [0,1)$ and a positive integer $\lambda$, the randomized rounding operator $\lfloor \mu \rceil _\lambda$ is defined by

$$\lfloor \mu \rceil _\lambda =\lfloor 2^\lambda \mu \rfloor /2^\lambda +B_\alpha /2^\lambda $$

with a Bernoulli random variable $B_\alpha$ of parameter $\alpha =2^\lambda \mu -\lfloor 2^\lambda \mu \rfloor$. In particular, if $\mu >1$ then

$$\mu ^\prime \leftarrow \lfloor \mu \rfloor +\lfloor \{\mu \}\rceil _\lambda ,$$

where $\lfloor \mu \rfloor$ and $\{\mu \}$ is the integer part and the fractional part of $\mu$ respectively.

Lemma 3

(Adapted from Lemma 5.3 in [22]). Let $\lambda >\log _2{4\pi }$ be a positive integer and $b=2^\lambda$. If $\sigma \ge \eta _\epsilon (\mathbb {Z})$, then

$$\varDelta _\mathrm {ML}(\mathcal {D}_{\mathbb {Z},\sigma ,\mu },\tilde{\mathcal {D}}_{\mathbb {Z},\sigma ,\lfloor \mu \rceil _\lambda })\le (\pi /b)^2+2\epsilon ,$$

where $\lfloor \cdot \rceil _\lambda$ is the randomized rounding operator as defined above.

Combining our proposed exact algorithm (Algorithm 2), and applying the convolution-like property, namely Lemma 2, we give Algorithm 5.

Theorem 2 gives the correctness of Algorithm 5 and estimates the (theoretical) max-log distance between the distribution $\tilde{\mathcal {D}}_{\mathbb {Z},\sigma , \mu }$ produced by Algorithm 5 and the ideal distribution $\mathcal {D}_{\mathbb {Z},\sigma , \mu }$. The equation that

$$\mu +\mathcal {D}_{-\mu +\mathbb {Z},\sigma }=\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$$

for any $\sigma >0$ and $\mu \in \mathbb {R}$ will be repeatedly used in the proof.

Theorem 2

Let $\lambda >\log _2{4\pi }$ be a positive integer and $b=2^\lambda$. Denote by $\tilde{\mathcal {D}}_{\mathbb {Z},\sigma , \mu }$ the probability distribution of integers that are output by Algorithm 5. If $\lfloor \sigma \rfloor >\eta _\epsilon (\mathbb {Z})$ and $\eta _\epsilon (\mathbb {Z})$ is taken to be a rational number, then we have

$$\varDelta _\mathrm {ML}(\mathcal {D}_{\mathbb {Z},\sigma , \mu },\tilde{\mathcal {D}}_{\mathbb {Z},\sigma , \mu })\le (\pi /b)^2+6\epsilon ,$$

by using Algorithm 1 in step 1, and using Algorithm 2 in step 4.

Proof

Let $\sigma _1=\lfloor \sigma \rfloor$ and $\sigma _2=2h\eta _\epsilon (\mathbb {Z})$. Then, we have $\sigma ^2=\sigma _1^2+\sigma _2^2$ and

$$\sigma _3=\left( \sigma _1^{-2}+(2h\eta _\epsilon (\mathbb {Z}))^{-2}\right) ^{-1/2}=\frac{\sigma _1}{\sigma }\cdot \sqrt{\sigma ^2-\sigma _1^2} \ge \sqrt{\sigma ^2-\sigma _1^2}\cdot \frac{\eta _\epsilon (\mathbb {Z})}{2\eta _\epsilon (\mathbb {Z})} =\eta _\epsilon (h\mathbb {Z}).$$

This is due to the fact that $\sigma _1/\sigma =\lfloor \sigma \rfloor /\sigma \ge 1/2$ for $\sigma >1$. With the notation of Lemma 2, taking $\mu _1=-\mu$, $\mu _2=0$, $\varLambda =h\mathbb {Z}$, $x_2=hx$ and $x_1\leftarrow x_2+\tilde{\mathcal {D}}_{\mu _1-x_2+\mathbb {Z},\sigma _1}$, we have $x_2=hx\leftarrow \tilde{\mathcal {D}}_{\mu _2+\varLambda ,\sigma _2}=\tilde{\mathcal {D}}_{h\mathbb {Z},h(2\eta _\epsilon (\mathbb {Z}))}=h\cdot \tilde{\mathcal {D}}_{\mathbb {Z},2\eta _\epsilon (\mathbb {Z})}$ and

$$\mu +x_1\leftarrow \mu +(x_2+\tilde{\mathcal {D}}_{\mu _1-x_2+\mathbb {Z},\sigma _1})=\mu +hx+\tilde{\mathcal {D}}_{-\mu -hx+\mathbb {Z},\lfloor \sigma \rfloor }=\tilde{\mathcal {D}}_{\mathbb {Z},\lfloor \sigma \rfloor ,\mu +hx}.$$

Since $\eta _\epsilon (\mathbb {Z})$ is a rational number, in Algorithm 5, $\tilde{\mathcal {D}}_{\mathbb {Z},2\eta _\epsilon (\mathbb {Z})}$ can be exactly sampled (without any statistical discrepancy) via Algorithm 1, which implies that

$$\varDelta _\mathrm {ML}(\mathcal {D}_{\mathbb {Z},2\eta _\epsilon (\mathbb {Z})},\tilde{\mathcal {D}}_{\mathbb {Z},2\eta _\epsilon (\mathbb {Z})})=0.$$

In contrast, $\tilde{\mathcal {D}}_{\mathbb {Z},\lfloor \sigma \rfloor ,\mu +hx}$ can be only realized by sampling from $\mathcal {D}_{\mathbb {Z},\lfloor \sigma \rfloor ,\lfloor \mu +hx\rceil _\lambda }$ with max-log distance $\varDelta _\mathrm {ML}\le (\pi /b)^2+2\epsilon$. Applying Lemma 2, we obtain that

$$\begin{aligned} \mu +x_1\leftarrow \mu +(x_2+\tilde{\mathcal {D}}_{\mu _1-x_2+\mathbb {Z},\sigma _1})= & {} \mu +(hx+\tilde{\mathcal {D}}_{-\mu -hx+\mathbb {Z},\lfloor \sigma \rfloor })\\\approx & {} \mu +\mathcal {D}_{-\mu +\mathbb {Z},\sigma }=\mathcal {D}_{\mathbb {Z},\sigma ,\mu }, \end{aligned}$$

where ‘$\approx$’ means that $\varDelta _\mathrm {ML}(hx+\mathcal {D}_{-\mu -hx+\mathbb {Z},\lfloor \sigma \rfloor },\mathcal {D}_{-\mu +\mathbb {Z},\sigma })$ is not more than

$$\begin{aligned}&{4\epsilon +\varDelta _\mathrm {ML}(\mathcal {D}_{-\mu -hx+\mathbb {Z},\lfloor \sigma \rfloor },\tilde{\mathcal {D}}_{-\mu -hx+\mathbb {Z},\lfloor \sigma \rfloor })+\varDelta _\mathrm {ML}(\mathcal {D}_{h\mathbb {Z},h(2\eta _\epsilon (\mathbb {Z}))},\tilde{\mathcal {D}}_{h\mathbb {Z},h(2\eta _\epsilon (\mathbb {Z}))})}\\&\qquad \,\; = 4\epsilon +\varDelta _\mathrm {ML}(\mathcal {D}_{\mathbb {Z},2\eta _\epsilon (\mathbb {Z})},\tilde{\mathcal {D}}_{\mathbb {Z},2\eta _\epsilon (\mathbb {Z})})\\&\qquad \,\; \quad + \varDelta _\mathrm {ML}(\mu +hx+\mathcal {D}_{-\mu -hx+\mathbb {Z},\lfloor \sigma \rfloor },\mu +hx+\tilde{\mathcal {D}}_{-\mu -hx+\mathbb {Z},\lfloor \sigma \rfloor })\\&\qquad \,\; \le 4\epsilon +\varDelta _\mathrm {ML}(\mathcal {D}_{\mathbb {Z},2\eta _\epsilon (\mathbb {Z})},\tilde{\mathcal {D}}_{\mathbb {Z},2\eta _\epsilon (\mathbb {Z})})+\varDelta _\mathrm {ML}(\mathcal {D}_{\mathbb {Z},\lfloor \sigma \rfloor ,\mu +hx},\tilde{\mathcal {D}}_{\mathbb {Z},\lfloor \sigma \rfloor ,\mu +hx})\\&\qquad \,\; \le 4\epsilon +((\pi /b)^2+2\epsilon ).\\&\qquad \,\; =6\epsilon +(\pi /b)^2. \end{aligned}$$

This completes the proof.   $\square$

The distribution produced by Algorithm 5 has a smaller max-log distance to the ideal distribution, as compared to one produced by Micciancio-Walter sampling algorithm, since both step 1 and step 4 can be implemented exactly, and do not lead to any statistical discrepancy. In contrast, the two corresponding steps in Micciancio-Walter algorithm are approximated ones (see Sect. 5 in [22]). The statistical discrepancy they produce must be counted in the total statistical discrepancy.

For instance, we take $\epsilon =2^{-112}$ and $\eta _\epsilon (\mathbb {Z})=2$, as $\sqrt{\ln (2(1+1/\epsilon ))/2}/\pi \le 2$ when $\epsilon =2^{-112}$. We take $\lambda =30$ and $b=2^{30}$, which results in $(\pi /b)^2\le 2^{-56}$. Then, we have $\varDelta _\mathrm {ML}(\mathcal {D}_{\mathbb {Z},\sigma , \mu },\tilde{\mathcal {D}}_{\mathbb {Z},\sigma , \mu })\le 2^{-56}+6\cdot 2^{-112}$. The practical max-log distance should also include the statistical discrepancy due to the floating-point operations in step 2. One can just follow the argument at the end of Sect. 5.3 in  [22].

Moreover, the first step in Micciancio-Walter algorithm requires sampling from a centered discrete Gaussian distribution $\mathcal {D}_{\mathbb {Z},\sigma _\mathrm {max}}$ with a possible varying parameter $\sigma _\mathrm {max}$, which should be determined before sampling according to the desired distribution. In Algorithm 5, however, step 1 is just to sample from a centered discrete Gaussian distribution with a fixed parameter $2\eta _\epsilon (\mathbb {Z})=4$. This means that Algorithm 5 has a simpler form than Micciancio-Walter algorithm.

5 Experimental Results

Karney’s sampling algorithm for discrete Gaussian distributions over the integers $\mathbb {Z}$ can be realized by using C++ library ‘RandomLib’³, in which the source code of his algorithm is encapsulated as a .hpp file named “DiscreteNormal.hpp”. “RandomLib” also supports the generation and some basic operations of random numbers of arbitrary precision.

On a laptop computer (Intel i7-6820 hq, 8 GB RAM), using the g++ compiler and enabling -O3 optimization option, we tested our Algorithm 2. The source code was based on the adaptation of ‘DiscreteNormal.hpp’ as well as the runtime environment provided by ‘RandomLib’. For discrete Gaussian distribution $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ with $\sigma$ from 4 to $2^{20}$ and $\mu$ uniformly from [0, 1) of precision 128 bits, combining Algorithms 3 and 4, one could get about $5.0\times 10^6$ samples per second by using Algorithm 2. It has almost the same performance as Karney’s algorithm.

We also tested the performance of the Micciancio-Walter algorithm with the same parameters. Using this algorithm, one could get about $1.3\times 10^6$ integers per second. We implemented its base sampler with the CDT-based method, which required an amount of extra memory, and took $\lambda =8$ and $b=16$. This guarantees the max-log distance to the ideal distribution is not more than $2^{-52}$.

We note that Micciancio-Walter algorithm has a constant execution time for given parameters if its base sampler is a constant-time algorithm. However, our Algorithm 2 as well as Algorithm 5 is not a constant-time one, and it seems to be inherently costly to turn into a constant-time one due to the fact that Algorithm 2 is always probabilistically rejecting samples. Therefore, an open question is how to make Algorithm 2 constant-time and be protected against side-channel attacks [4, 8].

6 Conclusion

For an integer-valued parameter $\sigma$, there exists an exact sampling algorithm for $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$. It requires no precomputation storage, uses no floating-point arithmetic, supports a varying $\mu$ of arbitrary precision, and does not have any statistical discrepancy. Applying the convolution-like property of discrete Gaussian distributions, it can be further extended to an approximated sampling algorithm for $\mathcal {D}_{\mathbb {Z},\sigma ,\mu }$ with a real-valued parameter $\sigma$. The extended algorithm also supports centers of arbitrary precision and it produces a distribution with a smaller max-log distance to the ideal distribution, as compared to Micciancio-Walter sampling algorithm.