A Lattice-Based Identity-Based Proxy Blind Signature Scheme in the Standard Model

Abstract

A proxy blind signature scheme is a special form of blind signature which allowed a designated person called proxy signer to sign on behalf of original signers without knowing the content of the message. It combines the advantages of proxy signature and blind signature. Up to date, most proxy blind signature schemes rely on hard number theory problems, discrete logarithm, and bilinear pairings. Unfortunately, the above underlying number theory problems will be solvable in the postquantum era. Lattice-based cryptography is enjoying great interest these days, due to implementation simplicity and provable security reductions. Moreover, lattice-based cryptography is believed to be hard even for quantum computers. In this paper, we present a new identity-based proxy blind signature scheme from lattices without random oracles. The new scheme is proven to be strongly unforgeable under the standard hardness assumption of the short integer solution problem (SIS) and the inhomogeneous small integer solution problem (ISIS). Furthermore, the secret key size and the signature length of our scheme are invariant and much shorter than those of the previous lattice-based proxy blind signature schemes. To the best of our knowledge, our construction is the first short lattice-based identity-based proxy blind signature scheme in the standard model.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Academic Editor:Yan-Wu Wang

Institute of Information Engineering and Huanghe Science and Technology College, Zhengzhou 450063, China

Received 25 April 2014; Revised 15 August 2014; Accepted 17 August 2014; 25 September 2014

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.

1. Introduction

Digital signature schemes are the cornerstone of e-business, e-government, software security, and many more applications. The importance of these schemes is likely to grow in the future as more and more everyday tasks and processes are computerized.

The concept of blind signature was first proposed in 1982 by Chaum [1]: user A could obtain the signature of B on any given message, without any information about the message or its signature revealed, and any receiver could verify the signature that is signed by signer B.

In 1996, Mambo et al. introduced the concept of proxy signature [2]: an original signer delegates his signing authority to another signer, who is called a proxy signer. At last, the proxy signer can sign any message on behalf of the original signer and the verifier can verify and distinguish between normal signature and proxy signature.

In 1985, Shamir introduced the concept of identity-based (ID-based) cryptography and presented an ID-based signature (IBS) scheme [3]. In an IBS scheme, a public key can be derived from the identity of the user, and a corresponding secret key can be generated by a private key generator (PKG). Of course, the IBS scheme can simplify key management procedures in certificate-based public key systems, so it can be an alternative for certificate-based public key systems in some occasions, especially, when efficient key management and moderate security are required.

In 2000, Lin and Jan [4] introduced the concept of proxy blind signature. Proxy blind signatures are actually the combination of both proxy signature and blind signature. It plays an important role in the following scenario: in e-cash system, the user makes the bank blindly sign a coin using blind signature schemes. Whenever a user goes through a valid branch to withdraw a coin, he/she needs the branch to make proxy blind signature on behalf of the signee bank.

Tan et al.'s scheme is a proxy blind signature scheme which is based on Schnorr blind signature. But Awasthi and der Lal [5] showed a forgery attack on Tan et al.'s scheme and proposed a more secure proxy blind signature scheme. Recently Sun et al. [6] pointed out that neither Tan et al.'s scheme nor Awasthi and der Lal's scheme satisfies the unlinkability property of the proxy blind signature scheme. But they did not give an improved scheme to overcome the insecurity. For the first time, Zhang et al. [7] proposed a proxy blind signature scheme from bilinear pairings. In 2004, Zheng et al. [8] proposed an ID-based proxy blind signature scheme which uses bilinear pairings of elliptic curves or hyperelliptic curves. Since then, many identity-based proxy blind signature schemes have been proposed, for example, [9-11].

Up to date, most of proposed identity-based proxy blind signature schemes rely on hard number theory problems such as integer factorization, discrete logarithm, and bilinear pairings with the Diffie-Hellman problem. However, the above underlying number theory problems will be solvable if practical quantum computers become reality, so it implies a potential security threat to these identity-based proxy blind schemes. Thus, a natural question one can ask is how to design identity-based proxy blind signature schemes that are secure in the quantum environment.

In recent years, lattices have emerged as a possible alternative to number theories. Lattice-based cryptography began with the seminal work of Ajtai [12], who showed that it is possible to construct families of cryptographic functions. Moreover, lattice-based cryptography is believed to be hard even for quantum computers [13]. Several lattice-based signature schemes [14-18] have been proposed so far. Among them, Jiang et al. [18] presented the first proxy signature scheme from lattices. Unfortunately, Tian and Huang [19] pointed that an original signer is able to forge a proxy signature on any message in the scheme. In 2010, Cash et al. put forward a new cryptographic notion called a bonsai tree based on hard lattice [20]. Since then, many proxy signatures [21, 22] were presented in bonsai tree model based on the bonsai tree signature scheme. However, both the private keys and the signatures in these schemes become dramatically longer than general signature. Therefore, they may not be practical for large communities.

Recently, Agrawal et al. [23] presented a basis delegation algorithm which keeps the dimension of the lattices involved constant. Based on the algorithm, the first lattice-based hierarchical identity-based encryption scheme with short ciphertexts in the standard model was proposed in [23]. Still, there is no identity-based proxy blind signature scheme from lattices in the standard model.

Following the above discussion, in this paper, we will construct a new identity-based proxy blind signature scheme from lattices in the standard model, which is obtained from Agrawal et al.'s basis delegation algorithm [23]. The new scheme is provably secure against strong forgery under hard problems on lattices, and the size of secret keys and the signature length of our scheme are much shorter than those of signature schemes [21, 22].

The rest of the paper is organized as follows: the next section gives the introduction of lattices, Section 3 explains briefly the definition of proxy blind signature, and Section 4 gives a detailed description of our identity-based proxy blind signature from lattice basis delegation. In Section 5, an analysis about our scheme is presented. Section 6 concludes this paper.

2. Preliminaries

2.1. Lattice

Let B = [ _{b 1} , _{b 2} , ... , _{b n} ] and let _{b 1} , _{b 2} , ... , _{b n} be n linearly independent vectors in ^{R n} ; the n -dimensional lattice Λ generated by the basis B is [figure omitted; refer to PDF] here B is called a basis of the lattice ^{Λ [perpendicular]} ( B ) . For a basis B = [ _{b 1} , _{b 2} , ... , _{b n} ] , let B ~ denote its Gram-Schmidt orthogonalization, defined iteratively as follows: _{b 1} ~ = _{b 1} , and for i = 2,3 , ... , n , _{b i} ~ is the component of _{b i} orthogonal to span ( _{b 1} , _{b 2} , ... , _{b i - 1} ).

The minimum distance _{λ 1} of the lattice is the length _{l 2} (in the Euclidean norm, unless otherwise indicated) of its shortest nonzero vector: [figure omitted; refer to PDF]

We define the orthogonal lattice ^{Λ [perpendicular]} ( B ) as [figure omitted; refer to PDF]

2.2. Hard Problems on Lattices

Security of our signature scheme rests on the hardness assumption of the short integer solution (SIS) problem and the inhomogeneous small integer solution problem [14].

Definition 1 (the small integer solution problem (SIS) (in the Euclidean _{l 2} norm)).

Given an integer q , a matrix A ∈ ^{R q n × m} , and a real β , the goal of the short integer solution problem SI _{S q , m , β} is to find a nonzero integer vector e ∈ ^{Z q m} , such that A e = 0 mod q and _{|| e || 2} ...4; β .

Definition 2 (the inhomogeneous small integer solution problem (ISIS) (in the Euclidean _{l 2} norm)).

Give an integer q , a matrix A ∈ ^{R q n × m} , a syndrome y ∈ ^{Z q n} , and a real β , to find an integer vector e ∈ ^{Z q m} , such that A e = y mod q and _{|| e || 2} ...4; β .

2.3. Trapdoor and Basis Delegation Functions for Lattices

It was shown in [14] that if SI _{S q , m , β} is hard, A ∈ ^{R q n × m} defines a one-way function _{f A} : _{D n} [arrow right] _{R n} , with _{f A} ( e ) = A e , where _{D n} = { e ∈ ^{Z m} |" || e || ...4; r m } and _{R n} = ^{Z q n} . The input distribution is _{D ^{Z m} , r} , and a short basis for ^{Λ [perpendicular]} ( A ) can be used as a trapdoor to sample from ^{f A - 1} ( y ) .

Here we briefly introduce some enhanced variants of trapdoor functions [14] with preimage sampling, which are given by a tuple of probabilistic polynomial-time algorithms (TrapGen , SampleD , and SamplePre ), which will be used as building blocks in our signature scheme.

The following functions take the Gaussian smoothing parameter r ...5; || B ~ || · ω ( l g m ) as a parameter.

TrapGen ( ^{1 n} ) . Let n , q , and m be integers with q ...5; 2 , m ...5; 2 n l g q ; TrapGen( ^{1 n} ) outputs a pair ( A , T ) , where A is statistically close to uniform on ^{Z q n × m} and T is a good basis of ^{Λ [perpendicular]} ( A ) , such that || B ~ || ...4; m l g m .

SampleD ( A , r ) . Sample an e from distribution _{D ^{Z m} , r} , for which the distribution of A e is uniform over ^{Z q n} .

SamplePre ( A , T , y , r ) . On input of A ∈ ^{Z q n × m} , a good basis T for ^{Λ [perpendicular]} ( A ) as the trapdoor, a vector y ∈ ^{Z q n} , and r , the conditional distribution of the output e is within negligible statistical distance of _{D ^{Λ y [perpendicular]} , r} .

At CRYPTO 2010, Agrawal et al. [23] presented a new short lattice basis delegation algorithm that keeps the lattice dimension unchanged. Now, we briefly recall the main results in [23].

Definition 3.

Let q be a prime, let m ...5; 6 n l g q , let and σ > m ω ( l g m ) ; _{D m × m} is defined as the distribution on full rank matrices { _{A i} = [ _{a i 1} , _{a i 2} , ... , _{a i m} ] } ∈ ^{Z q m × m} , where _{a i j} ~ _{D ^{Z m} , σ , 0} for all j ∈ [ m ] .

BasisDel ( A , R , _{S A} , σ ) . Let q > 2 , A ∈ ^{R q n × m} , R a matrix (or a product of d matrices) sampled from _{D m × m} , and _{S A} a basis of ^{Λ [perpendicular]} ( A ) ; the algorithm BasisDel ( A , R , _{S A} , σ ) outputs a random basis B for ^{Λ [perpendicular]} ( A ^{R - 1} ) , such that || B ~ || ...4; σ m , where σ ...5; || _{S A} ~ || ^{m d} ω ( l ^{g d + 1} ( m ) ) .

SampleRwithBasis ( A ) . For q > 2 , m > 5 n l g q , and A ∈ ^{R q n × m} , the algorithm SampleRwithBasis ( A ) outputs a random matrix R ~ _{D m × m} and a basis B for ^{Λ [perpendicular]} ( A ^{R - 1} ) , such that || B ~ || ...4; m .

3. Proxy Blind Signature

A proxy blind signature [4, 9-11] is considered to be the combination of proxy signature and blind signature. It consists of four participants: an original signer, a proxy blind signer, a user, and a verifier and the following four algorithms: keygen, generation of the proxy key, proxy signature generation, and verification. A proxy blind signature scheme should satisfy the following requirements.

Distinguishability. Proxy signatures are distinguishable from normal signatures by everyone.

Verifiability. From the proxy signature, the verifier can be convinced of the original signers agreement on the signed message.

Strong Nonforgeability. A designated proxy signer can create a valid proxy signature for the original signer. But the original signer and other third parties who are not designated as a proxy signer cannot create a valid proxy signature.

Strong Identifiability. Anyone can determine the identity of the corresponding proxy signer from the proxy signature.

Strong Nondeniability. Once a proxy signer creates a valid proxy signature of an original signer, he/she cannot repudiate the signature creation.

Prevention of Misuse. The proxy signer cannot use the proxy key for purposes other than generating a valid proxy signature. That is, he/she cannot sign messages that have not been authorized by the original signer.

Blindness Property. A signer cannot distinguish, except with negligible probability, the order in which he/she issued signatures.

4. A Lattice-Based Identity-Based Proxy Blind Signature Scheme in the Standard Model

We introduce our lattice-based identity-based proxy blind signature scheme in the standard model in this section which needs the following parameters.

Let n be a prime number, and m ...5; 2 n l g q , q ...5; β ω ( l g n ) , and β = p o l y ( n ) . A bound L ~ = O ( n l g q ) , the Gaussian parameter σ = L ~ ω ( l g n ) , and a hash function H that outputs matrices in ^{Z q m × m} is [figure omitted; refer to PDF]

The original signer A and the proxy blind signer B have the identity I _{D 1} and the identity I _{D 2} , respectively, and the details are described as follows.

Setup. Given the security parameter n , the PKG runs TrapGen ( ^{1 n} ) to generate a matrix _{A 0} ∈ ^{Z q n × m} and a corresponding short basis _{S 0} of ^{Λ [perpendicular]} ( _{A 0} ) . Let _{S 0} be the master secret key and let _{A 0} be the master public key. The following construction assumes that messages M are arbitrary d -bit strings in { 0,1 ^{} d} , choosing d independent matrices _{C 1} , _{C 2} , ... , _{C d} ∈ ^{Z q n} . Publish the system public parameters P K = Y9; _{A 0} , _{C 1} , _{C 2} , ... , _{C d} YA; and keep the master key _{S 0} secret.

KeyGen. On input of an identity I _{D i} ( i = 1,2 ) , the PKG runs BasisDel ( _{A 0} , H ( I _{D i} ) , _{S 0} , σ ) to generate a private key _{S i} for I _{D i} ( i = 1,2 ) , where _{S i} is a random basis for ^{Λ [perpendicular]} ( _{A 0} ( H ( I _{D i} ) ^{) - 1} ) and || _{S i} ~ || ...4; σ m .

Generation of the Proxy Key. The original signer A chooses the identity I _{D 2} of the proxy signer B and then runs BasisDel ( _{A 0} ( H ( I _{D 1} ) ^{) - 1} , H ( I _{D 2} ) , _{S 1} , σ ) to generate _{S δ} , where _{S δ} is a random basis for ^{Λ [perpendicular]} ( _{A 0} ( H ( I _{D 1} ) ^{) - 1} ( H ( I _{D 2} ) ^{) - 1} ) and || _{S σ} ~ || ...4; σ m . Then the original signer A sends _{S δ} to the proxy signer B as the proxy key.

Proxy Blind Signature. Suppose that M is the message to be signed, and the proxy signer B and the user C compute the signature as follows.

(1) Blinding: the user C chooses uniformly t ∈ D = { t ∈ R |" || t || ...5; 1 / σ } and samples _{t 1} , _{t 2} ~ _{D ^{Z m} , σ} using SampleD , where the distribution of _{A 0} ( H ( I _{D 1} ) ^{) - 1} ( H ( I _{D 2} ) ^{) - 1} _{t 1} and _{A 0} ( H ( I _{D 2} ) ^{) - 1} _{t 2} is uniform over ^{Z q n} . Then computes [figure omitted; refer to PDF]

: At last, he/she sends ( _{μ 1} , _{μ 2} ) to the proxy signer B.

(2) Signing: if ( _{μ 1} , _{μ 2} , ^{e 1 [variant prime]} , ^{e 2 [variant prime]} ) is in the local storage, B outputs ( ^{e 1 [variant prime]} , ^{e 2 [variant prime]} ) ; otherwise, B chooses nonzero vectors as follows: [figure omitted; refer to PDF]

: and then checks up || ^{e 1 [variant prime]} || ...4; σ m and || ^{e 2 [variant prime]} || ...4; σ m , and if not, B chooses ^{e 1 [variant prime]} and ^{e 2 [variant prime]} again, stores ( _{μ 1} , _{μ 2} , ^{e 1 [variant prime]} , ^{e 2 [variant prime]} ) in the local storage, and sends ( ^{e 1 [variant prime]} , ^{e 2 [variant prime]} ) to C.

(3) Unblinding: after receiving ( ^{e 1 [variant prime]} , ^{e 2 [variant prime]} ) , the user C computes [figure omitted; refer to PDF]

: and then he/she outputs ( M , _{e 1} , _{e 2} ) .

Verification. A verifier can accept the proxy blind signature ( M , _{e 1} , _{e 2} ) if and only if:

(1) _{e 1} ...0; 0 , and || _{e 1} || ...4; 2 ^{σ 2} m ;

(2) _{e 2} ...0; 0 , and || _{e 2} || ...4; 2 ^{σ 2} m ;

(3) _{A 0} ( H ( I _{D 1} ) ^{) - 1} ( H ( I _{D 2} ) ^{) - 1} _{e 1} = ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} ;

(4) _{A 0} ( H ( I _{D 2} ) ^{) - 1} _{e 2} = ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} .

5. Analysis of the Proposed Scheme

5.1. Completeness

For the proxy blind signature ( M , _{e 1} , _{e 2} ) , we have

(1) [figure omitted; refer to PDF]

(2) [figure omitted; refer to PDF]

(3) [figure omitted; refer to PDF]

(4) [figure omitted; refer to PDF]

5.2. Analysis of Security

Our proxy blind signature scheme satisfies all the requirements stated in Section 3 based on the hardness assumption of SIS problem and ISIS problem. We proof only blindness property and strong nonforgeability.

Theorem 4 (blindness).

The proxy blind signature scheme above is ( ∞ , 0 ) -blind [15].

Proof.

The proxy signer cannot relate the message M and blinded message ( _{μ 1} , _{μ 2} ) by definition; the statistical distance is [figure omitted; refer to PDF] because _{C 1} , _{C 2} , ... , _{C d} ∈ ^{Z q n} is uniformly random chosen from ^{Z q n} , so prob ( ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} = c ) is ( 1 / 2 ^{) n} . Because _{μ 1} = t ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} + _{A 0} ( H ( I _{D 1} ) ^{) - 1} ( H ( I _{D 2} ) ^{) - 1} _{t 1} and _{t 1} ~ _{D ^{Z m} , σ} , prob ( _{μ 1} = c ) is close to ( 1 / 2 ^{) n} . Thus, Δ ( ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} , _{μ 1} ) is close to 0. Similarly, Δ ( ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} , _{μ 2} ) is close to 0. So the proxy signer cannot relate the message M and blinded message ( _{μ 1} , _{μ 2} ) .

Theorem 5.

The proxy blind signature scheme in this paper is existentially unforgeable under chosen-message attack.

Proof.

If an adversary F breaks existentially unforgeability under chosen-message attack of the proxy blind signature scheme in this paper with probability [straight epsilon] , makes at most _{q e} ( _{q e} > 2 ) extraction queries and _{q s} signature queries, then there is a P P T algorithm T attacking the SIS problem with probability negligibly close to [figure omitted; refer to PDF]

Setup. At first, algorithm T chooses randomly a matrix B in ^{Z q n × m} and generates [figure omitted; refer to PDF] where _{R 1} ~ _{D m × m} , _{T 1} is a basis for ^{Λ [perpendicular]} ( B ^{R 1 - 1} ) , and || _{T 1} ~ || ...4; m . Then, choose _{R 2} ~ _{D m × m} and run BasisDel ( B ^{R 1 - 1} , _{R 2} , _{T 1} , σ ) to generate _{S 0} , where _{S 0} is a random basis for ^{Λ [perpendicular]} ( B ^{R 1 - 1 R 2 - 1} ) . Set _{A 0} = B ^{R 1 - 1 R 2 - 1} , and then let _{S 0} be the master secret key and let _{A 0} be the master public key. Next, sample d nonzero vectors _{E 1} , _{E 2} , ... , _{E d} ~ _{D ^{Z m} , ^{σ 2} / d , 0} , using SampleD ( ^{1 m} ) (if || _{E i} || > ( ^{σ 2} m ) / d , choose _{E i} again for i = 1,2 , ... , d ) and choose _{q e} - 2 independent nonsingular matrices _{R 3} , _{R 4} , ... , _{R q e} ~ _{D m × m} in ^{Z q m × m} . Finally, let _{C i} = B _{E i} for i = 1,2 , ... , d . We know that _{C i} is statistically close to uniform over ^{Z q n} .

Algorithm T sends the system parameters [figure omitted; refer to PDF] to adversary F and keeps the master key _{S 0} secret.

Extraction Queries. When the secret key of the identity I _{D i} is queried for i = 1,2 , ... , _{q e} , algorithm T lets H ( I _{D i} ) = ^{R i - 1} , runs BasisDel ( _{A 0} , H ( I _{D i} ) , _{S 0} , σ ) to generate _{S i} , and stores ( I _{D i} , _{S i} ) and sends _{S i} to the adversary F . (If the secret key was previously queried on I _{D i} , T looks up ( I _{D i} , _{S i} ) in its local storage and returns _{S i} to F .)

Proxy Key Queries. After receiving ( I _{D i} , I _{D j} ) , where I _{D i} is the identity of the original signer and I _{D j} is the identity of the proxy signer, algorithm T returns [figure omitted; refer to PDF] to F . Of course, ^{S δ i , j} is a random basis for [figure omitted; refer to PDF]

Signature Queries. When algorithm T receives ( I _{D i} , I _{D j} , _{μ 1 , M} , _{μ 2 , M} ) , where I _{D i} is the identity of the original signer, I _{D j} is the identity of the proxy signer, and ( _{μ 1 , M} , _{μ 2 , M} ) is the blinded message of M , he/she generates blinded signature ( ^{e 1 , M [variant prime]} , ^{e 2 , M [variant prime]} ) for ( _{μ 1 , M} , _{μ 2 , M} ) (blinded message of M ) as follows.

If ( I _{D i} , I _{D j} , _{μ 1 , M} , _{μ 2 , M} ) was queried previously, T looks up ( I _{D i} , I _{D j} , _{μ 1 , M} , _{μ 2 , M} , ^{e 1 , M [variant prime]} , ^{e 2 , M [variant prime]} ) in its local storage and returns ( ^{e 1 , M [variant prime]} , ^{e 2 , M [variant prime]} ) as the proxy signature to F ; otherwise, T chooses nonzero vectors [figure omitted; refer to PDF] Then T checks up || ^{e 1 , M [variant prime]} || ...4; σ m and || ^{e 2 , M [variant prime]} || ...4; σ m , and if not, it chooses ^{e 1 , M [variant prime]} and ^{e 2 , M [variant prime]} again and then stores ( I _{D i} , I _{D j} , _{μ 1 , M} , _{μ 2 , M} , ^{e 1 , M [variant prime]} , ^{e 2 , M [variant prime]} ) in the local storage and sends ( ^{e 1 , M [variant prime]} , ^{e 2 , M [variant prime]} ) to adversary F .

After receiving ( ^{e 1 , M [variant prime]} , ^{e 2 , M [variant prime]} ) , adversary F removes the blind factor to get the proxy blind signature ( I _{D i} , I _{D j} , M , _{e 1 , M} , _{e 2 , M} ) .

Forgery. Finally, if the adversary F outputs a valid forgery ( I _{D i} , I _{D j} , M , _{e 1 , M} , _{e 2 , M} ) with probability [straight epsilon] , we have

(1) _{e 1 , M} ...0; 0 , and || _{e 1 , M} || ...4; 2 ^{σ 2} m ;

(2) _{e 2 , M} ...0; 0 , and || _{e 2 , M} || ...4; 2 ^{σ 2} m ;

(3) _{A 0} ( H ( I _{D i} ) ^{) - 1} ( H ( I _{D j} ) ^{) - 1} _{e 1 , M} = ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} ;

(4) _{A 0} ( H ( I _{D j} ) ^{) - 1} _{e 2 , M} = ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} .

If i ...0; 2 or j ...0; 1 , we abort. Otherwise, if i = 2 and j = 1 , we have [figure omitted; refer to PDF] Because [figure omitted; refer to PDF] and _{C i} = B _{E i} , we can get B _{e 1 , M} = ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{C i} = ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} B _{E i} = B ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{E i} . Let _{E M} = ^{∑ i = 1 d} ... ( - 1 ^{) M [ i ]} _{E i} , and then B _{e 1 , M} = B _{E M} and || _{E M} || ...4; ^{∑ i = 1 d} ... || _{E i} || ...4; d × ( ^{σ 2} m ) / d = ^{σ 2} m , so [figure omitted; refer to PDF] Thus, T outputs _{e 1 , M} - _{E M} as a solution to the SIS problem with ( q , m , 3 ^{σ 2} m , B ) .

We now analyze the reduction: by the preimage min-entropy property of the hash family, thus the signature _{e 1 , M} = _{E M} with negligible probability ^{2 - ω ( l g m )} . The adversary F outputs the valid forgery ( I _{D i} , I _{D j} , M , _{e 1 , M} , _{e 2 , M} ) with probability [straight epsilon] , and prob ( i = 2 , j = 1 ) = 1 / ^{A _{q e} 2} , so _{e 1 , M} - _{E M} is a solution to the SIS problem with ( q , m , 3 ^{σ 2} m , B ) with probability negligibly close to [figure omitted; refer to PDF]

5.3. Efficiency Analysis

The efficiency of signature scheme is mainly considered to include the length of public keys, secret keys, and signatures. The lattice-based special signature scheme [21, 22] is also provably secure; however, the private keys and the signatures in these schemes are dependent on the identity length of the signer. In contrast, the size of private keys and the size of signature in our scheme are both unchanged and much shorter. Therefore, our scheme is more practical. Table 1 shows the comparison of the schemes.

Table 1: Comparison between schemes [21, 22] and our scheme.

Schemes	[21]	[22]	This work
The length of public keys	3 mn	3 mn	mn + dm
The length of secret keys	5 m 2	5 m 2	m 2
The length of signature	2 m	6 m	2 m

6. Conclusions

In this paper, we have constructed a new lattice-based proxy blind signature scheme with short secret keys and short signatures in the standard model. Our signature scheme is more efficient than other current proxy blind signature schemes, and the security mainly depends on hard problems on lattices, so this scheme in this paper is still secure in quantum computing environment.

Acknowledgments

This work was supported by Scientific Research Project Fund of Science and Technology Bureau of Zhengzhou (no. 20140713) and the project of science and technology office of Henan province (no. 142300410342). The authors gratefully acknowledge the anonymous reviewers for their valuable comments.

Conflict of Interests

The authors declared that they have no conflict of interests regarding this work.

References

[1] D. Chaum, "Blind signat ures for untraceable payments," in Proceedings of CRYPTO 82, pp. 199-203, 1982.

[2] M. Mambo, K. Usuda, E. Okamoto, "Proxy signatures for delegating signing operation," in Proceedings of the 3rd ACM Conference on Computer and Communications Security, pp. 48-56, ACM Press, March 1996.

[3] A. Shamir, "Identity-based cryptosystems and signature schemes," Advances in Cryptology , vol. 196, of Lecture Notes in Computer Science, pp. 47-53, Springer, Berlin, Germany, 1985.

[4] W. D. Lin, J. K. Jan, "A security personal learning tools using a proxy blind signature scheme," in Proceedings of International Conference on Chinese Language Computing, pp. 273-277, Chicago, Ill, USA, 2000.

[5] A. K. Awasthi, S. Lal, "Proxy blind signature scheme," Transaction on Cryptology , vol. 2, no. 1, pp. 5-11, 2005.

[6] H. M. Sun, B. T. Hsieh, S. M. Tseng, "On the security of some proxy blind signature schemes," Journal of Systems and Software , vol. 74, no. 3, pp. 297-302, 2005.

[7] F. Zhang, R. Safavi-Naini, C.-Y. Lin, "New Proxy Signature, Proxy Blind Signature and Proxy Ring Signature Schemes from Bilinear Pairing," Cryptology ePrint Archive, 2003, http://eprint.iacr.org/2003/104

[8] D. Zheng, Z. Huang, K. Chen, W. D. Kou, "Id-based proxy blind signature," in Proceedings of the 18th International Conference on Advanced Information and Applications, vol. 74, pp. 380-383, IEEE Computer Society, 2004.

[9] W. Lang, Z. Yang, Y. Tang, "An identity-bas ed proxy blind signature scheme from bilinear pairings," Asian Journal of Information Technology , vol. 3, no. 10, pp. 839-842, 2004.

[10] Q. Zhang, Q. Wen, G. Chen, "Efficient ID-based proxy blind signature scheme," Wuhan University Journal of Natural Sciences , vol. 12, no. 1, pp. 105-108, 2007.

[11] M. Yang, Y. Wang, "A new efficient ID-based proxy blind signature scheme," Journal of Electronics , vol. 25, no. 2, pp. 226-231, 2008.

[12] M. Ajtai, "Generating hard instances of lattice problems," in Proceedings of the STOC, pp. 99-108, New York, NY, USA, 1996.

[13] O. Regev, "Lattice-based cryptography," Advances in Cryptology (CRYPTO '06) , vol. 4117, of Lecture Notes in Computer Science, pp. 131-141, 2006.

[14] G. Craig, C. Peikert, V. Vaikuntanathan, "Trapdoors for hard lattices and new cryptographic constructions," in Proceedings of the S-TOC, pp. 197-206, 2008.

[15] M. Rückert, "Lattice-based blind signatures," Advances in Cryptology--ASIACRYPT 2010 , vol. 6477, of Lecture Notes in Computer Science, pp. 413-430, Springer, Berlin, Germany, 2010.

[16] S. D. Gordon, J. Katz, V. Vaikuntanathan, "A group signature scheme from lattice assumptions," Advances in Cryptology--ASIACRYPT 2010 , vol. 6477, of Lecture Notes in Computer Science, pp. 395-412, Springer, Berlin, Germany, 2010.

[17] M. R{\"u}ckert, "Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles," Post-Quantum Cryptography , vol. 6061, of Lecture Notes in Computer Science, pp. 182-200, Springer, Berlin, Germany, 2010.

[18] Y. Jiang, F. Kong, X. Ju, "Lattice-based proxy signature," in Proceeding of the International Conference on Computational Intelligence and Security (CIS '10), pp. 382-385, Nanning, China, December 2010.

[19] M. Tian, L. Huang, "Breaking a proxy signature scheme from lattices," International Journal of Network Security , vol. 14, no. 6, pp. 320-323, 2012.

[20] D. Cash, D. Hofheinz, E. Kiltz, C. Peikert, "Bonsai trees, or how to delegate a lattice basis," Advances in Cryptology--EUROCRYPT 2010LNCS , vol. 6110, of Lecture Notes in Computer Science, pp. 523-552, 2010.

[21] L. L. Zhang, Y. Sang, "A lattice-based identity-based proxy signature from bonsai trees," International Journal of Advancements in Computing Technology , vol. 4, no. 20, pp. 99-104, 2012.

[22] F. Xia, B. Yang, S. Ma, H. Sun, M. Zhang, "Lattice-based proxy signature scheme," Journal of Hunan University , vol. 38, no. 6, pp. 84-88, 2011.

[23] S. Agrawal, D. Boneh, X. Boyen, "Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE," Advances in Cryptology--{CRYPTO} 2010 , vol. 6223, of Lecture Notes in Computer Science, pp. 98-115, Springer, Berlin, Germany, 2010.