# Rejection Sampling Revisit: How to Choose Parameters in Lattice-Based Signature

Authors: Zhongxiang Zheng; Anyu Wang; Lingyue Qin
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Rejection sampling technology is a core tool in the design of lattice-based signatures with ‘Fiat–Shamir with Aborts’ structure, and it is related to signing efficiency and signature, size as well as security. In the rejection sampling theorem proposed by Lyubashevsky, the masking vector of rejection sampling is chosen from discrete Gaussian distribution. However, in practical designs, the masking vector is more likely to be chosen from bounded uniform distribution due to better efficiency and simpler implementation. Besides, as one of the third-round candidate signatures in the NIST postquantum cryptography standardization process, the 3rd round version of CRYSTALS-Dilithium has proposed a new method to decrease the rejection probability in order to achieve better efficiency and smaller signature size by decreasing the number of nonzero coefficients of the challenge polynomial according to the security levels. However, it is seen that small entropies in this new method may lead to higher risk of forgery attack compared with former schemes proposed in its 2nd version. Thus, in this paper, we first analyze the complexity of forgery attack for small entropies and then introduce a new method to decrease the rejection probability without loss of security including the security against forgery attack. This method is achieved by introducing a new rejection sampling theorem with tighter bound by utilizing Rényi divergence where masking vector follows uniform distribution. By observing large gaps between the security claim and actual security bound in CRYSTALS-Dilithium, we propose two series of adapted parameters for CRYSTALS-Dilithium. The first set can improve the efficiency of the signing process in CRYSTALS-Dilithium by factors of61.7%and41.7%, according to the security levels, and ensure the security against known attacks, including forgery attack. And, the second set can reduce the signature size by a factor of 14.09% with small improvements in efficiency at the same security level.


---

## Body

## 1. Introduction

With the rapid developments in quantum algorithms and computations, research in lattice-based cryptography has attracted considerable attention because lattice-based cryptosystems are likely to be effective against quantum computing attacks in the future. The first lattice-based cryptosystem is proposed by Ajtai and Dwork [1] in 1997 which is also known as the first cryptosystem that achieves worst case to average case reduction. Since then, many well-known lattice-based cryptosystems have been designed, including GGH [2] by Goldreich et al. and NTRU [3] by Hoffstein et al., as well as LWE by Regev [4]. Nowadays, schemes with various features, such as digital signatures [5, 6], identity-based and attribute-based encryption [7, 8], zero-knowledge proof [9], and fully homomorphic schemes [10], can be realized based on these basic designs. On the contrary, the developments of methods in solving lattice problem including enumeration [11, 12] and lattice reduction algorithms [13, 14], as well as sieving algorithms [15, 16], also contribute to the selection of parameters in these schemes. As a result, lattice-based cryptosystems are now regarded as promising candidates for the NIST postquantum cryptography standardization process.Most lattice-based signatures are designed based on three general structures, namely, GGH structure, Fiat–Shamir structure, and GPV trapdoor structure. The GGH signature is the first practical lattice-based signature scheme which is proposed in [2] and known as the source of signatures following the GGH structure. This scheme is based on the closest vector problem (CVP) and enjoys the advantages such as high efficiency, small signature size, and simple verification. However, analysis [17] shows that signatures of the scheme leak the information of the secret key; thus, the secret key can be recovered by collecting enough number of signatures. As a result, many variants based on GGH structure concentrate on improving the security against the attack proposed in [17]. As for another basic type, Fiat–Shamir structure is first used to design practical lattice-based signature scheme in [18]. This work combines the Fiat–Shamir structure with rejection sampling technology to avoid the risk of secret leakage. Due to its high security, high efficiency, and small signature size, many variants have been proposed based on this work including [19–21]. Among the signature schemes based on Fiat–Shamir structure, two schemes named CRYSTALS-Dilithium [22] and qTESLA [23] have been widely studied because they are known as the 2nd round NIST postquantum cryptography standardization candidates. Moreover, recently CRYSTALS-Dilithium has become one of the 3rd round NIST candidates of signatures. The other type of lattice-based signature schemes is based on GPV trapdoor structure [24], such as [25, 26]. Compared with those based on Fiat–Shamir structure, the schemes have smaller signature size but lower efficiency. Furthermore, it should be noted that the scheme FALCON [27] is a 3rd round NIST postquantum cryptography standardization candidate with the GPV trapdoor structure.As an important subroutine in Fiat–Shamir structure, rejection sampling technology is widely used in the design of signatures schemes. The idea of this process is simple but effective, where it demands the signer selectively outputs signatures to ensure that the secret key should not be leaked by signatures. To achieve this goal, the rejection sampling process will choose to output a signature or reject it according to a fixed condition. This technology is first introduced in [18] and then further improved in [19]. When first introduced in [18], the vector for masking the secret is chosen from a bounded uniform distribution and then changed to be chosen from discrete Gaussian distribution in [19]. Besides, a theoretical analysis is also provided in [19] to prove that, under properly chosen parameters, a masking vector sampled from discrete Gaussian distribution can be used to protect the secret key from leakage by ensuring the outputted distribution of the rejection sampling process is statistically close to a certain discrete Gaussian distribution. In other words, the upper bound of statistical distance between the output distribution and the ideal one is small.Although discrete Gaussian distribution enjoys the property of high security, sampling from it demands more time and space complexity than from a uniform distribution. As a result, many practical schemes choose to sample from a bounded uniform distribution for the masking vector including the two NIST candidates, CRYSTALS-Dilithium [22] and qTESLA [23]. Besides, the method to increase the success probability of rejection sampling without loss of securities is an important issue in the design of these schemes. For example, in the third-round version of CRYSTALS-Dilithium, a new technique is used to decrease the rejection probability to achieve better efficiency and smaller signature size by decreasing the number of nonzero coefficients of the challenge polynomial according to the security levels. However, it is seen that small entropies in this new method may lead to higher risk of forgery attack compared with former schemes proposed in the 2nd version which will be described in Section 2.In this paper, we propose another way to increase the success probability of rejection sampling without loss of security. This idea is obtained by firstly proposing a more practical rejection sampling theorem with masking vector sampled from bounded uniform distribution, where a tighter bound is achieved by using Rényi divergence rather than statistical distance. Secondly, we use the proposed theorem to analyze the parameters used in CRYSTALS-Dilithium and observe that more accurate security estimation can be obtained due to the new rejection sampling theorem which allows us to adjust the parameters by balancing the securities and optimize their efficiencies as well as sizes. Our result shows that, by choosing proper parameters, the efficiency of sign algorithm in CRYSTALS-Dilithium can be further improved depending on the security levels. As lattice-based signatures with the Fiat–Shamir structure usually have higher efficiency but larger size compared with other types of lattice-based signatures, how to minimize the size of public key and signature is a core issue in the designs. So, we further propose a variant of the scheme with optimized size by utilizing our rejection sampling theorem which reduces the size of signature at the same security level. This is the third contribution of our paper.The rest of the paper is organized as follows. InSection 2, we introduce some background about lattice, discrete Gaussian sampling, LWE problem, divergences, and rejection sampling technology. Our analysis of the rejection sampling theorem for the uniform distribution and its proof are presented in Section 3. In Section 4, some applications of the above theorem are described, including a security analysis of CRYSTALS-Dilithium parameters and several variants of CRYSTALS-Dilithium which can provide higher efficiency of signing and smaller signature size. Finally, we give our conclusion in Section 5.


## 2. Preliminaries

Forx∈R, let ⌊x⌋ be the maximum integer that is no more than x and let ⌊x⌋ be the nearest integer to x. Let ℤq denote the set of integers in 0,q−1.


### 2.1. Lattice

Anm-dimensional lattice is a discrete additive subgroup in ℝm which can be represented as the set of integer linear combination of n linearly independent vectors b1,…,bn, i.e.,(1)ℒB=∑i=1nxibi|xi∈,∀i∈1,n,where B=b1,…,bn is called a basis of ℒ which is not unique, nn≤m is the rank of the lattice, a lattice is called full-rank if m=n. The determinant of ℒ is defined as(2)detℒ=detB⊤B.The quantitydetℒ is invariant regardless of the choice of B. The dual lattice ℒ∗ is defined as(3)ℒ∗=w∈Rm|∀v∈ℒ,w,v∈.q-ary lattice: as a kind of important lattices in lattice-based cryptography, a q-ary lattice refers to the lattice such that qZn⊆ℒ⊆Zn, where q is an integer.Two types ofq-ary lattices frequently used in lattice cryptography are defined as follows, with respect to an n×m matrix B∈Zqn×m:(4)ℒqB=y∈m|y=B⊤xmodq,x∈n,ℒq⊥B=y∈m|By=0modq.


### 2.2. Gaussian Distribution over Lattices

Fors>0, the Gaussian function is defined as(5)ρc,sy=e−πy−c2/s2,for y∈ℝm, where s is called the width. When s=1 or c=0, the corresponding subscript is usually omitted for simplicity.Definition 1.
(discrete Gaussian distribution). Fors>0 and c∈ℝm, the discrete Gaussian distribution Dℒ+c,s over ℒ+c is defined as(6)Dℒ+c,sx=ρsxρsℒ+c,where x∈ℒ+c and ρsℒ+c=∑x∈ℒ+cρsx. We call σ=s/2π the standard deviation for Dℒ+c,s.It is difficult to calculate the sumρsℒ directly, but it is related to the sum of values of a Gaussian function over the dual lattice according to the celebrated Poisson summation formula.Lemma 1.
(Poisson summation formula, see [28]). For an n-dimensional lattice ℒ, let s>0 and t∈Rn, and the following hold:(1)
ρsℒ=sn/detℒρ1/sℒ∗(2)
ρsℒ+t=sn/detℒ∑w∈ℒ∗e2πiw,tρ1/swThere is a tail bound for the continuous Gaussian distribution and the discrete Gaussian distribution also has a similar property which was first proven by Banaszczyk [28]. The following is a refinement to the bound of Banaszczyk given in [29].Lemma 2.
(tail bound, see [29]). For the variable X∼N0,1, then PrX>t≤2e−πt2. For an n-dimensional lattice ℒ and a vector t∈Rn, let s>0 and c≥1/2π, and we have(7)PrX⟵$Dℒ+t,sX>csn≤2πec2n/2e−πnc2ρsℒρsℒ+t.


### 2.3. LWE Problem

Learning with error (LWE) problem was proposed by Regev [4] in 2005 and has been widely used in the construction of lattice-based cryptography. We first introduce some definitions in order to describe LWE problems.Definition 2.
(LWE distribution). Letn≥1, q≥2 and χ be an error distribution over Zq; given a secret vector s∈Zqn, the LWE distribution Ls,χ over Zqn×Zq is sampled by choosing a⟵$UZqnUZqn and e⟵$χχ and outputting a,b=a,s+emodq.The LWE problem has a search version and a decision version, which are defined as follows.Definition 3.
(search-LWE). Givenm samples ai,bi∈Zqn×Zq that are independently sampled from Ls,χ with a fixed secret s∈Zqn, the goal of search-LWE is to find the secret vector s.In the following part of this paper, we denoteA∈Zqn×m to be the matrix formed by m columns aii=1m and b=b1,b2,…,bm⊤∈Zqm, where bi=ai,s+eimodq.Definition 4.
(decision-LWE). Givenm independent samples A,b∈Zqm×n×Zqm that follow either the LWE distribution Ls,χ with a fixed secret s∈Zqn or the uniform distribution, the goal of decision-LWE is to decide which distribution the samples follow.To make LWE more practical in cryptography, variants of LWE problems (e.g., ring-LWE and module-LWE) have been investigated. More details of these variants can be found in [30].


### 2.4. Statistical Distance and Rényi Divergence

Statistical distance and Rényi divergence are two measures of closeness of two probability distributions which are often used in security proofs. The definitions of statistical distance and Rényi divergence are as follows.Definition 5.
(statistical distance). For any two discrete probability distributionsP and Q over a countable support X, the statistical distance between the two distributions, denoted as Δsd, is defined by(8)ΔsdPQ=12∑k∈XPk−Qk.Definition 6.
(Rényi divergence). For any two discrete probability distributionsP and Q such that SuppP⊂SuppQ and α∈1,+∞, the Rényi divergence of order α, denoted as Δα, is defined by(9)ΔαPQ=∑k∈SuppPPkαQkα−11/α−1.According to the research of [31], using Rényi divergence to estimate security can provide smaller parameters in designing lattice-based schemes than using statistical distance.


### 2.5. Rejection Sampling

Rejection sampling is an important tool which is widely used in designing lattice-based signature [19, 22, 23]. It is first proposed in [18] and can be used to produce a distribution that is statistically close to another one. In this way, one can output a distribution without leaking information of the secret keys and the lower bound of the complexity against attacks which use the information of signatures and has been given in Theorem 1.Theorem 1.
(rejection sampling theorem, see [19]). Let V be a subset of Zm in which all elements have norms less than T, σ be some element in ℝ such that σ=ωTlogm, and h:V⟶R be a probability distribution. Then, there exists a constant M=O1 such that the distribution of the following algorithm A is as follows:(1)
v⟵$h,(2)
z⟵$Dv,σm,(3)
outputz,v with probability minρσmz/Mρv,σmz.
Within statistical distance2−ωlogm/M of the distribution, algorithm ℱ is as follows:(1)
v⟵$h,(2)
z⟵$Dσm,(3)
Outputz,v with probability 1/M.
Moreover, the probability thatA outputs something is at least 1−2−ωlogm/M.


### 2.6. Overview of Signatures Based on Fiat–Shamir with Aborts

Fiat–Shamir with Aborts approach is an LWE-based signature framework that is firstly introduce in [18]. Based on this framework, many improvements have been proposed for better security and efficiency in [19, 22, 23]. The overview of the ‘Fiat–Shamir with Aborts’ framework can be summarized in Figure 1. Note that the original scheme proposed in [18] is based on the LWE problem, and further improvements [19, 22, 23] are mainly designed based on ring-LWE or module-LWE to achieve better efficiency. In this paper, we concentrate on practical designs; thus, all elements as well as computations in the following paper are in the polynomial ring ZqX/Xn+1.Figure 1
Framework of signatures based on Fiat–Shamir with Aborts.


### 2.7. The Entropy of Challenge Polynomial

In the updated version of the 3rd-round submission of CRYSTALS-Dilithium, a new method is introduced to decrease the rejection probability in order to achieve better efficiency where the number of nonzero coefficients of the challenge polynomial c varies according to the security levels. For example, in the 3rd round version, the challenge polynomial c are chosen from B24,B30,B39,B49,B60,B60, and B60, respectively, for the parameters with the security claims of 55,89,112,165,229,298, and 343, while in the 2nd version, c is chosen from B60 for all parameters. Since all coefficients of the challenge polynomial are in the set of −1,0,1, the entropy of a challenge polynomial chosen from Bτ is log256τ+τ bit. However, small entropy leads to a direct forgery attack without any valid message for ‘Fiat–Shamir with Aborts’ structure. Recall the verification process of the schemes; given the public key pk=A,t, forgery attack can be performed by finding a set of signature σ′=z′,c′ which satisfies z′∞<γ1−β and c′=HM‖w1′=HM‖HighBitsAz′−c′t,2γ2. For any fixed c′∈Bτ, an adversary can forge a signature by picking some z′ that satisfied z′∞<γ1−β and check if c′=HM‖HighBitsAz′−c′t,2γ2. Since the entropy of z′ is much larger than the entropy of c′, the adversary shall succeed with the complexity of Olog256τ+τ in the classical model. Furthermore, by regarding the formula c′=HM‖HighBitsAz′−c′t,2γ2 as a function of z′, the Grover algorithm can be used to achieve quadratical speedup with the complexity of Olog256τ+τ in the quantum model. As a result, the securities of these sets of parameters against forgery attack shall be 67,80,96,112,128,128, and 128 in the quantum model, where the corresponding security claims are 55,89,112,165,229,298, and 343. For these seven sets of parameters, the last six of them suffer from this quantum forgery attack and the last two sets of parameters even may not be secure in the classical model, as shown in Table 1. Since the proposed idea of decreasing the rejection probability may also decrease the security of the scheme, in Section 3, we will provide another method to achieve this goal without loss of security and use it to introduce variants of CRYSTALS-Dilithium which achieve better efficiency and smaller signature size. Since the security claims of the third round parameters in CRYSTALS-Dilithium have large gaps with the complexities of the forgery attack, our comparisons shall be conducted based on the second version of parameters in CRYSTALS-Dilithium rather than the third-round ones (note that the practical verification process of the 3rd version CRYSTALS-Dilithium is more complex than the framework shown in Figure 1 due to the application of hint vector as well as two stages’ sampling process; however, it is easy to check that the proposed forgery attack also applies to this practical scheme).Table 1
Forgery attack for parameters of CRYSTALS-Dilithium 3rd version.
ParametersDilithium: 1− −Dilithium: 1−Dilithium: 2Dilithium: 3Dilithium: 4Dilithium: 5+Dilithium: 5++Weight ofc24303949606060Entropy ofc135160192225257257257Classical forgery attack135160192225257257257Quantum forgery attack678096112128128128Security claim5589112165229298343


## 2.1. Lattice

Anm-dimensional lattice is a discrete additive subgroup in ℝm which can be represented as the set of integer linear combination of n linearly independent vectors b1,…,bn, i.e.,(1)ℒB=∑i=1nxibi|xi∈,∀i∈1,n,where B=b1,…,bn is called a basis of ℒ which is not unique, nn≤m is the rank of the lattice, a lattice is called full-rank if m=n. The determinant of ℒ is defined as(2)detℒ=detB⊤B.The quantitydetℒ is invariant regardless of the choice of B. The dual lattice ℒ∗ is defined as(3)ℒ∗=w∈Rm|∀v∈ℒ,w,v∈.q-ary lattice: as a kind of important lattices in lattice-based cryptography, a q-ary lattice refers to the lattice such that qZn⊆ℒ⊆Zn, where q is an integer.Two types ofq-ary lattices frequently used in lattice cryptography are defined as follows, with respect to an n×m matrix B∈Zqn×m:(4)ℒqB=y∈m|y=B⊤xmodq,x∈n,ℒq⊥B=y∈m|By=0modq.


## 2.2. Gaussian Distribution over Lattices

Fors>0, the Gaussian function is defined as(5)ρc,sy=e−πy−c2/s2,for y∈ℝm, where s is called the width. When s=1 or c=0, the corresponding subscript is usually omitted for simplicity.Definition 1.
(discrete Gaussian distribution). Fors>0 and c∈ℝm, the discrete Gaussian distribution Dℒ+c,s over ℒ+c is defined as(6)Dℒ+c,sx=ρsxρsℒ+c,where x∈ℒ+c and ρsℒ+c=∑x∈ℒ+cρsx. We call σ=s/2π the standard deviation for Dℒ+c,s.It is difficult to calculate the sumρsℒ directly, but it is related to the sum of values of a Gaussian function over the dual lattice according to the celebrated Poisson summation formula.Lemma 1.
(Poisson summation formula, see [28]). For an n-dimensional lattice ℒ, let s>0 and t∈Rn, and the following hold:(1)
ρsℒ=sn/detℒρ1/sℒ∗(2)
ρsℒ+t=sn/detℒ∑w∈ℒ∗e2πiw,tρ1/swThere is a tail bound for the continuous Gaussian distribution and the discrete Gaussian distribution also has a similar property which was first proven by Banaszczyk [28]. The following is a refinement to the bound of Banaszczyk given in [29].Lemma 2.
(tail bound, see [29]). For the variable X∼N0,1, then PrX>t≤2e−πt2. For an n-dimensional lattice ℒ and a vector t∈Rn, let s>0 and c≥1/2π, and we have(7)PrX⟵$Dℒ+t,sX>csn≤2πec2n/2e−πnc2ρsℒρsℒ+t.


## 2.3. LWE Problem

Learning with error (LWE) problem was proposed by Regev [4] in 2005 and has been widely used in the construction of lattice-based cryptography. We first introduce some definitions in order to describe LWE problems.Definition 2.
(LWE distribution). Letn≥1, q≥2 and χ be an error distribution over Zq; given a secret vector s∈Zqn, the LWE distribution Ls,χ over Zqn×Zq is sampled by choosing a⟵$UZqnUZqn and e⟵$χχ and outputting a,b=a,s+emodq.The LWE problem has a search version and a decision version, which are defined as follows.Definition 3.
(search-LWE). Givenm samples ai,bi∈Zqn×Zq that are independently sampled from Ls,χ with a fixed secret s∈Zqn, the goal of search-LWE is to find the secret vector s.In the following part of this paper, we denoteA∈Zqn×m to be the matrix formed by m columns aii=1m and b=b1,b2,…,bm⊤∈Zqm, where bi=ai,s+eimodq.Definition 4.
(decision-LWE). Givenm independent samples A,b∈Zqm×n×Zqm that follow either the LWE distribution Ls,χ with a fixed secret s∈Zqn or the uniform distribution, the goal of decision-LWE is to decide which distribution the samples follow.To make LWE more practical in cryptography, variants of LWE problems (e.g., ring-LWE and module-LWE) have been investigated. More details of these variants can be found in [30].


## 2.4. Statistical Distance and Rényi Divergence

Statistical distance and Rényi divergence are two measures of closeness of two probability distributions which are often used in security proofs. The definitions of statistical distance and Rényi divergence are as follows.Definition 5.
(statistical distance). For any two discrete probability distributionsP and Q over a countable support X, the statistical distance between the two distributions, denoted as Δsd, is defined by(8)ΔsdPQ=12∑k∈XPk−Qk.Definition 6.
(Rényi divergence). For any two discrete probability distributionsP and Q such that SuppP⊂SuppQ and α∈1,+∞, the Rényi divergence of order α, denoted as Δα, is defined by(9)ΔαPQ=∑k∈SuppPPkαQkα−11/α−1.According to the research of [31], using Rényi divergence to estimate security can provide smaller parameters in designing lattice-based schemes than using statistical distance.


## 2.5. Rejection Sampling

Rejection sampling is an important tool which is widely used in designing lattice-based signature [19, 22, 23]. It is first proposed in [18] and can be used to produce a distribution that is statistically close to another one. In this way, one can output a distribution without leaking information of the secret keys and the lower bound of the complexity against attacks which use the information of signatures and has been given in Theorem 1.Theorem 1.
(rejection sampling theorem, see [19]). Let V be a subset of Zm in which all elements have norms less than T, σ be some element in ℝ such that σ=ωTlogm, and h:V⟶R be a probability distribution. Then, there exists a constant M=O1 such that the distribution of the following algorithm A is as follows:(1)
v⟵$h,(2)
z⟵$Dv,σm,(3)
outputz,v with probability minρσmz/Mρv,σmz.
Within statistical distance2−ωlogm/M of the distribution, algorithm ℱ is as follows:(1)
v⟵$h,(2)
z⟵$Dσm,(3)
Outputz,v with probability 1/M.
Moreover, the probability thatA outputs something is at least 1−2−ωlogm/M.


## 2.6. Overview of Signatures Based on Fiat–Shamir with Aborts

Fiat–Shamir with Aborts approach is an LWE-based signature framework that is firstly introduce in [18]. Based on this framework, many improvements have been proposed for better security and efficiency in [19, 22, 23]. The overview of the ‘Fiat–Shamir with Aborts’ framework can be summarized in Figure 1. Note that the original scheme proposed in [18] is based on the LWE problem, and further improvements [19, 22, 23] are mainly designed based on ring-LWE or module-LWE to achieve better efficiency. In this paper, we concentrate on practical designs; thus, all elements as well as computations in the following paper are in the polynomial ring ZqX/Xn+1.Figure 1
Framework of signatures based on Fiat–Shamir with Aborts.


## 2.7. The Entropy of Challenge Polynomial

In the updated version of the 3rd-round submission of CRYSTALS-Dilithium, a new method is introduced to decrease the rejection probability in order to achieve better efficiency where the number of nonzero coefficients of the challenge polynomial c varies according to the security levels. For example, in the 3rd round version, the challenge polynomial c are chosen from B24,B30,B39,B49,B60,B60, and B60, respectively, for the parameters with the security claims of 55,89,112,165,229,298, and 343, while in the 2nd version, c is chosen from B60 for all parameters. Since all coefficients of the challenge polynomial are in the set of −1,0,1, the entropy of a challenge polynomial chosen from Bτ is log256τ+τ bit. However, small entropy leads to a direct forgery attack without any valid message for ‘Fiat–Shamir with Aborts’ structure. Recall the verification process of the schemes; given the public key pk=A,t, forgery attack can be performed by finding a set of signature σ′=z′,c′ which satisfies z′∞<γ1−β and c′=HM‖w1′=HM‖HighBitsAz′−c′t,2γ2. For any fixed c′∈Bτ, an adversary can forge a signature by picking some z′ that satisfied z′∞<γ1−β and check if c′=HM‖HighBitsAz′−c′t,2γ2. Since the entropy of z′ is much larger than the entropy of c′, the adversary shall succeed with the complexity of Olog256τ+τ in the classical model. Furthermore, by regarding the formula c′=HM‖HighBitsAz′−c′t,2γ2 as a function of z′, the Grover algorithm can be used to achieve quadratical speedup with the complexity of Olog256τ+τ in the quantum model. As a result, the securities of these sets of parameters against forgery attack shall be 67,80,96,112,128,128, and 128 in the quantum model, where the corresponding security claims are 55,89,112,165,229,298, and 343. For these seven sets of parameters, the last six of them suffer from this quantum forgery attack and the last two sets of parameters even may not be secure in the classical model, as shown in Table 1. Since the proposed idea of decreasing the rejection probability may also decrease the security of the scheme, in Section 3, we will provide another method to achieve this goal without loss of security and use it to introduce variants of CRYSTALS-Dilithium which achieve better efficiency and smaller signature size. Since the security claims of the third round parameters in CRYSTALS-Dilithium have large gaps with the complexities of the forgery attack, our comparisons shall be conducted based on the second version of parameters in CRYSTALS-Dilithium rather than the third-round ones (note that the practical verification process of the 3rd version CRYSTALS-Dilithium is more complex than the framework shown in Figure 1 due to the application of hint vector as well as two stages’ sampling process; however, it is easy to check that the proposed forgery attack also applies to this practical scheme).Table 1
Forgery attack for parameters of CRYSTALS-Dilithium 3rd version.
ParametersDilithium: 1− −Dilithium: 1−Dilithium: 2Dilithium: 3Dilithium: 4Dilithium: 5+Dilithium: 5++Weight ofc24303949606060Entropy ofc135160192225257257257Classical forgery attack135160192225257257257Quantum forgery attack678096112128128128Security claim5589112165229298343


## 3. Rejection Sampling Theorem for Uniform Distribution

Rejection sampling theorem proposed in [19] can be used to estimate the security of the rejection sampling process against secret recovery attacks by computing the upper bound of the statistical distance of the output distribution and the target one where the two distributions follow discrete Gaussian distribution with distinct centers. However, in practical designs, uniform distributions are often used rather than discrete Gaussian distributions. This makes it more efficient and more convenient to sample elements, but the complexity of recovering secret key from the output of such samples remains unknown. Besides, by utilizing Rényi divergence instead of statistical distance used in the rejection sampling theorem of [19], a tighter security bound which leads to smaller parameter size can be obtained. So, let us start with clearly defining the problem and then providing a theorem about solving the problem.Definition 7.
(distinguish problem for rejection sampling with bounded uniform masking vector). LetSγ be a uniform distribution with elements in −γ,…,0,…,γ, Dη be an arbitrary distribution with the support −η,…,0,…,η, and β<γ be a positive constant. Given a number of samples, the goal is to decide which of the two algorithms the samples follow.
AlgorithmA:(1)
y⟵$Sγm,(2)
x⟵$Dηm,(3)
ify+x∞≥γ−β, restart,(4)
outputz=y+x.
Algorithmℱ:(1)
y⟵$Sγm,(2)
ify∞≥γ−β, restart,(3)
outputz=y.Theorem 2.
Given a distinguish problem for rejection sampling with bounded uniform masking vector defined by the probability distributionSγ and Dη and integers m>0,η>0,η≥β>0, the Rényi divergence between the output distributions, denoted as Δα, is(10)ΔαPzi′kQk=∑k∈−γ+β+1,γ−β−1Pzi′kαQkα−11/α−1,where Qk=1/2γ−β−1,(11)Pzi′k=12γ+1×11−S,ifk∈−γ+η+1,γ−η−1;12γ+1×CDFDk+γ1−S,ifk∈−γ+β+1,−γ+η;12γ+1×1−CDFDk−γ−11−S,ifk∈γ−η,γ−β−1,and S=∑k=−η−γ−γ+βPzik+∑k=γ−βγ+ηPzik, CDFDk=∑i=−ηkPx⟵$Dηx=i, and Pzik is defined as follows:(12)Pzik=12γ+1,ifk∈−γ+η+1,γ−η−1,12γ+1×CDFDk+γ,ifk∈−γ−η,−γ+η,12γ+1×1−CDFDk−γ−1,ifk∈γ−η,γ+η.Proof.
Let us first study the distribution ofz=y+x without rejection. As the support of yii∈1,m and xii∈1,m are separately sampled from −γ,…,0,…,γ and −η,…,0,…,η, it is clear that zii∈1,m has the support as −η−γ,…,0,…,η+γ. For any element k in its support, Pzikk∈−γ−η,γ+η follows the probability distribution as follows:(13)Pzik=12γ+1,ifk∈−γ+η+1,γ−η−1,12γ+1×CDFDk+γ,ifk∈−γ−η,−γ+η,12γ+1×1−CDFDk−γ−1,ifk∈γ−η,γ+η,where CDFD denotes the cumulative distribution function of the distribution Dη and CDFDk=∑i=−ηkPx⟵$Dηx=i.
When applying rejection sampling with the conditionzi≥γ−β to zi, whether β>η or not shall influence the output distribution, if β>η, we have Pzi′kk∈−γ+β+1,γ−β−1 as follows:(14)Pzi′k=12γ+1×12γ−β−1/2γ+1=12γ−β−1,ifk∈−γ+β,γ−β.
And, for0<β≤η, we have Pzi′kk∈−γ+β+1,γ−β−1 as follows:(15)Pzi′k=12γ+1×11−S,ifk∈−γ+η+1,γ−η−1,12γ+1×CDFDk+γ1−S,ifk∈−γ+β+1,−γ+η,12γ+1×1−CDFDk−γ−11−S,ifk∈γ−η,γ−β−1,where S=∑k=−η−γ−γ+βPzik+∑k=γ−βγ+ηPzik.
As a result, we now have the output distribution of algorithmA denoted as Pzi′k, and the output distribution P∗ of algorithm ℱ can be derived in a similar way. For β>0, we have Pzi∗kk∈−γ+β+1,γ−β−1 as follows:(16)Pzi∗k=12γ−β−1,ifk∈−γ+β+1,γ−β−1.
Now, we have clear descriptions of the output distributions of the two algorithms, and it is seen that the two distributions are exactly the same whenβ>η, and attacks utilizing the information of outputs can only be performed for the cases when β≤η. To measure the distances between the two probability distributions and evaluate the security, we shall recall the definition of Rényi divergence.
For any two discrete probability distributionsP and Q such that SuppP⊂SuppQ and α∈1,+∞, the Rényi divergence of order α, denoted as Δα, is defined by(17)ΔαPQ=∑k∈SuppPPkαQkα−11/α−1.
Combining the result ofPzi′k and the definition of Qk, this finishes the proof.To measure the complexities of distinguish problems by Theorem2, the probability distribution of Dη should be used. Note that, in signatures based on Fiat–Shamir with Aborts approach, as shown in Figure 1, a secret key s1 may be used for different signatures where random chosen challenge polynomials c are outputted. Their product corresponds to x in Theorem 2, where xi=∑j+k=imodmcj⋅s1,k. As a result, the probability distribution of xi, denoted as Dη, should be measured according to the challenge polynomials. As each challenge polynomial has τ nonzero coefficients randomly chosen from 1,−1, the entropy of a challenge polynomial is log256τ+τ bit. For a set of signatures signed with the same secret key if all challenge polynomials share a number of the same nonzero coefficients which forms a set Cshare containing l elements. Then, Dηl=∑cj∈Csharecj⋅s1,k+∑cj∉Csharecj⋅s1,k, and its first part r=∑cj∈Csharecj⋅s1,k is a constant and its second part can be measured as random variables following specific distribution because cj∉Cshare vary. Since the upper bound of s1,k is ηs, r is bounded by l⋅ηs, and the Rényi divergence, denoted as Δαl, of the distinguish problem in Definition 7 is bounded by taking Dη′l=l⋅ηs+∑cj∉Csharecj⋅s1,k as Dη in Theorem 2. Besides, to collect challenge polynomials which share the set Cshare, the probability of finding a challenge polynomial is computed by PCl=256−lτ−l2τ−l/256τ2τ⋅2, where the last 2 is due to the same values with the opposite symbol. So, the advantage for the distinguish problem under Cshare is given by Δαl⋅PCl and the advantage of a distinguish problem with any challenge polynomials is naturally obtained by enumerating all possible l as follows:(18)Adv=max0≤l≤τΔαl⋅PCl.


## 4. Applications of the Rejection Sampling Theorem for Uniform Distribution

### 4.1. Distinguish Analysis for Rejection Sampling

With the help of Theorem2 and equation (18), we can evaluate the security against attacks utilizing information of signatures by Rényi divergence for practical lattice-based signature schemes, including the NIST candidates. We shall take the parameters used in CRYSTALS-Dilithium as examples to show how to analyze the lower bound of the complexities of these attacks by utilizing Theorem 2. Besides, it should be noted that the compress technology proposed in [21] is commonly used to reduce the length of signature (which corresponds the rejection condition about the infinite norm of low bits shown in line 11 of Figure 1), this process can be viewed as another distinguish problem of rejection sampling for uniform distribution with different parameters. Take the parameters used in CRYSTALS-Dilithium-II and III which separately correspond to the first and the second level of NIST’s categories as examples, we can normalize them into the following distinguish problems in Table 2, where we use ‘R’ to denote the distinguish problem of rejection sampling process and ‘C’ to denote the distinguish problem of compress process.Table 2
Parameters of distinguish problem in CRYSTALS-Dilithium.
ParametersDilithium-II-RDilithium-II-CDilithium-III-RDilithium-III-Cη06655β325325275275γ523776−1261888523776−1261888m256×3256×4256×4256×5ηη0×60DηThe convolution of 60 independent uniform distributionsSince the upper bound of advantage for attacks utilizing the outputs of signatures is given by equation (18), say when advantage is no more than 2−α, the lower bound of complexity for attacks is at least 2α. Thus, applying Theorem 2 to the two distinguish problems, we can get the following results of security analysis, as shown in Table 3. Besides, we also take the proposed forgery attack into consideration because the securities of schemes are decided by the most optimal complexity of all known attacks. Thus, it is seen that, in CRYSTALS-Dilithium, the complexities of attacks utilizing the information of signatures are much larger than other types of attacks especially for the forgery attack brought by the small entropy of c. By observing the large gaps between complexities of different type attacks, refined parameters which can provide better efficiency, smaller sizes, and higher security can be obtained by balancing these complexities. We will discuss how to choose parameters and what can be achieved in Section 4.2.Table 3
Security of CRYSTALS-Dilithium.
Dilithium-IIDilithium-IIISIS block size340488Classical/quantum SIS security99.28/90.1142.49/129.59LWE block size255377Classical/quantum LWE security96.24/90.1142.28/130.911/advR300.43317.581/advC298.34315.58Entropy ofc257257Classical/quantum forgery attack257/128257/128Security against known attacks90.1128


### 4.2. Choosing New Parameters for Rejection Sampling of Dilithium

In Section4.1, we estimate the complexities of corresponding distinguish problems and observe there exist large gaps between the complexities of different types of attacks. As the parameters of rejection sampling relate to the efficiency, the security, and the signature size of the schemes at the same time, we can balance the gaps in order to achieve better efficiency, higher security, and smaller size of the schemes. The balancing shall be used based on parameters of CRYSTALS-Dilithium, and it should be noted that this technology can be naturally applied to other signature schemes using rejection sampling for uniform distributed masking vectors. Our approaches contain the following steps:(1)
Utilizing the method inSection 2.7 to balance the complexities of forgery attack by adjusting proper entropy of c according to the security levels(2)
Utilizing Theorem2 to balance the complexities of the two distinguish problems by setting β1 and β2 separately for rejection sampling process and compress process rather than using the same β for the two processes(3)
Utilizing the methods of primal attack, dual attack, and SIS attack used in [22] to balance the complexities of various types of attacks by choosing proper β,η, and γTo apply these modifications, new parameterβ1andβ2 should be introduced to replace β, and the revised framework is shown in Figure 2. Besides, since the choices of parameters for β1andβ2 are very close, the hardness reduction of the framework in Figure 2 follows the one in Figure 1 naturally.Figure 2
Revised framework of signatures based on Fiat–Shamir with Aborts.The success probability of rejection sampling and compress process relates to the efficiency of signature because the sign process will be continuously repeated until a proper signature is outputted, and the success probability is computed as(19)Psucc≈e−256β1l/γ1+β2k/γ2.Based on these analyses, we choose parameters by designing a program which contains the algorithms of success probabilities, primal attack estimation, dual attack estimation, sis attack estimation, and the distinguish attack estimation given by Theorem2. With the input of parameters, the program outputs these complexities and properties. And, the final results are obtained by testing different values iteratively and make a balance of these complexities and the efficiency.The comparisons of the parameters in this work (separately denoted as This Work-I and This Work-II corresponding to different security levels) and those in CRYSTALS-Dilithium are shown in Table4. The implementations can be found in https://github.com/Anonymous496/Digital-signatures. And, the experiments of efficiency are conducted with the environment of Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz.Table 4
Parameters of the adapted scheme I.
ParametersDilithium-IIThis Work-IDilithium-IIIThis Work-IIq8380417838041783804178380417d14141414Weight ofc60606060Entropy ofc257257257257γ1523776523776523776523776γ2261888261888261888261888k,l4,34,35,45,4η6655β325—275—β1—170—180β2—170—180ω80809696pk size (bytes)1184118414721472sig size (bytes)2044204427012701Expectation of repeats5.742.496.563.42keygen (ms)0.100.100.150.15Sign (ms)0.550.340.850.60Verify (ms)0.120.120.170.17SIS block size340340488488Classical/quantum SIS security99.28/90.199.28/90.1142.49/129.59142.49/129.59LWE block size255255377377Classical/quantum LWE security96.24/90.196.24/90.1142.28/130.91142.28/130.911/advR300.4395.19317.58129.771/advC298.3493.19315.58128.0Classical/quantum forgery attack257/128196/98257/128257/128Security against known attacks90.190.1128128As the signing procedure will repeat several times until a signature is outputted, the success probabilities influence the efficiency of signing process directly. In other words, the efficiency of the signing process with our technique are61.7%and41.7% faster than that in CRYSTALS-Dilithium according to the security levels. Furthermore, since the sizes of public key and signature are considered as more important factors than their efficiency for signature schemes based on Fiat–Shamir structure, we can use the proposed technology to introduce a new set of parameters with smaller signature size and keep the same security level with small improvement in efficiency. We denote the adapted scheme as this Work-III, and the comparisons can be found in Table 5.Table 5
Parameters of the adapted scheme II.
ParametersCRYSTALS-Dilithium-IIThis Work-IIIq8380417523777=219−29+1d1410Weight ofc6060Entropy ofc257196γ152377665472=216−26γ226188832736(=215−25)k,l4,34,3Error distributionUniform in−6,6Central binomial in−2,2β325—β1—46β2—48ω8080pk size (bytes)11841184sig size (bytes)20441756Expectation of repeats5.747.7keygen (ms)0.100.10Sign (ms)0.550.54Verify (ms)0.120.12SIS block size340449Classical/quantum SIS security99.28/90.1130.82/118.99LWE block size255349Classical/quantum LWE security96.24/90.1101.91/92.491/advR300.4392.461/advC298.3494.15Classical/quantum forgery attack257/128196/98Security against known attacks90.192.46From the comparison, it is seen that the signature size of the proposed scheme is14.09% smaller than the original one with small improvement in signing efficiency and keeps the same security level compared with CRYSTALS-Dilithium-II. It should be noted that similar optimizations can also be applied to other sets of parameters in CRYSTALS-Dilithium.


## 4.1. Distinguish Analysis for Rejection Sampling

With the help of Theorem2 and equation (18), we can evaluate the security against attacks utilizing information of signatures by Rényi divergence for practical lattice-based signature schemes, including the NIST candidates. We shall take the parameters used in CRYSTALS-Dilithium as examples to show how to analyze the lower bound of the complexities of these attacks by utilizing Theorem 2. Besides, it should be noted that the compress technology proposed in [21] is commonly used to reduce the length of signature (which corresponds the rejection condition about the infinite norm of low bits shown in line 11 of Figure 1), this process can be viewed as another distinguish problem of rejection sampling for uniform distribution with different parameters. Take the parameters used in CRYSTALS-Dilithium-II and III which separately correspond to the first and the second level of NIST’s categories as examples, we can normalize them into the following distinguish problems in Table 2, where we use ‘R’ to denote the distinguish problem of rejection sampling process and ‘C’ to denote the distinguish problem of compress process.Table 2
Parameters of distinguish problem in CRYSTALS-Dilithium.
ParametersDilithium-II-RDilithium-II-CDilithium-III-RDilithium-III-Cη06655β325325275275γ523776−1261888523776−1261888m256×3256×4256×4256×5ηη0×60DηThe convolution of 60 independent uniform distributionsSince the upper bound of advantage for attacks utilizing the outputs of signatures is given by equation (18), say when advantage is no more than 2−α, the lower bound of complexity for attacks is at least 2α. Thus, applying Theorem 2 to the two distinguish problems, we can get the following results of security analysis, as shown in Table 3. Besides, we also take the proposed forgery attack into consideration because the securities of schemes are decided by the most optimal complexity of all known attacks. Thus, it is seen that, in CRYSTALS-Dilithium, the complexities of attacks utilizing the information of signatures are much larger than other types of attacks especially for the forgery attack brought by the small entropy of c. By observing the large gaps between complexities of different type attacks, refined parameters which can provide better efficiency, smaller sizes, and higher security can be obtained by balancing these complexities. We will discuss how to choose parameters and what can be achieved in Section 4.2.Table 3
Security of CRYSTALS-Dilithium.
Dilithium-IIDilithium-IIISIS block size340488Classical/quantum SIS security99.28/90.1142.49/129.59LWE block size255377Classical/quantum LWE security96.24/90.1142.28/130.911/advR300.43317.581/advC298.34315.58Entropy ofc257257Classical/quantum forgery attack257/128257/128Security against known attacks90.1128


## 4.2. Choosing New Parameters for Rejection Sampling of Dilithium

In Section4.1, we estimate the complexities of corresponding distinguish problems and observe there exist large gaps between the complexities of different types of attacks. As the parameters of rejection sampling relate to the efficiency, the security, and the signature size of the schemes at the same time, we can balance the gaps in order to achieve better efficiency, higher security, and smaller size of the schemes. The balancing shall be used based on parameters of CRYSTALS-Dilithium, and it should be noted that this technology can be naturally applied to other signature schemes using rejection sampling for uniform distributed masking vectors. Our approaches contain the following steps:(1)
Utilizing the method inSection 2.7 to balance the complexities of forgery attack by adjusting proper entropy of c according to the security levels(2)
Utilizing Theorem2 to balance the complexities of the two distinguish problems by setting β1 and β2 separately for rejection sampling process and compress process rather than using the same β for the two processes(3)
Utilizing the methods of primal attack, dual attack, and SIS attack used in [22] to balance the complexities of various types of attacks by choosing proper β,η, and γTo apply these modifications, new parameterβ1andβ2 should be introduced to replace β, and the revised framework is shown in Figure 2. Besides, since the choices of parameters for β1andβ2 are very close, the hardness reduction of the framework in Figure 2 follows the one in Figure 1 naturally.Figure 2
Revised framework of signatures based on Fiat–Shamir with Aborts.The success probability of rejection sampling and compress process relates to the efficiency of signature because the sign process will be continuously repeated until a proper signature is outputted, and the success probability is computed as(19)Psucc≈e−256β1l/γ1+β2k/γ2.Based on these analyses, we choose parameters by designing a program which contains the algorithms of success probabilities, primal attack estimation, dual attack estimation, sis attack estimation, and the distinguish attack estimation given by Theorem2. With the input of parameters, the program outputs these complexities and properties. And, the final results are obtained by testing different values iteratively and make a balance of these complexities and the efficiency.The comparisons of the parameters in this work (separately denoted as This Work-I and This Work-II corresponding to different security levels) and those in CRYSTALS-Dilithium are shown in Table4. The implementations can be found in https://github.com/Anonymous496/Digital-signatures. And, the experiments of efficiency are conducted with the environment of Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz.Table 4
Parameters of the adapted scheme I.
ParametersDilithium-IIThis Work-IDilithium-IIIThis Work-IIq8380417838041783804178380417d14141414Weight ofc60606060Entropy ofc257257257257γ1523776523776523776523776γ2261888261888261888261888k,l4,34,35,45,4η6655β325—275—β1—170—180β2—170—180ω80809696pk size (bytes)1184118414721472sig size (bytes)2044204427012701Expectation of repeats5.742.496.563.42keygen (ms)0.100.100.150.15Sign (ms)0.550.340.850.60Verify (ms)0.120.120.170.17SIS block size340340488488Classical/quantum SIS security99.28/90.199.28/90.1142.49/129.59142.49/129.59LWE block size255255377377Classical/quantum LWE security96.24/90.196.24/90.1142.28/130.91142.28/130.911/advR300.4395.19317.58129.771/advC298.3493.19315.58128.0Classical/quantum forgery attack257/128196/98257/128257/128Security against known attacks90.190.1128128As the signing procedure will repeat several times until a signature is outputted, the success probabilities influence the efficiency of signing process directly. In other words, the efficiency of the signing process with our technique are61.7%and41.7% faster than that in CRYSTALS-Dilithium according to the security levels. Furthermore, since the sizes of public key and signature are considered as more important factors than their efficiency for signature schemes based on Fiat–Shamir structure, we can use the proposed technology to introduce a new set of parameters with smaller signature size and keep the same security level with small improvement in efficiency. We denote the adapted scheme as this Work-III, and the comparisons can be found in Table 5.Table 5
Parameters of the adapted scheme II.
ParametersCRYSTALS-Dilithium-IIThis Work-IIIq8380417523777=219−29+1d1410Weight ofc6060Entropy ofc257196γ152377665472=216−26γ226188832736(=215−25)k,l4,34,3Error distributionUniform in−6,6Central binomial in−2,2β325—β1—46β2—48ω8080pk size (bytes)11841184sig size (bytes)20441756Expectation of repeats5.747.7keygen (ms)0.100.10Sign (ms)0.550.54Verify (ms)0.120.12SIS block size340449Classical/quantum SIS security99.28/90.1130.82/118.99LWE block size255349Classical/quantum LWE security96.24/90.1101.91/92.491/advR300.4392.461/advC298.3494.15Classical/quantum forgery attack257/128196/98Security against known attacks90.192.46From the comparison, it is seen that the signature size of the proposed scheme is14.09% smaller than the original one with small improvement in signing efficiency and keeps the same security level compared with CRYSTALS-Dilithium-II. It should be noted that similar optimizations can also be applied to other sets of parameters in CRYSTALS-Dilithium.


## 5. Conclusion

In this paper, we study rejection sampling technology for lattice-based signatures and concentrate on the conditions for practical designs. We first introduce a new rejection sampling theorem for bounded uniform distributed masking vectors which is widely used in current designs where a tighter result is obtained due to the usage of Rényi divergence, and then, we use the proposed theorem to analyze the complexities against attacks utilizing information of signatures for the parameters in CRYSTALS-Dilithium and observe that there exist large gaps between complexities of different types of attacks, e.g., forgery attack and key recovery attack. Thirdly, we propose two series of adapted parameters for CRYSTALS-Dilithium. The first set can improve the efficiency of the signing process in CRYSTALS-Dilithium by factors of61.7%and41.7% according to the security levels and ensure the same signature size as well as security claims including forgery attack. And, the second set can reduce the signature size by a factor of 14.09% with small improvement in signing efficiency and keep the same security level.



---

*Source: 9948618-2021-06-07.xml*