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

Authors: Lili Zhang; Yanqin Ma
Journal: Mathematical Problems in Engineering
 (2014)

---

## 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.


---

## Body

## 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, Section3 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

LetB
=
[
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
(1)
Λ
(
B
)
=
{
B
c
=
∑
i
=
1
n
‍
b
i
c
i
∣
c
∈
Z
n
}
,
here B is called a basis of the lattice Λ
⊥
(
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:
(2)
λ
1
(
Λ
)
=
min
⁡
x
∈
Λ
⁡
∥
x
∥
.We define the orthogonal latticeΛ
⊥
(
B
) as
(3)
Λ
⊥
(
B
)
=
{
e
∈
R
m
∣
B
e
=
0
mod
⁡
q
,
B
∈
R
q
n
×
m
}
.


### 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 Euclideanl
2 norm)).
Given an integerq, 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
≤
β.Definition 2 (the inhomogeneous small integer solution problem (ISIS) (in the Euclideanl
2 norm)).
Give an integerq, 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
≤
β.


### 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
→
R
n, with f
A
(
e
)
=
A
e, where D
n
=
{
e
∈
Z
m
∣
∥
e
∥
≤
r
m
} and R
n
=
Z
q
n. The input distribution is D
Z
m
,
r, and a short basis for Λ
⊥
(
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, andSamplePre), which will be used as building blocks in our signature scheme.The following functions take the Gaussian smoothing parameterr
≥
∥
B
~
∥
·
ω
(
l
g
m
) as a parameter.TrapGen
(
1
n
)
. Let n
,
q, and m be integers with q
≥
2, m
≥
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 Λ
⊥
(
A
), such that ∥
B
~
∥
≤
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 Λ
⊥
(
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
⊥
,
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.
Letq be a prime, let m
≥
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 Λ
⊥
(
A
); the algorithm BasisDel (A
,
R
,
S
A
,
σ) outputs a random basis B for Λ
⊥
(
A
R
-
1
), such that ∥
B
~
∥
≤
σ
m, where σ
≥
∥
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 Λ
⊥
(
A
R
-
1
), such that ∥
B
~
∥
≤
m.


## 2.1. Lattice

LetB
=
[
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
(1)
Λ
(
B
)
=
{
B
c
=
∑
i
=
1
n
‍
b
i
c
i
∣
c
∈
Z
n
}
,
here B is called a basis of the lattice Λ
⊥
(
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:
(2)
λ
1
(
Λ
)
=
min
⁡
x
∈
Λ
⁡
∥
x
∥
.We define the orthogonal latticeΛ
⊥
(
B
) as
(3)
Λ
⊥
(
B
)
=
{
e
∈
R
m
∣
B
e
=
0
mod
⁡
q
,
B
∈
R
q
n
×
m
}
.


## 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 Euclideanl
2 norm)).
Given an integerq, 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
≤
β.Definition 2 (the inhomogeneous small integer solution problem (ISIS) (in the Euclideanl
2 norm)).
Give an integerq, 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
≤
β.


## 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
→
R
n, with f
A
(
e
)
=
A
e, where D
n
=
{
e
∈
Z
m
∣
∥
e
∥
≤
r
m
} and R
n
=
Z
q
n. The input distribution is D
Z
m
,
r, and a short basis for Λ
⊥
(
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, andSamplePre), which will be used as building blocks in our signature scheme.The following functions take the Gaussian smoothing parameterr
≥
∥
B
~
∥
·
ω
(
l
g
m
) as a parameter.TrapGen
(
1
n
)
. Let n
,
q, and m be integers with q
≥
2, m
≥
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 Λ
⊥
(
A
), such that ∥
B
~
∥
≤
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 Λ
⊥
(
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
⊥
,
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.
Letq be a prime, let m
≥
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 Λ
⊥
(
A
); the algorithm BasisDel (A
,
R
,
S
A
,
σ) outputs a random basis B for Λ
⊥
(
A
R
-
1
), such that ∥
B
~
∥
≤
σ
m, where σ
≥
∥
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 Λ
⊥
(
A
R
-
1
), such that ∥
B
~
∥
≤
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.Letn be a prime number, and m
≥
2
n
l
g
q, q
≥
β
ω
(
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
(4)
H
:
{
0,1
}
*
⟶
Z
q
m
×
m
,
H
(
ID
)
~
D
m
×
m
.The original signer A and the proxy blind signer B have the identityI
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 Λ
⊥
(
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
=
〈
A
0
,
C
1
,
C
2
,
…
,
C
d
〉 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 Λ
⊥
(
A
0
(
H
(
I
D
i
)
)
-
1
) and ∥
S
i
~
∥
≤
σ
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 Λ
⊥
(
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
) and ∥
S
σ
~
∥
≤
σ
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 uniformlyt
∈
D
=
{
t
∈
R
∣
∥
t
∥
≥
1
/
σ
} and samples t
1
,
t
2
~
D
Z
m
,
σ usingSampleD, 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
(5)
μ
1
=
t
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
+
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
t
1
;
(6)
μ
2
=
t
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
+
A
0
(
H
(
I
D
2
)
)
-
1
t
2
.
At last, he/she sends(
μ
1
,
μ
2
) to the proxy signer B.
(2)
Signing: if(
μ
1
,
μ
2
,
e
1
′
,
e
2
′
) is in the local storage, B outputs (
e
1
′
,
e
2
′
); otherwise, B chooses nonzero vectors as follows:
(7)
e
1
′
⟵
SamplePre
(
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
,
S
δ
,
μ
1
,
σ
)
,
e
2
′
⟵
SamplePre
(
A
0
(
H
(
I
D
2
)
)
-
1
,
S
2
,
μ
2
,
σ
)
,
and then checks up∥
e
1
′
∥
≤
σ
m and ∥
e
2
′
∥
≤
σ
m, and if not, B chooses e
1
′ and e
2
′ again, stores (
μ
1
,
μ
2
,
e
1
′
,
e
2
′
) in the local storage, and sends (
e
1
′
,
e
2
′
) to C.
(3)
Unblinding: after receiving(
e
1
′
,
e
2
′
), the user C computes
(8)
e
1
=
t
-
1
(
e
1
′
-
t
1
)
,
e
2
=
t
-
1
(
e
2
′
-
t
2
)
,
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, and ∥
e
1
∥
≤
2
σ
2
m;
(2)
e
2
≠
0, and ∥
e
2
∥
≤
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)
(9)
∥
e
1
∥
=
∥
t
-
1
(
e
1
′
-
t
1
)
∥
=
(
1
|
t
|
)
∥
(
e
1
′
-
t
1
)
∥
≤
σ
(
∥
e
1
′
∥
+
∥
t
1
∥
)
≤
σ
×
(
2
σ
m
)
=
2
σ
2
m
,
(2)
(10)
∥
e
2
∥
=
∥
t
-
1
(
e
2
′
-
t
2
)
∥
=
(
1
|
t
|
)
∥
(
e
2
′
-
t
2
)
∥
≤
σ
(
∥
e
2
′
∥
+
∥
t
2
∥
)
≤
σ
×
(
2
σ
m
)
=
2
σ
2
m
,
(3)
(11)
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
e
1
=
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
[
t
-
1
(
e
1
′
-
t
1
)
]
=
t
-
1
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
(
e
1
′
-
t
1
)
=
t
-
1
[
μ
1
-
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
t
1
]
=
t
-
1
[
t
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
]
=
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
,
(4)
(12)
A
0
(
H
(
I
D
2
)
)
-
1
e
2
=
A
0
(
H
(
I
D
2
)
)
-
1
[
t
-
1
(
e
2
′
-
t
2
)
]
=
t
-
1
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
(
e
2
′
-
t
2
)
=
t
-
1
[
μ
2
-
A
0
(
H
(
I
D
2
)
)
-
1
t
2
]
=
t
-
1
[
t
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
]
=
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
.


### 5.2. Analysis of Security

Our proxy blind signature scheme satisfies all the requirements stated in Section3 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 messageM and blinded message (
μ
1
,
μ
2
) by definition; the statistical distance is
(13)
Δ
(
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
,
μ
1
)
=
1
2
∑
c
∈
Z
q
n
‍
|
prob
(
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
=
c
)
-
prob
(
μ
1
=
c
)
|
,
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 adversaryF breaks existentially unforgeability under chosen-message attack of the proxy blind signature scheme in this paper with probability ε, 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
(14)
(
1
-
2
-
ω
(
l
g
m
)
)
(
1
-
1
A
q
e
2
)
ε
.Setup. At first, algorithm T chooses randomly a matrix B in Z
q
n
×
m and generates
(15)
(
R
1
,
T
1
)
⟵
SampleRwithBasis
(
B
)
,
where R
1
~
D
m
×
m, T
1 is a basis for Λ
⊥
(
B
R
1
-
1
), and ∥
T
1
~
∥
≤
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 Λ
⊥
(
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.AlgorithmT sends the system parameters
(16)
P
K
=
〈
A
0
,
C
1
,
C
2
,
…
,
C
d
〉
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
(17)
S
δ
i
,
j
⟵
BasisDel
(
A
0
(
H
(
I
D
i
)
)
-
1
,
(
H
(
I
D
j
)
)
,
S
i
,
σ
)
to F. Of course, S
δ
i
,
j is a random basis for
(18)
Λ
⊥
(
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
)
=
Λ
⊥
(
A
0
R
i
R
j
)
.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
′
,
e
2
,
M
′
) 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
′
,
e
2
,
M
′
) in its local storage and returns (
e
1
,
M
′
,
e
2
,
M
′
) as the proxy signature to F; otherwise, T chooses nonzero vectors
(19)
e
1
,
M
′
⟵
SamplePre
(
A
0
H
(
I
D
i
)
-
1
H
(
I
D
j
)
-
1
,
S
δ
i
,
j
,
μ
1
,
M
,
σ
)
,
e
2
,
M
′
⟵
SamplePre
(
A
0
H
(
I
D
j
)
-
1
,
S
j
,
μ
2
,
M
,
σ
)
.
Then T checks up ∥
e
1
,
M
′
∥
≤
σ
m and ∥
e
2
,
M
′
∥
≤
σ
m, and if not, it chooses e
1
,
M
′ and e
2
,
M
′ again and then stores (
I
D
i
,
I
D
j
,
μ
1
,
M
,
μ
2
,
M
,
e
1
,
M
′
,
e
2
,
M
′
) in the local storage and sends (
e
1
,
M
′
,
e
2
,
M
′
) to adversary F.After receiving(
e
1
,
M
′
,
e
2
,
M
′
), 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 ε, we have(1)
e
1
,
M
≠
0, and ∥
e
1
,
M
∥
≤
2
σ
2
m;
(2)
e
2
,
M
≠
0, and ∥
e
2
,
M
∥
≤
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.Ifi
≠
2 or j
≠
1, we abort. Otherwise, if i
=
2 and j
=
1, we have
(20)
A
0
(
H
(
I
D
i
)
)
-
1
(
H
(
I
D
j
)
)
-
1
=
B
R
1
-
1
R
2
-
1
R
2
R
1
=
B
.
Because
(21)
A
0
(
H
(
I
D
i
)
)
-
1
(
H
(
I
D
j
)
)
-
1
e
1
,
M
=
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
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
∥
≤
∑
i
=
1
d
‍
∥
E
i
∥
≤
d
×
(
σ
2
m
)
/
d
=
σ
2
m, so
(22)
B
(
e
1
,
M
-
E
M
)
=
0
mod
⁡
q
,
∥
e
1
,
M
-
E
M
∥
≤
∥
e
1
,
M
∥
+
∥
E
M
∥
≤
2
σ
2
m
+
σ
2
m
=
3
σ
2
m
.
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 signaturee
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 ε, 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
(23)
(
1
-
2
-
ω
(
l
g
m
)
)
(
1
-
1
A
q
e
2
)
ε
.


### 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


## 5.1. Completeness

For the proxy blind signature(
M
,
e
1
,
e
2
), we have(1)
(9)
∥
e
1
∥
=
∥
t
-
1
(
e
1
′
-
t
1
)
∥
=
(
1
|
t
|
)
∥
(
e
1
′
-
t
1
)
∥
≤
σ
(
∥
e
1
′
∥
+
∥
t
1
∥
)
≤
σ
×
(
2
σ
m
)
=
2
σ
2
m
,
(2)
(10)
∥
e
2
∥
=
∥
t
-
1
(
e
2
′
-
t
2
)
∥
=
(
1
|
t
|
)
∥
(
e
2
′
-
t
2
)
∥
≤
σ
(
∥
e
2
′
∥
+
∥
t
2
∥
)
≤
σ
×
(
2
σ
m
)
=
2
σ
2
m
,
(3)
(11)
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
e
1
=
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
[
t
-
1
(
e
1
′
-
t
1
)
]
=
t
-
1
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
(
e
1
′
-
t
1
)
=
t
-
1
[
μ
1
-
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
t
1
]
=
t
-
1
[
t
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
]
=
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
,
(4)
(12)
A
0
(
H
(
I
D
2
)
)
-
1
e
2
=
A
0
(
H
(
I
D
2
)
)
-
1
[
t
-
1
(
e
2
′
-
t
2
)
]
=
t
-
1
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
(
e
2
′
-
t
2
)
=
t
-
1
[
μ
2
-
A
0
(
H
(
I
D
2
)
)
-
1
t
2
]
=
t
-
1
[
t
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
]
=
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
.


## 5.2. Analysis of Security

Our proxy blind signature scheme satisfies all the requirements stated in Section3 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 messageM and blinded message (
μ
1
,
μ
2
) by definition; the statistical distance is
(13)
Δ
(
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
,
μ
1
)
=
1
2
∑
c
∈
Z
q
n
‍
|
prob
(
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
=
c
)
-
prob
(
μ
1
=
c
)
|
,
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 adversaryF breaks existentially unforgeability under chosen-message attack of the proxy blind signature scheme in this paper with probability ε, 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
(14)
(
1
-
2
-
ω
(
l
g
m
)
)
(
1
-
1
A
q
e
2
)
ε
.Setup. At first, algorithm T chooses randomly a matrix B in Z
q
n
×
m and generates
(15)
(
R
1
,
T
1
)
⟵
SampleRwithBasis
(
B
)
,
where R
1
~
D
m
×
m, T
1 is a basis for Λ
⊥
(
B
R
1
-
1
), and ∥
T
1
~
∥
≤
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 Λ
⊥
(
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.AlgorithmT sends the system parameters
(16)
P
K
=
〈
A
0
,
C
1
,
C
2
,
…
,
C
d
〉
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
(17)
S
δ
i
,
j
⟵
BasisDel
(
A
0
(
H
(
I
D
i
)
)
-
1
,
(
H
(
I
D
j
)
)
,
S
i
,
σ
)
to F. Of course, S
δ
i
,
j is a random basis for
(18)
Λ
⊥
(
A
0
(
H
(
I
D
1
)
)
-
1
(
H
(
I
D
2
)
)
-
1
)
=
Λ
⊥
(
A
0
R
i
R
j
)
.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
′
,
e
2
,
M
′
) 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
′
,
e
2
,
M
′
) in its local storage and returns (
e
1
,
M
′
,
e
2
,
M
′
) as the proxy signature to F; otherwise, T chooses nonzero vectors
(19)
e
1
,
M
′
⟵
SamplePre
(
A
0
H
(
I
D
i
)
-
1
H
(
I
D
j
)
-
1
,
S
δ
i
,
j
,
μ
1
,
M
,
σ
)
,
e
2
,
M
′
⟵
SamplePre
(
A
0
H
(
I
D
j
)
-
1
,
S
j
,
μ
2
,
M
,
σ
)
.
Then T checks up ∥
e
1
,
M
′
∥
≤
σ
m and ∥
e
2
,
M
′
∥
≤
σ
m, and if not, it chooses e
1
,
M
′ and e
2
,
M
′ again and then stores (
I
D
i
,
I
D
j
,
μ
1
,
M
,
μ
2
,
M
,
e
1
,
M
′
,
e
2
,
M
′
) in the local storage and sends (
e
1
,
M
′
,
e
2
,
M
′
) to adversary F.After receiving(
e
1
,
M
′
,
e
2
,
M
′
), 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 ε, we have(1)
e
1
,
M
≠
0, and ∥
e
1
,
M
∥
≤
2
σ
2
m;
(2)
e
2
,
M
≠
0, and ∥
e
2
,
M
∥
≤
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.Ifi
≠
2 or j
≠
1, we abort. Otherwise, if i
=
2 and j
=
1, we have
(20)
A
0
(
H
(
I
D
i
)
)
-
1
(
H
(
I
D
j
)
)
-
1
=
B
R
1
-
1
R
2
-
1
R
2
R
1
=
B
.
Because
(21)
A
0
(
H
(
I
D
i
)
)
-
1
(
H
(
I
D
j
)
)
-
1
e
1
,
M
=
∑
i
=
1
d
‍
(
-
1
)
M
[
i
]
C
i
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
∥
≤
∑
i
=
1
d
‍
∥
E
i
∥
≤
d
×
(
σ
2
m
)
/
d
=
σ
2
m, so
(22)
B
(
e
1
,
M
-
E
M
)
=
0
mod
⁡
q
,
∥
e
1
,
M
-
E
M
∥
≤
∥
e
1
,
M
∥
+
∥
E
M
∥
≤
2
σ
2
m
+
σ
2
m
=
3
σ
2
m
.
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 signaturee
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 ε, 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
(23)
(
1
-
2
-
ω
(
l
g
m
)
)
(
1
-
1
A
q
e
2
)
ε
.


## 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.



---

*Source: 307637-2014-09-25.xml*