# An Efficient Identity-Based Proxy Blind Signature for Semioffline Services

Authors: Hongfei Zhu; Yu-an Tan; Liehuang Zhu; Quanxin Zhang; Yuanzhang Li
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Fog computing extends the cloud computing to the network edge and allows deploying a new type of semioffline services, which can provide real-time transactions between two entities, while the central cloud server is offline and network edge devices are online. For an e-payment system and e-voting with such feature, proxy blind signature is a cornerstone to protect users’ privacy. However, the signature based on number theorem, such as hard mathematical problems on factoring problem, discrete logarithm problem, and bilinear pairings, cannot defeat quantum computers attack. Meanwhile, these schemes need to depend on complex public key infrastructure. Thus, we construct an identity-based proxy blind signature scheme based on number theorem research unit lattice, which can defeat quantum computers attack and does not need to depend on public key infrastructure. The security of the proposed scheme is dependent on Ring-Small Integer Solution problem over number theorem research unit lattice. The proposed scheme meets the properties of blind signature and proxy signature. Then we compare the proposed scheme with other existing proxy blind signature schemes; the result shows that the proposed scheme outperforms ZM scheme except in proxy signer’s signature size and can be more secure than TA scheme and MMHP scheme.


---

## Body

## 1. Introduction

Fog computing was initially introduced by Cisco, which can overcome cloud computing’s disadvantages, such as non-real-time service and long delay [1–3]. More specifically, fog computing adds a new layer between cloud server and terminal user [4, 5]; that is, fog servers can be access point, base station, router, or mobile equipment [6–9]. Thus, the semioffline e-payment system can be deployed by utilizing the advantages of fog computing model [10, 11].In order to defend user’s privacy in offline e-payment system, blind signature (BS) is crucial for that it never permits signer to sign on a plaintext before knowing its content [12]. Therefore, BS can protect user privacy during the transactions [13] instead of encrypting the data and searching on the ciphertext [14]. However, this system is deployed in real environment; it will use distributed architecture [15]. The original signer should authorize an agent to sign for himself. Then a proxy signature (PS) should be used in e-payment system, since proxy signer can satisfy this requirement [16]. Combining those two types of schemes together, a new proxy blind signature (PBS) was proposed, which meets the properties of those two signature schemes. After that, many PBS schemes were constructed by scholars.However, most of the PBS schemes are based on number theory, such as discrete logarithm problem (DLP) and bilinear pairings. These schemes are considered to be insecure to resist the quantum computer attack. Therefore, the e-payment and e-voting systems in the cloud still face the threat from quantum computer attack [17]. Meanwhile, these schemes need to rely on complex public key infrastructure (PKI) [18, 19]. In conclusion, these schemes based on number theorem cannot defeat the quantum computers attack according to the recent research results.Therefore, the lattice-based PBS schemes become one alternative solution, since they are sufficient enough and able to resist quantum computer attack [20, 21]. Besides, if lattice-based PBS schemes can combine with identity-based cryptography (called IDPBS), they can overcome the shortcomings of traditional PBS schemes, such as relying on complex PKI [22]. Meanwhile, they can transfer less data than biological recognition methods during the transactions [23, 24].Zhu et al. presented a new lattice-based BS [20], which can be secure enough for cloud services. However, this scheme has to be combined with proxy signature in practice. Combining BS scheme and IDPS scheme, we initially present an IDPBS on number theorem research unit lattice (IDPBS-NTRU), which can defeat quantum computer attack.(1) Inspired by [25], a new IDPBS-NTRU scheme is proposed based on NTRU lattice, which can make semioffline e-payment and e-voting systems deployed in fog computing model secure enough to resist quantum computer attack.(2) The proposed IDPBS-NTRU scheme is proven to be secure. That is, the proposed scheme is correct, blind, unforgeable, verifiable, strong identifiable, strong undeniable, and key-dependent.(3) The proposed IDPBS-NTRU is compared with the existing IDPBS schemes in terms of performances. The result shows that it outperforms the ZM scheme except in proxy signer’s signing key size, and it is more secure than TA and MMHP schemes.The paper is introduced as follows. Section2 introduces the background knowledge about NTRU lattice and main key technology. Section 3 introduces the security model for IDPBS. Section 4 shows that the proposed IDPBS is proven to be secure and it is compared with other IDPBS schemes in terms of performances. At last, Section 5 draws the conclusions.


## 2. Related Works

IDPBS Schemes Based on DLP. In 2011, Beura et al. proposed a new proxy blind signature based on DLP; their scheme satisfies the properties of blind signature and proxy signature. This scheme is more secure and efficient than factoring signature schemes [26]. To improve the efficiency, Tan et al. introduced a couple of PBS schemes; both of them were constructed on Schnorr blind signature. However, Sun et al. pointed that both of them were not unforgeable and unlinkable [27]. However, in 2014, Wang and Liao proved that the schemes proposed by Oo et al. and Beura et al. did not satisfy unlinkability [28]. In 2013, Tan proposed a PBS based on DLP, which did not depend on PKI [29] and was proven to be secure in the random oracle [30]. However, most of these schemes are dependent on PKI and are not strictly proven to be secure.IDPBS Schemes Based on Bilinear Pairings. In 2003, Zhang et al. proposed a new proxy blind signature based on bilinear pairings, which satisfies distinguishability, verifiability, strong nonforgeability, strong identifiability, strong nondeniability, and prevention of misuse. Meanwhile, this scheme did not depend on public key infrastructure (PKI) [31]. Later, Li et al. introduced a new PBS, which was also constructed on bilinear pairings; it was independent of PKI [32]. However, these schemes are inefficient and are not proven to be secure.IDPBS Schemes Based on Lattice. In 2014, Zhang and Ma initially proposed a proxy blind signature on lattice; it does not need to depend on PKI; its security is based on short integer solution problem. However, this scheme is still inefficient. [33].


## 3. Preliminaries

In the beginning, we will define the denotations that will be used all over the paper in Denotations.


### 3.1. NTRU Lattice and Rejection Sampling on Lattice

Definition 1 (NTRU lattice).
The notations are defined asf, g
∈
R and h
=
g
f
-
1 mod q; after that, the NTRU lattice can be defined as L
h
,
q
=
u
,
v
∈
R
2
:
u
+
v
h
=
0
mod
q. That is, L
h
,
q is on behalf of a R
2
N full-rank lattice whose basis is -
T
N
(
h
)
I
N
q
I
N
O
N, I
N denotes a unit matrix, O
N denotes a null matrix, and T
N
h denotes an anticirculant matrix h
0
h
1
⋯
h
N
-
1
-
h
N
-
1
h
0
⋯
h
N
-
2
⋮
⋮
⋮
⋮
-
h
1
-
h
2
⋯
h
0.Definition 2 (R-S
I
S
q
,
1,2
,
β
κ on NTRU lattice).
Smallf and  g can be sampled from D
Z
N
,
σ (f
,
g
mod
q
∈
R
q
×); then L
h
,
q
=
h
,
1
∈
R
q
1
×
2 and h
=
g
f
-
1 can be obtained by using Algorithm  3 in [25]. Therefore, R-SIS on NTRU means finding z
1
,
z
2 satisfying L
h
,
q
z
1
,
z
2
T
=
0 mod q and z
1
,
z
2
≤
β.Theorem 3 (rejection sampling theorem).
V denotes one subset of Z
m, the norms of V’s elements are less than constant T, σ
=
ω
(
T
log
⁡
m
)
∈
R, (M is invariable), and h
:
V
→
R is a probability distribution. Two algorithms are as follows: One is(1)
v
⟵
h
;
w
⟵
D
v
,
σ
N
;
get
w
,
v
with probability
min
⁡
D
σ
N
w
M
D
v
,
σ
N
w
,
1
.The other is(2)
v
⟵
h
;
w
⟵
D
σ
N
;
get
w
,
v
with probability
1
M
.
Then the distribution of first algorithm will not exceed the second one’s statistical distance2
-
ω
(
log
⁡
N
)
/
M. Moreover, The first one will export something with probability at least 1
-
2
-
ω
log
⁡
N
/
M.


### 3.2. The Definitions of IDPBS Scheme

An IDPBS consists of seven algorithms(
S
T
ε
,
K
E
ε
,
D
G
ε
,
B
S
ε
,
P
S
ε
,
U
B
ε
,
P
V
ε
) [12, 36, 37]. TTP will execute S
T
ε
1
N to produce public parameters and keys [29, 38, 39]. The formal definition is presented as follows (Algorithm 1):(i)
S
T
ε
(
1
n
) outputs p
a
r
a
m
s and m
k
=
(
m
s
k
,
m
p
k
).
(ii)
K
E
ε
(
p
a
r
a
m
s
,
m
s
k
,
i
d
i
) outputs s
k
i
d
i for O and P (i
=
O or P).
(iii)
D
G
ε
(
i
d
O
,
s
k
i
d
O
,
w
) outputs ψ for P.
(iv)
Proxy blind signature:U interacts with P according to the following protocol:
(1)
B
S
(
m
,
f
): U blinds m to m
′ by using f and then sends m
′ to P.
(2)
P
S
ε
(
m
′
,
i
d
P
,
s
k
P
,
i
d
O
,
ψ
): P signs on m
′ using s
k
i
d
P and sends the signature σ
′ to U.
(3)
U
B
(
σ
′
,
f
): U unblinds σ
′ by using f and outputs the blind signature σ.
(v)
P
V
ε
(
i
d
O
,
i
d
P
,
w
,
m
,
ψ
,
σ
): if ψ
,
σ are valid, the algorithm outputs true. Otherwise it outputs false.Algorithm 1:General IDPBS scheme.
S
e
t
u
p
:
S
T
ε
(
1
N
)
→
(
p
a
r
a
m
s
,
m
k
)
K
e
y
E
x
t
r
a
c
t
i
o
n
:
K
E
ε
(
p
a
r
a
m
s
,
m
k
,
i
d
i
)
→
s
k
i
d
i, i
=
O
,
P
D
e
l
e
g
a
t
i
o
n
G
e
n
e
r
a
t
i
o
n
:
D
G
ε
(
i
d
O
,
s
k
i
d
O
,
ω
)
→
ψ
→
ψ
proxy signer P
Blind (user):
B
S
ε
(
m
,
f
)
→
m
′
→
m
′
Proxy Signature (proxy signer):
P
S
ε
(
m
′
,
i
d
P
,
s
k
P
,
i
d
O
,
ψ
)
→
σ
′
←
σ
′
Unblind (user):
U
B
(
σ
′
,
f
)
→
σ
Proxy Verify:
P
V
ε
(
i
d
O
,
i
d
P
,
ω
,
m
,
ψ
,
σ
)
→
t
r
u
e
/
f
a
l
s
eAn IDPBS scheme should meet the following six properties. The details can be seen in [20, 33, 40–42].(1) Blindness. P
∗ are denoted as an adversary who can control the proxy signer. P
∗ chooses two messages m
0 and m
1. Then a random bit i
∈
{
0,1
} is chosen in the game. m
0 and m
1 are randomly denoted as m
i and m
1
-
i. These two messages are, respectively, used as two user’s inputs. After that, P
∗ will adaptively and parallelly interact with two honest users according to the signature protocol. Finally, two users output σ
i and σ
1
-
i respectively. Then σ
i and σ
1
-
i ordered by m
i and m
1
-
i are delivered to P
∗; after that, P
∗ will output i
′
∈
{
0,1
}.(2) One More Unforgeability.
P can generate a legal proxy σ instead of O. However, O and all the other entities fail to generate a legal signature. The game is presented as follows [33]: A
d
v
U
∗, the advantage of U
∗, is denoted as success probability in Algorithm 3. If no adversary can win Algorithm 3 at minimum with negligible probability η in time t, then it satisfies one more unforgeability [31].(3) Verifiability.
V can check whether σ is delegated by O.(4) Strong Identifiability. Any V can determine P’s identity once he receives the proxy signature tuple.(5) Strong Undeniability.
P cannot refuse to admit it once he creates the proxy signature σ.(6) Key Dependence.
P can sign on a message if and only if he has the authorization from O.


## 3.1. NTRU Lattice and Rejection Sampling on Lattice

Definition 1 (NTRU lattice).
The notations are defined asf, g
∈
R and h
=
g
f
-
1 mod q; after that, the NTRU lattice can be defined as L
h
,
q
=
u
,
v
∈
R
2
:
u
+
v
h
=
0
mod
q. That is, L
h
,
q is on behalf of a R
2
N full-rank lattice whose basis is -
T
N
(
h
)
I
N
q
I
N
O
N, I
N denotes a unit matrix, O
N denotes a null matrix, and T
N
h denotes an anticirculant matrix h
0
h
1
⋯
h
N
-
1
-
h
N
-
1
h
0
⋯
h
N
-
2
⋮
⋮
⋮
⋮
-
h
1
-
h
2
⋯
h
0.Definition 2 (R-S
I
S
q
,
1,2
,
β
κ on NTRU lattice).
Smallf and  g can be sampled from D
Z
N
,
σ (f
,
g
mod
q
∈
R
q
×); then L
h
,
q
=
h
,
1
∈
R
q
1
×
2 and h
=
g
f
-
1 can be obtained by using Algorithm  3 in [25]. Therefore, R-SIS on NTRU means finding z
1
,
z
2 satisfying L
h
,
q
z
1
,
z
2
T
=
0 mod q and z
1
,
z
2
≤
β.Theorem 3 (rejection sampling theorem).
V denotes one subset of Z
m, the norms of V’s elements are less than constant T, σ
=
ω
(
T
log
⁡
m
)
∈
R, (M is invariable), and h
:
V
→
R is a probability distribution. Two algorithms are as follows: One is(1)
v
⟵
h
;
w
⟵
D
v
,
σ
N
;
get
w
,
v
with probability
min
⁡
D
σ
N
w
M
D
v
,
σ
N
w
,
1
.The other is(2)
v
⟵
h
;
w
⟵
D
σ
N
;
get
w
,
v
with probability
1
M
.
Then the distribution of first algorithm will not exceed the second one’s statistical distance2
-
ω
(
log
⁡
N
)
/
M. Moreover, The first one will export something with probability at least 1
-
2
-
ω
log
⁡
N
/
M.


## 3.2. The Definitions of IDPBS Scheme

An IDPBS consists of seven algorithms(
S
T
ε
,
K
E
ε
,
D
G
ε
,
B
S
ε
,
P
S
ε
,
U
B
ε
,
P
V
ε
) [12, 36, 37]. TTP will execute S
T
ε
1
N to produce public parameters and keys [29, 38, 39]. The formal definition is presented as follows (Algorithm 1):(i)
S
T
ε
(
1
n
) outputs p
a
r
a
m
s and m
k
=
(
m
s
k
,
m
p
k
).
(ii)
K
E
ε
(
p
a
r
a
m
s
,
m
s
k
,
i
d
i
) outputs s
k
i
d
i for O and P (i
=
O or P).
(iii)
D
G
ε
(
i
d
O
,
s
k
i
d
O
,
w
) outputs ψ for P.
(iv)
Proxy blind signature:U interacts with P according to the following protocol:
(1)
B
S
(
m
,
f
): U blinds m to m
′ by using f and then sends m
′ to P.
(2)
P
S
ε
(
m
′
,
i
d
P
,
s
k
P
,
i
d
O
,
ψ
): P signs on m
′ using s
k
i
d
P and sends the signature σ
′ to U.
(3)
U
B
(
σ
′
,
f
): U unblinds σ
′ by using f and outputs the blind signature σ.
(v)
P
V
ε
(
i
d
O
,
i
d
P
,
w
,
m
,
ψ
,
σ
): if ψ
,
σ are valid, the algorithm outputs true. Otherwise it outputs false.Algorithm 1:General IDPBS scheme.
S
e
t
u
p
:
S
T
ε
(
1
N
)
→
(
p
a
r
a
m
s
,
m
k
)
K
e
y
E
x
t
r
a
c
t
i
o
n
:
K
E
ε
(
p
a
r
a
m
s
,
m
k
,
i
d
i
)
→
s
k
i
d
i, i
=
O
,
P
D
e
l
e
g
a
t
i
o
n
G
e
n
e
r
a
t
i
o
n
:
D
G
ε
(
i
d
O
,
s
k
i
d
O
,
ω
)
→
ψ
→
ψ
proxy signer P
Blind (user):
B
S
ε
(
m
,
f
)
→
m
′
→
m
′
Proxy Signature (proxy signer):
P
S
ε
(
m
′
,
i
d
P
,
s
k
P
,
i
d
O
,
ψ
)
→
σ
′
←
σ
′
Unblind (user):
U
B
(
σ
′
,
f
)
→
σ
Proxy Verify:
P
V
ε
(
i
d
O
,
i
d
P
,
ω
,
m
,
ψ
,
σ
)
→
t
r
u
e
/
f
a
l
s
eAn IDPBS scheme should meet the following six properties. The details can be seen in [20, 33, 40–42].(1) Blindness. P
∗ are denoted as an adversary who can control the proxy signer. P
∗ chooses two messages m
0 and m
1. Then a random bit i
∈
{
0,1
} is chosen in the game. m
0 and m
1 are randomly denoted as m
i and m
1
-
i. These two messages are, respectively, used as two user’s inputs. After that, P
∗ will adaptively and parallelly interact with two honest users according to the signature protocol. Finally, two users output σ
i and σ
1
-
i respectively. Then σ
i and σ
1
-
i ordered by m
i and m
1
-
i are delivered to P
∗; after that, P
∗ will output i
′
∈
{
0,1
}.(2) One More Unforgeability.
P can generate a legal proxy σ instead of O. However, O and all the other entities fail to generate a legal signature. The game is presented as follows [33]: A
d
v
U
∗, the advantage of U
∗, is denoted as success probability in Algorithm 3. If no adversary can win Algorithm 3 at minimum with negligible probability η in time t, then it satisfies one more unforgeability [31].(3) Verifiability.
V can check whether σ is delegated by O.(4) Strong Identifiability. Any V can determine P’s identity once he receives the proxy signature tuple.(5) Strong Undeniability.
P cannot refuse to admit it once he creates the proxy signature σ.(6) Key Dependence.
P can sign on a message if and only if he has the authorization from O.


## 4. Proposed IDPBS-NTRU Scheme

Here, we introduce a novel IDPBS-NTRUε
=
S
T
ε
,
K
E
ε
,
D
G
ε
,
B
S
ε
,
P
S
ε
,
U
B
ε
,
P
V
ε, which can be seen in Algorithm 4. The details are as follows.(1)
S
T
ε
1
N. q
=
P
o
l
y
N, ε
∈
(
0
,
ln
⁡
N
/
ln
⁡
q
), and s
=
Ω
~
N
3
/
2
σ. If N
>
2
,
σ
=
N
(
ln
⁡
8
N
q
q
1
/
2
+
ε
,
q
1
/
2
-
ε
=
Ω
~
n
7
/
2. If N
=
2
,
σ
=
N
ln
⁡
8
N
q
q
1
/
2
+
ε
,
q
1
/
2
-
ε
=
Ω
~
N
3. m
k
=
m
s
k
,
m
p
k can be obtained as below [25].The algorithm takes samplesf and g from D
Z
N
,
s. Here, f, g
mod
q
∉
R
q
×, f
,
g
≤
σ
N, and f
,
g
∈
R. After that, the algorithm can get F
1
,
G
1
∈
R according to the equation f
G
1
-
g
F
1
=
1. Given F
q
=
q
F
1 and
G
q
=
q
G
1, F
q
,
G
q can be obtained from f
,
g
,
x
f
,
x
g
,
…
,
x
N
-
1
f
,
x
N
-
1
g according to Babai algorithm [43]. Then there exists F
,
G
=
F
q
,
G
q
-
k
f
,
g. If F
,
G
≤
N
σ, then the algorithm outputs system parameters p
a
r
a
s
=
q
,
ε
,
s; the master private-key msk and master public-key mpk are as follows:(3)
m
s
k
=
B
=
T
f
T
g
T
F
T
G
,
m
p
k
=
h
=
g
f
-
1
∈
R
q
×
.(2)
K
E
ε
(
p
a
r
a
s
,
i
d
i, msk
)
. The algorithm executes (4) to get an N-dimension matrix t; then the algorithm executes (6) and outputs s
k
i
d
i according to corresponding i
d
i
i
=
O
,
P [25].(4)
t
⟵
H
1
i
d
i
,
(5)
s
k
i
d
i
=
s
i
1
,
s
i
2
⟵
t
,
0
-
Gausssian
m
s
k
,
σ
,
t
,
0
,
s
i
1
+
s
i
2
h
=
t
.(3)
D
G
ε
.
ω is denoted as a warrant. O will execute this algorithm to generate a valid delegation.(i)
The algorithm choosesy
1
,
y
2
∈
D
Z
N
,
s at random.
(ii)
The algorithm executes (6) to get an N-dimension matrix u.
(iii)
The algorithm executes (7) and (8) to generate valid delegations σ
1 and σ
2. Here, the algorithm uses the rejection sampling theorem to keep the delegation independent on O’s secret keys s
O
1 and s
O
2.
(iv)
O sends (
σ
1
,
σ
2
,
u
,
ω
) to P.(6)
u
=
H
2
y
1
+
h
y
2
,
ω
,
(7)
σ
1
=
y
1
+
s
O
1
u
,
(8)
σ
2
=
y
2
+
s
O
2
u
.(4)
B
S
ε
.
m is a plaintext. U will execute this algorithm to generate a blind message, which needs to be signed by P.(i)
The algorithm will randomly selecty
3
,
y
4
,
α
,
γ
∈
D
Z
N
,
s.
(ii)
The algorithm executes (9) to get an N-dimension e.
(iii)
The algorithm executes (10) to blind e.
(iv)
U sends y
3
,
y
4
,
e
∗ to a proxy signer P. (9)
e
=
H
3
y
3
+
h
y
4
+
h
γ
+
α
-
α
H
i
d
,
m
,
(10)
e
∗
=
e
-
α
.(5)
P
S
ε
. The proxy signer P will execute this algorithm to sign on the blinded message.(i)
The algorithm validates whether (11) and (12) are true. If either is false, P aborts the algorithm. Otherwise, it continues.
(ii)
The algorithm will execute (13) and (14). Here, the rejection sample theory is used to keep the proxy signatures σ
3 and σ
4 independent on P’s secret keys s
P
1 and s
P
2.
(iii)
The algorithm outputs the tuple(
m
,
ω
,
σ
1
,
σ
2
,
u
,
σ
3
,
σ
4
,
e
). (11)
σ
1
,
σ
2
≤
2
s
2
N
,
(12)
H
2
h
σ
2
+
σ
1
-
H
1
i
d
O
u
,
ω
=
u
,
(13)
σ
3
=
y
3
+
s
P
1
e
,
(14)
σ
4
=
y
4
+
s
P
2
e
.(6)
U
B
ε
.
U will execute the algorithm to unblind the proxy signature.(i)
The algorithm executes (15) to unblind the proxy signature tuple.
(ii)
U outputs the signature tuple (
σ
1
,
m
,
σ
2
,
ω
,
u
,
σ
3
,
σ
4
,
e
).(15)
σ
3
=
σ
3
∗
+
α
,
σ
4
=
σ
4
∗
+
γ
.(7)
P
V
ε
(
σ
1
,
m
,
σ
2
,
ω
,
u
,
σ
3
,
σ
4
,
e
,
i
d
O
,
i
d
P
)
.
V will execute this algorithm to validate whether the signature tuple satisfies (16). If all the equations mentioned above are true, the signatures are valid. Otherwise, they are invalid.(16)
σ
1
,
σ
2
≤
2
s
2
N
,
H
2
h
σ
2
+
σ
1
-
H
1
i
d
O
u
,
w
=
u
,
σ
3
,
σ
4
≤
2
s
2
N
,
H
3
h
σ
4
+
σ
3
-
H
1
i
d
P
e
,
m
=
e
.


## 5. Security and Performance Comparison

### 5.1. Security

(1)Theorem 4 (correctness).
The IDPBS-NTRU scheme is correct.Proof.
According to the construction of our IDPBS scheme, we can get(17)
h
∗
σ
2
+
σ
1
-
H
i
d
O
∗
u
=
h
y
2
+
s
O
2
u
+
y
1
+
s
O
1
u
-
H
i
d
O
∗
u
=
y
1
+
h
y
2
.
Therefore,H
2
h
∗
σ
2
+
σ
1
-
H
i
d
O
∗
u
,
m
=
u.(18)
h
σ
4
+
σ
3
-
H
1
i
d
P
e
=
h
σ
4
∗
+
γ
+
σ
3
∗
+
α
-
H
i
d
P
∗
e
=
h
y
4
+
s
P
2
e
∗
+
γ
+
y
3
+
α
+
s
P
1
e
∗
-
H
i
d
P
∗
e
=
y
3
+
h
y
4
+
h
γ
+
α
-
α
H
1
i
d
P
.Thus, H
3
(
h
σ
4
+
σ
3
-
H
1
(
i
d
P
)
e
,
m
)
=
e.(2)Theorem 5 (blindness).
The IDPBS-NTRU scheme satisfies blindness.Proof.
As shown in Algorithm2, A random bit i
∈
{
0,1
} which is kept secret from P
∗. Then P
∗ chooses two messages m
0 and m
1. m
0 and m
1 are randomly denoted as m
i and m
1
-
i. m
i and m
1
-
i are the inputs of two honest users, respectively. P
∗ adaptively and parallelly interacts with two honest users, respectively. Finally, these two honest users output σ
i and σ
1
-
i, respectively. The sequence σ
i and σ
1
-
i ordered by m
i and m
1
-
i will be sent to P
∗. P
∗ will output a bit i
′
∈
{
0,1
}.
In the process of signature protocol, all intermediate results do not depend onm; thus it is enough to analyze e
∗, y
3, y
4, σ
1, σ
2, u, ω, σ
3
∗, and σ
4
∗.
Toe
∗, the statistical distance is presented as follows:(19)
Δ
e
i
∗
,
e
1
-
i
∗
=
1
2
∑
e
∗
′
∈
D
Z
N
,
s
Pr
⁡
e
i
∗
=
e
∗
′
-
Pr
⁡
e
1
-
i
∗
=
e
∗
′
.Algorithm 2:
E
x
p
t
S
∗
b
d
n.
i
∈
$
{
0,1
}
(
p
a
r
a
m
s
,
m
s
k
)
←
S
T
(
1
n
)
s
k
i
d
b
←
E
X
p
a
r
a
m
s
,
i
d
b
,
m
s
k, b
=
O
o
r
P
ψ
←
D
G
ε
(
i
d
O
,
s
k
i
d
O
,
ω
)
(
m
0
,
m
1
,
ω
,
ψ
,
s
t
a
t
e
f
i
n
d
)
←
$
P
∗
(
f
i
n
d
,
s
k
i
d
P
,
i
d
P
,
i
d
O
,
ψ
)
s
t
a
t
e
i
s
s
u
e
←
$
P
*
<
.
,
U
(
i
d
P
,
m
i
)
1
>
,
<
.
,
U
(
i
d
P
,
m
1
-
i
)
1
>
(
i
s
s
u
e
,
s
t
a
t
e
f
i
n
d
)
σ
i, σ
1
-
i are respectively U
(
i
d
P
,
m
i
)
,
U
(
i
d
P
,
m
1
-
i
)’s output
if  σ
0
≠
f
a
i
l and σ
1
≠
f
a
i
l  then
i
′
←
$
P
∗
(
g
u
e
s
s
,
σ
0
,
σ
1
,
s
t
a
t
e
i
s
s
u
e
)
else
i
′
←
$
P
∗
(
g
u
e
s
s
,
f
a
i
l
,
f
a
i
l
,
s
t
a
t
e
i
s
s
u
e
)
end if
return true iffi
′
=
iAlgorithm 3:
E
x
p
t
U
∗
o
m
f
n.
(
p
a
r
a
m
s
,
m
s
k
)
←
S
T
(
1
n
)
s
k
i
d
b
←
E
X
(
p
a
r
a
m
s
,
i
d
b
,
m
s
k
), b
=
O
o
r
P
ψ
←
D
G
ε
(
i
d
O
,
s
k
i
d
O
,
ω
)
m
1
,
σ
1
,
.
.
.
,
m
k
,
σ
k
←
$
U
∗
h
(
.
)
,
<
S
(
s
k
i
d
P
)
,
.
>
∞
(
i
d
P
)
l is the successful interaction number between U
∗ and P
return true iff
m
i
≠
m
j for 1
≤
i
<
j
≤
k and
V
F
(
m
i
,
σ
i
,
i
d
)
=
1 and
l
+
1
=
kAlgorithm 4:IDPBS-NTRU protocol.
S
e
t
u
p
:
S
T
ε
(
1
N
)
→
(
p
a
r
a
s
,
m
k
)
K
e
y
E
x
t
r
a
c
t
i
o
n
:
t
←
H
1
(
i
d
i
)
,
s
k
i
d
i
=
(
s
i
1
,
s
i
2
)
←
[
(
t
,
0
)
-
G
a
u
s
s
s
i
a
n
(
m
s
k
,
σ
,
(
t
,
0
)
)
]
D
e
l
e
g
a
t
i
o
n
G
e
n
e
r
a
t
i
o
n
(
o
r
i
g
i
n
a
l
s
i
g
n
e
r
O
)
:
y
1
,
y
2
∈
D
Z
N
,
s
u
=
H
2
(
y
1
+
h
y
2
,
ω
)
σ
1
=
y
1
+
s
O
1
u
σ
2
=
y
2
+
s
O
2
u
→
ω
,
u
,
σ
1
,
σ
2
proxy signer P
Blind (userU):
y
3
,
y
4
,
α
,
γ
∈
D
Z
N
,
s
e
=
H
3
(
y
3
+
h
y
4
+
h
γ
+
α
-
α
H
(
i
d
)
,
m
)
e
∗
=
e
-
α
→
e
∗
,
y
3
,
y
4
Proxy Signature (proxy signerP):
σ
3
∗
=
y
3
+
s
P
1
e
∗
σ
4
∗
=
y
4
+
s
P
2
e
∗
←
σ
1
,
σ
2
,
u
,
ω
,
σ
3
∗
,
σ
4
∗
Unblind (userU):
σ
3
=
σ
3
∗
+
α
σ
4
=
σ
4
∗
+
γ
s
i
g
n
a
t
u
r
e
t
u
p
l
e
(
ω
,
m
,
σ
1
,
σ
2
,
u
,
σ
3
,
σ
4
,
e
)
P
r
o
x
y
V
e
r
i
f
y
(
v
e
r
i
f
i
e
r
V
)
:
if σ
1
,
σ
2
≤
2
s
2
N
&
σ
3
,
σ
4
≤
2
s
2
N
&
H
2
(
h
σ
2
+
σ
1
-
H
1
(
i
d
O
)
u
,
ω
)
=
u
&
H
3
(
h
σ
4
+
σ
3
-
H
1
(
i
d
P
)
e
,
m
)
=
e
output true, otherwise falseSinceα is chosen at random, next we obtain the equations Pr
⁡
e
i
∗
=
e
∗
′
=
1
/
2 and Pr
⁡
e
1
-
i
∗
=
e
∗
′
=
1
/
2. Therefore, we obtain Δ
e
i
∗
,
e
1
-
i
∗
=
0.In the same way, we can obtainΔ
(
y
3
i
,
y
3
1
-
i
)
=
0, Δ
(
y
4
i
,
y
4
1
-
i
)
=
0, Δ
(
σ
1
i
∗
,
σ
1
1
-
i
∗
)
=
0, Δ
(
σ
2
i
∗
,
σ
2
1
-
i
∗
)
=
0, Δ
u
i
∗
,
u
1
-
i
∗
=
0, Δ
(
ω
i
∗
,
ω
1
-
i
∗
)
=
0, Δ
(
σ
3
i
∗
,
σ
3
1
-
i
∗
)
=
0, and Δ
(
σ
4
i
∗
,
σ
4
1
-
i
∗
)
=
0. Therefore, S
∗ cannot distinguish m among e
∗, y
3, y
4, σ
1, σ
2, u, ω, σ
3
∗, and σ
4
∗; that is, S
∗ can win this experiment with probability 1/2. Thus, the theorem is proven.We denoteδ
1, δ
2, δ
3, δ
4, δ
5, and δ
6 as the cost functions of H
1, H
2, H
3 hash oracle, extract Oracle, DG oracle, and signature oracle, respectively, η as a nonnegligible probability, Θ as a polynomial time algorithm, and Γ as a polynomial time forger.(3)Theorem 6 (one more unforgeability).
IfΓ is able to generate a legal IDPBS signature with η in t successfully, after at most τ
1
,
τ
2
,
τ
3
,
τ
4
,
τ
5
,
τ
6 times queries, respectively, to H
1
,
H
2
,
H
3 hash, extract, DG, and blind signature oracles, then R-S
I
S
q
,
1,2
,
β
κ can be solved by Θ with probability at least η
′
=
(
(
1
-
2
-
ω
(
log
⁡
N
)
)
η
)
2 in time t
′
=
t
+
τ
1
τ
4
+
τ
6
(
τ
1
ξ
1
+
τ
6
ξ
6
+
τ
4
ξ
4
)
+
τ
2
τ
5
(
τ
2
ξ
2
+
τ
5
ξ
5
).Proof.
We suppose thatΓ is able to generate an IDPBS signature successfully with η; we are able to construct Θ to calculate R
-
S
I
S’s solution. The interaction environment can be simulated as follows.
Setup.
Θ selects h
∈
R
q
× and H
1, H
2, and H
3 at random. Next Θ calculates and delivers p
a
r
a
s
=
{
h
,
H
1
,
H
2
,
ϵ
,
q
,
s
} to Γ.
Queries on
H
1
Oracle. To reply to H
1 oracle’s query, Θ creates one null list L
1. Once Θ obtains one i
d
i, Θ will query H
1. If there is a t
i consistent with the query, Θ will return t
i. Otherwise, Θ will select a random t
i. At last, Θ will return t
i to Γ and save (
i
d
i
,
t
i
) to L
1.
Queries on
H
2
Oracle. To reply to H
2’s queries, Θ creates a list L
2; is initialized null. When Θ receives an (
y
i
1
,
y
i
2
,
w
i
), Θ will query H
2. If there is one corresponding value t
i, Θ will return u
i. Else Θ will choose one u
i at random. Finally, Θ will return u
i to Γ and save (
y
i
1
,
y
i
2
,
w
i
,
u
i
) to L
2.
K
E
Oracle Queries. When Θ queries a private key related to one i
d
i, Γ will recover the corresponding (
i
d
i
,
t
i
) from L
1. Next Γ will run s
k
i
d
i
=
(
s
i
1
,
s
i
2
)
←
[
(
t
,
0
)
-
G
a
u
s
s
s
i
a
n
(
s
k
,
σ
,
(
t
,
0
)
)
]; Γ will return i
d
i
,
t
i
,
s
k
i
d
i to Θ and save the tuple to L
3.
D
G
Oracle Queries. When Θ requests the delegation queries, Θ will verify whether i
d
i has been queried for H
1 or K
E
ε oracle. If it has been queried, Θ will obtain (
i
d
i
,
t
i
,
s
k
i
d
i
) from L
3. Else Θ will simulate K
E
ε oracle and get a new private key. Next Θ will execute σ
i
1
=
y
i
1
+
s
O
i
1
u
i and σ
i
2
=
y
i
2
+
s
O
i
2
u
i to get a legal delegation signature (
w
i
,
u
i
,
σ
i
1
,
σ
i
2
) and save (
y
i
1
,
y
i
2
,
m
i
,
σ
i
1
,
σ
i
2
) to L
4.
Signature Oracle Queries.
Γ queries the signing oracle for y
i
3, y
i
4, α
i, β
i, i
d
i, and m
i. Θ will verify whether i
d
i has been queried for H
1 or K
E
ε oracle. If it has been queried, Θ will obtain (
i
d
i
,
t
i
,
s
k
i
d
i
) from L
3. Else Θ will simulate the E
X
ϵ oracle and get a new private key. Next Θ will execute D
G queries and then obtain (
y
i
1
,
y
i
2
,
ω
i
,
u
i
,
σ
i
1
,
σ
i
2
) from L
4. Then Θ will execute σ
i
3
=
y
i
3
+
s
P
i
1
e
i and σ
i
4
=
y
i
4
+
s
P
i
2
e
i to get a valid signature (
m
i
,
u
i
,
σ
i
3
,
σ
i
4
,
e
i
) and save (
y
i
1
,
y
i
2
,
ω
i
,
u
i
,
σ
i
1
,
σ
i
2
,
y
i
3
,
α
i
,
β
i
,
y
i
4
,
m
i
,
σ
i
3
,
σ
i
4
,
e
i
) to L
5.
Output. At last, Γ will output one forged signature (
u
i
,
ω
i
,
σ
i
1
,
σ
i
2
,
m
i
,
e
i
,
σ
i
3
,
σ
i
4
) on w
i, m
i, i
d
O
i, and i
d
P
i for the first time. Θ will rewind Γ to the point where w
i and m
i are queried for H
1; next Γ will get a valid tuple (
u
i
′
,
ω
i
′
,
σ
i
1
′
,
σ
i
2
′
,
m
i
′
,
e
i
′
,
σ
i
3
′
,
σ
i
4
′
) once again.
Thus,Θ are able to solve R-S
I
S
q
,
1,2
,
β
κ problem. Θ will compute σ
i
3
∗
=
y
i
3
+
s
O
i
1
e
i, σ
i
4
=
y
i
4
+
s
P
i
2
e
i, and σ
i
3
+
σ
i
4
h
-
H
(
i
d
P
i
)
e
i. Next Θ will verify whether σ
i
3
+
σ
i
4
h
-
H
(
i
d
P
i
)
e
i
=
σ
i
3
′
+
σ
i
4
′
h
-
H
(
i
d
P
i
)
e
i
=
y
i
3
+
h
y
i
4
+
h
γ
i
+
α
i
-
α
i
H
(
i
d
P
i
). If (
σ
i
3
,
σ
i
4
)
≠
(
σ
i
3
′
,
σ
i
4
′
), we can obtain (
σ
i
3
-
σ
i
3
′
,
σ
i
4
-
σ
i
4
′
)
≤
4
s
2
N. After that, (
σ
i
4
-
σ
i
4
′
,
σ
i
3
-
σ
i
3
′
) is a solution to R-S
I
S
q
,
1,2
,
β
κ. Similarly, we can obtain that (
σ
i
2
-
σ
i
2
′
,
σ
i
1
-
σ
i
1
′
) is a solution to R-S
I
S
q
,
1,2
,
β
κ.
After that, we begin to analyzeΘ’s advantages. As mentioned above, Θ will win this game if Γ has already forged a valid (
σ
i
1
′
,
ω
i
,
m
i
,
σ
i
2
′
,
u
i
′
,
σ
i
3
′
,
σ
i
4
′
,
e
i
′
) and (
σ
i
1
,
σ
i
2
)
≠
(
σ
i
1
′
,
σ
i
2
′
) and (
σ
i
3
,
z
i
4
)
≠
(
σ
i
3
′
,
σ
i
4
′
). The simulation of the E
X
ϵ oracle fails if H
2 causes inconformity. Then Θ is able to solve R-S
I
S
q
,
1,2
,
β
κ with probability at minimum η
′
=
(
(
1
-
2
-
ω
(
log
⁡
N
)
)
η
)
2 [25]; here, β
=
4
s
2
N; it is clear that t
′
=
t
+
τ
1
τ
4
+
τ
6
(
τ
1
ξ
1
+
τ
6
ξ
6
+
τ
4
ξ
4
)
+
τ
2
τ
5
(
τ
2
ξ
2
+
τ
5
ξ
5
). Therefore, we can prove the theorem.
(4) Verifiability. Once receiving (
w
,
m
,
σ
1
,
σ
2
,
u
,
σ
3
,
σ
4
,
e
,
i
d
O
,
i
d
P
), V will execute P
V
ε to check whether (
σ
1
,
σ
2
)
≤
2
s
2
N and H
2
(
h
σ
2
+
σ
1
-
H
1
(
i
d
O
)
u
,
w
)
=
u are true. If both are true, the proxy signer is delegated by O to sign on m.
(5) Strong Identifiability. After receiving (
w
,
m
,
σ
1
,
σ
2
,
u
,
σ
3
,
σ
4
,
e
,
i
d
O
,
i
d
P
), V can confirm P’s identity in accordance with i
d
P; thus the IDPBS-NTRU scheme satisfies strong identifiability.
(6) Strong Undeniability.
σ
3 and
σ
4 are signed by using P’s secret keys s
P
1 and s
P
2; they will only be known by P; thus P cannot refuse his signature once he signed; thus the IDPBS-NTRU scheme satisfies strong undeniability.
(7) Key Dependence.
σ
1 and σ
2 on warrant ω are signed by O’s secret keys s
O
1 and
s
O
2; they are only known by O,;  P has no legal right to sign on a message before he is authorized by O; thus the IDPBS-NTRU scheme satisfies key dependence.


### 5.2. Performance

In this section, we compare the performance of IDPBS-NTRU with other IDPBS schemes.λ is written as security parameter, we denote O’s signature size and signing-key size as OSS and OSK, respectively. P’s signature size and signing key size are denoted as PSS and PSK, respectively. In ZM scheme [33], the parameters satisfy m
≥
2
N
lg
⁡
q and q
>
β
ω
log
⁡
n. In TA [34] and MMHP [35] schemes, the security parameter m is equal to N.In Table1, we compute the signature size and signing key size for O and P. It is clear to draw a conclusion that our proxy signer’s OSS, OSK, and PSK are smaller than ZM, TA, and MMHP schemes, our PSS is larger than ZM scheme, our PSS is smaller than TA scheme and MMHP scheme, and our OSS, OSK, PSK, and PSS are larger than TA and MMHP schemes. However, TA scheme and MMHP scheme are based on DLP; they are considered as not secure to resist the quantum computer attack. So our scheme can be more secure than them.Table 1
Performance comparison with other lattice-based IDPBS schemes.
ZM [33]
TA [34]
MMHP [35]
Ours
Problem
SIS
DLP
DLP
R-SIS
OSS
m
2
log
⁡
λ
+
1
3
m
m
2
N
log
⁡
12
σ
+
N
log
⁡
λ
+
1
OSK
m
2
log
⁡
λ
+
1
m
m
2
N
log
⁡
(
s
N
)
PSS
2
m
log
⁡
λ
+
1
m
m
4
N
log
⁡
12
σ
+
2
N
log
⁡
λ
+
1
PSK
m
2
log
⁡
λ
+
1
7
m
m
2
N
log
⁡
s
N


## 5.1. Security

(1)Theorem 4 (correctness).
The IDPBS-NTRU scheme is correct.Proof.
According to the construction of our IDPBS scheme, we can get(17)
h
∗
σ
2
+
σ
1
-
H
i
d
O
∗
u
=
h
y
2
+
s
O
2
u
+
y
1
+
s
O
1
u
-
H
i
d
O
∗
u
=
y
1
+
h
y
2
.
Therefore,H
2
h
∗
σ
2
+
σ
1
-
H
i
d
O
∗
u
,
m
=
u.(18)
h
σ
4
+
σ
3
-
H
1
i
d
P
e
=
h
σ
4
∗
+
γ
+
σ
3
∗
+
α
-
H
i
d
P
∗
e
=
h
y
4
+
s
P
2
e
∗
+
γ
+
y
3
+
α
+
s
P
1
e
∗
-
H
i
d
P
∗
e
=
y
3
+
h
y
4
+
h
γ
+
α
-
α
H
1
i
d
P
.Thus, H
3
(
h
σ
4
+
σ
3
-
H
1
(
i
d
P
)
e
,
m
)
=
e.(2)Theorem 5 (blindness).
The IDPBS-NTRU scheme satisfies blindness.Proof.
As shown in Algorithm2, A random bit i
∈
{
0,1
} which is kept secret from P
∗. Then P
∗ chooses two messages m
0 and m
1. m
0 and m
1 are randomly denoted as m
i and m
1
-
i. m
i and m
1
-
i are the inputs of two honest users, respectively. P
∗ adaptively and parallelly interacts with two honest users, respectively. Finally, these two honest users output σ
i and σ
1
-
i, respectively. The sequence σ
i and σ
1
-
i ordered by m
i and m
1
-
i will be sent to P
∗. P
∗ will output a bit i
′
∈
{
0,1
}.
In the process of signature protocol, all intermediate results do not depend onm; thus it is enough to analyze e
∗, y
3, y
4, σ
1, σ
2, u, ω, σ
3
∗, and σ
4
∗.
Toe
∗, the statistical distance is presented as follows:(19)
Δ
e
i
∗
,
e
1
-
i
∗
=
1
2
∑
e
∗
′
∈
D
Z
N
,
s
Pr
⁡
e
i
∗
=
e
∗
′
-
Pr
⁡
e
1
-
i
∗
=
e
∗
′
.Algorithm 2:
E
x
p
t
S
∗
b
d
n.
i
∈
$
{
0,1
}
(
p
a
r
a
m
s
,
m
s
k
)
←
S
T
(
1
n
)
s
k
i
d
b
←
E
X
p
a
r
a
m
s
,
i
d
b
,
m
s
k, b
=
O
o
r
P
ψ
←
D
G
ε
(
i
d
O
,
s
k
i
d
O
,
ω
)
(
m
0
,
m
1
,
ω
,
ψ
,
s
t
a
t
e
f
i
n
d
)
←
$
P
∗
(
f
i
n
d
,
s
k
i
d
P
,
i
d
P
,
i
d
O
,
ψ
)
s
t
a
t
e
i
s
s
u
e
←
$
P
*
<
.
,
U
(
i
d
P
,
m
i
)
1
>
,
<
.
,
U
(
i
d
P
,
m
1
-
i
)
1
>
(
i
s
s
u
e
,
s
t
a
t
e
f
i
n
d
)
σ
i, σ
1
-
i are respectively U
(
i
d
P
,
m
i
)
,
U
(
i
d
P
,
m
1
-
i
)’s output
if  σ
0
≠
f
a
i
l and σ
1
≠
f
a
i
l  then
i
′
←
$
P
∗
(
g
u
e
s
s
,
σ
0
,
σ
1
,
s
t
a
t
e
i
s
s
u
e
)
else
i
′
←
$
P
∗
(
g
u
e
s
s
,
f
a
i
l
,
f
a
i
l
,
s
t
a
t
e
i
s
s
u
e
)
end if
return true iffi
′
=
iAlgorithm 3:
E
x
p
t
U
∗
o
m
f
n.
(
p
a
r
a
m
s
,
m
s
k
)
←
S
T
(
1
n
)
s
k
i
d
b
←
E
X
(
p
a
r
a
m
s
,
i
d
b
,
m
s
k
), b
=
O
o
r
P
ψ
←
D
G
ε
(
i
d
O
,
s
k
i
d
O
,
ω
)
m
1
,
σ
1
,
.
.
.
,
m
k
,
σ
k
←
$
U
∗
h
(
.
)
,
<
S
(
s
k
i
d
P
)
,
.
>
∞
(
i
d
P
)
l is the successful interaction number between U
∗ and P
return true iff
m
i
≠
m
j for 1
≤
i
<
j
≤
k and
V
F
(
m
i
,
σ
i
,
i
d
)
=
1 and
l
+
1
=
kAlgorithm 4:IDPBS-NTRU protocol.
S
e
t
u
p
:
S
T
ε
(
1
N
)
→
(
p
a
r
a
s
,
m
k
)
K
e
y
E
x
t
r
a
c
t
i
o
n
:
t
←
H
1
(
i
d
i
)
,
s
k
i
d
i
=
(
s
i
1
,
s
i
2
)
←
[
(
t
,
0
)
-
G
a
u
s
s
s
i
a
n
(
m
s
k
,
σ
,
(
t
,
0
)
)
]
D
e
l
e
g
a
t
i
o
n
G
e
n
e
r
a
t
i
o
n
(
o
r
i
g
i
n
a
l
s
i
g
n
e
r
O
)
:
y
1
,
y
2
∈
D
Z
N
,
s
u
=
H
2
(
y
1
+
h
y
2
,
ω
)
σ
1
=
y
1
+
s
O
1
u
σ
2
=
y
2
+
s
O
2
u
→
ω
,
u
,
σ
1
,
σ
2
proxy signer P
Blind (userU):
y
3
,
y
4
,
α
,
γ
∈
D
Z
N
,
s
e
=
H
3
(
y
3
+
h
y
4
+
h
γ
+
α
-
α
H
(
i
d
)
,
m
)
e
∗
=
e
-
α
→
e
∗
,
y
3
,
y
4
Proxy Signature (proxy signerP):
σ
3
∗
=
y
3
+
s
P
1
e
∗
σ
4
∗
=
y
4
+
s
P
2
e
∗
←
σ
1
,
σ
2
,
u
,
ω
,
σ
3
∗
,
σ
4
∗
Unblind (userU):
σ
3
=
σ
3
∗
+
α
σ
4
=
σ
4
∗
+
γ
s
i
g
n
a
t
u
r
e
t
u
p
l
e
(
ω
,
m
,
σ
1
,
σ
2
,
u
,
σ
3
,
σ
4
,
e
)
P
r
o
x
y
V
e
r
i
f
y
(
v
e
r
i
f
i
e
r
V
)
:
if σ
1
,
σ
2
≤
2
s
2
N
&
σ
3
,
σ
4
≤
2
s
2
N
&
H
2
(
h
σ
2
+
σ
1
-
H
1
(
i
d
O
)
u
,
ω
)
=
u
&
H
3
(
h
σ
4
+
σ
3
-
H
1
(
i
d
P
)
e
,
m
)
=
e
output true, otherwise falseSinceα is chosen at random, next we obtain the equations Pr
⁡
e
i
∗
=
e
∗
′
=
1
/
2 and Pr
⁡
e
1
-
i
∗
=
e
∗
′
=
1
/
2. Therefore, we obtain Δ
e
i
∗
,
e
1
-
i
∗
=
0.In the same way, we can obtainΔ
(
y
3
i
,
y
3
1
-
i
)
=
0, Δ
(
y
4
i
,
y
4
1
-
i
)
=
0, Δ
(
σ
1
i
∗
,
σ
1
1
-
i
∗
)
=
0, Δ
(
σ
2
i
∗
,
σ
2
1
-
i
∗
)
=
0, Δ
u
i
∗
,
u
1
-
i
∗
=
0, Δ
(
ω
i
∗
,
ω
1
-
i
∗
)
=
0, Δ
(
σ
3
i
∗
,
σ
3
1
-
i
∗
)
=
0, and Δ
(
σ
4
i
∗
,
σ
4
1
-
i
∗
)
=
0. Therefore, S
∗ cannot distinguish m among e
∗, y
3, y
4, σ
1, σ
2, u, ω, σ
3
∗, and σ
4
∗; that is, S
∗ can win this experiment with probability 1/2. Thus, the theorem is proven.We denoteδ
1, δ
2, δ
3, δ
4, δ
5, and δ
6 as the cost functions of H
1, H
2, H
3 hash oracle, extract Oracle, DG oracle, and signature oracle, respectively, η as a nonnegligible probability, Θ as a polynomial time algorithm, and Γ as a polynomial time forger.(3)Theorem 6 (one more unforgeability).
IfΓ is able to generate a legal IDPBS signature with η in t successfully, after at most τ
1
,
τ
2
,
τ
3
,
τ
4
,
τ
5
,
τ
6 times queries, respectively, to H
1
,
H
2
,
H
3 hash, extract, DG, and blind signature oracles, then R-S
I
S
q
,
1,2
,
β
κ can be solved by Θ with probability at least η
′
=
(
(
1
-
2
-
ω
(
log
⁡
N
)
)
η
)
2 in time t
′
=
t
+
τ
1
τ
4
+
τ
6
(
τ
1
ξ
1
+
τ
6
ξ
6
+
τ
4
ξ
4
)
+
τ
2
τ
5
(
τ
2
ξ
2
+
τ
5
ξ
5
).Proof.
We suppose thatΓ is able to generate an IDPBS signature successfully with η; we are able to construct Θ to calculate R
-
S
I
S’s solution. The interaction environment can be simulated as follows.
Setup.
Θ selects h
∈
R
q
× and H
1, H
2, and H
3 at random. Next Θ calculates and delivers p
a
r
a
s
=
{
h
,
H
1
,
H
2
,
ϵ
,
q
,
s
} to Γ.
Queries on
H
1
Oracle. To reply to H
1 oracle’s query, Θ creates one null list L
1. Once Θ obtains one i
d
i, Θ will query H
1. If there is a t
i consistent with the query, Θ will return t
i. Otherwise, Θ will select a random t
i. At last, Θ will return t
i to Γ and save (
i
d
i
,
t
i
) to L
1.
Queries on
H
2
Oracle. To reply to H
2’s queries, Θ creates a list L
2; is initialized null. When Θ receives an (
y
i
1
,
y
i
2
,
w
i
), Θ will query H
2. If there is one corresponding value t
i, Θ will return u
i. Else Θ will choose one u
i at random. Finally, Θ will return u
i to Γ and save (
y
i
1
,
y
i
2
,
w
i
,
u
i
) to L
2.
K
E
Oracle Queries. When Θ queries a private key related to one i
d
i, Γ will recover the corresponding (
i
d
i
,
t
i
) from L
1. Next Γ will run s
k
i
d
i
=
(
s
i
1
,
s
i
2
)
←
[
(
t
,
0
)
-
G
a
u
s
s
s
i
a
n
(
s
k
,
σ
,
(
t
,
0
)
)
]; Γ will return i
d
i
,
t
i
,
s
k
i
d
i to Θ and save the tuple to L
3.
D
G
Oracle Queries. When Θ requests the delegation queries, Θ will verify whether i
d
i has been queried for H
1 or K
E
ε oracle. If it has been queried, Θ will obtain (
i
d
i
,
t
i
,
s
k
i
d
i
) from L
3. Else Θ will simulate K
E
ε oracle and get a new private key. Next Θ will execute σ
i
1
=
y
i
1
+
s
O
i
1
u
i and σ
i
2
=
y
i
2
+
s
O
i
2
u
i to get a legal delegation signature (
w
i
,
u
i
,
σ
i
1
,
σ
i
2
) and save (
y
i
1
,
y
i
2
,
m
i
,
σ
i
1
,
σ
i
2
) to L
4.
Signature Oracle Queries.
Γ queries the signing oracle for y
i
3, y
i
4, α
i, β
i, i
d
i, and m
i. Θ will verify whether i
d
i has been queried for H
1 or K
E
ε oracle. If it has been queried, Θ will obtain (
i
d
i
,
t
i
,
s
k
i
d
i
) from L
3. Else Θ will simulate the E
X
ϵ oracle and get a new private key. Next Θ will execute D
G queries and then obtain (
y
i
1
,
y
i
2
,
ω
i
,
u
i
,
σ
i
1
,
σ
i
2
) from L
4. Then Θ will execute σ
i
3
=
y
i
3
+
s
P
i
1
e
i and σ
i
4
=
y
i
4
+
s
P
i
2
e
i to get a valid signature (
m
i
,
u
i
,
σ
i
3
,
σ
i
4
,
e
i
) and save (
y
i
1
,
y
i
2
,
ω
i
,
u
i
,
σ
i
1
,
σ
i
2
,
y
i
3
,
α
i
,
β
i
,
y
i
4
,
m
i
,
σ
i
3
,
σ
i
4
,
e
i
) to L
5.
Output. At last, Γ will output one forged signature (
u
i
,
ω
i
,
σ
i
1
,
σ
i
2
,
m
i
,
e
i
,
σ
i
3
,
σ
i
4
) on w
i, m
i, i
d
O
i, and i
d
P
i for the first time. Θ will rewind Γ to the point where w
i and m
i are queried for H
1; next Γ will get a valid tuple (
u
i
′
,
ω
i
′
,
σ
i
1
′
,
σ
i
2
′
,
m
i
′
,
e
i
′
,
σ
i
3
′
,
σ
i
4
′
) once again.
Thus,Θ are able to solve R-S
I
S
q
,
1,2
,
β
κ problem. Θ will compute σ
i
3
∗
=
y
i
3
+
s
O
i
1
e
i, σ
i
4
=
y
i
4
+
s
P
i
2
e
i, and σ
i
3
+
σ
i
4
h
-
H
(
i
d
P
i
)
e
i. Next Θ will verify whether σ
i
3
+
σ
i
4
h
-
H
(
i
d
P
i
)
e
i
=
σ
i
3
′
+
σ
i
4
′
h
-
H
(
i
d
P
i
)
e
i
=
y
i
3
+
h
y
i
4
+
h
γ
i
+
α
i
-
α
i
H
(
i
d
P
i
). If (
σ
i
3
,
σ
i
4
)
≠
(
σ
i
3
′
,
σ
i
4
′
), we can obtain (
σ
i
3
-
σ
i
3
′
,
σ
i
4
-
σ
i
4
′
)
≤
4
s
2
N. After that, (
σ
i
4
-
σ
i
4
′
,
σ
i
3
-
σ
i
3
′
) is a solution to R-S
I
S
q
,
1,2
,
β
κ. Similarly, we can obtain that (
σ
i
2
-
σ
i
2
′
,
σ
i
1
-
σ
i
1
′
) is a solution to R-S
I
S
q
,
1,2
,
β
κ.
After that, we begin to analyzeΘ’s advantages. As mentioned above, Θ will win this game if Γ has already forged a valid (
σ
i
1
′
,
ω
i
,
m
i
,
σ
i
2
′
,
u
i
′
,
σ
i
3
′
,
σ
i
4
′
,
e
i
′
) and (
σ
i
1
,
σ
i
2
)
≠
(
σ
i
1
′
,
σ
i
2
′
) and (
σ
i
3
,
z
i
4
)
≠
(
σ
i
3
′
,
σ
i
4
′
). The simulation of the E
X
ϵ oracle fails if H
2 causes inconformity. Then Θ is able to solve R-S
I
S
q
,
1,2
,
β
κ with probability at minimum η
′
=
(
(
1
-
2
-
ω
(
log
⁡
N
)
)
η
)
2 [25]; here, β
=
4
s
2
N; it is clear that t
′
=
t
+
τ
1
τ
4
+
τ
6
(
τ
1
ξ
1
+
τ
6
ξ
6
+
τ
4
ξ
4
)
+
τ
2
τ
5
(
τ
2
ξ
2
+
τ
5
ξ
5
). Therefore, we can prove the theorem.
(4) Verifiability. Once receiving (
w
,
m
,
σ
1
,
σ
2
,
u
,
σ
3
,
σ
4
,
e
,
i
d
O
,
i
d
P
), V will execute P
V
ε to check whether (
σ
1
,
σ
2
)
≤
2
s
2
N and H
2
(
h
σ
2
+
σ
1
-
H
1
(
i
d
O
)
u
,
w
)
=
u are true. If both are true, the proxy signer is delegated by O to sign on m.
(5) Strong Identifiability. After receiving (
w
,
m
,
σ
1
,
σ
2
,
u
,
σ
3
,
σ
4
,
e
,
i
d
O
,
i
d
P
), V can confirm P’s identity in accordance with i
d
P; thus the IDPBS-NTRU scheme satisfies strong identifiability.
(6) Strong Undeniability.
σ
3 and
σ
4 are signed by using P’s secret keys s
P
1 and s
P
2; they will only be known by P; thus P cannot refuse his signature once he signed; thus the IDPBS-NTRU scheme satisfies strong undeniability.
(7) Key Dependence.
σ
1 and σ
2 on warrant ω are signed by O’s secret keys s
O
1 and
s
O
2; they are only known by O,;  P has no legal right to sign on a message before he is authorized by O; thus the IDPBS-NTRU scheme satisfies key dependence.


## 5.2. Performance

In this section, we compare the performance of IDPBS-NTRU with other IDPBS schemes.λ is written as security parameter, we denote O’s signature size and signing-key size as OSS and OSK, respectively. P’s signature size and signing key size are denoted as PSS and PSK, respectively. In ZM scheme [33], the parameters satisfy m
≥
2
N
lg
⁡
q and q
>
β
ω
log
⁡
n. In TA [34] and MMHP [35] schemes, the security parameter m is equal to N.In Table1, we compute the signature size and signing key size for O and P. It is clear to draw a conclusion that our proxy signer’s OSS, OSK, and PSK are smaller than ZM, TA, and MMHP schemes, our PSS is larger than ZM scheme, our PSS is smaller than TA scheme and MMHP scheme, and our OSS, OSK, PSK, and PSS are larger than TA and MMHP schemes. However, TA scheme and MMHP scheme are based on DLP; they are considered as not secure to resist the quantum computer attack. So our scheme can be more secure than them.Table 1
Performance comparison with other lattice-based IDPBS schemes.
ZM [33]
TA [34]
MMHP [35]
Ours
Problem
SIS
DLP
DLP
R-SIS
OSS
m
2
log
⁡
λ
+
1
3
m
m
2
N
log
⁡
12
σ
+
N
log
⁡
λ
+
1
OSK
m
2
log
⁡
λ
+
1
m
m
2
N
log
⁡
(
s
N
)
PSS
2
m
log
⁡
λ
+
1
m
m
4
N
log
⁡
12
σ
+
2
N
log
⁡
λ
+
1
PSK
m
2
log
⁡
λ
+
1
7
m
m
2
N
log
⁡
s
N


## 6. Conclusions

In this work, we present an IDPBS-NTRU scheme by using NTRU lattice; this scheme plays an important role in offline e-payment system, which can be deployed in fog computing model. We demonstrate that IDPBS-NTRU is efficient and secure. In addition, our IDPBS-NTRU’s OSS, OSK, and PSK are smaller than ZM scheme and safer than TA and MMHP schemes. The proposed scheme is constructed based on NTRU lattice, which has the advantages of NTRU lattice. In the future, we will continue to construct a partial IDPBS scheme based on lattice.



---

*Source: 5401890-2018-05-09.xml*