[Cryptography] An Identity-Based Blind Signature Scheme Using Lattice with Provable Security

[Bob Hettinga]

https://www.hindawi.com/journals/mpe/2020/7528571/

An Identity-Based Blind Signature Scheme Using Lattice with Provable Security
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.

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 an -bit integer can be decomposed by the -qubit quantum computer easily is proposed by Beauregard [1]. As for the discrete logarithm problem, Proos and Zalka [2] pointed out that -bits elliptic curve discrete logarithmic problem [3, 4] can be solved by -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 lattice is defined as a discrete additive subgroup of n-dimensional Euclidean vector space . Namely, if are linearly independent vectors in , a lattice is the set of all integer combinations of these vectors:and the matrix is one base of . Normally, is described as its corresponding dimension.

In particular, the following two types of lattices should be paid more attention, called module lattice:

3.1.1. Small Integer Solution (SIS) Problem

Given a positive integer , a matrix , and a real number , the SIS problem is to find a nonzero vector such that , and . This kind of SIS problem is homogeneous. As for inhomogeneous SIS problem, it is to find a nonzero preimage satisfying , where .

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 integer , ; there is an effective algorithm that can generate a matrix and a basis of the lattice . Besides, the distribution of the matrix is the uniform distribution in approximately and the orthogonal matrix .

3.1.3. General Preimage Sampling Algorithm

There are an integer , a prime number , and a positive integer . The lattice is defined by the matrix . Additionally, the matrix is a base of the lattice . If the parameter of the Gaussian distribution , there is a polynomial-time algorithm , where is a random matrix defined in , sampling a matrix in a distribution closing to , such that .

3.2. Gaussian Distribution and Bimodal Gaussian Rejection Sampling

3.2.1. Gaussian Distribution

In statistics, the distribution function of continuous Gaussian distribution is , where is the center and is the standard deviation. Furthermore, if , we usually make the equation simpler, writing it as . In the case of lattice , the function is . So the discrete Gaussian distribution over is written as . Meanwhile, the discrete Gaussian distribution defined over is normally described as . If the center , we usually write these two symbols as and .

In the following, some theorems on the discrete Gaussian distribution are shown.

Theorem 1. We assume that , so the following formula holds:

Furthermore, if we have , and for any element , the following conclusion is made out:

Theorem 2. It is described that we have , where , and is an element in . We have

Theorem 3. If the matrix is chosen randomly and , we have that , whose distribution is uniform approximately in .

3.2.2. Rejection Sampling

The rejection sampling is a useful aborting skill in lattice-based schemes. Speaking in formal terms, when the positive constant and a special distribution are given, we need to find another distribution , which makes . So we can say that the distribution is seen as another distribution with the probability . In general, is the mean value of times to get an effective sample.

(1) Rejection Sampling Lemma. It is assumed that is a distribution whose preimage is , where , and maps to . When , we can have a constant to give the distribution of the following output:(1).(2).(3)The is given out with the probability is within the statistical distance of another distribution:(1)(2)(3)The output is sent with the probability

(2) Bimodal Gaussian Rejection Sampling. In the original Gaussian rejection sampling, the mean value of repetitions of the sampling is , when the standard deviation , 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, 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 is sampled. Then, the relevant signature is . Thus, the probability distribution of is . According to the requirement of rejection sampling, firstly, the inequality must be held. Secondly, we need to make as small as possible. For the sake of interpretation, we give out the following formula:

Because there is a fact in math that the inequality is always true for any , we can get the value by making get the value instead of the value . It is easy to see that the mean value 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 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 users and . In addition, is considered to be a malicious signer. The game of blindness is defined as follows:(1) gets the public parameters by querying .(2) performs . Namely, can get the secret key of the identity by using Key Extract algorithm.(3) chooses a random bit secretly. Then it sends a pair of messages to and .(4) executes the signature scheme with and , respectively. The messages input by and are and .(5)The outputs and received by and are sent to in arbitrary order.(6) outputs a bit .

It is worth noting that wins the game of blindness if and only if . Moreover, we consider as the advantage of to win this game.

Next, another security game aimed at unforgeability will be defined as below. In this game, acts as the challenger and is an adversary playing as a user.

4.2. Unforgeability Game

We think that can break the unforgeability of an ID-based blind signature scheme, if makes extract queries and issue queries during the time and the corresponding advantage of is at least. Otherwise, this scheme is unforgeability. The game of unforgeability is defined as follows:(1)Setup: after inputting the security parameter , runs the Setup algorithm to generate the systematic public parameter and the master secret key . Then, the public parameter is sent to .(2)Query: there are three kinds of queries that can choose to send to .(a)Hash query: after getting this query, would select a random value and return it to . It is worth noting that random oracle queries are responded by the challenger consistently.(b)Extract query: after receiving this query, would run the Key Extract algorithm to get the relevant secret key and give it back to .(c)Issue query: after obtaining this query, executes the sign algorithm with cooperatively to get the signature . But before this operation, would get the ’s secret key by performing the extract query. Finally, the signature is given back to .(3)Forgery: after the above query phase, will use the useful information to forge a signature corresponding to the message of the user, of which identity is . Additionally, outputs valid signature pairs , where . If the following conditions are satisfied by these signature pairs, we can conclude that wins this game. Furthermore, is the advantage of to get final success in this game.(a)For any and , we have that , where and .(b).(c) never uses the extract query to get the secret key of the user whose identity is .

Generally, an ID-based blind signature is considered to have blindness and unforgeability, if and 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 are and [37, 38]. Meanwhile, public key generator (PKG) is the trusted third party.

5.1. System Setup

After getting the safety parameter and , PKG performs the following four steps:(1)Choosing a prime number , , , and , where .(2)Executing the algorithm , where . These matrices and are the public key and the secret key of PKG, respectively.(3)Selecting two secure hash functions and . Actually, .(4)Making the parameters public and keeping 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 Figure 1.(1)Computing and performing the algorithm . We can know that and .(2)Owing to , getting , and choosing rows of randomly and then computing the relevant transposed matrix and finally calculating .(3)Computing and , where is the unit matrix, and then making the computation . So, and are the user’s public keys and is the corresponding secret key.

5.3. Sign Phase

Essentially, this phase is an interactive three-move identification scheme over lattice based on SIS problem. It is assumed that is the actual message needed to be signed. The specific interaction process is as follows:(1)The signer selects a random vector and calculates . Then, is transmitted to the user.(2)Blind: the user chooses two blind factors and and computes . Noticeably, is the message to be signed and is a random value. Besides, the function is a commitment. Then, is worked out, where . Finally, is sent to the signer by using the bimodal Gaussian rejection sampling to stop from leaking some information of .(3)BSign: the signer selects randomly. Upon that, it can compute . Similarly, is sent to the user in the same way to hide relevant information of .(4)Unblind: the user can get the value of . Then, is output by the unimodal Gaussian rejection sampling. If , we make , where is the rejection region of Gaussian sampling. Otherwise, we have . Finally, is given to the signer.(5)After holding , the signer checks whether the value of is or not. If it holds, the blind signature is valid. On the contrary, if , , and , the signer restarts the sign phase with the user.

The sign phase is shown in Figure 2.

5.4. Verify Phase

In this phase, the verifier should check whether the following conditions are right or not:(1)(2)

Actually, is the final signature pair. If the two above conditions are satisfied, we have .

5.5. Correctness Analysis Phase

In this section, we mainly talk about the correctness and repetition of our blind signature. Firstly, we have

Thus, we have the fact that  = . Additionally, on the basis of Theorem 1 and rejection sampling lemma, there is 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

In the rejection sampling lemma, we need to keep as small as possible. Therefore, the value of is worked out, where , and . Obviously, and are both less than the original values in the general rejection sampling, but not . Therefore, it means that a valid blind signature can be generated successfully in lesser repetitions, whose specific number is .

6. Security Proof

In this section, we mainly prove that our scheme is blind and unforgeable by using the security model defined in Section 4. 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 signer selects two messages and . Then these messages are sent to two honest users and , where . Then this malicious signer plays the game of blindness with and in the interactive way, respectively. Therefore, we can prove that our ID-based blind signature scheme is blind to 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 and the final signature . Because we have that , is always a random number in the view of . Therefore, we can only consider two values and .
Firstly, we consider about . We assume that and are generated in the game of blindness. is held by . Similarly, is corresponding to . In our scheme, we can know that , where can be seen as a random value. Besides, is transmitted by using the bimodal Gaussian rejection sampling. Therefore, after getting and , cannot link and to their respective messages or . It is because the distribution of and is both , but the output distribution of them is the same as that of under the bimodal Gaussian rejection sampling, which is . In fact, the mean value of the distribution of should be different from that of . However, we know these mean values can be considered as a random number. So we set the mean value as uniformly for sake of simplicity. So we can say that the statistical distance between and is 0; namely, .
Next, we talk about . In the proposed scheme, we have that , where is a blind factor. However, the output way of is different from that of the above challenge , 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 is the final signature of and is related signature received. Similarly, we set the mean value of distribution of and as . It is because the value is computed by the signer that the distribution of and is both . According to the Gaussian rejection sampling, the output distribution of and is the same as that of , which is . Therefore, cannot determine the corresponding messages of and from their output distribution. That is, the relevant statistical distance .
On the contrary, we assume that gets the corresponding parameters and the secret key by playing the game of blindness with and . Besides, and are information has after playing this game. It is worth noting that if uses the method of guessing a random value of without any help to win the game of blindness, this probability is .
In addition, for , , and are the data exchanged between the signer and the user, when the issue query is performed by the user. Finally, and are returned to the dishonest signer . For each , there are two random blind factors that map to . Thus, and . Since , where is the unit matrix, we haveIn the above equations, are two elements in one view and are two data in another view. Besides, two blind factors and are always included in the equation, which result in the indistinguishability to . Therefore, the probabilistic polynomial time adversary makes out the right value of successfully with probability .
In a word, our ID-based blind signature scheme on lattice has the security attribute of blindness.

6.2. Unforgeability

In fact, unforgeability ensures that valid signatures can be output by a malicious user at most. 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. If 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 as its subroutine to solve the SIS problem with overwhelming probability.

Proof. We assume that and are the maximum of queries that can make to the random oracle and the signer. Furthermore, the values of responses of the random oracle are determined in advance. Thus, we have , where , because the adversary would make a query to before sending a signature query. As shown in the following content, plays the game of unforgeability with the challenger :(i)Setup: after inputting the security parameter , the challenger picks a random matrix and a hash function . Additionally, the random oracle is controlled by . Then, these systematic public parameters are opened to .(ii)Query: can make four types of queries to : query, query, extract query, and issue query. It is worth noting that could maintain four empty lists before answering to those queries, namely, , , , and . The specific processes of the answers to these queries will be displayed as follows:(1) query: as mentioned above, holds an empty list in advance, whose form of item is . After receiving an query about the identity , searches the corresponding item in firstly. If there is an element , gives to as its response. Otherwise, chooses a matrix at random, whose columns obey the distribution . Then, computes . According to Theorems 1 and 3 in the Gaussian Distribution section, and a random matrix are held with nonnegligible probability. Finally, the new item is inserted into . Besides, is returned to .(2)Extract query: after acquiring this query, looks for the corresponding item in firstly. Then gets a random matrix from the matrix , where . Moreover, can compute the transposed matrix of the matrix and we assign the value of to . In the end, is inserted in and is given back to . If a corresponding item does not exist, picks a random matrix and makes an query. Similarly, the new item is added in the list and the relevant matrix is transmitted to . Furthermore, calculates . Then, can compute and give to the adversary as the public key of the user whose identity is .(3) query: similarly, the challenger maintains an empty list , of which item is . When launches an query, searches the corresponding item in . If there is a related item in , the element is given back to . Otherwise, the answer to the adversary is a random that is not used yet, . Besides, the new item is added in .(4)Issue query: after acquiring this query, searches for the corresponding item on the basis of in . Then, uses as the secret key to execute the sign algorithm. Indeed, we can get the final signature . Finally, sends to as a response to this issue query.(iii)Forgery: after completing valid issue queries, gives out valid message-signature pairs with nonnegligible probability . It is worth noting that we always have .If the response to an query is predetermined, namely, , can make as the answer of the random oracle with the probability . Here, is the size of output set of the random oracle . In other words, is one element in with probability . Therefore, can make a successful forgery with the probability , where comes from . As mentioned previously, the query can take place in two places, so we need to talk about the specific scheme in two different scenarios:(1)Scenario 1: is generated by during responding to an issue query made by . Because is the response of a signature on , we can have . Thus, we must have that and . If not, it means that we can find a collision of the hash function . So, we can make a conclusion that . Besides, we have , because .(2)Scenario 2: is an answer of the random oracle . In order to solve the SIS problem, replays the game of unforgeability with . However, there is something different from the first process of this game. changes the values of response of random oracle , which is . are different random values. According to the General Forking Lemma, can forge a new signature of with the probability , such that and . Additionally, the probability of isBecause of , we can haveIn addition, and are held. Thus, with overwhelming probability, we haveIf , then a valid solution of the SIS hard problem is found. Thus, we need to prove that the probability of is overwhelming. According to the property of minimum entropy of the preimage, we can know that there is another secret key such that , which is different from . Additionally, the adversary cannot distinguish the secret key from , after getting the view . Currently, we assume the secret key used in this game is . Furthermore, we calculate by the following way:As mentioned above, we have , so the equation is set up. Then we can get . Therefore, the event that wants to tell the relevant secret on the basis of could not take place. Then, we haveSo, if , we can get the conclusion that is satisfied. Simultaneously, the adversary cannot tell which secret key is used by the challenger in the game. Thus, is set up with the probability 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 defined in [40], which can reach 80 bits. Table 1 shows some important system parameters in these two schemes, where are used to keep the hardness of SIS problem.

Zhang et al.’s scheme	Value	Our scheme	Value
—	512	—	512
—		—	
—	1	—	1
8786		8786
—	80		8274
—	28	—	28
64		2
2.72		2.7
30000
2.72		2.7
2.72		2.7
1.1		1.1
In Table 1, 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 to keep the correctness error at . 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 instead of . In this case, the bimodal Gaussian rejection sampling can work with the minimum mean value . Normally, because and are the mean values of the bimodal Gaussian rejection sampling, they are independent of , and , . For , we have that when . This can hold because we have and . Similarly, we can get the optimal value of while we make that . However, because is the mean value of the unimodal rejection sampling, we need to only require that . In addition, the distribution of the final signature is . By Theorem 1, we can determine that the size of ’s every coefficient is with the probability at least . Because the value of 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 bits approximately. Additionally, our , , and 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, and are the common system parameters in these two schemes. Moreover, is the bit size of the user’s identity and 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 . According to the explanation of Rückert et al. [39], the size of signature is 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.

Schemes	Signature size	Security level (bits)	Cryptosystem
Zhang et al.		80	PKI-based
Ruckert et al.		76	ID-based
Our scheme		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.

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (nos. 61772224, 61932016, and 61972294).

References

S. Beauregard, “Circuit for shor’s algorithm using 2n + 3 qubits,” 2002, http://arxiv.org/abs/0205095. View at: Google Scholar
J. Proos and C. Zalka, “Shor’s discrete logarithm quantum algorithm for elliptic curves,” 2003, http://arxiv.org/abs/0301141. View at: Google Scholar
D. He, Y. Zhang, D. Wang, and K.-K. R. Choo, “Secure and efficient two-party signing protocol for the identity-based signature scheme in the IEEE P1363 standard for public key cryptography,” IEEE Transactions on Dependable and Secure Computing, vol. 1, no. 99, pp. 1–10, 2019. View at: Publisher Site | Google Scholar
Q. Feng, D. He, Z. Liu, D. Wang, and K.-K. R. Choo, “Distributed signing protocol for IEEE P1363-compliant identity-based signature scheme,” IET Information Security, vol. 1, no. 99, pp. 1–10, 2020. View at: Publisher Site | Google Scholar
D. Chaum, “Blind signatures for untraceable payments,” in Advances in Cryptology, pp. 199–203, Springer, Berlin, Germany, 1983. View at: Google Scholar
C. Popescu, “Blind signature schemes based on the elliptic curve discrete logarithm problem,” Studies in Informatics and Control, vol. 19, no. 4, pp. 397–402, 2010. View at: Publisher Site | Google Scholar
N. A. Moldovyan, “Blind signature protocols from digital signature standards,” International Journal of Network Security, vol. 13, no. 1, pp. 22–30, 2011. View at: Google Scholar
A. Shamir, “Identity-based cryptosystems and signature schemes,” in Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, pp. 47–53, Springer, Paris, France, April 1984. View at: Google Scholar
D. S. Gupta and G. P. Biswas, “Design of lattice-based elgamal encryption and signature schemes using sis problem,” Transactions on Emerging Telecommunications Technologies, vol. 29, no. 6, p. e3255, 2018. View at: Publisher Site | Google Scholar
S. Mukherjee, D. S. Gupta, and G. P. Biswas, “An efficient and batch verifiable conditional privacy-preserving authentication scheme for vanets using lattice,” Computing, vol. 101, no. 12, pp. 1763–1788, 2019. View at: Publisher Site | Google Scholar
D. S. Gupta and G. P. Biswas, “A novel and efficient lattice-based authenticated key exchange protocol in c-k model,” International Journal of Communication Systems, vol. 31, no. 3, p. e3473, 2018. View at: Publisher Site | Google Scholar
M. Rückert, “Lattice-based blind signatures,” in Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, pp. 413–430, Springer, Singapore, December 2010. View at: Google Scholar
P. Zhang, H. Jiang, Z. Zheng, P. Hu, and Q. Xu, “A new post-quantum blind signature from lattice assumptions,” IEEE Access, vol. 6, pp. 27 251–27 258, 2018. View at: Publisher Site | Google Scholar
F. Li, M. Zhang, and T. Takagi, “Identity-based partially blind signature in the standard model for electronic cash,” Mathematical and Computer Modelling, vol. 58, no. 1-2, pp. 196–203, 2013. View at: Publisher Site | Google Scholar
L. Lopez-Garcia, L. J. D. Perez, and F. Rodriguez-Henriquez, “A pairing-based blind signature e-voting scheme,” The Computer Journal, vol. 57, no. 10, pp. 1460–1471, 2013. View at: Publisher Site | Google Scholar
C.-C. Chang and T.-F. Cheng, “A provably secure t-out-of-n oblivious transfer mechanism based on blind signature,” Journal of Information Hiding & Multimedia Signal Processing, vol. 5, no. 1, pp. 1–12, 2014. View at: Google Scholar
L.-C. Wu, Y.-S. Yeh, and C.-I. Fan, “Fail-stop blind signature scheme based on the integer factorization,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 7, no. 3, pp. 281–290, 2004. View at: Publisher Site | Google Scholar
H. Mala and N. Nezhadansari, “New blind signature schemes based on the (elliptic curve) discrete logarithm problem,” in Proceedings of the ICCKE 2013, pp. 196–201, IEEE, Mashhad, Iran, October 2013. View at: Publisher Site | Google Scholar
K. Chakraborty and J. Mehta, “A stamped blind signature scheme based on elliptic curve discrete logarithm problem,” International Journal of Network Security, vol. 14, no. 6, pp. 316–319, 2012. View at: Google Scholar
F. Zhang and K. Kim, “Id-based blind signature and ring signature from pairings,” in Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, pp. 533–547, Springer, Queenstown, New Zealand, 2002. View at: Google Scholar
Z. Huang, K. Chen, and Y. Wang, “Efficient identity-based signatures and blind signatures,” in Proceedings of the International Conference on Cryptology and Network Security, pp. 120–133, Springer, Xiamen, China, December 2005. View at: Google Scholar
S. Kalkan, K. Kaya, and A. A. Selcuk, “Generalized id-based blind signatures from bilinear pairings,” in Proceedings of the 2008 23rd International Symposium on Computer and Information Sciences, pp. 1–6, IEEE, Istanbul, Turkey, May 2008. View at: Publisher Site | Google Scholar
B. U. Rao, K. Ajmath, P. V. Reddy, and T. Gowri, “An id-based blind signature scheme from bilinear pairings,” International Journal of Computer Science and Security, vol. 4, no. 1, pp. 98–106, 2010. View at: Google Scholar
F. Hess, “Efficient identity based signature schemes based on pairings,” in Proceedings of the International Workshop on Selected Areas in Cryptography, pp. 310–324, Springer, Newfoundland, Canada, August 2002. View at: Google Scholar
C.-I. Fan, W.-Z. Sun, and V. S.-M. Huang, “Provably secure randomized blind signature scheme based on bilinear pairing,” Computers & Mathematics with Applications, vol. 60, no. 2, pp. 285–293, 2010. View at: Publisher Site | Google Scholar
L. Zhang, Y. Hu, X. Tian, and Y. Yang, “Novel identity-based blind signature for electronic voting system,” in Proceedings of the 2010 Second International Workshop on Education Technology and Computer Science, vol. 2, pp. 122–125, IEEE, Wuhan, China, March 2010. View at: Publisher Site | Google Scholar
R. Shakerian, T. MohammadPour, S. H. Kamali, and M. Hedayati, “An identity based public key cryptography blind signature scheme from bilinear pairings,” in Proceedings of the 2010 3rd International Conference on Computer Science and Information Technology, vol. 7, pp. 28–32, IEEE, Chengdu, China, July 2010. View at: Publisher Site | Google Scholar
D. He, J. Chen, and R. Zhang, “An efficient identity-based blind signature scheme without bilinear pairings,” Computers & Electrical Engineering, vol. 37, no. 4, pp. 444–450, 2011. View at: Publisher Site | Google Scholar
S. H. Islam, R. Amin, G. P. Biswas, M. S. Obaidat, and M. K. Khan, “Provably secure pairing-free identity-based partially blind signature scheme and its application in online e-cash system,” Arabian Journal for Science and Engineering, vol. 41, no. 8, pp. 3163–3176, 2016. View at: Publisher Site | Google Scholar
M. Kumar, C. P. Katti, and P. C. Saxena, “An untraceable identity-based blind signature scheme without pairing for e-cash payment system,” in Proceedings of the International Conference on Ubiquitous Communications and Network Computing, pp. 67–78, Springer, Bangalore, India, February 2017. View at: Google Scholar
S. James, N. B. Gayathri, and P. V. Reddy, “Pairing free identity-based blind signature scheme with message recovery,” Cryptography, vol. 2, no. 4, p. 29, 2018. View at: Publisher Site | Google Scholar
H. Zhu, Y.-a. Tan, X. Zhang, L. Zhu, C. Zhang, and J. Zheng, “A round-optimal lattice-based blind signature scheme for cloud services,” Future Generation Computer Systems, vol. 73, pp. 106–114, 2017. View at: Publisher Site | Google Scholar
L. Zhang and Y. Ma, “A lattice-based identity-based proxy blind signature scheme in the standard model,” Mathematical Problems in Engineering, vol. 2014, Article ID 307637, 6 pages, 2014. View at: Publisher Site | Google Scholar
W. Gao, Y. Hu, B. Wang, and J. Xie, “Identity-based blind signature from lattices in standard model,” in Proceedings of the International Conference on Information Security and Cryptology, pp. 205–218, Springer, Seoul, South Korea, 2016. View at: Google Scholar
W. Gao, Y. Hu, B. Wang, J. Xie, and M. Liu, “Identity-based blind signature from lattices,” Wuhan University Journal of Natural Sciences, vol. 22, no. 4, pp. 355–360, 2017. View at: Publisher Site | Google Scholar
L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky, “Lattice signatures and bimodal Gaussians,” in Proceedings of the Annual Cryptology Conference, pp. 40–56, Springer, Santa Barbara, CA, USA, August 2013. View at: Google Scholar
C. Gentry, C. Peikert, and V. Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,” in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 197–206, ACM, Victoria, Canada, May 2008. View at: Publisher Site | Google Scholar
J. Alwen and C. Peikert, “Generating shorter bases for hard random lattices,” Theory of Computing Systems, vol. 48, no. 3, pp. 535–553, 2011. View at: Publisher Site | Google Scholar
M. Rückert, “Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles,” in Proceedings of the International Workshop on Post-Quantum Cryptography, pp. 182–200, Springer, Darmstadt, Germany, May 2010. View at: Google Scholar
N. Gama and P. Q. Nguyen, “Predicting lattice reduction,” in Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 31–51, Springer, Istanbul, Turkey, April 2008. View at: Google Scholar
Copyright

Copyright © 2020 Quanrun Li et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20200513/7ef63265/attachment-0001.htm>