# An Identity-Based Blind Signature Scheme Using Lattice with Provable Security

Authors: Quanrun Li; Chingfang Hsu; Debiao He; Kim-Kwang Raymond Choo; Peng Gong
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

With the rapid development of quantum computing and quantum information technology, the universal quantum computer will emerge in the near decades with a very high probability and it could break most of the current public key cryptosystems totally. Due to the ability of withstanding the universal quantum computer’s attack, the lattice-based cryptosystems have received lots of attention from both industry and academia. In this paper, we propose an identity-based blind signature scheme using lattice. We also prove that the proposed scheme is provably secure in the random oracle model. The performance analysis shows that the proposed scheme has less mean value of sampling times and smaller signature size than previous schemes. Thus, the proposed scheme is more suitable for practical applications.


---

## Body

## 1. Introduction

Currently, the emergence of quantum computing causes a potential threat to the traditional cryptosystems. In 2011, the first commercial quantum computer “D-Wave One” was worked out, which provided the application of certain cracking algorithms to the traditional public key cryptography with feasible condition. Furthermore, it is because most of mathematical hard problems in the traditional cryptosystems are vulnerable to the strong computing power of quantum computers. Therefore, it is obvious that the influence quantum computers bring to the traditional cryptosystem will permeate into the information security and Internet security of all areas of a country, such as politics, economy, culture, and military.Specifically, it can be explained from two main aspects: Firstly, for the integer factorization problem, the conjecture that ann-bit integer can be decomposed by the n-qubit quantum computer easily is proposed by Beauregard [1]. As for the discrete logarithm problem, Proos and Zalka [2] pointed out that n-bits elliptic curve discrete logarithmic problem [3, 4] can be solved by n-qubit quantum computer. Secondly, the valid length of the secret key in traditional cryptosystem will be half of the original length under the attack of quantum adversary.Blind signature was first proposed by Chaum [5] to make electronic money in an electronic cash system. In general, the user can get a valid signature of any message through a blind signature scheme, where the signer knows nothing about the actual message. This special property makes the blind signature used widely. Therefore, a plenty of blind schemes were worked out after the work of Chaum, such as [6, 7]. However, those schemes had the significant problem on certificates, which is the core problem in public key infrastructure (PKI) cryptosystem. In 1984, the identity-based (ID-based) public key cryptosystem was worked out by Shamir [8], which is useful to eliminate the serious defect of the PKI cryptosystem. Since then, lots of ID-based blind signature schemes were proposed with efficient performance.As is known to all, most of the above blind signature schemes cannot resist the attack of quantum algorithms. It is because the computational power of the quantum computers is so strong that the hard problems in those schemes are easy to be broken. In order to remove this threat, the postquantum cryptography appears in the vision of cryptographers, which is that the traditional cryptosystem still holds its security under the attack of the quantum adversary. In the postquantum cryptography systems, the lattice-based cryptography is the most promising. Currently, lots of cryptographic protocols have been devised on the lattice, such as [9–11].There are several advantages of the lattice-based cryptography which are worth noting. Firstly, this cryptosystem has got widespread attention in the last decade. Then, this cryptography currently cannot be broken by any algorithms, including quantum algorithms. Moreover, lattice-based cryptography has the same level of security in the average case and the worst case. Finally, the designs of lattice-based schemes are very simple and efficient, including mainly matrix-vector multiplication, linear summation operation, and modulo operation.Taking advantage of these benefits, some blind signature schemes were designed, but several problems included in these schemes make them inapplicable in the real environment. For example, some blind signature schemes lack the formal security proof or describe the ability of the adversary incorrectly. Besides, the efficiency shortcomings in other schemes are too serious to be neglected, such as the scheme proposed by Rückert [12] and the work of Zhang et al. [13]. The main reason for this is that complex algorithms are used in the process of signing or the efficient aborting technology is not involved in these blind signature schemes.In order to improve the practicability of blind signature, a new ID-based scheme on lattice is proposed in this paper, which is more efficient and secure. Specifically, the main contributions of this paper are as follows:(1)
Firstly, our blind signature scheme can resist the attack of the malicious quantum adversaries, because it is based on lattice. Meanwhile, we prove that our scheme is secure based on SIS problem in the random oracle model. The lattice cryptosystem also makes it more efficient due to the simple operations involved in lattice-based algorithms.(2)
Secondly, we use the bimodal Gaussian rejection sampling in our scheme to prevent the leakage of critical information, such as the signer’s secret key. Using this aborting technology, it makes the mean value of sampling times needed to generate a valid signature smaller. Additionally, we can get the blind signature with smaller size under this novel technology.(3)
Finally, because the framework of ID-based cryptosystem is used in our scheme, it means that the additional cost is not needed to manage lots of certificates in our scheme. Therefore, the proposed scheme under this cryptosystem is more practical in the real application.


## 2. Related Work

In this section, we will mainly talk about the related works on the blind signature schemes. Due to its excellent concealment, blind signature has been studied widely and put into the applications where important data needs to hold its privacy, such as electronic cash (e-cash) [14], electronic voting [15], and oblivious transfer [16].In order to design electronic money used in the e-cash system, Chaum [5] proposed the first blind signature scheme. After the work of Chaum, lots of blind signature schemes were worked out based on PKI cryptosystem, the hardness of which is mostly based on the integer factorization problem or discrete logarithm problem [17–19]. However, as we all know, the issue of certificates’ management is an apparent defect in this cryptosystem. Fortunately, the identity-based public key cryptography was proposed by Shamir [8] to eliminate this drawback.Owing to the good advantages of ID-based cryptosystem, the first ID-based blind signature scheme was worked out by Zhang and Kim [20]. Later, Huang et al. [21] proposed another ID-based blind signature scheme in 2005. In 2008, a generalized ID-based blind signature with bilinear pairings was designed by Kalkan et al. [22]. Then, in 2010, Rao et al. [23] constructed a blind signature scheme on the basis of ID-based digital signature framework proposed by Hess [24]. Following the work of Rao et al, a provably secure randomized blind signature scheme was constructed by Fan et al. [25] using bilinear pairings. Furthermore, there were two other new ID-based blind signature schemes based on bilinear pairings designed by Zhang et al. [26] and Shakerian et al. [27], respectively, in the same year.However, in 2011, He et al. [28] proposed a novel ID-based blind signature scheme using no bilinear pairings. Their work opened up a new direction in the design of the ID-based blind signature scheme, because the new blind signature scheme constructed by them guaranteed both high efficiency and anonymity. Later, a new provably secure and pairing-free ID-based partially blind signature scheme was worked out by Islam et al. [29] in 2016, which was used in an online e-cash system. Besides, this scheme was provably secure in the random oracle model. In 2017, an untraceable ID-based blind signature scheme without pairing for e-cash payment system was proposed by Kumar et al. [30]. Then, James et al. [31] proposed an efficient pairing-free ID-based blind signature scheme with message recovery in 2018.Although ID-based cryptosystem can solve the efficiency drawback of schemes in PKI cryptosystem, it cannot resist the attack of quantum algorithms. In 2010, the first lattice-based blind signature scheme was proposed by Rückert [12], which was provably secure in the random oracle model. Later, in 2017, a novel round-optimal lattice-based blind signature scheme used in the cloud services was constructed by Zhu et al. [32]. Similarly, a new postquantum blind signature scheme on lattice was proposed by Zhang et al. [13] in 2018, in which the unimodal rejection sampling technology was used to improve the probability of generating a valid signature.Unfortunately, the efficiency problem still existed in these schemes because they were designed under the PKI cryptosystem. So some ID-based blind signature schemes were worked out to deal with this disadvantage of previous schemes. In 2014, Zhang and Ma [33] proposed a lattice-based proxy blind signature scheme based on ID-based cryptosystem, whose security was held in the standard model. Then, another ID-based blind signature scheme on lattice was constructed by Gao et al. [34] in 2016, which was based on the standard model. Interestingly, a two-round ID-based blind signature scheme on lattice was still proposed by Gao et al. [35] on the random oracle model in 2017. In addition, this scheme was proved to have the power to resist the selective identity and chosen message attacks to remain unforgeable and unconditionally blind based on the SIS problem.However, no aborting technology or only unimodal rejection sampling was used in these schemes. In 2013, Ducas et al. [36] proposed a modified aborting technology based on the original rejection sampling, called bimodal Gaussians rejection sampling, which reduces the rejecting field between the actual sampling distribution function and the expected sampling distribution function. This means that the signer can generate a valid signature with fewer samples. Additionally, this new aborting technology still keeps the basic ability to prevent the leakage of information of the signer’s secret key. Therefore, using the bimodal Gaussian rejection sampling, a new ID-based blind signature scheme on lattice is constructed in this paper based on the work of Zhang et al. [13]. Our scheme has the excellent ability to resist quantum algorithm and high efficiency, combining the advantages of lattice-based cryptosystem with that of ID-based cryptosystem.


## 3. Preliminaries

In this section, the basic knowledge about lattices will be described firstly. Next, we introduce the Gaussian distribution in detail.


### 3.1. Lattices

A latticeL is defined as a discrete additive subgroup of n-dimensional Euclidean vector space Rn. Namely, if b1,…,bn are n linearly independent vectors in Rn, a lattice L is the set of all integer combinations of these vectors:(1)LB=Lb1,…,bn=∑i=1nxibi:xi∈Z,and the matrix B is one base of LB. Normally, n is described as its corresponding dimension.In particular, the following two types of lattices should be paid more attention, called module lattice:(2)Lq⊥A=x∈Zm:Ax=0modq,LquA=x∈Zm:Ax=umodq.


#### 3.1.1. Small Integer Solution (SIS) Problem

Given a positive integerq, a matrix A∈Zqn∗m, and a real number β>0, the SIS problem is to find a nonzero vector v∈Zm such that Av=0modq, and v≤β. This kind of SIS problem is homogeneous. As for inhomogeneous SIS problem, it is to find a nonzero preimage v∈Zm satisfying Av=tmodq, where v≤β.Then, there are two important algorithms used in our protocol, which are applied to generate the secret keys of the trusted third party and the signer.


#### 3.1.2. Trapdoor Generation Algorithm

An integerq≥3, m>5nlogq; there is an effective algorithm TrapGenq,m that can generate a matrix A∈Zqn∗m and a basis TA∈Zm∗m of the lattice L⊥A. Besides, the distribution of the matrix A is the uniform distribution in Zqn∗m approximately and the orthogonal matrix TA^≤Onlogq.


#### 3.1.3. General Preimage Sampling Algorithm

There are an integerm≥n, a prime number q, and a positive integer k. The lattice L⊥A is defined by the matrix A∈Zqn∗m. Additionally, the matrix TA∈Zm∗m is a base of the lattice L⊥A. If the parameter of the Gaussian distribution s≥TA^ωlogn, there is a polynomial-time algorithm SampleMatA,TA,s,U, where U is a random matrix defined in Zqn∗k, sampling a matrix V∈Zm∗k in a distribution closing to GLUA,s, such that AV=Umodq.


### 3.2. Gaussian Distribution and Bimodal Gaussian Rejection Sampling

#### 3.2.1. Gaussian Distribution

In statistics, the distribution function of continuous Gaussian distribution isρc,δx=e−x−c2/2δ2, where c is the center and δ is the standard deviation. Furthermore, if c=0, we usually make the equation simpler, writing it as ρδx. In the case of lattice L, the function is ρc,δL=∑x∈Lρc,δx. So the discrete Gaussian distribution over Z is written as Gc,δx=ρc,δx/ρc,δZ. Meanwhile, the discrete Gaussian distribution defined over Zm is normally described as Gc,δmx=ρc,δx/ρc,δZm. If the center c=0, we usually write these two symbols as Gδx and Gδmx.In the following, some theorems on the discrete Gaussian distribution are shown.Theorem 1.
We assume thatk≥1, so the following formula holds:(3)Prz>k∗δ∗m:z⟵Gδm<kmem/21−k2.Furthermore, if we haveδ,r>0, and for any element v∈Rm, the following conclusion is made out:(4)Prz,v>r:z⟵Gδm≤2e−r2/2v2δ2.Theorem 2.
It is described that we haveδ=αv, where α>0, and v is an element in Zm. We have(5)PrGδmzGv,δmz<e12/α+1/2α2:z⟵Gδm=1−2−100.Theorem 3.
If the matrixA∈Zqn∗m is chosen randomly and e⟵GZm,δ, we have that t=Aemodq, whose distribution is uniform approximately in Zqn.


#### 3.2.2. Rejection Sampling

The rejection sampling is a useful aborting skill in lattice-based schemes. Speaking in formal terms, when the positive constantM and a special distribution f are given, we need to find another distribution g, which makes fx≤M∗gx. So we can say that the distribution x⟵g is seen as another distribution f with the probability fx/Mgx. In general, M is the mean value of times to get an effective sample.(1) Rejection Sampling Lemma. It is assumed that h is a distribution whose preimage is V, where V⊆Zm, and V maps to R. When δ=ωTlogm, we can have a constant M to give the distribution of the following output:(1)
v⟵h.(2)
z⟵Gδm.(3)
Thez,v is given out with the probability 1/M is within the statistical distance 2−ωlogm/M of another distribution:(1)
v⟵h(2)
z⟵Gv,δm(3)
The outputz,v is sent with the probability minGδmz/MGv,δmz,1(2) Bimodal Gaussian Rejection Sampling. In the original Gaussian rejection sampling, the mean value of repetitions of the sampling is M≈e1, when the standard deviation δ=τSc, where the Gaussian “tail-cut” factor τ is proportional to the square root of the security parameter.In this paper, we introduce the bimodal Gaussian rejection sampling in our scheme to get a smaller rejection area and signature size. As the paper in [13] mentioned, z=Sc+y is considered as signer’s signature. But the form of the signature must be changed if we need to use the bimodal Gaussian rejection sampling in the scheme. Before the signer begins to sign the message, a random bit b∈−1,1 is sampled. Then, the relevant signature is z=bSc+y. Thus, the probability distribution of z is 1/2GSc,δm+1/2G−Sc,δm. According to the requirement of rejection sampling, firstly, the inequality fx≤M∗gx must be held. Secondly, we need to make M as small as possible. For the sake of interpretation, we give out the following formula:(6)Gδmx1/2GSc,δmx+1/2G−Sc,δmx=eSc2/2δ2/coshx,Sc/δ2≤eSc2/2δ2.Because there is a fact in math that the inequalitycoshy≥1 is always true for any y, we can get the value M=e1 by making δ get the value Sc/2 instead of the value τSc. It is easy to see that the mean value M in the bimodal Gaussian rejection sampling is smaller than that of original Gaussian rejection sampling. Besides, we know that the size of the final signature on lattice is roughly δm so that this size of the signature produced by using this rejection sampling is much shorter.


## 3.1. Lattices

A latticeL is defined as a discrete additive subgroup of n-dimensional Euclidean vector space Rn. Namely, if b1,…,bn are n linearly independent vectors in Rn, a lattice L is the set of all integer combinations of these vectors:(1)LB=Lb1,…,bn=∑i=1nxibi:xi∈Z,and the matrix B is one base of LB. Normally, n is described as its corresponding dimension.In particular, the following two types of lattices should be paid more attention, called module lattice:(2)Lq⊥A=x∈Zm:Ax=0modq,LquA=x∈Zm:Ax=umodq.


### 3.1.1. Small Integer Solution (SIS) Problem

Given a positive integerq, a matrix A∈Zqn∗m, and a real number β>0, the SIS problem is to find a nonzero vector v∈Zm such that Av=0modq, and v≤β. This kind of SIS problem is homogeneous. As for inhomogeneous SIS problem, it is to find a nonzero preimage v∈Zm satisfying Av=tmodq, where v≤β.Then, there are two important algorithms used in our protocol, which are applied to generate the secret keys of the trusted third party and the signer.


### 3.1.2. Trapdoor Generation Algorithm

An integerq≥3, m>5nlogq; there is an effective algorithm TrapGenq,m that can generate a matrix A∈Zqn∗m and a basis TA∈Zm∗m of the lattice L⊥A. Besides, the distribution of the matrix A is the uniform distribution in Zqn∗m approximately and the orthogonal matrix TA^≤Onlogq.


### 3.1.3. General Preimage Sampling Algorithm

There are an integerm≥n, a prime number q, and a positive integer k. The lattice L⊥A is defined by the matrix A∈Zqn∗m. Additionally, the matrix TA∈Zm∗m is a base of the lattice L⊥A. If the parameter of the Gaussian distribution s≥TA^ωlogn, there is a polynomial-time algorithm SampleMatA,TA,s,U, where U is a random matrix defined in Zqn∗k, sampling a matrix V∈Zm∗k in a distribution closing to GLUA,s, such that AV=Umodq.


## 3.1.1. Small Integer Solution (SIS) Problem

Given a positive integerq, a matrix A∈Zqn∗m, and a real number β>0, the SIS problem is to find a nonzero vector v∈Zm such that Av=0modq, and v≤β. This kind of SIS problem is homogeneous. As for inhomogeneous SIS problem, it is to find a nonzero preimage v∈Zm satisfying Av=tmodq, where v≤β.Then, there are two important algorithms used in our protocol, which are applied to generate the secret keys of the trusted third party and the signer.


## 3.1.2. Trapdoor Generation Algorithm

An integerq≥3, m>5nlogq; there is an effective algorithm TrapGenq,m that can generate a matrix A∈Zqn∗m and a basis TA∈Zm∗m of the lattice L⊥A. Besides, the distribution of the matrix A is the uniform distribution in Zqn∗m approximately and the orthogonal matrix TA^≤Onlogq.


## 3.1.3. General Preimage Sampling Algorithm

There are an integerm≥n, a prime number q, and a positive integer k. The lattice L⊥A is defined by the matrix A∈Zqn∗m. Additionally, the matrix TA∈Zm∗m is a base of the lattice L⊥A. If the parameter of the Gaussian distribution s≥TA^ωlogn, there is a polynomial-time algorithm SampleMatA,TA,s,U, where U is a random matrix defined in Zqn∗k, sampling a matrix V∈Zm∗k in a distribution closing to GLUA,s, such that AV=Umodq.


## 3.2. Gaussian Distribution and Bimodal Gaussian Rejection Sampling

### 3.2.1. Gaussian Distribution

In statistics, the distribution function of continuous Gaussian distribution isρc,δx=e−x−c2/2δ2, where c is the center and δ is the standard deviation. Furthermore, if c=0, we usually make the equation simpler, writing it as ρδx. In the case of lattice L, the function is ρc,δL=∑x∈Lρc,δx. So the discrete Gaussian distribution over Z is written as Gc,δx=ρc,δx/ρc,δZ. Meanwhile, the discrete Gaussian distribution defined over Zm is normally described as Gc,δmx=ρc,δx/ρc,δZm. If the center c=0, we usually write these two symbols as Gδx and Gδmx.In the following, some theorems on the discrete Gaussian distribution are shown.Theorem 1.
We assume thatk≥1, so the following formula holds:(3)Prz>k∗δ∗m:z⟵Gδm<kmem/21−k2.Furthermore, if we haveδ,r>0, and for any element v∈Rm, the following conclusion is made out:(4)Prz,v>r:z⟵Gδm≤2e−r2/2v2δ2.Theorem 2.
It is described that we haveδ=αv, where α>0, and v is an element in Zm. We have(5)PrGδmzGv,δmz<e12/α+1/2α2:z⟵Gδm=1−2−100.Theorem 3.
If the matrixA∈Zqn∗m is chosen randomly and e⟵GZm,δ, we have that t=Aemodq, whose distribution is uniform approximately in Zqn.


### 3.2.2. Rejection Sampling

The rejection sampling is a useful aborting skill in lattice-based schemes. Speaking in formal terms, when the positive constantM and a special distribution f are given, we need to find another distribution g, which makes fx≤M∗gx. So we can say that the distribution x⟵g is seen as another distribution f with the probability fx/Mgx. In general, M is the mean value of times to get an effective sample.(1) Rejection Sampling Lemma. It is assumed that h is a distribution whose preimage is V, where V⊆Zm, and V maps to R. When δ=ωTlogm, we can have a constant M to give the distribution of the following output:(1)
v⟵h.(2)
z⟵Gδm.(3)
Thez,v is given out with the probability 1/M is within the statistical distance 2−ωlogm/M of another distribution:(1)
v⟵h(2)
z⟵Gv,δm(3)
The outputz,v is sent with the probability minGδmz/MGv,δmz,1(2) Bimodal Gaussian Rejection Sampling. In the original Gaussian rejection sampling, the mean value of repetitions of the sampling is M≈e1, when the standard deviation δ=τSc, where the Gaussian “tail-cut” factor τ is proportional to the square root of the security parameter.In this paper, we introduce the bimodal Gaussian rejection sampling in our scheme to get a smaller rejection area and signature size. As the paper in [13] mentioned, z=Sc+y is considered as signer’s signature. But the form of the signature must be changed if we need to use the bimodal Gaussian rejection sampling in the scheme. Before the signer begins to sign the message, a random bit b∈−1,1 is sampled. Then, the relevant signature is z=bSc+y. Thus, the probability distribution of z is 1/2GSc,δm+1/2G−Sc,δm. According to the requirement of rejection sampling, firstly, the inequality fx≤M∗gx must be held. Secondly, we need to make M as small as possible. For the sake of interpretation, we give out the following formula:(6)Gδmx1/2GSc,δmx+1/2G−Sc,δmx=eSc2/2δ2/coshx,Sc/δ2≤eSc2/2δ2.Because there is a fact in math that the inequalitycoshy≥1 is always true for any y, we can get the value M=e1 by making δ get the value Sc/2 instead of the value τSc. It is easy to see that the mean value M in the bimodal Gaussian rejection sampling is smaller than that of original Gaussian rejection sampling. Besides, we know that the size of the final signature on lattice is roughly δm so that this size of the signature produced by using this rejection sampling is much shorter.


## 3.2.1. Gaussian Distribution

In statistics, the distribution function of continuous Gaussian distribution isρc,δx=e−x−c2/2δ2, where c is the center and δ is the standard deviation. Furthermore, if c=0, we usually make the equation simpler, writing it as ρδx. In the case of lattice L, the function is ρc,δL=∑x∈Lρc,δx. So the discrete Gaussian distribution over Z is written as Gc,δx=ρc,δx/ρc,δZ. Meanwhile, the discrete Gaussian distribution defined over Zm is normally described as Gc,δmx=ρc,δx/ρc,δZm. If the center c=0, we usually write these two symbols as Gδx and Gδmx.In the following, some theorems on the discrete Gaussian distribution are shown.Theorem 1.
We assume thatk≥1, so the following formula holds:(3)Prz>k∗δ∗m:z⟵Gδm<kmem/21−k2.Furthermore, if we haveδ,r>0, and for any element v∈Rm, the following conclusion is made out:(4)Prz,v>r:z⟵Gδm≤2e−r2/2v2δ2.Theorem 2.
It is described that we haveδ=αv, where α>0, and v is an element in Zm. We have(5)PrGδmzGv,δmz<e12/α+1/2α2:z⟵Gδm=1−2−100.Theorem 3.
If the matrixA∈Zqn∗m is chosen randomly and e⟵GZm,δ, we have that t=Aemodq, whose distribution is uniform approximately in Zqn.


## 3.2.2. Rejection Sampling

The rejection sampling is a useful aborting skill in lattice-based schemes. Speaking in formal terms, when the positive constantM and a special distribution f are given, we need to find another distribution g, which makes fx≤M∗gx. So we can say that the distribution x⟵g is seen as another distribution f with the probability fx/Mgx. In general, M is the mean value of times to get an effective sample.(1) Rejection Sampling Lemma. It is assumed that h is a distribution whose preimage is V, where V⊆Zm, and V maps to R. When δ=ωTlogm, we can have a constant M to give the distribution of the following output:(1)
v⟵h.(2)
z⟵Gδm.(3)
Thez,v is given out with the probability 1/M is within the statistical distance 2−ωlogm/M of another distribution:(1)
v⟵h(2)
z⟵Gv,δm(3)
The outputz,v is sent with the probability minGδmz/MGv,δmz,1(2) Bimodal Gaussian Rejection Sampling. In the original Gaussian rejection sampling, the mean value of repetitions of the sampling is M≈e1, when the standard deviation δ=τSc, where the Gaussian “tail-cut” factor τ is proportional to the square root of the security parameter.In this paper, we introduce the bimodal Gaussian rejection sampling in our scheme to get a smaller rejection area and signature size. As the paper in [13] mentioned, z=Sc+y is considered as signer’s signature. But the form of the signature must be changed if we need to use the bimodal Gaussian rejection sampling in the scheme. Before the signer begins to sign the message, a random bit b∈−1,1 is sampled. Then, the relevant signature is z=bSc+y. Thus, the probability distribution of z is 1/2GSc,δm+1/2G−Sc,δm. According to the requirement of rejection sampling, firstly, the inequality fx≤M∗gx must be held. Secondly, we need to make M as small as possible. For the sake of interpretation, we give out the following formula:(6)Gδmx1/2GSc,δmx+1/2G−Sc,δmx=eSc2/2δ2/coshx,Sc/δ2≤eSc2/2δ2.Because there is a fact in math that the inequalitycoshy≥1 is always true for any y, we can get the value M=e1 by making δ get the value Sc/2 instead of the value τSc. It is easy to see that the mean value M in the bimodal Gaussian rejection sampling is smaller than that of original Gaussian rejection sampling. Besides, we know that the size of the final signature on lattice is roughly δm so that this size of the signature produced by using this rejection sampling is much shorter.


## 4. Security Model

In this section, the security model of the blind signature will be introduced in detail. Normally, in addition to all kinds of security attributes that a general signature scheme has, a blind signature should have two more security attributes:(i)
Blindness: the signer does not know the specific content of the actual message signed by itself.(ii)
Unforgeability: after a message is signed, the signer who gets the signature of this message cannot link this signature to the details of the corresponding process.In fact, blindness means that a malicious signer can only get information independent of the actual message. In particular, there is a formal game used to describe the blindness.


### 4.1. Blindness Game

If any probabilistic polynomial-time algorithm cannot win the following game, we will consider the corresponding ID-based signature protocol as blind. In this game, there are two honest usersU0 and U1. In addition, A is considered to be a malicious signer. The game of blindness is defined as follows:(1)
A gets the public parameters params by querying Setup.(2)
A performs Extractparams,ID⟶SID. Namely, A can get the secret key SID of the identity ID by using Key Extract algorithm.(3)
A chooses a random bit b∈0,1 secretly. Then it sends a pair of messages mb,m1−b to U0 and U1.(4)
A executes the signature scheme with U0 and U1, respectively. The messages input by U0 and U1 are mb and m1−b.(5)
The outputsδb,mb and δ1−b,m1−b received by U0 and U1 are sent to A in arbitrary order.(6)
A outputs a bit b′∈0,1.It is worth noting thatA wins the game of blindness if and only if b′=b. Moreover, we consider AdvIDBSBlind as the advantage of A to win this game.Next, another security game aimed at unforgeability will be defined as below. In this game,S acts as the challenger and A is an adversary playing as a user.


### 4.2. Unforgeability Game

We think thatA can break the unforgeability of an ID-based blind signature scheme, if A makes qE extract queries and qS issue queries during the time t and the corresponding advantage AdvIDPSUF of A is ε at least. Otherwise, this scheme is unforgeability. The game of unforgeability is defined as follows:(1)
Setup: after inputting the security parameter1λ, S runs the Setup algorithm to generate the systematic public parameter params and the master secret key sk. Then, the public parameter params is sent to A.(2)
Query: there are three kinds of queries thatA can choose to send to S.(a)
Hash query: after getting this query,S would select a random value and return it to A. It is worth noting that random oracle queries are responded by the challenger consistently.(b)
Extract query: after receiving this query,S would run the Key Extract algorithm to get the relevant secret key skID and give it back to A.(c)
Issue query: after obtaining this query,S executes the sign algorithm with A cooperatively to get the signature sig. But before this operation, S would get the ID’s secret key SID by performing the extract query. Finally, the signature sig is given back to A.(3)
Forgery: after the above query phase,A will use the useful information to forge a signature sig⋆ corresponding to the message u⋆ of the user, of which identity is ID⋆. Additionally, A outputs n valid signature pairs u1,sig1,…,un,sign, where u⋆,sig⋆=un,sign. If the following conditions are satisfied by these signature pairs, we can conclude that A wins this game. Furthermore, AdvIDBSUF is the advantage of A to get final success in this game.(a)
For anyi and j, we have that ui≠uj, where i≠j and i,j∈1,…,n.(b)
n>qS.(c)
A never uses the extract query to get the secret key sID⋆ of the user whose identity is ID⋆.Generally, an ID-based blind signature is considered to have blindness and unforgeability, ifAdvIDBSBlind and AdvIDBSUF of any polynomial time adversary are negligible.


## 4.1. Blindness Game

If any probabilistic polynomial-time algorithm cannot win the following game, we will consider the corresponding ID-based signature protocol as blind. In this game, there are two honest usersU0 and U1. In addition, A is considered to be a malicious signer. The game of blindness is defined as follows:(1)
A gets the public parameters params by querying Setup.(2)
A performs Extractparams,ID⟶SID. Namely, A can get the secret key SID of the identity ID by using Key Extract algorithm.(3)
A chooses a random bit b∈0,1 secretly. Then it sends a pair of messages mb,m1−b to U0 and U1.(4)
A executes the signature scheme with U0 and U1, respectively. The messages input by U0 and U1 are mb and m1−b.(5)
The outputsδb,mb and δ1−b,m1−b received by U0 and U1 are sent to A in arbitrary order.(6)
A outputs a bit b′∈0,1.It is worth noting thatA wins the game of blindness if and only if b′=b. Moreover, we consider AdvIDBSBlind as the advantage of A to win this game.Next, another security game aimed at unforgeability will be defined as below. In this game,S acts as the challenger and A is an adversary playing as a user.


## 4.2. Unforgeability Game

We think thatA can break the unforgeability of an ID-based blind signature scheme, if A makes qE extract queries and qS issue queries during the time t and the corresponding advantage AdvIDPSUF of A is ε at least. Otherwise, this scheme is unforgeability. The game of unforgeability is defined as follows:(1)
Setup: after inputting the security parameter1λ, S runs the Setup algorithm to generate the systematic public parameter params and the master secret key sk. Then, the public parameter params is sent to A.(2)
Query: there are three kinds of queries thatA can choose to send to S.(a)
Hash query: after getting this query,S would select a random value and return it to A. It is worth noting that random oracle queries are responded by the challenger consistently.(b)
Extract query: after receiving this query,S would run the Key Extract algorithm to get the relevant secret key skID and give it back to A.(c)
Issue query: after obtaining this query,S executes the sign algorithm with A cooperatively to get the signature sig. But before this operation, S would get the ID’s secret key SID by performing the extract query. Finally, the signature sig is given back to A.(3)
Forgery: after the above query phase,A will use the useful information to forge a signature sig⋆ corresponding to the message u⋆ of the user, of which identity is ID⋆. Additionally, A outputs n valid signature pairs u1,sig1,…,un,sign, where u⋆,sig⋆=un,sign. If the following conditions are satisfied by these signature pairs, we can conclude that A wins this game. Furthermore, AdvIDBSUF is the advantage of A to get final success in this game.(a)
For anyi and j, we have that ui≠uj, where i≠j and i,j∈1,…,n.(b)
n>qS.(c)
A never uses the extract query to get the secret key sID⋆ of the user whose identity is ID⋆.Generally, an ID-based blind signature is considered to have blindness and unforgeability, ifAdvIDBSBlind and AdvIDBSUF of any polynomial time adversary are negligible.


## 5. Our Scheme

In this section, we will introduce our ID-based blind signature scheme in detail. Notably, there are two important algorithms used in our scheme, which areTrapGen and SampleMat[37, 38]. Meanwhile, public key generator (PKG) is the trusted third party.


### 5.1. System Setup

After getting the safety parameter1λ and n, PKG performs the following four steps:(1)
Choosing a prime numberq≥3, m>5nlogq, s≥Lωlogn, and δ=12smλ, where L=Onlogq.(2)
Executing the algorithmTrapGenq,m⟶A,B, where B^≤L. These matrices A∈Zqn∗m and B∈Zqm∗m are the public key and the secret key of PKG, respectively.(3)
Selecting two secure hash functionsH:0,1∗⟶v:v∈−1,0,1n,v1≤n and H1:0,1∗⟶Zqn∗k. Actually, k=m−n.(4)
Making the parametersA,H,H1 public and keeping sk=B as a secret.


### 5.2. Key Extraction Phase

In our scheme, PKG uses the following method to generate the user’s key pair. The key extract phase is shown in Figure1.(1)
ComputingH1ID=A′∈Zqn∗k and performing the algorithm SampleMatA,B,s,A′⟶SIDm∗k. We can know that ASID=H1ID and SID≤sm.(2)
Owing tom>n, getting SID⟶SID′, and choosing n rows of SID randomly and then computing the relevant transposed matrix S′k∗n=SID′T and finally calculating A″=A′S′modq.(3)
ComputingAun∗m=2A′2A″+qI and Sum∗n=S′/−IT, where I is the unit matrix, and then making the computation T=AuSumod2q=qI. So, T and Au are the user’s public keys and Su is the corresponding secret key.Figure 1
Key extraction phase.


### 5.3. Sign Phase

Essentially, this phase is an interactive three-move identification scheme over lattice based on SIS problem. It is assumed thatu is the actual message needed to be signed. The specific interaction process is as follows:(1)
The signer selects a random vectorr⟵Gδ2m and calculates x=Aur. Then, x is transmitted to the user.(2)
Blind: the user chooses two blind factorsa⟵Gδ3m and b⟵Gδ1n and computes c=Hx+Aua+Tbmod2q,comu,t. Noticeably, u is the message to be signed and t is a random value. Besides, the function com is a commitment. Then, e=pc+b is worked out, where p∈−1,1. Finally, e is sent to the signer by using the bimodal Gaussian rejection sampling to stop e from leaking some information of c.(3)
BSign: the signer selectsw⟵−1,1 randomly. Upon that, it can compute y=r+wSue. Similarly, y is sent to the user in the same way to hide relevant information of Su.(4)
Unblind: the user can get the value ofz=y+a. Then, z is output by the unimodal Gaussian rejection sampling. If z∈J, we make result=a,b,c,m,comu,t, where J is the rejection region of Gaussian sampling. Otherwise, we have result=accept. Finally, result is given to the signer.(5)
After holdingresult, the signer checks whether the value of result is accept or not. If it holds, the blind signature z,c is valid. On the contrary, if e−b=mc=mHx+Aua+Tbmod2q,comu,t, c=HAua+Auy−Tcmod2q,comu,t, and y+a∈J, the signer restarts the sign phase with the user.The sign phase is shown in Figure2.Figure 2
Blind sign phase.


### 5.4. Verify Phase

In this phase, the verifier should check whether the following conditions are right or not:(1)
c=HAuz−qcmod2q,comu,t(2)
z≤2mδ3Actually,z,c is the final signature pair. If the two above conditions are satisfied, we have VerifyAu,T,z,c,u=1.


### 5.5. Correctness Analysis Phase

In this section, we mainly talk about the correctness and repetition of our blind signature. Firstly, we have(7)Auz−qcmod2q=Auy+a−qcmod2q=Aur+kSue+Aua−qcmod2q=x+kTmc+b+Aua−qcmod2q=x+Aua+kmqc−qc+kTbmod2q=x+Aua+kqbmod2q=x+Aua+Tbmod2q.Thus, we have the fact thatc=Hx+Aua+Tbmod2q,comu,t = HAuz−qcmod2q,comu,t. Additionally, on the basis of Theorem 1 and rejection sampling lemma, there is z≤2δ3m with overwhelming probability.Next, because the bimodal Gaussian rejection sampling is used in two places in our scheme, the mean value of repetitions is smaller than that of the original scheme. According to the introduction of Gaussian distribution, we have that(8)Gδ3mzM3Gy,δ3mz≤1M3e24yδ3+y2/2δ32≤1,Gδ2myM21/2GSue,δ2my+1/2G−Sue,δ2my≤1M2eSue2/2δ22≤1,Gδ1neM11/2Gc,δ1ne+1/2G−c,δ1ne≤1M1ec2/2δ12≤1.In the rejection sampling lemma, we need to keepMii∈1,2,3 as small as possible. Therefore, the value of Mi is worked out, where M1=ec2/2δ12,M2=eSue2/2δ22, and M3=e24yδ3+y2/2δ32. Obviously, M1 and M2 are both less than the original values in the general rejection sampling, but not M3. Therefore, it means that a valid blind signature can be generated successfully in lesser repetitions, whose specific number is ∏i=13Mi.


## 5.1. System Setup

After getting the safety parameter1λ and n, PKG performs the following four steps:(1)
Choosing a prime numberq≥3, m>5nlogq, s≥Lωlogn, and δ=12smλ, where L=Onlogq.(2)
Executing the algorithmTrapGenq,m⟶A,B, where B^≤L. These matrices A∈Zqn∗m and B∈Zqm∗m are the public key and the secret key of PKG, respectively.(3)
Selecting two secure hash functionsH:0,1∗⟶v:v∈−1,0,1n,v1≤n and H1:0,1∗⟶Zqn∗k. Actually, k=m−n.(4)
Making the parametersA,H,H1 public and keeping sk=B as a secret.


## 5.2. Key Extraction Phase

In our scheme, PKG uses the following method to generate the user’s key pair. The key extract phase is shown in Figure1.(1)
ComputingH1ID=A′∈Zqn∗k and performing the algorithm SampleMatA,B,s,A′⟶SIDm∗k. We can know that ASID=H1ID and SID≤sm.(2)
Owing tom>n, getting SID⟶SID′, and choosing n rows of SID randomly and then computing the relevant transposed matrix S′k∗n=SID′T and finally calculating A″=A′S′modq.(3)
ComputingAun∗m=2A′2A″+qI and Sum∗n=S′/−IT, where I is the unit matrix, and then making the computation T=AuSumod2q=qI. So, T and Au are the user’s public keys and Su is the corresponding secret key.Figure 1
Key extraction phase.


## 5.3. Sign Phase

Essentially, this phase is an interactive three-move identification scheme over lattice based on SIS problem. It is assumed thatu is the actual message needed to be signed. The specific interaction process is as follows:(1)
The signer selects a random vectorr⟵Gδ2m and calculates x=Aur. Then, x is transmitted to the user.(2)
Blind: the user chooses two blind factorsa⟵Gδ3m and b⟵Gδ1n and computes c=Hx+Aua+Tbmod2q,comu,t. Noticeably, u is the message to be signed and t is a random value. Besides, the function com is a commitment. Then, e=pc+b is worked out, where p∈−1,1. Finally, e is sent to the signer by using the bimodal Gaussian rejection sampling to stop e from leaking some information of c.(3)
BSign: the signer selectsw⟵−1,1 randomly. Upon that, it can compute y=r+wSue. Similarly, y is sent to the user in the same way to hide relevant information of Su.(4)
Unblind: the user can get the value ofz=y+a. Then, z is output by the unimodal Gaussian rejection sampling. If z∈J, we make result=a,b,c,m,comu,t, where J is the rejection region of Gaussian sampling. Otherwise, we have result=accept. Finally, result is given to the signer.(5)
After holdingresult, the signer checks whether the value of result is accept or not. If it holds, the blind signature z,c is valid. On the contrary, if e−b=mc=mHx+Aua+Tbmod2q,comu,t, c=HAua+Auy−Tcmod2q,comu,t, and y+a∈J, the signer restarts the sign phase with the user.The sign phase is shown in Figure2.Figure 2
Blind sign phase.


## 5.4. Verify Phase

In this phase, the verifier should check whether the following conditions are right or not:(1)
c=HAuz−qcmod2q,comu,t(2)
z≤2mδ3Actually,z,c is the final signature pair. If the two above conditions are satisfied, we have VerifyAu,T,z,c,u=1.


## 5.5. Correctness Analysis Phase

In this section, we mainly talk about the correctness and repetition of our blind signature. Firstly, we have(7)Auz−qcmod2q=Auy+a−qcmod2q=Aur+kSue+Aua−qcmod2q=x+kTmc+b+Aua−qcmod2q=x+Aua+kmqc−qc+kTbmod2q=x+Aua+kqbmod2q=x+Aua+Tbmod2q.Thus, we have the fact thatc=Hx+Aua+Tbmod2q,comu,t = HAuz−qcmod2q,comu,t. Additionally, on the basis of Theorem 1 and rejection sampling lemma, there is z≤2δ3m with overwhelming probability.Next, because the bimodal Gaussian rejection sampling is used in two places in our scheme, the mean value of repetitions is smaller than that of the original scheme. According to the introduction of Gaussian distribution, we have that(8)Gδ3mzM3Gy,δ3mz≤1M3e24yδ3+y2/2δ32≤1,Gδ2myM21/2GSue,δ2my+1/2G−Sue,δ2my≤1M2eSue2/2δ22≤1,Gδ1neM11/2Gc,δ1ne+1/2G−c,δ1ne≤1M1ec2/2δ12≤1.In the rejection sampling lemma, we need to keepMii∈1,2,3 as small as possible. Therefore, the value of Mi is worked out, where M1=ec2/2δ12,M2=eSue2/2δ22, and M3=e24yδ3+y2/2δ32. Obviously, M1 and M2 are both less than the original values in the general rejection sampling, but not M3. Therefore, it means that a valid blind signature can be generated successfully in lesser repetitions, whose specific number is ∏i=13Mi.


## 6. Security Proof

In this section, we mainly prove that our scheme is blind and unforgeable by using the security model defined in Section4. In fact, we need a malicious adversary to play games of security with a challenger.


### 6.1. Blindness

We mainly prove the blindness of our scheme from the indistinguishability of views. Normally, views are the information conveyed between the signer and the users, as the following theorem shows.Theorem 4.
The proposed ID-based blind signature scheme on lattice has blindness.Proof.
As the game of blindness shows, a dishonest signerA⋆pk,sk selects two messages u0 and u1. Then these messages are sent to two honest users U0pk,ub and U1pk,u1−b, where b∈0,1. Then this malicious signer plays the game of blindness with U0 and U1 in the interactive way, respectively. Therefore, we can prove that our ID-based blind signature scheme is blind to A⋆ by showing all outputs of the users are independent of the relevant messages signed. We can see from the proposed scheme that the outputs are e and the final signature z,c. Because we have that c⟵v∈−1,0,1n:v1≤n, c is always a random number in the view of A⋆. Therefore, we can only consider two values e and z.
Firstly, we consider aboute. We assume that eb and e1−b are generated in the game of blindness. eb is held by U0. Similarly, e1−b is corresponding to U1. In our scheme, we can know that e=mc+b, where c can be seen as a random value. Besides, e is transmitted by using the bimodal Gaussian rejection sampling. Therefore, after getting eb and e1−b, A⋆ cannot link eb and e1−b to their respective messages ub or u1−b. It is because the distribution of eb and e1−b is both 1/2Gc,δ1n+1/2G−c,δ1n, but the output distribution of them is the same as that of b under the bimodal Gaussian rejection sampling, which is Gδ1n. In fact, the mean value of the distribution of eb should be different from that of e1−b. However, we know these mean values can be considered as a random number. So we set the mean value as c uniformly for sake of simplicity. So we can say that the statistical distance between eb and e1−b is 0; namely, Δeb,e1−b=0.
Next, we talk aboutz. In the proposed scheme, we have that z=y+a, where a⟵Gδ3m is a blind factor. However, the output way of z is different from that of the above challenge e, because the Gaussian rejection sampling used in this place is unimodal rather than bimodal. But this cannot make an influence on the blindness. Similarly, we assume that zb is the final signature of U0 and z1−b is related signature U1 received. Similarly, we set the mean value of distribution of zb and z1−b as y. It is because the value y is computed by the signer that the distribution of zb and z1−b is both Gy,δ3. According to the Gaussian rejection sampling, the output distribution of zb and z1−b is the same as that of a, which is Gδ3m. Therefore, A⋆ cannot determine the corresponding messages of zb and z1−b from their output distribution. That is, the relevant statistical distance Δzb,z1−b=0.
On the contrary, we assume thatA⋆ gets the corresponding parameters ID and the secret key SID by playing the game of blindness with U0 and U1. Besides, δub and δu1−b are information A⋆ has after playing this game. It is worth noting that if A⋆ uses the method of guessing a random value of b′ without any help to win the game of blindness, this probability is 1/2.
In addition, fori∈0,1, xi,ei, and yi are the data exchanged between the signer and the user, when the issue query is performed by the user. Finally, z0,c0 and z1,c1 are returned to the dishonest signer A⋆. For each i,j∈0,1, there are two random blind factors a,b that map xi,ei,yi to zj,cj. Thus, a=zj−yi and b=−mcj+ei. Since T=qI, where I is the unit matrix, we have(9)cj=HAuzj−Tcjmod2q,comu,t=HAua+yi−Tmei−bmod2q,comu,t=HAua+Auyi+Tei−bmod2q,comu,t=HAuyi+Tei+Aua−Tbmod2q,comu,t.
In the above equations,yi,ei are two elements in one view and zj,cj are two data in another view. Besides, two blind factors a and b are always included in the equation, which result in the indistinguishability to A⋆. Therefore, the probabilistic polynomial time adversary A⋆ makes out the right value of b successfully with probability 1/2.
In a word, our ID-based blind signature scheme on lattice has the security attribute of blindness.


### 6.2. Unforgeability

In fact, unforgeability ensures thatn valid signatures can be output by a malicious user at most. n is the maximum of queries that this adversary can make to the challenger. As the process of the game of unforgeability, we will give out the specific steps of this game on the basis of the proposed scheme.Theorem 5.
IfA⋆ is a probabilistic polynomial time adversary, it can break our ID-based blind signature on lattice with the nonnegligible probability. So, we can construct a polynomial-time algorithm using A⋆ as its subroutine to solve the SIS problem with overwhelming probability.Proof.
We assume thath and l are the maximum of queries that A⋆ can make to the random oracle H and the signer. Furthermore, the values of responses of the random oracle H are determined in advance. Thus, we have H⟶c1,…,cs, where s=l+h, because the adversary would make a query to H before sending a signature query. As shown in the following content, A⋆ plays the game of unforgeability with the challenger S:(i)
Setup: after inputting the security parameter1λ, the challenger picks a random matrix A∈Zqn∗m and a hash function H1:0,1∗⟶Zqn∗k. Additionally, the random oracle H is controlled by S. Then, these systematic public parameters are opened to A⋆.(ii)
Query:A⋆ can make four types of queries to S: H1 query, H query, extract query, and issue query. It is worth noting that S could maintain four empty lists before answering to those queries, namely, H1list, Hlist, SKlist, and Siglist. The specific processes of the answers to these queries will be displayed as follows:(1)
H1 query: as mentioned above, S holds an empty list H1list in advance, whose form of item is ID,PID,SID. After receiving an H1 query about the identity ID, S searches the corresponding item in H1list firstly. If there is an element IDi=ID, S gives PIDi to A⋆ as its response. Otherwise, S chooses a matrix SID∈Zm∗k at random, whose columns obey the distribution GZm,s. Then, S computes PID=ASID. According to Theorems 1 and 3 in the Gaussian Distribution section, SID≤sm and a random matrix PID∈Zn∗k are held with nonnegligible probability. Finally, the new item ID,PID,SID is inserted into H1list. Besides, PID is returned to A⋆.(2)
Extract query: after acquiring this query,S looks for the corresponding item ID,PID,SID in H1list firstly. Then A⋆ gets a random matrix SID′ from the matrix SID, where SID′∈Zn∗k. Moreover, A⋆ can compute the transposed matrix SID″k∗n of the matrix SID′ and we assign the value of SID″ to S′. In the end, S′ is inserted in SKlist and SKID=S′IT is given back to A⋆. If a corresponding item does not exist, S picks a random matrix S′∈Zk∗n and makes an H1 query. Similarly, the new item ID,PID,SID,S′ is added in the list SKlist and the relevant matrix SKID is transmitted to A⋆. Furthermore, S calculates A″=PIDSKIDmodq. Then, S can compute Au=2PID|2A′′+qI and give Au to the adversary as the public key of the user whose identity is ID.(3)
H query: similarly, the challenger maintains an empty list Hlist, of which item is xi+Aa+Tb,u,h. When A⋆ launches an H query, S searches the corresponding item in Hlist. If there is a related item in Hlist, the element h is given back to A⋆. Otherwise, the answer h to the adversary is a random ci that is not used yet, i∈1,…,s. Besides, the new item ci=h is added in Hlist.(4)
Issue query: after acquiring this query,S searches for the corresponding item ID,PID,SID,S′ on the basis of ID in SKlist. Then, S uses S′−IT as the secret key to execute the sign algorithm. Indeed, we can get the final signature z,h. Finally, S sends z,h to A⋆ as a response to this issue query.(iii)
Forgery: after completingl valid issue queries, A⋆ gives out l+1 valid message-signature pairs z1,c1,u1,…,zl+1,cl+1,ul+1 with nonnegligible probability ρ. It is worth noting that we always have zi≤2δ3m.
If the response to anH query is predetermined, namely, c∉c1,…,cs, A⋆ can make c as the answer of the random oracle H with the probability 1/H. Here, H is the size of output set of the random oracle H. In other words, c is one element in c1,…,cs with probability 1−1/H. Therefore, A⋆ can make a successful forgery zl+1,cl+1,ul+1 with the probability ρ−1/H, where cl+1 comes from c1,…,cs. As mentioned previously, the H query can take place in two places, so we need to talk about the specific scheme in two different scenarios:(1)
Scenario 1:c is generated by S during responding to an issue query made by A⋆. Because c is the response of a signature on Auz′−Tc,u′, we can have HAuz−Tc,u=HAuz′−Tc,u′. Thus, we must have that u=u′ and Auz−Tc=Auz′−Tc. If not, it means that we can find a collision of the hash function H. So, we can make a conclusion that Auz−z′=0mod2q. Besides, we have z−z′≤4δ3m, because z,z′≤2δ3m.(2)
Scenario 2:c is an answer of the random oracle H. In order to solve the SIS problem, S replays the game of unforgeability with A⋆. However, there is something different from the first process of this game. S changes the values of response of random oracle H, which is c1,…,cj−1,cj′,…,cs′. cj′,…,cs′ are different random values. According to the General Forking Lemma, A⋆ can forge a new signature c,z⋆ of ID,ul+1 with the probability ρ′, such that c≠cl+1 and Auzl+1−Tcl+1=Auz⋆−Tc. Additionally, the probability of ρ′ is(10)ρ′=ρ−1Hρ−1/Hs−1H.
Because ofT=AuSKID, we can have(11)Auzl+1−z⋆+SKIDcl+1−SKIDc=0.
In addition,zl+1,z⋆≤2δ3m and SKIDcl+1,SKIDc≤sλm are held. Thus, with overwhelming probability, we have(12)zl+1−z⋆+SKIDcl+1−SKIDc≤4δ3+2sλm.
Ifzl+1−z⋆+SKIDcl+1−SKIDc≠0, then a valid solution of the SIS hard problem is found. Thus, we need to prove that the probability of zl+1−z⋆+SKIDcl+1−SKIDc≠0 is overwhelming. According to the property of minimum entropy of the preimage, we can know that there is another secret key SID⋆ such that AuSID⋆=AuSID, which is different from SID. Additionally, the adversary cannot distinguish the secret key SID⋆ from SID, after getting the view x,e,y. Currently, we assume the secret key used in this game is SID⋆. Furthermore, we calculate r′ by the following way:(13)r′=y−kSID⋆e=r+kSIDe−kSID⋆e=r+keSID−SID⋆.
As mentioned above, we haveAuSID=AuSID⋆, so the equation Aur′=Aur is set up. Then we can get y′=r′+kSID⋆e=y. Therefore, the event that A⋆ wants to tell the relevant secret on the basis of r could not take place. Then, we have(14)zl+1−z⋆+SIDcl+1−c−zl+1−z⋆+SID⋆cl+1−c=SID−SID⋆cl+1−c≠0.
So, ifzl+1−z⋆+SIDcl+1−c=0, we can get the conclusion that zl+1−z⋆+SID⋆cl+1−c≠0 is satisfied. Simultaneously, the adversary cannot tell which secret key is used by the challenger S in the game. Thus, zl+1−z⋆+SIDcl+1−c≠0 is set up with the probability 1/2 at least.


## 6.1. Blindness

We mainly prove the blindness of our scheme from the indistinguishability of views. Normally, views are the information conveyed between the signer and the users, as the following theorem shows.Theorem 4.
The proposed ID-based blind signature scheme on lattice has blindness.Proof.
As the game of blindness shows, a dishonest signerA⋆pk,sk selects two messages u0 and u1. Then these messages are sent to two honest users U0pk,ub and U1pk,u1−b, where b∈0,1. Then this malicious signer plays the game of blindness with U0 and U1 in the interactive way, respectively. Therefore, we can prove that our ID-based blind signature scheme is blind to A⋆ by showing all outputs of the users are independent of the relevant messages signed. We can see from the proposed scheme that the outputs are e and the final signature z,c. Because we have that c⟵v∈−1,0,1n:v1≤n, c is always a random number in the view of A⋆. Therefore, we can only consider two values e and z.
Firstly, we consider aboute. We assume that eb and e1−b are generated in the game of blindness. eb is held by U0. Similarly, e1−b is corresponding to U1. In our scheme, we can know that e=mc+b, where c can be seen as a random value. Besides, e is transmitted by using the bimodal Gaussian rejection sampling. Therefore, after getting eb and e1−b, A⋆ cannot link eb and e1−b to their respective messages ub or u1−b. It is because the distribution of eb and e1−b is both 1/2Gc,δ1n+1/2G−c,δ1n, but the output distribution of them is the same as that of b under the bimodal Gaussian rejection sampling, which is Gδ1n. In fact, the mean value of the distribution of eb should be different from that of e1−b. However, we know these mean values can be considered as a random number. So we set the mean value as c uniformly for sake of simplicity. So we can say that the statistical distance between eb and e1−b is 0; namely, Δeb,e1−b=0.
Next, we talk aboutz. In the proposed scheme, we have that z=y+a, where a⟵Gδ3m is a blind factor. However, the output way of z is different from that of the above challenge e, because the Gaussian rejection sampling used in this place is unimodal rather than bimodal. But this cannot make an influence on the blindness. Similarly, we assume that zb is the final signature of U0 and z1−b is related signature U1 received. Similarly, we set the mean value of distribution of zb and z1−b as y. It is because the value y is computed by the signer that the distribution of zb and z1−b is both Gy,δ3. According to the Gaussian rejection sampling, the output distribution of zb and z1−b is the same as that of a, which is Gδ3m. Therefore, A⋆ cannot determine the corresponding messages of zb and z1−b from their output distribution. That is, the relevant statistical distance Δzb,z1−b=0.
On the contrary, we assume thatA⋆ gets the corresponding parameters ID and the secret key SID by playing the game of blindness with U0 and U1. Besides, δub and δu1−b are information A⋆ has after playing this game. It is worth noting that if A⋆ uses the method of guessing a random value of b′ without any help to win the game of blindness, this probability is 1/2.
In addition, fori∈0,1, xi,ei, and yi are the data exchanged between the signer and the user, when the issue query is performed by the user. Finally, z0,c0 and z1,c1 are returned to the dishonest signer A⋆. For each i,j∈0,1, there are two random blind factors a,b that map xi,ei,yi to zj,cj. Thus, a=zj−yi and b=−mcj+ei. Since T=qI, where I is the unit matrix, we have(9)cj=HAuzj−Tcjmod2q,comu,t=HAua+yi−Tmei−bmod2q,comu,t=HAua+Auyi+Tei−bmod2q,comu,t=HAuyi+Tei+Aua−Tbmod2q,comu,t.
In the above equations,yi,ei are two elements in one view and zj,cj are two data in another view. Besides, two blind factors a and b are always included in the equation, which result in the indistinguishability to A⋆. Therefore, the probabilistic polynomial time adversary A⋆ makes out the right value of b successfully with probability 1/2.
In a word, our ID-based blind signature scheme on lattice has the security attribute of blindness.


## 6.2. Unforgeability

In fact, unforgeability ensures thatn valid signatures can be output by a malicious user at most. n is the maximum of queries that this adversary can make to the challenger. As the process of the game of unforgeability, we will give out the specific steps of this game on the basis of the proposed scheme.Theorem 5.
IfA⋆ is a probabilistic polynomial time adversary, it can break our ID-based blind signature on lattice with the nonnegligible probability. So, we can construct a polynomial-time algorithm using A⋆ as its subroutine to solve the SIS problem with overwhelming probability.Proof.
We assume thath and l are the maximum of queries that A⋆ can make to the random oracle H and the signer. Furthermore, the values of responses of the random oracle H are determined in advance. Thus, we have H⟶c1,…,cs, where s=l+h, because the adversary would make a query to H before sending a signature query. As shown in the following content, A⋆ plays the game of unforgeability with the challenger S:(i)
Setup: after inputting the security parameter1λ, the challenger picks a random matrix A∈Zqn∗m and a hash function H1:0,1∗⟶Zqn∗k. Additionally, the random oracle H is controlled by S. Then, these systematic public parameters are opened to A⋆.(ii)
Query:A⋆ can make four types of queries to S: H1 query, H query, extract query, and issue query. It is worth noting that S could maintain four empty lists before answering to those queries, namely, H1list, Hlist, SKlist, and Siglist. The specific processes of the answers to these queries will be displayed as follows:(1)
H1 query: as mentioned above, S holds an empty list H1list in advance, whose form of item is ID,PID,SID. After receiving an H1 query about the identity ID, S searches the corresponding item in H1list firstly. If there is an element IDi=ID, S gives PIDi to A⋆ as its response. Otherwise, S chooses a matrix SID∈Zm∗k at random, whose columns obey the distribution GZm,s. Then, S computes PID=ASID. According to Theorems 1 and 3 in the Gaussian Distribution section, SID≤sm and a random matrix PID∈Zn∗k are held with nonnegligible probability. Finally, the new item ID,PID,SID is inserted into H1list. Besides, PID is returned to A⋆.(2)
Extract query: after acquiring this query,S looks for the corresponding item ID,PID,SID in H1list firstly. Then A⋆ gets a random matrix SID′ from the matrix SID, where SID′∈Zn∗k. Moreover, A⋆ can compute the transposed matrix SID″k∗n of the matrix SID′ and we assign the value of SID″ to S′. In the end, S′ is inserted in SKlist and SKID=S′IT is given back to A⋆. If a corresponding item does not exist, S picks a random matrix S′∈Zk∗n and makes an H1 query. Similarly, the new item ID,PID,SID,S′ is added in the list SKlist and the relevant matrix SKID is transmitted to A⋆. Furthermore, S calculates A″=PIDSKIDmodq. Then, S can compute Au=2PID|2A′′+qI and give Au to the adversary as the public key of the user whose identity is ID.(3)
H query: similarly, the challenger maintains an empty list Hlist, of which item is xi+Aa+Tb,u,h. When A⋆ launches an H query, S searches the corresponding item in Hlist. If there is a related item in Hlist, the element h is given back to A⋆. Otherwise, the answer h to the adversary is a random ci that is not used yet, i∈1,…,s. Besides, the new item ci=h is added in Hlist.(4)
Issue query: after acquiring this query,S searches for the corresponding item ID,PID,SID,S′ on the basis of ID in SKlist. Then, S uses S′−IT as the secret key to execute the sign algorithm. Indeed, we can get the final signature z,h. Finally, S sends z,h to A⋆ as a response to this issue query.(iii)
Forgery: after completingl valid issue queries, A⋆ gives out l+1 valid message-signature pairs z1,c1,u1,…,zl+1,cl+1,ul+1 with nonnegligible probability ρ. It is worth noting that we always have zi≤2δ3m.
If the response to anH query is predetermined, namely, c∉c1,…,cs, A⋆ can make c as the answer of the random oracle H with the probability 1/H. Here, H is the size of output set of the random oracle H. In other words, c is one element in c1,…,cs with probability 1−1/H. Therefore, A⋆ can make a successful forgery zl+1,cl+1,ul+1 with the probability ρ−1/H, where cl+1 comes from c1,…,cs. As mentioned previously, the H query can take place in two places, so we need to talk about the specific scheme in two different scenarios:(1)
Scenario 1:c is generated by S during responding to an issue query made by A⋆. Because c is the response of a signature on Auz′−Tc,u′, we can have HAuz−Tc,u=HAuz′−Tc,u′. Thus, we must have that u=u′ and Auz−Tc=Auz′−Tc. If not, it means that we can find a collision of the hash function H. So, we can make a conclusion that Auz−z′=0mod2q. Besides, we have z−z′≤4δ3m, because z,z′≤2δ3m.(2)
Scenario 2:c is an answer of the random oracle H. In order to solve the SIS problem, S replays the game of unforgeability with A⋆. However, there is something different from the first process of this game. S changes the values of response of random oracle H, which is c1,…,cj−1,cj′,…,cs′. cj′,…,cs′ are different random values. According to the General Forking Lemma, A⋆ can forge a new signature c,z⋆ of ID,ul+1 with the probability ρ′, such that c≠cl+1 and Auzl+1−Tcl+1=Auz⋆−Tc. Additionally, the probability of ρ′ is(10)ρ′=ρ−1Hρ−1/Hs−1H.
Because ofT=AuSKID, we can have(11)Auzl+1−z⋆+SKIDcl+1−SKIDc=0.
In addition,zl+1,z⋆≤2δ3m and SKIDcl+1,SKIDc≤sλm are held. Thus, with overwhelming probability, we have(12)zl+1−z⋆+SKIDcl+1−SKIDc≤4δ3+2sλm.
Ifzl+1−z⋆+SKIDcl+1−SKIDc≠0, then a valid solution of the SIS hard problem is found. Thus, we need to prove that the probability of zl+1−z⋆+SKIDcl+1−SKIDc≠0 is overwhelming. According to the property of minimum entropy of the preimage, we can know that there is another secret key SID⋆ such that AuSID⋆=AuSID, which is different from SID. Additionally, the adversary cannot distinguish the secret key SID⋆ from SID, after getting the view x,e,y. Currently, we assume the secret key used in this game is SID⋆. Furthermore, we calculate r′ by the following way:(13)r′=y−kSID⋆e=r+kSIDe−kSID⋆e=r+keSID−SID⋆.
As mentioned above, we haveAuSID=AuSID⋆, so the equation Aur′=Aur is set up. Then we can get y′=r′+kSID⋆e=y. Therefore, the event that A⋆ wants to tell the relevant secret on the basis of r could not take place. Then, we have(14)zl+1−z⋆+SIDcl+1−c−zl+1−z⋆+SID⋆cl+1−c=SID−SID⋆cl+1−c≠0.
So, ifzl+1−z⋆+SIDcl+1−c=0, we can get the conclusion that zl+1−z⋆+SID⋆cl+1−c≠0 is satisfied. Simultaneously, the adversary cannot tell which secret key is used by the challenger S in the game. Thus, zl+1−z⋆+SIDcl+1−c≠0 is set up with the probability 1/2 at least.


## 7. Performance Evaluation

In this section, the performance analysis of our scheme is talked about in detail. Generally, we will give out the result of comparison between our scheme and two other representative articles in terms of communication complexity and computing complexity. Specifically, these data are mainly derived from the signature’s size and computational cost of generating system parameters of the relevant scheme. Currently, most of the lattice-based blind signature schemes are proved secure in the random oracle model, where the scheme in [39] proposed by Rückert was the most authoritative in 2010. Besides, another blind scheme was proposed by Zhang et al. [13] in 2018, on which we design our new ID-based blind signature scheme. It is worth noting that we do not consider the computational cost of the key extraction phase of our scheme when we make a comparison of the performance between our scheme and Zhang et al.’s [13] signature scheme because their scheme is a PKI-based blind signature scheme on lattice.Firstly, we show a detailed comparison between our scheme and the blind signature scheme proposed by Zhang et al. [13]. To keep the reasonability, we will use the same way in Zhang et al.’s scheme [13] to choose the public system parameters. Namely, the security level of our scheme is the same as that of the scheme [13] proposed by Zhang et al. owing to the Hermite factor δ=1.007 defined in [40], which can reach 80 bits. Table 1 shows some important system parameters in these two schemes, where n,q,andk are used to keep the hardness of SIS problem.Table 1
The key parameters in blind signature scheme on lattice.
Zhang et al.’s scheme
Value
Our scheme
Value
n
—
512
—
512
q
—
2
27
—
2
27
d
—
1
—
1
m
64
+
n
log
q
/
log
2
d
+
1
8786
64
+
n
log
q
/
log
2
d
+
1
8786
k
—
80
m
−
n
8274
κ
—
28
—
28
δ
1
12
κ
64
κ
/
2
2
M
1
e
12
κ
/
δ
1
+
κ
/
2
δ
1
2
2.72
e
κ
/
2
δ
1
2
2.7
δ
2
12
d
η
δ
1
m
k
2
19
d
η
δ
1
m
k
/
2
30000
M
2
e
1
+
1
/
288
2.72
e
2.7
δ
3
12
d
η
δ
2
m
2
29.5
12
η
δ
2
m
3
∗
10
7
M
3
e
1
+
1
/
288
2.72
e
2.7
η
1.1
,
1.3
1.1
1.1
,
1.3
1.1In Table1, the parameters of the rejection sampling in our scheme are smaller than those of the scheme [13] proposed by Zhang et al. obviously. This is because the bimodal Gaussian rejection sampling is used in our scheme. Specifically, the size of a challenge is determined by the parameter κ. In general, κ should satisfy the condition 2κkκ≥2100 to keep the correctness error at 2−100. According to rejection sampling lemma, we need to keep the rejection area between the actual distribution and objective distribution as small as possible. In this way, the signature algorithm can generate a valid signature using as few repetitions as possible. On the basis of the property of bimodal Gaussian rejection sampling, we only need to require that δ=c/2 instead of 12c. In this case, the bimodal Gaussian rejection sampling can work with the minimum mean value M=e1. Normally, because M1 and M2 are the mean values of the bimodal Gaussian rejection sampling, they are independent of δ1, c and δ2, Sue. For M1, we have that M1=eκ/2δ12 when δ1=c/2=κ/2. This can hold because we have c1≤κ and c2≤κ. Similarly, we can get the optimal value of M2 while we make that δ2=dηδ1mk/2. However, because M3 is the mean value of the unimodal rejection sampling, we need to only require that δ3=12ηδ2m. In addition, the distribution of the final signature z is Gδ3m. By Theorem 1, we can determine that the size of z’s every coefficient is 12δ3 with the probability at least 1−2−100. Because the value of δ3 in our scheme is far less than that in Zhang et al.’s scheme [13], we can get the smaller valid signature that is equal to mlog12δ3 bits approximately. Additionally, our M1, M2, and M3 are smaller than those of the scheme proposed by Zhang et al. [13]. This means our blind signature scheme can use less time to generate a valid signature in the same security level. In the end, what we need to emphasize is that our blind signature scheme on lattice is based on the ID-based cryptosystem, which has already stronger efficiency than the PKI cryptosystem.Next, we will give out the comparison between our scheme and the classical scheme proposed by Rückert et al. simply [39]. Here, m and n are the common system parameters in these two schemes. Moreover, c is the bit size of the user’s identity and s¯=sc+1mωlogn is the expansive Gaussian parameter in Rückert et al.’s scheme [39]. We can know that the size of final signature in our scheme is mlog12δ3. According to the explanation of Rückert et al. [39], the size of signature is c+1mlogs¯c+1m+n in their ID-based blind scheme. Obviously, it is easy to make the conclusion that the signature’s size in our scheme is smaller than that of Rückert et al.’s scheme [39] in the random oracle model. In terms of computing complexity, there are only some simple operators involved in our sign algorithm and verify algorithm, such as scalar-multiplication on vector, addition on vector, matrix-vector multiplication, and hash function. However, in sign algorithm and verify algorithm of Rückert et al.’s scheme [39], the complex algorithms are included to generate a valid signature, such as ExtBasis algorithm and SamplePre algorithm. So our scheme is simpler and more efficient than the scheme proposed by Rückert et al. [39].Based on the above result, we can make a conclusion that our scheme has less communicational and computational cost, compared with the latest blind signature scheme on lattice proposed by Zhang et al. [13] and the most authoritative blind signature scheme on lattice proposed by Rückert et al. [39]. Thus, our scheme has more efficient and practical value in applications. Table 2 shows the result of relevant comparison in detail.Table 2
The comparison of relevant blind signature scheme.
Schemes
Signature size
Security level (bits)
Cryptosystem
Zhang et al.
m
log
12
δ
3
80
PKI-based
Ruckert et al.
c
+
1
m
log
s
¯
c
+
1
m
+
n
76
ID-based
Our scheme
m
log
12
δ
3
80
ID-based


## 8. Conclusion

Integrating the advantage of ID-based cryptosystem with lattice-based cryptosystem, we construct an efficient and secure ID-based blind signature scheme in this paper to protect the privacy of confidential data, which can be widely applied to the e-cash and electronic voting system. Moreover, a useful aborting technology, bimodal Gaussian rejection sampling, is used in our scheme to accelerate the speed of generating a valid blind signature. Meanwhile, our scheme is provably secure in the random oracle model, which is on the basis of the SIS problem. By showing the comparison with the scheme of Zhang et al. [13] and that of Rückert et al. [39], we demonstrate the superiority of our scheme in communicational and computational efficiency.To extend our scheme to get other useful properties and complete an original model of evaluating the extended scheme in the real application environment is the future work executed by us.



---

*Source: 7528571-2020-05-11.xml*