Polar sampler: A novel Bernoulli sampler using polar codes with application to integer Gaussian sampling

In this work, we propose a novel Bernoulli sampler using polar codes and apply it to DGS over the integers. Polar codes are the first class of efficiently encodable and decodable codes which provably achieve channel capacity of symmetric channels [3]. It can also achieve Shannon’s data compression rate [4]. The power of polar codes stems from the polarization phenomenon: under Arıkan’s polar transform, information measures of synthesized sources (or channels) converge to either 0 or 1 when coding becomes trivial. Moreover, the state-of-the-art decoding runs with \(O(N\log \log N)\) complexity where N denotes the block length of a polar code [38]. Given their attractive performance, polar codes have found a wide range of applications in information theory and communication systems. In particular, they have been standardized for the fifth-generation (5G) wireless communication networks.

This work tackles the sampling problem from a source coding perspective, namely, sampling can be considered the inverse problem of source coding. In source coding or data compression, one typically encodes a block of symbols of a certain distribution into some bits which become uniformly random as the block length tends to infinity [9]. Since a source code is invertible, inverting this process would produce samples from the desired distribution. Polar sampling is well suited for applications where a large number of independent discrete Gaussian samples are required (e.g. fully homomorphic encryption (FHE), digital signatures) as the averaged randomness consumption per sample decreases asymptotically to the optimum thanks to the polarization effect. Note that the polar sampler is not restricted to sampling from the discrete Gaussian distribution, but can be extended to other distributions of interest in cryptography.

The principal contributions of this paper are summarized as follows:The proposed multilevel polar sampler scheme complements and distinguishes from existing discrete Gaussian samplers in the literature. In addition to offering a different approach, it exhibits several salient features:Of course, the proposed sampler can be combined with existing “expander” techniques such as convolution if needed. In this work, we focus on the theoretic design and analysis of polar samplers, whereas various optimization issues (e.g., concrete computational/storage costs etc.) are left to future work. Nevertheless, we have found it in experiments that even a prototype implementation significantly outperforms the Knuth–Yao sampler in speed in benchmark experiments.

The roadmap of this paper is given as follows. Section 2 introduces the proposed Bernoulli sampler, i.e., polar sampler, and elucidates its relation to polar source coding. Section 3 presents how we devise an integer Gaussian sampler using multiple polar samplers. Section 4 analyses the approximation error of our integer Gaussian sampler based on KL divergence. In Sect. 5, the security, precision and parameter selection are discussed based on KL and Rényi divergence. Section 6 gives a comprehensive analysis of the constant-time feature and compares our integer Gaussian sampler with state-of-the-art samplers regarding the complexity. Section 7 concludes this paper.

Given a vector \(x^{1:N}\) and a set \(\mathcal {A} \subset \{1,\ldots ,N\}\), we denote by \(x_{\mathcal {A}}\) the subvector of \(x^{1:N}\) indexed by \(\mathcal {A}\) and denote by \(x^{(i)}\) the i-th coordinate of \(x^{1:N}\). A capital letter is used to denote a variable while its lowercase represents a realization. Denote by \(X\sim P\) a distribution P of X over a countable set \(\mathcal {X}\). Then the entropy of X is defined as \(H_P(X)=-\sum _{x\in \mathcal {X}}p(x)\log {p(x)}\). We write \(H(X)=H_P(X)\) for brevity if the distribution is clear. Suppose X and Y have a joint distribution P(X, Y). The conditional entropy of X given Y is defined as \(H(X|Y)=\sum _{x\in \mathcal {X},y\in \mathcal {Y}}p(x,y)\log \frac{p(y)}{p(x,y)}\). The logarithm to base 2 is denoted by \(\log \) while the natural logarithm is denoted by \(\ln \).

The key idea of polar source coding can be found in [4] where a polar code was proposed to achieve Shannon’s source coding bound. Let \((X^{1:N},Y{}^{1:N})\) denotes N i.i.d. copies of a memoryless source (X, Y) of joint distribution \(P_{X,Y}\), where X takes values over \(\mathcal {X}=\{0,1\}\) while Y takes values over a countable set \(\mathcal {Y}\). The two random source X and Y are correlated, and Y is called the side-information. In source coding, the encoder compresses a sequence \(X^{1:N}\) into a shorter codeword such that the decoder can yield an estimation \(\hat{X}^{1:N}\) of \(X^{1:N}\) given the shorter codeword and side information \(Y^{1:N}\).²

Polar codes are proved to achieve Shannon’s source coding bound asymptotically. The source polarization transform from \(X^{1:N}\) to \(U^{1:N}\) is performed by applying an entropy-preserving circuit to \(X^{1:N}\), i.e.,where \(^{\otimes n}\) denotes the n-th Kronecker power, and \(B_{N}\) is a bit-reversal permutation [3] of the input vector. Figure 1 illustrates the source polarization transform of \(X^{1:2}\) and \(X^{1:4}\) where \(\oplus \) denotes mod-2 sum. This transform preserves the entropy in the sense thatMeanwhile, it also polarizes the entropy in the sense thatand

By applying the construction in Fig. 1 recursively, we derive a bijection \(U^{1:N}=X^{1:N}G_{N}\) inducing a combined source pair \((U^{1:N},Y^{1:N})\) and a transition \(W_{N}:U^{1:N}\rightarrow Y^{1:N}\). This combined source pair is then split into N synthesized source pairs \((U^{(i)},Y^{1:N}\times U^{1:i-1})\) giving rise to N sub-transitions \(W_{N}^{(i)}:{U^{(i)}}\rightarrow {Y}^{1:N}\times {X}^{1:i-1}\). A polarization phenomenon happened to sub-source pairs is observed and stated as follows.

Note that in the absence of side information Y, the above theorem still holds by considering Y independent of X.

It is implied by Proposition 1 that for a source (X, Y), the parameters \(H(U^{(i)}\mid Y^{1:N},U^{1:i-1})\) and \(Z(U^{(i)}\mid Y^{1:N},U^{1:i-1})\) polarize simultaneously in the sense that \(H(U^{(i)}\mid Y^{1:N},U^{1:i-1})\) approaches 0 (resp. 1) as \(Z(U^{(i)}\mid Y^{1:N},U^{1:i-1})\) approaches 0 (resp. 1).

For \(\beta \in (0,1/2)\) and \(\alpha =2^{-N^{\beta }}\), the indexes of \(U^{1:N}\) can be divided into a low-entropy setand its complement \(\mathcal {L}^c{}_{X|Y}\). Again, in the absence of side information Y, the two sets are defined in the same way by considering Y independent of X and U.

This gives rise to the encoding and decoding scheme described in [4]. More specifically, for a realization of (\(X^{1:N},Y^{1:N})=(x^{1:N},y^{1:N})\), the encoder computes \(u^{1:N}=x^{1:N}G_{N}\) and only shares \(u_{\mathcal{L}^c_{X|Y}}\) with the decoder. The compression rate is defined as \(R = |\mathcal{L}^c_{X|Y}| / N\). The decoder can obtain an estimate \(\hat{u}^{1:N}\) of \(u^{1:N}\) in a successive manner aswhere \(L_{N}^{(i)}(y^{1:N},\hat{u}^{1:i-1})\) is called the likelihood ratio (LR) defined by

It implies that any compression rate \(R>H(X|Y)\) is achievable with a vanishing block error probability for polar source coding of sufficiently large N. As N goes to infinity, the polarization process removes the randomness of the low-entropy set almost surely while the other set becomes random. Additionally, the complexity of polar encoding and decoding are both \(O(N\log N)\).

Given the notion of memoryless source \((X,Y)\sim P_{X,Y}\) and polar source coding, we now consider the sampling problem, i.e., to sample from a Bernoulli distribution P(X) given (or without) side information Y. We propose a novel Bernoulli sampler called \(\text {PolarSampler}(\cdot )\) in Algorithm 1. The interfaces, key operations and subroutines are described as follows.

A good closeness metric can help reduce the complexity of implementation. In this section, we will evaluate the closeness error of the proposed sampling scheme.

Let \(P_{X^{1:N}}(x^{1:N})\) denote the distribution of N i.i.d. Bernoullis X defined as above. For any \(0<\beta <0.5\), \(N=2^n, n\ge 1\) and the corresponding high- and low-entropy sets defined in (9) and (6), one can generate a distribution \(Q_{X^{1:N}}(x^{1:N})\) using the rules (10) and (11). To give the KL divergence between \(P_{X^{1:N}}(x^{1:N})\) and \(Q_{X^{1:N}}(x^{1:N})\), we first modify the Bernoulli sampling rules (10) and (11) to bewhere only the deterministic decisions for \(U^{(i)}\) in \(\mathcal {L}_{X|Y}\) are replaced by random decisions. Let \(Q_{X^{1:N}}'(x^{1:N})\) denote the distribution derived by the new Bernoulli sampling rules described in (15) and (16).

Although we cannot give the KL divergence between \(P_{X^{1:N}}\) and \(Q_{X^{1:N}}\) due to the lack of triangle inequality, the absence of \(D_{KL}(P_{X^{1:N}}\Vert Q_{X^{1:N}})\) will not prevent us from giving the security analysis which will be explained in Sect. 5.

In a concrete implementation, an ideal discrete Gaussian distribution is replaced by an approximation. To give a sharp estimation of the accuracy/security of a cryptographic primitive, the closeness between the ideal distribution and its approximation should be measured. In this section, we will derive the upper bounds on the closeness between the ideal distribution and the one generated by our sampling scheme measured by KL divergence.

The approximation error comes from two sources, the tailcut (owing to finite levels of partitions) and the polar sampling. On the one hand, we need to decide how many levels of partitions are needed. On the other hand, the error introduced by polar sampling should also be analysed. Denote by \(D_{\mathbb {Z},c,s}\) the target discrete Gaussian distribution and we decide to employ r levels of partition. If polar sampling did not introduce any error, we would generate a distribution \(P_{X_{1:r}}\) with a closeness measure \(\delta (D_{\mathbb {Z},c,s},P_{X_{1:r}})\) which is determined only by r for some metric \(\delta \). In reality, polar sampling produces a distribution \(Q_{X_{1:r}}(x_{1:r})\) and it introduces an error of \(\delta (P_{X_{1:r}},Q_{X_{1:r}})\). We will in this section analyse the above two closeness quantities using Kullback–Leibler (KL) divergence.

Since the KL divergence does not satisfy the triangle inequality, we will give \(D_{KL}(D_{\mathbb {Z},c,s}\Vert P_{X_{1:r}})\) and \(D_{KL}(P_{X_{1:r}}\Vert Q_{X_{1:r}})\) separately rather than a total KL divergence \(D_{KL}(D_{\mathbb {Z},c,s}\Vert Q_{X_{1:r}})\). However, as discussed in [31, Chapter 3] the lack of symmetry and triangle inequality can be handled by a KL-based security argument which will be presented in Sect. 5.

The smoothing parameter quantifies how large s must be for \(D_{\Lambda ,{c},s}\) to behave like a continuous Gaussian distribution. It is implied by Definition 4 that for any \(\epsilon >0\), the smoothing parameter \(\eta _{\epsilon }(\mathbb {Z})\) of \(\mathbb {Z}\) is the smallest s such that \(\rho (s \mathbb {Z})\le 1+\epsilon \).

Instead of sampling over the full domain of the integer lattice, a distribution tail of negligible probability is cut off in practice. Suppose \(2^r\) samples are left after the tailcut. Let \(\mathcal {A}=\mathbb {Z}\cap [-2^{r-1}+c,2^{r-1}+c)\). The distribution of the finite set iswhere \(a\in \mathcal {A}\) and \(\gamma \) is the probability of the tail. This constellation \(\mathcal {A}\) of \(2^r\) points can be represented as a binary partition tree labeled by \(X_{1:r}\) in the same way as Fig. 4. In our sampling scheme, we derive a sample labeled byThere exists a one-to-one mapping from \(X_{1:r}\) to \(\mathcal {A}\). Therefore \(P_{X_{1:r}}\) and the tailcut distribution \(D_{\gamma }\) are exactly the same and we can obtain \(D_{KL}(D_{\mathbb {Z},c,s}\Vert P_{X_{1:r}})\) by calculating \(D_{KL}(D_{\mathbb {Z},c,s}\Vert D_\gamma )\). The distribution \(D_\gamma \) over the finite constellation \(\mathcal {A}\) can be written in the formThe KL divergence between \(D_\gamma \) and \(D_{\mathbb {Z},c,s}\) isAccording to the second-order Taylor bound, if \(D_{\mathbb {Z},c,s}(a\in \mathcal {A})=1-\gamma \) for any \(0<\gamma <1\), \(D_{KL}(D_\gamma \Vert D_{\mathbb {Z},c,s})\) is bounded byand so is \(D_{KL}(P_{X_{1:r}}\Vert D_{\mathbb {Z},c,s})\).

The target discrete Gaussian distribution is tailcut to be \(P_{X_{1:r}}\) which is exactly the distribution of r bits of Bernoullis. Let \(P_{X_{1:r}^{1:N}}\) denote the distribution of N i.i.d. \(X_{1:r}\). As discussed in Sect. 3, for properly chosen \(0<\beta <0.5\), \(N=2^n, n\ge 1\) and the corresponding high- and low-entropy sets defined in (26) and (27), one can approximate \(P_{X_{1:r}^{1:N}}\) in a level-by-level manner using PolarSampler\((\cdot )\) for r times giving rise to the produced distribution \(Q_{X_{1:r}^{1:N}}\).

Recall it in Theorem 3 that an intermediate distribution \(Q'\) is introduced to analyse the KL divergence between P and Q. Likewise, for every \(1\le k\le r\) we introduce an intermediate distribution \(Q'_{X_k^{1:N}}\) such that \(X_k^{1:N}=U_k^{1:N}G_N\) andwhere only the deterministic decisions for \(U_{k}^{(i)}\) in \(\mathcal {L}{}_{X_{k}|X_{1:k-1}}\) are replaced by random decisions. We can bound the KL divergence between \(P_{X_{1:r}^{1:N}}\) and \(Q'_{X_{1:r}^{1:N}}\) aswhere the equalities and inequalities are derived by (a) one-to-one mapping from \(X_{1:r}^{1:N}\) to \(U_{1:r}^{1:N}\); (b) the chain rule of joint distribution; (c) the chain rule of KL divergence; (d) Theorem 3. Likewise, we bound the KL divergence between \(Q_{X_{1:r}^{1:N}}\) and \(Q'_{X_{1:r}^{1:N}}\) aswhere the inequality (e) is derived by Theorem 3. An explicit security analysis based on the KL divergence \(D_{KL}(P_{X_{1:r}}\Vert D_{\mathbb {Z},c,s})\), \(D_{KL}(P_{X_{1:r}^{1:N}}\Vert Q'_{X_{1:r}^{1:N}})\) and \(D_{KL}(Q_{X_{1:r}^{1:N}}\Vert Q'_{X_{1:r}^{1:N}})\) will be given in the sequel.

Security argument [31] It can be concluded from Lemma 3 that if a scheme is \(\lambda \)-bit secure with oracle access to a perfect distribution \(\mathcal {P}\) and the KL divergence between \(\mathcal {P}\) and another distribution \(\mathcal {Q}\) satisfies \(D_{KL}(\mathcal {P}\Vert \mathcal {Q})\le 2^{-\lambda }\), then this scheme is also about \(\lambda \)-bit secure with oracle access to \(\mathcal {Q}\). Note that this security argument holds only if \(\mathcal {E}\) is a search problem but not a decisional one. The security argument based on KL divergence satisfies symmetry and triangle inequality though KL divergence itself does not (see [31, Sect. 3.2] for detail).

Consider that a scheme with access to a perfect distribution \(D_{\mathbb {Z}^N,c,s}\) is \(\lambda \)-bit secure. Assume an adversary obtains N samples at each query. By the additivity of KL divergence and Eq. (31), we have \(D_{KL}(D_{\mathbb {Z}^{1:N},c,s}\Vert P_{X_{1:r}^{1:N}})\le N(\gamma +\gamma ^2)\). In order to achieve \(\lambda \)-bit security after the tailcut, we need to set \(N(\gamma +\gamma ^2)\approx 2^{-\lambda }\) by selecting \(t\approx \sqrt{(\lambda +\log N)\ln 2/\pi }\). The number of levels needed is therefore \(r=\lceil \log (2t\cdot s) \rceil \). As given in Sect. 4.3, the approximation error introduced by polar sampling is determined by both \(D_{KL}(P_{X_{1:r}^{1:N}}\Vert Q'_{X_{1:r}^{1:N}})\) and \(D_{KL}(Q'_{X_{1:r}^{1:N}}\Vert P_{X_{1:r}^{1:N}})\) which are upper bounded asIn order to preserve \(\lambda \)-bit security after \(P_{X_{1:r}^{1:N}}\) is replaced by \(Q_{X_{1:r}^{1:N}}\), we need to select \(n=\log N\) and \(\beta \) properly such that \(2^{-2^{n\beta }+n+\log (r)+1}\approx 2^{-\lambda }\).

Figure 6 shows how the security level of interest is related to \(\beta \) in terms of different s and n. We can observe that the curves with the same n but different in s are quite close. It is understandable because the security is dependent on the approximation error as is almost independent of what the target distribution is if the proposed GaussianSampling\((\cdot )\) is used. We also find that to preserve \(\lambda =128\) bits of security, a larger n implies a smaller \(\beta \). This is because larger n means deeper polarization and therefore smaller unpolarized set (i.e. smaller \(\beta \)). This observation is instructional in selecting parameters for GaussianSampling\((\cdot )\). At the implementation stage, the entropy consumption to produce \(U_k^{(i)}\) are totally different for polarized and unpolarized set. Given optional choices of \(\beta \) and n to preserve \(\lambda \)-bit security, we suggest smaller \(\beta \) for less entropy consumption per sample.

The KL-based security analysis is a reminder about Rényi divergence (RD). However, the approximation error of the proposed sampler measured by Rényi divergence is not given in this work because how polarization phenomenon converges in the metric of RD is an open problem in the area of coding theory. Nonetheless, RD can still be used to analyse the tailcut and precision.

In [32], a sharper bound on security based on Rényi divergence is given under the assumption that the number of adversarial queries q to a \(\lambda \)-bit secure scheme is far less than \(2^\lambda \). Consider a cryptographic scheme with \(\lambda \) bits of security and the number of queries to \(\mathcal {Q}\) satisfies \(q\le 2^{64}\). By the security argument in [32], this scheme is proved to lose at most one bit of security when \(\mathcal {Q}\) is replaced by \(\mathcal {Q}_\gamma \) provided that one of following conditions is satisfied. In the context of multilevel polar sampling, if \(t\approx \sqrt{\frac{\ln 2(66+\log N)}{\pi }}\) and \(r=\left\lceil \log \left( 2s \sqrt{\frac{(66+\log N)\ln 2}{\pi }}\right) \right\rceil \), a \((\lambda +1)\)-bit secure scheme will be at least \(\lambda \)-bit secure when the ideal distribution \(D_{\mathbb {Z},c,s}\) is replaced by its tailcut \(P_{X_{1:r}}\) for \(\lambda =128\), \(q=2^{64}\) and \(a=2\lambda \). Compared with the KL-based analysis of tailcut, Rényi divergence contributes to a smaller r by reducing the partitions by at most 1 level. Moreover, the security argument for relative error can be translated to \(\gamma \le 2^{-36.5}\) for \(\lambda =128\), \(q=2^{64}\) and \(a=2\lambda \) [32]. The precision requirement of polar sampler to achieve the target security is determined by the Bernoulli sampling step in formula (28) and (29). A practical approach to draw Bernoulli samples is to calculate the bias \(Q_{\gamma }\) subject to the relative precision provided. Then sample \(q\in (0,1)\) uniformly at random and yield 1 if \(q<Q_{\gamma }\). As long as the relative precision provided for the LR recursions in Algorithm 2 and the biases computed in formula (28) and (29) is more than 36 bits, polar sampler can achieve \(\lambda =128\). In our application, it suffices to use double precision in the LR recursions which provides 52 bits of relative precision. It can also be simulated using fixed-point numbers of 64 bits of precision particularly in 64-bit architectures.

Given a probabilistic or deterministic algorithm, we consider it to be constant-time if its execution time is independent of the sensitive part of its input and output [17]. Instead of making every operation finish exactly in a constant interval, we protect sensitive information from being recovered by timing-based side channel attacks. The proposed \(\text {GaussianSampling}(\cdot )\) algorithm composes of multiple serially connected \(\text {PolarSampler}(\cdot )\). We now study which part of \(\text {PolarSampler}(\cdot )\) is constant-time and which part is not.

The input of \(\text {PolarSampler}(\cdot )\) includes the block length N, the side information vector \(y^{1:N}\), a precomputed bias table \({{\textbf {c}}}\) and the corresponding high- and low-entropy sets \(\mathcal {H}_{X|Y},\mathcal {L}_{X|Y}\), meanwhile it yields a Bernoulli sample vector \(x^{1:N}\). Normally, we do not expect to disclose either the Bernoulli biases or the output samples. Therefore, it makes sense to consider N and \(y^{1:N}\) to be non-sensitive as they are irrelevant to what the target biases and output samples are. Table \({{\textbf {c}}}\) and the two sets \(\mathcal {H}_{X|Y},\mathcal {L}_{X|Y}\) are sensitive as the Bernoulli biases \(P(X=1|Y)\) for every \(Y=y\) are stored in \({{\textbf {c}}}\) and \(\mathcal {H}_{X|Y},\mathcal {L}_{X|Y}\) are also computed according to \(P(X=1|Y)\).

\(\text {PolarSampler}(\cdot )\) composes of four types of operations: (a) table lookup for \({{\textbf {c}}}[y^{1:N}]\) given \(y^{1:N}\); (b) recursive calculating the LRs by SC decoding; (c) probabilistic/deterministic sampling of 1 bit; (d) calculating \(x^{1:N}=u^{1:N}G_N\). Whether these operations are relevant to the aforementioned sensitive information is listed in Table 1.

Firstly, the table lookup for \({{\textbf {c}}}[y^{1:N}]\) may remind us of the cache-based attack breaking BLISS which exploits the weakness of CDT table search and the Bernoulli sampling with a precomputed table of exponential values [8]. Fortunately, this is not the case for \(\text {PolarSampler}(\cdot )\). On one hand, the bias vector \({{\textbf {c}}}[y^{1:N}]\) is indexed by the side information \(y^{1:N}\) and no binary search or search-with-guide-table method as in CDT sampling is needed. On the other hand, the Bernoulli sampler in BLISS leaks information about the yielded Bernoulli samples because of the conditional branching in the table lookup and bitwise sampling process. As a result, Bernoulli samples yielded faster (resp. slower) are more likely to be 0 s (resp. 1 s). But such conditional branches are not needed when searching for \({{\textbf {c}}}[y^{1:N}]\) in \({{\textbf {c}}}\) as long as table \({{\textbf {c}}}\) is allocated with continuous memory. In this case one can easily find \({{\textbf {c}}}[y^{1:N}]\) by moving the pointer to \({{\textbf {c}}}\) by offset \(y^{1:N}\). This operation is irrelevant to what the biases and the output are.

Secondly, if the block length is N, the SC decoding carries out exactly \(\frac{N\log N}{2}\) LR calculations as in formula (13) along with exactly \(\frac{N\log N}{2}\) LR calculations as in formula (14) regardless of what the input and output are. Concerns arise from the floating-point instructions and a comprehensive analysis is given as follows.Thirdly, line 6, 9 and 12 of Algorithm 1 are non constant-time with respect to the input if no further measurements are taken. Sampling for the high- and low-entropy sets would be easy as it consumes only 1 bit of randomness for \(\mathcal {H}_{X|Y}\) and 0 for \(\mathcal {L}_{X|Y}\), whereas sampling for \(\mathcal {H}_{X|Y}^{c}\backslash \mathcal {L}_{X|Y}\) is complicated and would take longer time. Therefore, the running time of line 6, 9 and 12 may reveal the proportion of \(\mathcal {H}_{X|Y},\mathcal {L}_{X|Y}\) and \(\mathcal {H}_{X|Y}^{c}\backslash \mathcal {L}_{X|Y}\) which in turn discloses some information about the biases. As for the output, we consider it to be safe regardless of the running time of line 6, 9 and 12. The weak points are those floating-point comparisons in line 9 and 12. Generally speaking, comparing two approximate floating-point values would take longer, but it is equally likely to return \( {True}\) and \( {False}\) nonetheless. Therefore, it makes sense to consider this type of operations to be unsafe with respect to input but safe with respect to output.

Lastly, calculating \(x^{1:N}=u^{1:N}G_N\) takes exactly \(N\log N \) binary additions which is obviously constant-time.

To conclude, we claim that \(\text {PolarSampler}(\cdot )\) is constant-time in the sense that its running time is irrelevant to the output samples. The same statement holds for the proposed integer Gaussian sampling for two reasons if \(\text {PolarSampler}(\cdot )\) is adopted as in Algorithm 4. Firstly, the number of levels r is determined by the width of the integer Gaussian distribution. Secondly, if no further measurements are taken, the floating-point implementation of \(\text {PolarSampler}(\cdot )\) is non constant-time with respect to input.

The latest trend of DGS solutions is to expand a base sampler into one for arbitrary parameters. For example, the Knuth–Yao and CDT sampler can work as a base sampler to produce samples which are then combined into new samples with a relatively large standard deviation in a convolutional manner [26, 30]. Our Gaussian sampler is also eligible for such extension for potential speedup. The focus of this subsection is to compare the GaussianSampling\((\cdot )\) with other base samplers. Karmakar et al. [19] compared the time complexity of Knuth–Yao and CDT showing that the former can be made more time-saving. Therefore, it is fair to compare our Gaussian sampler only with Knuth–Yao and we used a non constant-time Knuth–Yao implemented in C++⁷ as well as its constant-time version.⁸ We also give the benchmarks of a prototype GaussianSampling\((\cdot )\) for different choices of parameter s in C++.⁹ Note that we substitute probability recursion for LR recursion (see Appendix B) to avoid floating-point divisions.

The experiment is conducted on a PC with Ubuntu 18.04 and an Intel i9-9900K processor running at 3.60 GHz using one core. We use \(\textsf {g}\)++ to compile both Knuth–Yao and our implementation with compilation flag -\(\textsf {Ofast}\) enabled. For the benchmarks, we select \(s\in \sqrt{2\pi }\cdot \{3,8,32,256\}\) and a target security level \(\lambda =64\).¹⁰ According to the KL-based security analysis in Sect. 5, we specify \(\beta \) to achieve 64 bits of security with respect to \(N\in \{2^{13},2^{14},2^{15}\}\), and we select \(r=\lceil \log (2s t) \rceil \) where \(t\approx \sqrt{(\lambda +\log N)\ln 2/\pi }\). We assume that the adversary obtains N integer samples for each query to the sampling algorithm. The simulation results are shown in Table 2. Firstly, our Gaussian sampler always outperforms Knuth–Yao in speed with respect to the above setting. Secondly, Knuth–Yao slows down almost linearly as \(2^r\) grows while GaussianSampling\((\cdot )\) still provides a competitive speed. This advantage stems from the binary partition of the integers. Thirdly, GaussianSampling\((\cdot )\) shows modest speed reduction as the block length increases from \(2^{13}\) to \(2^{15}\). This doesn’t contradict the asymptotic information optimality which implies less randomness consumption per sample for larger N. The polarization effect can reduce the consumption of randomness and contribute to the speed. However, the overall running time, in the current implementation, is dominated by the floating-point recursions in Fig. 3 with complexity \(O(N\log N)\). In the literature, practical boosting approaches for the butterfly circuit include semi-parallel design [21] and pruned SC decoding [1, 38] giving computational complexity up to \(O(\log \log N)\).

At the construction stage, we need to store a table \({{\textbf {c}}}\) of biases, i.e., \(P({x_k=1|x_{1:k-1}})\) for \(1\le k\le r\). The table consists of \(2^{r}-1\) elements for the overall r levels. The biases are stored in natural order of \(X_{1:k-1}\) such that once the samples \(x_{1:k-1}\) for the preceding \(k-1\) levels are ready we can find the associated biases in \({{\textbf {c}}}\) by moving the pointer by offset \(x_{1:k-1}\).

We also give in Table 3 an asymptotic comparison of entropy consumption, computational and storage complexity between GaussianSampling\((\cdot )\) and other existing samplers, e.g. the binary sampling algorithm [11], constant-time CDT [16], constant-time Knuth–Yao sampler [19].

The overall running time of GaussianSampling\((\cdot )\) depends on the SC decoding (LR recursions) and Bernoulli sampling (entropy consumption). As indicated in Corollary 1, the fraction of unpolarized set scales as \(N^{-\frac{1}{\mu }}\). When \(N\rightarrow \infty \), the average entropy consumption approaches H(X) which is the Shannon’s entropy of the target distribution X.

For binary sampling in BLISS [11], one sample requires entropy consumption of approximately \(6 + 3 \times \log (s)\) . If we use a full-table access CDT for the base sampler and use a full-table access Bernoulli sampler, the computational complexity would be \(O(\log (t \times s_0))\) (\(s_0\): the parameter of a base sampler) for table lookup plus some constant number of integer arithmetic and the entropy cost will be much greater than \(6+3 \times \log (s)\). Falcon uses bimodal Gaussian and rejection sampling which should have similar complexity to binary sampling.

The full-table access CDT [16] has a computational complexity of \(O(\log (t \times s))\) and requires a storage of \(O(\lambda \times t \times s)\). The constant-time Knuth–Yao in [19], which is a variant of standard Knuth–Yao in [12] and performs totally different types of operations, has a computational complexity of \(O(\log (t \times s))\) for Boolean function evaluations with \(\lambda \) random bits of input and its entropy consumption is \(O(\lambda )\). It requires large programmable memory to store \(O(\log (t*s))\) Boolean functions.

In conclusion, we claim our multilevel polar sampler to achieve the information-theoretic optimality (i.e., asymptotically optimal entropy consumption) which compares favorably with other samplers. For most sampling methods, the overall speed depends on computational complexity and randomness generation (e.g. producing Bernoulli samples in the binary sampling method). The computational complexity of our sampler is less attractive due to the \(\log (N)\) factor but (a) multilevel polar sampler saves the time of producing randomness which is not considered as computational complexity but entropy consumption (b) our experiments in Table 2 show that multilevel polar sampler is much faster than a standard Knuth–Yao [12]. In addition, there is room to improve the computational efficiency seeing that the state-of-the-art SC decoding achieves a per-bit complexity of \(O(\log \log N)\) [38].