Treffer: On the Rejection Rate of Exact Sampling Algorithm for Discrete Gaussian Distributions over the Integers

Title:

On the Rejection Rate of Exact Sampling Algorithm for Discrete Gaussian Distributions over the Integers

Authors:

Yusong Du, Xiao Ma

Source:

Theory of Computing Systems. 66:1099-1122

Publisher Information:

Springer Science and Business Media LLC, 2022.

Publication Year:

2022

Subject Terms:

0202 electrical engineering, electronic engineering, information engineering, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences

Document Type:

Fachzeitschrift Article

Language:

English

ISSN:

1433-0490
1432-4350

DOI:

10.1007/s00224-022-10102-y

Rights:

Springer TDM

Accession Number:

edsair.doi...........3b44c72b3ea87fb99f958c2d875c26d5

Database:

OpenAIRE

Weitere Informationen

AN0160140348;2uh01dec.22;2022Nov14.02:32;v2.2.500

On the Rejection Rate of Exact Sampling Algorithm for Discrete Gaussian Distributions over the Integers

A discrete Gaussian distribution over the integers is a Gaussian distribution restricted so that its support is the set of all the integers. This paper studies the problem of sampling exactly from discrete Gaussian distributions over the integers. It is required to generate integers according to a given discrete Gaussian distribution without any statistical discrepancy. In 2016, Karney proposed an exact sampling algorithm for discrete Gaussian distributions whose parameters are rational numbers. This algorithm uses rejection sampling, and it is a discretization of his algorithm for sampling exactly from the standard normal distribution. In this paper, we give a rigorous and complete analysis of the rejection rate of this algorithm, which was not given by Karney, and show that it cannot generate integers efficiently in the case where the standard deviation of the distribution is very small (e.g. much smaller than 1/2). Then, we present an alternative algorithm for this special case, which can sample exactly and efficiently from discrete Gaussian distributions with very small standard deviations.

Keywords: Random number generation; Rejection sampling; Exact sampling; Discrete Gaussian distribution

Copyright comment Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Introduction

We denote the set of real numbers by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℝ</mi></math> and the set of integers by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℤ</mi></math> . The Gaussian function on <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℝ</mi></math> with parameter σ > 0 and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>μ</mi><mo>∈</mo><mi mathvariant="double-struck">ℝ</mi></math> evaluated at <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi><mo>∈</mo><mi mathvariant="double-struck">ℝ</mi></math> can be defined by

Graph

Normalizing ρ<subs>σ,μ</subs>(x) by its total measure <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mo>∫</mo></mrow><mrow><mi>x</mi><mo>∈</mo><mi mathvariant="double-struck">ℝ</mi></mrow></msub><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo><mo>=</mo><msqrt><mrow><mn>2</mn><mi>π</mi></mrow></msqrt><mi>σ</mi></math> over <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℝ</mi></math> , we obtain the probability density function of the (continuous) Gaussian distribution <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> , namely the normal distribution.

We extend any real function f(⋅) to a countable set A by defining <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>f</mi><mo stretchy="false">(</mo><mi>A</mi><mo stretchy="false">)</mo><mo>=</mo><msub><mrow><mo>∑</mo></mrow><mrow><mi>x</mi><mo>∈</mo><mi>A</mi></mrow></msub><mi>f</mi><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo></math> if it exists. The discrete Gaussian distribution over the integers <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℤ</mi></math> is simply the Gaussian distribution <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> restricted so that its support is the set of all the integers. That is, for all <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi><mo>∈</mo><mi mathvariant="double-struck">ℤ</mi></math> ,

Graph

where σ and μ can also be called the standard deviation and the mean of the discrete Gaussian distribution. By convention, the subscript μ is omitted when it is taken to be 0.

Discrete Gaussian sampling over the integers is to generate random integers according to a given discrete Gaussian distribution <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> . The methods of sampling from a continuous Gaussian distribution are not trivially applicable for the discrete case. In recent years, this issue has received increasing attention because of its application in cryptography. Discrete Gaussian sampling has been considered as one of the fundamental building blocks of lattice-based cryptography [[8], [11], [14], [17]]. It 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.

Exact Discrete Gaussian Sampling over the Integers

A good random sampling algorithm (not necessarily for discrete Gaussian distributions) should not only be fast, but also has a negligible statistical discrepancy with the target distribution. Most of existing sampling algorithms for discrete Gaussian distributions are approximation algorithms, such as the inversion sampling (using a cumulative distribution table) [[15]] and the Knuth-Yao method (using a discrete distribution generating (DDG) tree) [[6]]. These algorithms are very efficient, however, most of them are usually designed only for discrete Gaussian distributions with specific parameters. Some of them also support varying parameters (varying σ or/and μ), but they require floating-point arithmetic or precomputation storage. Therefore, it is interesting to consider exact sampling, which requires no floating-point arithmetic and no precomputation storage, and can be suitable for varying parameters.

Furthermore, the aforementioned approximation algorithms usually involve complicated and careful security analysis based on statistical measures (e.g. Rényi divergence [[2], [16]] and max-log distance [[13]]), since attaining a negligible statistical measure to the ideal Gaussian distribution may be crucial for lattice-based cryptography. In contrast, exact sampling algorithms generate integers according to given discrete Gaussian distributions without any statistical discrepancy. The security analysis based on statistical measures for exact sampling algorithms can be simplified or even be omitted.

In 2016, Charles F. F. Karney proposed an exact sampling algorithm for discrete Gaussian distributions over the integers whose parameters are allowed to be arbitrary rational numbers. This algorithm uses rejection sampling, and it is a discretization of his algorithm for sampling exactly from the standard normal distribution. Karney's exact sampling algorithm is of theoretical interest as an example of an algorithm in which exact transcendental results can be achieved with simple integer arithmetic, although it is unlikely to directly displace existing methods at present for practical cryptographic applications because of the leakage of secret information caused by side-channel (timing) attacks on Discrete Gaussian sampling algorithms over the integers [[4], [7]].

We remark that it is necessary to rely entirely on integer arithmetic (limited to additions, multiplications, bitwise operations, and shifts on 32-bit or 64-bit operands). Indeed, division instructions are quite likely not constant-time, especially when the divisor is considered a variable parameter. Floating-point arithmetic rarely offers constant-time execution guarantees [[1]]. Floating-point operations are often variable time even in the presence of a floating-point unit (FPU), and even for simpler operations like multiplications, so the effect that floating point multiplications are constant time could be overly optimistic [[3]].

Our Motivation

In this paper, we try to give a rigorous and complete analysis of the rejection rate of this algorithm, which was not given by Karney. The work most closely related to ours is the Bernoulli(-type) sampling algorithm proposed by Ducas et al. in [[5]] (Algorithm 10, 11, and 12 in [[5]]). It was designed exclusively for a centered discrete Gaussian distribution over the integers, namely <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> with σ = kσ<subs>2</subs> and μ = 0, where k is a positive integer and <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msub><mo>=</mo><msqrt><mrow><mn>1</mn><mo stretchy="false">/</mo><mo stretchy="false">(</mo><mn>2</mn><mo>⋅</mo><mi>ln</mi><mn>2</mn><mo stretchy="false">)</mo></mrow></msqrt></math> . This algorithm also uses rejection sampling, and it was shown that the rejection rate of this algorithm is not more than 1.47, which does not depend on the parameter k. However, the analysis process of Karney's exact sampling algorithm cannot fully follow this, since Karney's algorithm supports arbitrary and varying rational parameters, while the Bernoulli sampling algorithm only allows σ to be an integer multiple of σ<subs>2</subs> ≈ 0.849 and μ to be zero.

Graph: Algorithm 1 [[10]] Sampling Dℤ,σ,μ for σ,μ∈ℚ and σ > 0.

In fact, one can see that the rejection rate of Karney's sampling algorithm for discrete Gaussian distributions is about 2.03 for the parameter σ large, which is identical to that of Karney's sampling algorithm for the standard normal distribution, and the steps designed to achieve the exactness do not affect the rejection rate of sampling algorithm in essence. Nevertheless, a rigorous and complete analysis should include the influence of parameters (i.e., σ and μ) on the rejection rate, which was not well studied in Karney's paper. Specifically, Karney's algorithm outputs an integer in the form of s(⌈kσ + sμ⌉ + j) such that ⌈kσ + sμ⌉− kσ − sμ + j < σ, which is a relatively complex form, where s ∈{− 1,1} and j is a uniformly random integer from [0,⌈σ⌉). The parameters σ and μ may have some substantial influence on the rejection rate of the algorithm. So, the algorithm analysis in this paper mainly tries to address this issue.

The influence of parameters σ and μ on the rejection rate is also related to the defense of the algorithm against timing attacks. Recently, Howe et al. in [[9]] proposed the concept of isochronous Gaussian sampling, which is weaker than being constant-time, but it nevertheless suffices to argue security against timing attacks. They showed that the rejection rate as well as the running time of their isochronous sampler is independent of the parameters σ, μ and of the output z. If we consider the influence of parameters σ and μ on the rejection rate of Karney's algorithm, we could determine whether Karney's algorithm has the potential to become an isochronous sampling algorithm.

Moreover, Karney's sampling algorithm for the standard normal distribution can also be regarded as sampling by mapping distributions—with an iterative and adaptive control structure (not a simple functional mapping). The essence is conveyed beautifully by Fig. 1 of Karney's paper [[10]] showing the decomposition of the area under the bell curve into succinctly-specified rectangles, each representing a non-negative integer plus a particular u-rand[1] that could be selected in the sampling process. Each rectangle is an "accepted" query. The mean count of "rejected" queries is the main complexity measure, namely rejection rate of the sampling algorithm. The objective is finding coverings by rectangles that are legal u-rands in base b that collectively minimize the complexity measure. However, for discrete Gaussian distributions, there is no such explanation in Karney's paper. In this paper, we try to give a similar explanation of Karney's sampling algorithm for discrete Gaussian distributions from the view of mapping distributions.

Our Contribution

We show that the rejection rate of Karney's algorithm can approximately be given by 2.03/τ(σ) and that the value of μ has little effect on the rejection rate for any rational σ ≥ 1, where τ = σ/⌈σ⌉. This means that for an integer σ or a large σ the rejection rate of Karney's algorithm is almost independent of the parameters σ, μ and of the output z. Therefore, if each step of Karney's algorithm could be modified to an isochronous operation, then Karney's algorithm can become an isochronous sampling algorithm.

We also discuss the rejection rate for 0 < σ < 1. In particular, we show that a very small σ (e.g. much smaller than 1/2) will lead to a dramatic increase in the probability of rejection, which means that the algorithm cannot generate integers efficiently in this case. Then, we present an alternative exact sampling algorithm for this special case, and give the proof of correctness and the analysis of rejection rate. The results show that our proposed algorithm can sample efficiently from discrete Gaussian distributions over the integers whose standard deviations are very small. We provide experimental data that can verify the theoretical results.

From the view of mapping distributions, we show that the sampling process involves a one-to-one mapping from a set of integer 3-tuples satisfying certain conditions to the set of all the integers, it can be viewed as querying randomly from a set of all the possible integer 3-tuples. If an integer 3-tuple satisfying the conditions is found, then the algorithm probabilistically accepts or rejects the integer 3-tuple, and get an integer from the discrete Gaussian distribution by the mapping. For the parameter σ ≥ 1, an integer 3-tuple satisfying the conditions can be found with a high probability, while for a σ much less than one, this probability becomes very low. This also explains the fact that Karney's sampling algorithm cannot generate integers efficiently in the case where the standard deviation of the distribution is very small. In our proposed sampling algorithm, however, one can see that the mapping is from a set of integer 2-tuples to the set of all the integers, and a 2-tuple can always be found and be accepted with high probability for a σ much less than one, so our algorithm can handle the case of the σ being much less than one.

Preliminaries

Floor and Ceiling Functions

Taking as input a real number x, the ceiling function gives the least integer greater than or equal to x, denoted by ⌈x⌉. Similarly, the floor function maps x to the greatest integer less than or equal to x, denoted by ⌊x⌋. The ceiling and floor functions are basic primitives in Karney's exact sampling algorithm and their application produces an exact result in the algorithm's base. In this paper, we will repeatedly and implicitly apply the following properties of the floor and ceiling functions, which are well-known.

0 ≤⌈x⌉− x < 1;

⌈x⌉ + ⌈y⌉− 1 ≤⌈x + y⌉≤⌈x⌉ + ⌈y⌉;

x − 1 < ⌊x⌋≤ x.

Karney's Exact Sampling Algorithm

The exact sampling algorithm for the discrete Gaussian distribution <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> , proposed by Karney in 2016, uses rejection sampling and it is a discretization of his algorithm for sampling exactly from the standard normal distribution [[10]]. Karney's algorithm is described as Algorithm 1 in this paper, where σ and μ are in the set of rational numbers <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℚ</mi></math> .

From the perspective of rejection sampling, in Algorithm 1, we can see that step 1 and step 2 form a rejection sampling procedure, which generates <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> according to

Graph

which is a discrete Gaussian distribution over the set of non-negative integers <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> . Then, the proposal distribution for the whole algorithm can be written as

Graph

with z = s(⌈kσ + sμ⌉ + j). Then, the algorithm accepts z as the returned value with probability <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mn>2</mn></mrow></mfrac><mi>x</mi><mo stretchy="false">(</mo><mn>2</mn><mi>k</mi><mo>+</mo><mi>x</mi><mo stretchy="false">)</mo></mrow></msup></math> , where x = (⌈kσ + sμ⌉− (kσ + sμ) + j)/σ < 1. It is not hard to see that

Graph

which guarantees that the returned value has the desired (relative) probability density.

Karney also proposed an algorithm for generating a random Boolean value according to the Bernoulli distribution <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">B</mi></mrow><mrow><mn>1</mn><mo stretchy="false">/</mo><msqrt><mrow><mi>e</mi></mrow></msqrt></mrow></msub></math> , which is described as Algorithm 2 in this paper. In Algorithm 1, one uses Algorithm 2 to exactly sample <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> with (relative) probability density <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mn>1</mn></mrow></msub><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo><mo>=</mo><mi>exp</mi><mo stretchy="false">(</mo><mo>−</mo><msup><mrow><mi>k</mi></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">/</mo><mn>2</mn><mo stretchy="false">)</mo></math> . More precisely, one applies Algorithm 2 repeatedly (k + 1) times to select an integer k ≥ 0 with probability <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>exp</mi><mo stretchy="false">(</mo><mo>−</mo><mi>k</mi><mo stretchy="false">/</mo><mn>2</mn><mo stretchy="false">)</mo><mo>⋅</mo><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>exp</mi><mo stretchy="false">(</mo><mo>−</mo><mn>1</mn><mo stretchy="false">/</mo><mn>2</mn><mo stretchy="false">)</mo><mo stretchy="false">)</mo></math> (step 1), then continues to apply Algorithm 2 at most k(k − 1) times to accept or reject k with probability <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>exp</mi><mfenced close=")" open="("><mrow><mo>−</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mn>2</mn></mrow></mfrac><mi>k</mi><mo stretchy="false">(</mo><mi>k</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mfenced></math> (step 2).

Graph: Algorithm 2 [[10]] Generating a random Boolean value b which is true with probability 1/e.

Algorithm 2 is adapted by Karney from von Neummann's algorithm for exactly sampling from the exponential distribution e<sups>−x</sups> for real x > 0. More precisely, the probability that the length of the longest decreasing sequence is n is x<sups>n</sups>/n! − x<sups>n+ 1</sups>/(n + 1)!, and the probability that n is even is exactly equal to

Graph

In Algorithm 1, step 8 will also be implemented by using a specifically designed algorithm, so that it produces no any statistical discrepancy. The main idea is to sample two sets of uniform deviates u<subs>1</subs>,u<subs>2</subs>,... and v<subs>1</subs>,v<subs>2</subs>,... from [0,1), and to determine the maximum value n ≥ 0 such that x > u<subs>1</subs> > u<subs>2</subs> > ... > u<subs>n</subs> and v<subs>i</subs> < (2k + x)/(2k + 2). If n is even, it returns <bold>true</bold>, and the probability is exactly equal to

Graph

Then, by applying the this procedure at most k + 1 times, one can obtain a Bernoulli random value which is true with probability <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>exp</mi><mfenced close=")" open="("><mrow><mo>−</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mn>2</mn></mrow></mfrac><mi>x</mi><mo stretchy="false">(</mo><mn>2</mn><mi>k</mi><mo>+</mo><mi>x</mi><mo stretchy="false">)</mo></mrow></mfenced></math> for given k and x, since

Graph

Hence, step 6 ensures that x is in the allowed range for implementing step 8. If σ is an integer, it was pointed out that step 6 can be omitted since 'x ≥ 1' cannot happen in this case. Moreover, Step 7 is designed to avoid double counting 0 when μ is an integer.

The Rejection Rate of Karney's Algorithm for σ ≥ 1

Sampling an integer x according to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> is equivalent to sampling an integer x −⌊μ⌋ according to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><mo stretchy="false">{</mo><mi>μ</mi><mo stretchy="false">}</mo></mrow></msub></math> , since

Graph

where ⌊μ⌋ and {μ} are the integer and fractional part of μ respectively such that 0 ≤{μ} < 1, and an arbitrary rational μ can be written as μ = ⌊μ⌋ + {μ}. In this section, we discuss the rejection rate of Karney's algorithm (Algorithm 1) in the case where σ ≥ 1 and 0 ≤ μ < 1.

Note that the integers generated by Algorithm 1 is in the form of z = s(⌈kσ + sμ⌉ + j) such that ⌈kσ + sμ⌉− kσ − sμ + j < σ for given σ and μ. Firstly, we will prove that the support of the probability distribution produced by Algorithm 1 is exactly[2] the set of integers, as the proof was not given by Karney in his paper. This proof also helps us analyze the rejection rate of Algorithm 1 more precisely.

Lemma 1

If σ ≥ 1 and 0 < μ < 1, for any integer z, then there exists a unique 3-tuple (k,j,s) with <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mo>⌈</mo><mi>σ</mi><mo>⌉</mo><mo stretchy="false">)</mo><mo>∩</mo><mi mathvariant="double-struck">ℤ</mi></math> , and s ∈{− 1,1}, such that z = s(⌈kσ + sμ⌉ + j) and ⌈kσ + sμ⌉− kσ − sμ + j < σ.

Proof

For an integer i ≥ 0, we let

Graph

and

Graph

We can see that <math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mrow><mo>∪</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></msubsup><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi><mo>,</mo><mi>i</mi></mrow><mrow><mo>+</mo></mrow></msubsup></math> includes all the positive integers, and <math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mrow><mo>∪</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></msubsup><msubsup><mrow><mi mathvariant="script">I</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi><mo>,</mo><mi>i</mi></mrow><mrow><mo>−</mo></mrow></msubsup></math> includes all the non-positive integers. This is due to the following two facts

Graph

and

Graph

Then, for any integer z, there exist k ≥ 0 and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mo>⌈</mo><mi>σ</mi><mo>⌉</mo><mo stretchy="false">)</mo><mo>∩</mo><mi mathvariant="double-struck">ℤ</mi></math> such that z = s(⌈kσ + sμ⌉ + j), where s = 1 if z > 0 and s = − 1 if z ≤ 0. It is clear that

Graph

if j < ⌈σ⌉− 1. When j = ⌈σ⌉− 1, if ⌈kσ + sμ⌉− kσ − sμ + j ≥ σ, then ⌈kσ + sμ⌉ + (⌈σ⌉− 1) ≥ σ + kσ + sμ. It follows that

Graph

which implies that ⌈σ + kσ + sμ⌉ = ⌈kσ + sμ⌉ + ⌈σ⌉− 1. Thus, by taking <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mi>k</mi></mrow><mrow><mi>′</mi></mrow></msup><mo>=</mo><mi>k</mi><mo>+</mo><mn>1</mn></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mi>j</mi></mrow><mrow><mi>′</mi></mrow></msup><mo>=</mo><mn>0</mn></math> we have

Graph

and

Graph

This guarantees that there always exists a 3-tuple (k,j,s) we desire. Suppose that ⌈k<subs>1</subs>σ + sμ⌉ + j<subs>1</subs> = ⌈k<subs>2</subs>σ + sμ⌉ + j<subs>2</subs>, where 0 ≤ k<subs>1</subs> < k<subs>2</subs> and j<subs>1</subs>,j<subs>2</subs> ∈ [0,⌈σ⌉). Then ⌈k<subs>2</subs>σ + sμ⌉−⌈k<subs>1</subs>σ + sμ⌉ = j<subs>1</subs> − j<subs>2</subs>. It follows that

Graph

This implies that k<subs>2</subs> = k<subs>1</subs> + 1, j<subs>1</subs> = ⌈σ⌉− 1 and j<subs>2</subs> = 0 if there exist 0 ≤ k<subs>1</subs> < k<subs>2</subs> and j<subs>1</subs>,j<subs>2</subs> ∈ [0,⌈σ⌉) such that ⌈k<subs>1</subs>σ + sμ⌉ + j<subs>1</subs> = ⌈k<subs>2</subs>σ + sμ⌉ + j<subs>2</subs>. In this case, we have ⌈k<subs>1</subs>σ + sμ⌉ + ⌈σ⌉− 1 = ⌈k<subs>1</subs>σ + σ + sμ⌉. Hence,

With the notation of Algorithm 1, we let i<subs>0</subs> = ⌈kσ + sμ⌉ and x = (⌈kσ + sμ⌉− kσ − sμ + j)/σ. In step 6, the algorithm enforces the condition x ∈ [0,1), which is equivalent to i<subs>0</subs> + j = ⌈kσ + sμ⌉− kσ − sμ + j < σ. In step 7, the algorithm will go to step 1 if and only if μ = 0 and (k,j,s) = (0,0,− 1). By Lemma 1 and Corollary 1, we can see that step 6 and step 7 guarantee that s(i<subs>0</subs> + j) = s(⌈kσ + sμ⌉ + j), such that ⌈kσ + sμ⌉− kσ − sμ + j < σ and (μ,k,j,s)≠(0,0,0,− 1), exactly runs over the set of all the integers, where <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mo>⌈</mo><mi>σ</mi><mo>⌉</mo><mo stretchy="false">)</mo><mo>∩</mo><mi mathvariant="double-struck">ℤ</mi></math> and s ∈{− 1,1}. This implies that

Graph

where <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">S</mi><mo>=</mo><mo stretchy="false">{</mo><mo stretchy="false">(</mo><mi>k</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>s</mi><mo stretchy="false">)</mo><mo stretchy="false">|</mo><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mo>⌈</mo><mi>σ</mi><mo>⌉</mo><mo stretchy="false">)</mo><mo>∩</mo><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>s</mi><mo>∈</mo><mo stretchy="false">{</mo><mo>−</mo><mn>1</mn><mo>,</mo><mn>1</mn><mo stretchy="false">}</mo><mo>,</mo><mo>⌈</mo><mi>k</mi><mi>σ</mi><mo>+</mo><mi>s</mi><mi>μ</mi><mo>⌉</mo><mo>−</mo><mi>k</mi><mi>σ</mi><mo>−</mo><mi>s</mi><mi>μ</mi><mo>+</mo><mi>j</mi><mo><</mo><mi>σ</mi><mo>,</mo><mo stretchy="false">(</mo><mi>μ</mi><mo>,</mo><mi>k</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>s</mi><mo stretchy="false">)</mo><mo>≠</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>0</mn><mo>,</mo><mn>0</mn><mo>,</mo><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo><mo stretchy="false">}</mo></math> . Since

Graph

the probability of accepting x in step 8 can be given by

Graph

By Lemma 3, since <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>σ</mi><mo>≥</mo><msub><mrow><mi>η</mi></mrow><mrow><mi>𝜖</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo></math> , we have <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>≈</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>≈</mo><msqrt><mrow><mn>2</mn><mi>π</mi></mrow></msqrt><mi>σ</mi></math> for 0 ≤ μ < 1. In particular, <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>=</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>≈</mo><msqrt><mrow><mn>2</mn><mi>π</mi></mrow></msqrt><mi>σ</mi></math> if μ = 0. Then, the probability is equal to

Graph

where <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo stretchy="false">/</mo><mn>2</mn><mi>σ</mi><msub><mrow><mi>ρ</mi></mrow><mrow><mn>1</mn></mrow></msub><mo stretchy="false">(</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo stretchy="false">)</mo><mo>≈</mo><msqrt><mrow><mi>π</mi><mo stretchy="false">/</mo><mn>2</mn></mrow></msqrt><mo stretchy="false">/</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mn>1</mn></mrow></msub><mo stretchy="false">(</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo stretchy="false">)</mo><mo>=</mo><mi>c</mi></math> and τ(σ) = σ/⌈σ⌉. Finally, by Corollary 2, if σ is an integer, in step 6, the algorithm will never go to step 1. In this case, the expected success rate is exactly equal to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo stretchy="false">/</mo><mn>2</mn><mi>σ</mi><msub><mrow><mi>ρ</mi></mrow><mrow><mn>1</mn></mrow></msub><mo stretchy="false">(</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo stretchy="false">)</mo><mo>≈</mo><msqrt><mrow><mi>π</mi><mo stretchy="false">/</mo><mn>2</mn></mrow></msqrt><mo stretchy="false">/</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mn>1</mn></mrow></msub><mo stretchy="false">(</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo stretchy="false">)</mo><mo>=</mo><mi>c</mi></math> .

□

Let's look at Karney's sampling algorithm from the view of mapping distributions. The discrete Gaussian distributions can be represented as "blockier" versions of the bell curve, and each rectangle in the discrete case represents a particular integer that could be selected in the sampling process. Lemma 1 as well as corollary 1 given above shows that there exists a one-to-one corresponding between the set of integer 3-tuples (k,j,s) satisfying certain conditions and the set of all the integers <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℤ</mi></math> , where the conditions are <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn>0</mn><mo>,</mo><mo>⌈</mo><mi>σ</mi><mo>⌉</mo><mo stretchy="false">)</mo><mo>∩</mo><mi mathvariant="double-struck">ℤ</mi></math> , s ∈{− 1,1}, ⌈kσ + sμ⌉− kσ − sμ + j < σ, and (μ,k,j,s)≠(0,0,0,− 1). Therefore, as shown in Fig. 1, each rectangle in the blockier bell curve can also be marked with an integer 3-tuple (k,j,s) satisfying those conditions.

Karney's sampling algorithm for discrete Gaussian distributions can be viewed as a mapping from the set of integer 3-tuples (k,j,s) satisfying certain conditions to the set of all the integers <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℤ</mi></math> , it queries randomly in the set

Graph

then accepts probabilistically those 3-tuples (k,j,s) satisfying ⌈kσ + sμ⌉− kσ − sμ + j < σ and (μ,k,j,s)≠(0,0,0,− 1), and reject those 3-tuples that do not meet the conditions. The objective is to find coverings by rectangles that are legal integer 3-tuples (k,j,s). If we find an integer 3-tuple (k,j,s) satisfying the conditions, and accept it, then we fall into the corresponding rectangle, and obtain a sample from the discrete Gaussian distribution. From Theorem 1 and its proof, we can see that the acceptance/rejection rate of the algorithm can be estimated by determining the probability of finding and accepting in <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">T</mi></math> an integer 3-tuple that meets the conditions, i.e., the probability of accepting x in step 8 in Algorithm 1.

Theorem 1 requires that <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>σ</mi><mo>≥</mo><msub><mrow><mi>η</mi></mrow><mrow><mi>𝜖</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo></math> , and the actual value of the smooth parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>η</mi></mrow><mrow><mi>𝜖</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo></math> depends on 𝜖. In cryptographic applications, the value of 𝜖 should be small enough (say 2<sups>− 80</sups>) so that the resulting statistical error has a small enough impact on the security of the cryptographic scheme. However, when we only talk about the average rejection rate of the sampling algorithm, the error requirement between theoretical rejection rate and approximately estimated rejection rate is not as high as in cryptography. This means that 𝜖 can be relatively large, and therefore σ can be relatively small in Theorem 1.

For example, taking 𝜖 = 2<sups>− 27</sups> we have <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>δ</mi></mrow><mrow><mtext>RE</mtext></mrow></msub><mo stretchy="false">(</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>,</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo><</mo><mn>2</mn><mi>𝜖</mi><mo>=</mo><msup><mrow><mn>2</mn></mrow><mrow><mo>−</mo><mn>26</mn></mrow></msup></math> . We believe that <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo></math> are sufficiently close to each other for discussing the rejection rate of the sampling algorithm. According to Lemma 2, we get <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>η</mi></mrow><mrow><mi>𝜖</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>≈</mo><mn>0.991578</mn></math> with 𝜖 = 2<sups>− 27</sups>. Then we can take σ ≥ 1 in Theorem 1.

Figure 2 shows the probability that Algorithm 1 accepts x in step 8. Karney pointed out in his paper that the probability of Algorithm 1 accepting x in step 8 is about 0.715 for σ large [[10]]. In Theorem 1, we have <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>c</mi><mo>=</mo><msqrt><mrow><mi>π</mi><mo stretchy="false">/</mo><mn>2</mn></mrow></msqrt><mo stretchy="false">/</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mn>1</mn></mrow></msub><mo stretchy="false">(</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo stretchy="false">)</mo><mo>≈</mo><mn>0.715</mn></math> . From Fig. 2, one can see that the value of μ has little effect on the probability (the curves with four different values of μ coincide with each other as plotted in the figure), but the probability is not always approximately equal to 0.715, especially for a small σ.

Graph: Fig. 2 The probability of Algorithm 1 accepting x in step 8 (1 ≤ σ ≤ 16, μ = 7/8,1/2,1/8,0). There are four curves corresponding to four different values of μ, but they coincide with each other as plotted

In particular, for a positive integer i and a small real number 𝜖 > 0, if σ = i + 𝜖, i.e., σ is strictly more than i but is approximately equal to i, then τ(σ) = σ/⌈σ⌉≈ i/(i + 1). The approximation '≈' here can also be described by using relative error δ<subs>RE</subs>(i/(i + 1),(i + 𝜖)/(i + 1)) = 𝜖/i. It makes sense especially for a small positive integer i (say, i = 1, and τ(σ) is approximately equal to 1/2).

Finally, in this section, in the case that steps 1 and 2 in Algorithm 1 successfully produce the integer k, the rejection rate of Algorithm 1 can be given by 1/(c ⋅ τ(σ)). As mentioned in Section 2.2, step 1 and step 2 also form a rejection sampling procedure, which generates <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> according to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo>,</mo><mn>1</mn></mrow></msub></math> . The probability that the algorithm accepts k in step 2 is <math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo stretchy="false">/</mo><msqrt><mrow><mi>e</mi></mrow></msqrt><mo stretchy="false">)</mo><mo>⋅</mo><msubsup><mrow><mo>∑</mo></mrow><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></msubsup><mi>exp</mi><mfenced close=")" open="("><mrow><mfrac><mrow><mn>1</mn></mrow><mrow><mn>2</mn></mrow></mfrac><msup><mrow><mi>i</mi></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfenced><mo>≈</mo><mn>0.690</mn></math> [[10]]. Therefore, the 'full' rejection rate of Algorithm 1 is about

Graph

which means that the algorithm goes back to step 1 about (2.027/τ(σ) − 1) times on average before it returns an integer as the output.

The Rejection Rate of Karney's Algorithm for 0 < σ < 1

In this section, we discuss the rejection rate of Karney's algorithm in the case where 0 < σ < 1 and 0 ≤ μ ≤ 1/2. The parameter μ is constrained to lie between 0 and 1/2, since sampling an integer x according to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> is equivalent to sampling an integer 1 − x according to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><msup><mrow><mi>μ</mi></mrow><mrow><mi>′</mi></mrow></msup></mrow></msub></math> for any real μ ∈ [1/2,1), where <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mi>μ</mi></mrow><mrow><mi>′</mi></mrow></msup><mo>∈</mo><mo stretchy="false">(</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>2</mn><mo stretchy="false">]</mo></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>μ</mi><mo>=</mo><mn>1</mn><mo>−</mo><msup><mrow><mi>μ</mi></mrow><mrow><mi>′</mi></mrow></msup></math> .

Recall that Karney's sampling algorithm for discrete Gaussian distributions (Algorithm 1) is a discretization of his algorithm for sampling exactly from the standard normal distribution. Specifically, one can replace step 4, 5, 6 and 7 in Algorithm 1 by directly setting x to be a uniform deviate from [0,1), and accepts x with probability <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>exp</mi><mfenced close=")" open="("><mrow><mo>−</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mn>2</mn></mrow></mfrac><mi>x</mi><mo stretchy="false">(</mo><mn>2</mn><mi>k</mi><mo>+</mo><mi>x</mi><mo stretchy="false">)</mo></mrow></mfenced></math> , then obtains a number in the form of s(k + x) from the standard normal distribution (see Algorithm N in [[10]]). From this perspective, Algorithm 1 can be understood by identifying

Graph

which is analogous to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>exp</mi><mo stretchy="false">(</mo><mo>−</mo><msup><mrow><mo stretchy="false">(</mo><mi>k</mi><mo>+</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">/</mo><mn>2</mn><mo stretchy="false">)</mo></math> versus <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>exp</mi><mo stretchy="false">(</mo><mo>−</mo><msup><mrow><mo stretchy="false">(</mo><mi>s</mi><mo stretchy="false">(</mo><msub><mrow><mi>i</mi></mrow><mrow><mn>0</mn></mrow></msub><mo>+</mo><mi>j</mi><mo stretchy="false">)</mo><mo>−</mo><mi>μ</mi><mo stretchy="false">)</mo></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">/</mo><mn>2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">)</mo></math> . We have to guarantee that (k + x)σ + sμ = (kσ + sμ) + σx is an integer so that the returned value s(i<subs>0</subs> + j) is an integer. Thus, we compute x by x = (⌈kσ + sμ⌉− (kσ + sμ) + j)/σ in Algorithm 1, and

Graph

must be an integer. The requirement that x ∈ [0,1) imposes the condition (⌈kσ + sμ⌉− (kσ + sμ) + j) < σ. Corollary 2 shows that the inequality (⌈kσ + sμ⌉− (kσ + sμ) + j) < σ holds with probability at least 1/2 if σ ≥ 1 for the 3-tuple (k,j,s) generated randomly by Algorithm 1. However, when σ ≪ 1, the following Lemma shows that the inequality (⌈kσ + sμ⌉− (kσ + sμ) + j) < σ holds only for the integer k that satisfies certain conditions.

Lemma 4

Let 0 < σ < 1, 0 ≤ μ ≤ 1/2, s ∈{− 1,1} and k be a non-negative integer. If there exists an integer i ≥ (1 + s)/2 such that k = ⌊(i − sμ)/σ⌋, then ⌈kσ + sμ⌉− kσ − sμ < σ, otherwise ⌈kσ + sμ⌉− kσ − sμ ≥ σ.

Proof

For s ∈{− 1,1}, let

Graph

Since ⌊(μ − 1)/σ⌋≤− 1 and ⌊−μ/σ⌋≤ 0, we can see that <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">I</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi><mo>,</mo><mi>s</mi></mrow></msub></math> includes all the non-negative integers. For each i ≥ (1 + s)/2, if ⌊(i − 1 − sμ)/σ⌋ < k ≤⌊(i − sμ)/σ⌋, then we have

Graph

i.e., i − 1 < kσ + sμ ≤ i, which implies that ⌈kσ + sμ⌉ = i and

Graph

If k = ⌊(i − sμ)/σ⌋, then we have ⌈kσ + sμ⌉− kσ − sμ = i − sμ − kσ < σ, otherwise i − sμ − kσ ≥ σ gives a contradiction that (i − sμ)/σ − 1 ≥ k. If ⌊(i − 1 − sμ)/σ⌋ < k < ⌊(i − sμ)/σ⌋, then we have

Graph

This completes the proof. □

Let σ > 0 and 0 ≤ μ ≤ 1/2. Algorithm 3 outputs an integer according to discrete Gaussian distribution <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> , and the probability that Algorithm 3 accepts z in step 5 is <math xmlns="http://www.w3.org/1998/Math/MathML"><mfenced close=")" open="("><mrow><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo stretchy="false">/</mo><mn>2</mn><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi></mrow></msub><mo stretchy="false">(</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo stretchy="false">)</mo></mrow></mfenced><mo>⋅</mo><mi>exp</mi><mfenced close=")" open="("><mrow><msup><mrow><mi>μ</mi></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">/</mo><mn>2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfenced></math> .

Graph: Algorithm 3 Sampling Dℤ,σ,μ for σ,μ∈ℚ.

Proof

We observe Algorithm 3 from the perspective of rejection sampling. Step 1 and step 2 form a rejection sampling procedure, which generates <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> according to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo>,</mo><mi>σ</mi></mrow></msub><mo>=</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi></mrow></msub><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo><mo stretchy="false">/</mo><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi></mrow></msub><mo stretchy="false">(</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup><mo stretchy="false">)</mo></math> , because

Graph

This also implies that the probability of accepting k in step 2 is

Graph

The relative probability density of accepting z in step 5 is equal to

Graph

which is proportional to the desired relative probability density

Graph

This guarantees the correctness of the algorithm. For <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∈</mo><msup><mrow><mi mathvariant="double-struck">ℤ</mi></mrow><mrow><mo>+</mo></mrow></msup></math> , it is clear that z = sk + (s + 1)/2 with s = − 1 exactly runs over the set of all the non-positive integers, while z = sk + (s + 1)/2 with s = 1 exactly runs over the set of all the positive integers. Then, the probability that Algorithm 3 accepts z in step 5 can be given by

Graph

This completes the proof. □

Corollary 7

Let σ > 0. When σ approaches 0, the probability that Algorithm 3 outputs an integer before it goes back to step 1 is about 1/2 if 0 ≤ μ < 1/2, and approaches 1 if μ = 1/2.

Proof

In the proof of Theorem 3, <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>⋅</mo><mi>exp</mi><mfenced close=")" open="("><mrow><msup><mrow><mi>μ</mi></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">/</mo><mn>2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfenced></math> can also be written as follows.

Graph

Since

Graph

and we have

Graph

for 0 ≤ μ < 1/2. It follows that <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>⋅</mo><mi>exp</mi><mfenced close=")" open="("><mrow><msup><mrow><mi>μ</mi></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">/</mo><mn>2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfenced><mo>≈</mo><mn>1</mn></math> if σ approaches 0 and 0 ≤ μ < 1/2. In particular, for μ = 1/2 we have

Graph

Then, <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi>ρ</mi></mrow><mrow><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub><mo stretchy="false">(</mo><mi mathvariant="double-struck">ℤ</mi><mo stretchy="false">)</mo><mo>⋅</mo><mi>exp</mi><mfenced close=")" open="("><mrow><msup><mrow><mi>μ</mi></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">/</mo><mn>2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfenced><mo>≈</mo><mn>2</mn></math> if σ approaches 0 and μ = 1/2. Therefore, the probability Algorithm 3 successfully outputs an integer before it goes back to step 1 can be estimated to be

Graph

when σ approaches 0 and 0 ≤ μ < 1/2. If σ approaches 0 and μ = 1/2 the probability can be estimated by

Graph

This completes the proof. □

We remark that Algorithm 3 could not be used to sample from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi><mo>,</mo><mi>μ</mi></mrow></msub></math> with σ ≫ 1, though it is suitable theoretically for any rational σ > 0. It is not hard to see that increasing σ decreases the probability of successfully generating an integer. This can be seen from fact that <math xmlns="http://www.w3.org/1998/Math/MathML"><munder><mrow><mi>lim</mi></mrow><mrow><mi>σ</mi><mo>→</mo><mo>+</mo><mi>∞</mi></mrow></munder><mfenced close=")" open="("><mrow><mn>1</mn><mo>−</mo><mi>exp</mi><mfenced close=")" open="("><mrow><mo>−</mo><mn>1</mn><mo stretchy="false">/</mo><mo stretchy="false">(</mo><mn>2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msup><mo stretchy="false">)</mo></mrow></mfenced></mrow></mfenced><mo>=</mo><mn>0</mn></math> , which also means it may take a long time to select an integer k ≥ 0 in step 1 for a large σ. Figure 4 shows the probability that Algorithm 3 outputs an integer before it goes back to step 1 for 0 < σ ≤ 3.

Graph: Fig. 4 The probability of Algorithm 3 outputting an integer before going back to step 1

Let's look at Algorithm 3 from the view of mapping distributions. We can see that there exists a one-to-one corresponding between the set of integer 2-tuples and the set of all the integers <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℤ</mi></math> . Algorithm 3 queries randomly in the set

Graph

The integer 2-tuples here do not require any additional conditions. If we get an integer 2-tuple (k,s) from <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mi mathvariant="script">T</mi></mrow><mrow><mi>′</mi></mrow></msup></math> , and probabilistically accept it, then we obtain a sample z from the discrete Gaussian distribution by the mapping z = sk + (s + 1)/2. Since k conforms to the discrete Gaussian distribution <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mi>σ</mi></mrow></msub></math> and σ < 1, it follows that the probability <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>exp</mi><mfenced close=")" open="("><mrow><mo>−</mo><mfrac class="tfrac"><mrow><mi>s</mi><mi>k</mi><mo stretchy="false">(</mo><mi>s</mi><mo>+</mo><mn>1</mn><mo>−</mo><mn>2</mn><mi>μ</mi><mo stretchy="false">)</mo></mrow><mrow><mn>2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow></mfenced><mo>⋅</mo><mi>exp</mi><mfenced close=")" open="("><mrow><mo>−</mo><mfrac class="tfrac"><mrow><mo stretchy="false">(</mo><mi>s</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">/</mo><mn>2</mn><mo>−</mo><mi>μ</mi><mo stretchy="false">)</mo></mrow><mrow><mn>2</mn><msup><mrow><mi>σ</mi></mrow><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow></mfenced></math> in step 5 is close to one, which means that we can always accept such an integer 2-tuple (k,s) with a high probability.

The remaining problem is to implement Algorithm 3 exactly. This mainly relies on the following algorithm (Algorithm 4), which is a simply generalized version of Algorithm 2.

Graph: Algorithm 4 Generating a random Boolean value b which is true with probability exp(−x), where x is a positive rational number less than one.

The idea of Algorithm 4 is to replace 1/2 with x = p/q in Algorithm 2. Then, one can get a random Boolean value b which is true with probability e<sups>−p/q</sups>, namely sampling from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">B</mi></mrow><mrow><msup><mrow><mi>e</mi></mrow><mrow><mo>−</mo><mi>p</mi><mo stretchy="false">/</mo><mi>q</mi></mrow></msup></mrow></msub></math> , where p,q are positive integers such that p < q. This can be viewed as a simply generalized version of Algorithm 2. Furthermore, for a given rational number y = p/q ≥ 1, i.e., p ≥ q > 0, in order to sample from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">B</mi></mrow><mrow><mi>exp</mi><mo stretchy="false">(</mo><mo>−</mo><mi>y</mi><mo stretchy="false">)</mo></mrow></msub></math> , we should applying Algorithm 2 at least ⌊2p/q⌋ times, and then invoke Algorithm 4 with

Graph

If all the random Boolean values generated in this procedure are '<bold>true</bold>', then we obtain '<bold>true</bold>' from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">B</mi></mrow><mrow><mi>exp</mi><mo stretchy="false">(</mo><mo>−</mo><mi>y</mi><mo stretchy="false">)</mo></mrow></msub></math> , otherwise we have '<bold>false</bold>' from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">B</mi></mrow><mrow><mi>exp</mi><mo stretchy="false">(</mo><mo>−</mo><mi>y</mi><mo stretchy="false">)</mo></mrow></msub></math> .

In Algorithm 3, one can use Algorithm 4 (with p = 1 and q = 2σ<sups>2</sups>) repeatedly (k + 1) times to select an integer k ≥ 0 (step 1), then continues to apply Algorithm 4 at most k(k − 1) times to accept or reject k (step 2). Similarly, step 5 can be exactly implemented by applying Algorithm 4.

Experimental Results

On a laptop computer (Intel i7-8550U, 16GB RAM, the g++ compiler and enabling -O3 optimization option), and following the implementation of Algorithm 1 in Karney's C++ library RandomLib, we implemented our Algorithm 3, which is simply based on the adaption of DiscreteNormal.hpp as well as the runtime environment provided by RandomLib.

When μ = 0, using Algorithm 1 one can get about 13.3 × 10<sups>6</sups> sample values per second from the discrete Gaussian distribution <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn></mrow></msub></math> , but only about 5.52 × 10<sups>6</sups> sample values per second from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>4</mn></mrow></msub></math> . Furthermore, for some special standard deviations, say σ = 256/255, the rejection rate of Algorithm 1 increases significantly. Using Algorithm 1 one can only obtain about 3.897 × 10<sups>6</sups> sample values per second from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>256</mn><mo stretchy="false">/</mo><mn>255</mn></mrow></msub></math> .

The value of μ has little effect on the rejection rate of Algorithm 1 for any rational σ ≥ 1, while it has substantial influence on the rejection rate in the case of 0 < σ < 1. One can verified that the actual performance of Algorithm 1 also shows the same trend. For example, using Algorithm 1, one can obtain about 7.5 × 10<sups>6</sups> sample values per second from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo>,</mo><mi>μ</mi></mrow></msub></math> with 0 < μ < 1. However, the number of samples obtained per second from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>5</mn><mo>,</mo><mi>μ</mi></mrow></msub></math> varies significantly with the value of μ: 0.486 × 10<sups>6</sups>, 2.335 × 10<sups>6</sups> and 3.824 × 10<sups>6</sups> sample values per second for <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>5</mn><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>2</mn></mrow></msub></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>5</mn><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>4</mn></mrow></msub></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>5</mn><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>8</mn></mrow></msub></math> respectively.

Using Algorithm 3 one can obtain about 11.22 × 10<sups>6</sups> sample values per second from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>4</mn></mrow></msub></math> , and about 5.25 × 10<sups>6</sups> sample values per second from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>256</mn><mo stretchy="false">/</mo><mn>255</mn></mrow></msub></math> . The actual performance of Algorithm 3 also varies significantly with the value of μ since μ also has substantial influence on the rejection rate of Algorithm 3 in the case where 0 < σ < 1. Using Algorithm 3 one can obtain about 21.63 × 10<sups>6</sups>, 12.76 × 10<sups>6</sups>, 11.6 × 10<sups>6</sups> sample values per second from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>2</mn><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>2</mn></mrow></msub></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>2</mn><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>4</mn></mrow></msub></math> , and <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mrow><mi mathvariant="script">D</mi></mrow><mrow><mi mathvariant="double-struck">ℤ</mi><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>2</mn><mo>,</mo><mn>1</mn><mo stretchy="false">/</mo><mn>8</mn></mrow></msub></math> respectively.

Taking μ = 1/3 as an example, we tested the performance of Algorithm 1 and Algorithm 3 with 1/10 ≤ σ ≤ 1, and Fig. 5 shows the results. We can see that the performance of Algorithm 1 decreases significantly with the decrease of parameter σ, while the performance of Algorithm 3 remains above 7.0 × 10<sups>6</sups> sample values per second.

Graph: Fig. 5 The Actual Performance of Algorithm 1 and Algorithm 3 with 1/10 ≤ σ ≤ 1 and μ = 1/3 (106 sample values per second)

Conclusion

In this paper, we give a rigorous and complete analysis of the rejection rate of Karney's exact sampling algorithm for discrete Gaussian distributions over the integers. Karney pointed out in his paper that the rejection rate of the algorithm is about 1/0.715, but did not give a proof. We give a rigorous proof, which involves the notion of the smoothing parameter of the one-dimensional integer lattice <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="double-struck">ℤ</mi></math> . The rejection rate can approximately be given by 2.03/τ(σ) and the value of μ has little effect on the rejection rate for any rational σ ≥ 1, where τ = σ/⌈σ⌉. This means that for an integer σ or a large σ the rejection rate of Karney's algorithm is almost independent of the parameters σ, μ and of the output z, and Karney's algorithm has the potential to be modified to resist timing attacks.

Karney did not consider the case where 0 < σ < 1 in his paper. We present a complete analysis of the rejection rate in this case. The results show that Karney's algorithm cannot generate integers efficiently when σ is very small (e.g. much smaller than 1/2). We propose an alternative algorithm for this special case, which can sample exactly and efficiently from discrete Gaussian distributions with very small σ. We show the probability that our proposed algorithm generates an integer as the output is at least about 1/2 when σ approaches 0. The experimental results demonstrate the effectiveness of our proposed algorithm.

We also try to give an explanation of Karney's sampling algorithm as well as our proposed sampling algorithm for discrete Gaussian distributions from the view of mapping distributions. The sampling process involves a one-to-one mapping from a set of integer tuples satisfying certain conditions to the set of all the integers, it can be viewed as querying randomly from a set of all the possible integer tuples. If an integer tuple satisfying the conditions is found, then the algorithm probabilistically accepts or rejects the integer tuple, and get an integer from the discrete Gaussian distribution by the mapping.

Acknowledgements

This work was supported by Guangdong Major Project of Basic and Applied Research (2019B030302008), National Natural Science Foundations of China (Grant No. 61972431), and Guangdong Basic and Applied Basic Research Foundation (2020A1515010687, 2022A1515011512); Guangzhou Basic and Applied Basic Research Foundation (202102080332).

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

References

1 Andrysco, M, Kohlbrenner, D, Mowery, K, Jhala, R, Lerner, S, Shacham, H: On subnormal floating point and abnormal timing. In: 2015 IEEE symposium on security and privacy, SP 2015, San Jose, CA, USA, May 17–21, 2015, pp 623–639. IEEE Computer Society (2015)

2 Bai S, Lepoint T, Roux-Langlois A, Sakzad A, Stehlé D, Steinfeld R. Improved security proofs in lattice-based cryptography: Using the Rényi divergence rather than the statistical distance. J. Cryptol. 2018; 31; 2: 610-640. 10.1007/s00145-017-9265-9. 1444.94043

3 Barthe, G, Belaïd, S, Espitau, T, Fouque, P.-A, Rossi, M, Tibouchi, M: GALACTICS: gaussian sampling for lattice-based constant-time implementation of cryptographic signatures, revisited. In: Cavallaro, L, Kinder, J, Wang, X.F, Katz, J. (eds.) Proceedings of the 2019 ACM SIGSAC CCS 2019, London, UK, November 11–15, 2019, pp 2147–2164. ACM (2019)

4 Bruinderink, L.G, Hülsing, A, Lange, T, Yarom, Y: Flush, gauss, and reload—a cache attack on the BLISS lattice-based signature scheme. In: Gierlichs, B, Poschmann, A.Y. (eds.) CHES 2016, Santa Barbara, CA, USA, August 17–19, 2016, Proceedings, Volume 9813 of LNCS, pp 323–345. Springer (2016)

5 Ducas, L, Durmus, A, Lepoint, T, Lyubashevsky, V: Lattice signatures and bimodal gaussians. In: Canetti, R, Garay, J.A. (eds.) CRYPTO 2013, Santa Barbara, CA, USA, August 18–22, 2013. Proceedings, Part I, Volume 8042 of LNCS, pp 40–56. Springer (2013)

6 Dwarakanath NC, Galbraith SD. Sampling from discrete gaussians for lattice-based cryptography on a constrained device. Appl. Algebra Eng. Commun. Comput. 2014; 25; 3: 159. 3219507. 10.1007/s00200-014-0218-3. 1372.94425

7 Espitau, T, Fouque, P.-A, Gérard, B, Tibouchi, M: Side-channel attacks on bliss lattice-based signatures: Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers. In: Proceedings of the 2017 ACM SIGSAC CCS, pp 1857–1874. ACM (2017)

8 Gentry, C, Peikert, C, Vaikuntanathan, V: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) STOC 2008, Victoria, British Columbia, Canada, May 17–20, 2008, pp 197–206. ACM (2008)

9 Howe J, Khalid A, Rafferty C, Regazzoni F, O'Neill M. On practical discrete gaussian samplers for lattice-based cryptography. IEEE Trans. Comput. 2018; 67; 3: 322-334. 3769475. 10.1109/TC.2016.2642962. 1390.94843

Karney, C, F: Sampling exactly from the normal distribution. ACM Trans. Math. Softw. 42(1), 3:1–3:14 (2016)

Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. J. ACM. 2013; 60; 6: 43:1-43:35. 3144913. 10.1145/2535925. 1281.68140

Micciancio D, Regev O. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput. 2007; 37; 1: 267-302. 2306293. 10.1137/S0097539705447360. 1142.68037

Micciancio, D, Walter, M: Gaussian sampling over the integers: Efficient, generic, constant-time. In: Katz, J, Shacham, H. (eds.) CRYPTO 2017, Santa Barbara, CA, USA, August 20–24, 2017, Proceedings, Part II, Volume 10402 of LNCS, pp 455–485. Springer (2017)

Peikert, C: Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract. In: Mitzenmacher, M. (ed.) STOC 2009, Bethesda, MD, USA, May 31–June 2, 2009, pp 333–342. ACM (2009)

Peikert, C: An efficient and parallel gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010, Santa Barbara, CA, USA, August 15–19, 2010. Proceedings, Volume 6223 of LNCS, pp 80–97. Springer (2010)

Prest, T: Sharper bounds in lattice-based cryptography using the Rényi divergence. In: Takagi, T, Peyrin, T. (eds.) ASIACRYPT 2017, Hong Kong, China, December 3–7, 2017, Proceedings, Part I, Volume 10624 of LNCS, pp 347–374. Springer (2017)

Regev O. On lattices, learning with errors, random linear codes, and cryptography. J. ACM. 2009; 56; 6: 34:1-34:40. 2572935. 10.1145/1568318.1568324. 1325.68101

Footnotes

A u-rand is a uniform deviate over the range (0,1). It is not a floating-point number sampled in (0,1). Instead, it is a fraction represented by a radix point followed by an arbitrary number of digits in some base b, and the arithmetic operations are restricted to those that can be completed with a knowledge of only an initial portion of the fraction.

Graph: Fig. 1 The "blockier" version of the bell curve of discrete Gaussian distribution Dℤ,3,1/4. The probability of finding and accepting in T an integer 3-tuple (k,j,s) that meets the conditions is proportional to ρ3,1/4(s(⌈3k+s4⌉+j))

Intuitively, none of integers are missed, and there is no double-counting for every integer. Every integer can be uniquely expressed in this form.

By Yusong Du and Xiao Ma

Reported by Author; Author

Treffer: On the Rejection Rate of Exact Sampling Algorithm for Discrete Gaussian Distributions over the Integers

Weitere Informationen

On the Rejection Rate of Exact Sampling Algorithm for Discrete Gaussian Distributions over the Integers

Introduction

Exact Discrete Gaussian Sampling over the Integers

Our Motivation

Our Contribution

Preliminaries

Floor and Ceiling Functions

Karney's Exact Sampling Algorithm

The Rejection Rate of Karney's Algorithm for σ ≥ 1

Lemma 1

Proof

Corollary 1

Corollary 2

Definition 1 (a special case of 12, Definition 3.1)

Lemma 2 (a special case of 12, Lemma 3.3)

Lemma 3 (12, Lemma 2.8, implicit)

Theorem 1

Proof

The Rejection Rate of Karney's Algorithm for 0 < σ < 1

Lemma 4

Proof

Corollary 3

Corollary 4

Proof

Theorem 2

Proof

Corollary 5

Proof

Corollary 6

Proof

An Alternative Algorithm for Dℤ,σ,μ with Very Small σ

Theorem 3

Proof

Corollary 7

Proof

Experimental Results

Conclusion

Acknowledgements

Publisher's Note

References

Footnotes

Links

Zusatz-Funktionen