# Server-Aided Verification Signature with Privacy for Mobile Computing

Authors: Lingling Xu; Jin Li; Shaohua Tang; Joonsang Baek
Journal: Mobile Information Systems
 (2015)

---

## Abstract

With the development of wireless technology, much data communication and processing has been conducted in mobile devices with wireless connection. As we know that the mobile devices will always be resource-poor relative to static ones though they will improve in absolute ability, therefore, they cannot process some expensive computational tasks due to the constrained computational resources. According to this problem, server-aided computing has been studied in which the power-constrained mobile devices can outsource some expensive computation to a server with powerful resources in order to reduce their computational load. However,  in existing server-aided verification signature schemes, the server can learn some information about the message-signature pair to be verified, which is undesirable especially when the message includes some secret information. In this paper, we mainly study the server-aided verification signatures with privacy in which the message-signature pair to be verified can be protected from the server. Two definitions of privacy for server-aided verification signatures are presented under collusion attacks between the server and the signer. Then based on existing signatures, two concrete server-aided verification signature schemes with privacy are proposed which are both proved secure.


---

## Body

## 1. Introduction

Recent advances in wireless technology have led to mobile computing [1, 2] which is a technology that enables access to digital resources at any time, from any location. In mobile computing, much data communication and processing is conducted in mobile devices with wireless connection such as cell-phones, security access-cards, and sensors. Therefore, mobile computing represents the elimination of time-and-place restrictions imposed by desktop computers and wired networks. As we know mobile devices must be light and small to be easily carried around. Such considerations, in conjunction with a given cost and level of technology, will exact a penalty in computational resources of mobile devices such as processor speed. While mobile devices will improve in absolute ability, they will always be computationally weak in relation to static ones. As a consequence there are tasks, which potentially could enlarge a device’s range of application, which are beyond its reach. A natural solution is to outsource computations that are too expensive for one device, to other devices which are more powerful or numerous and connected to the device. For example, consider a sensor that is presented with an access-card, sends it a random challenge, and receives a digital signature of the random challenge. The computation is required to verify the signature involves public-key operations which are too expensive in both time and space for the sensor to run. Instead, it could outsource the verification to a powerful device in order to reduce its computational load. Recently, with the development of cloud computing, server-aided computation has received widespread attention which enables power-constrained devices to outsource expensive computational tasks to a server. The related works such as server-aided delegated computation [3–8] and server-aided verification signatures [9–16] have been widely studied. Delegated computation is a protocol between two polynomial-time parties, a client, and a server, to collaborate on the computation of a function F. Concretely, the client wants the server to compute F
(
x
) for any input instance x by the delegated computation protocol and verify the correctness of the results that is returned by the server. A key requirement is that the amount of work performed by the client to generate and verify work instances must be substantially cheaper than performing the computation on its own.A server-aided verification signature scheme consists of a digital signature scheme and a server-aided verification protocol. Signatures can be verified by executing the server-aided verification protocol with the server, where the verification requires less computation than the original verification algorithm of the digital signature. Different to delegated computation, the existing server-aided verification signature schemes can achieve the soundness of the server-aided verification protocol under their security definitions, namely, a trusted server cannot convince the verifier that an invalid signature is valid, and the verifier cannot directly verify the results computed by the server. The notion of server-aided verification signature was first introduced by Quisquater and de Soete [10] for speeding up RSA verification with a small exponent. Then, Lim and Lee [11] extended this idea into discrete-logarithm based schemes, by proposing efficient protocols for speeding up the verification of discrete-logarithm based identity proofs and signatures. Girault and Quisquater [13] introduced a different approach for server-aided verification signature which does not require precomputation or randomization. Its security remains computational, based on the hardness of a subproblem (viz. factorization) of the initial underlying problem (viz. composite discrete logarithm). Hohenberger and Lysyanskaya [17] addressed the situation in which the server is made of two untrusted softwares, which are assumed not to communicate with each other. Girault and Lefranc [14] presented a generic server-aided verification protocol for digital signatures from bilinear maps which has been used to construct many digital signature schemes such as [18–23].As to the security of server-aided verification signature, many efforts have been devoted to defining strong security models for it. The schemes [10, 11, 13, 14] considered the security property based on the assumption that the malicious server does not have any valid signatures on the message when it tries to prove an invalid signature of that message to be valid. Among them, the scheme [13] is computationally secure based on the hardness of a subproblem of the underlying complexity problem in the original signature scheme. To give stronger definition of this property, Wu et al. [15] formally defined this security assuming that the malicious server may collude with the signer and obtain the secret key of the signer. They first introduced and defined the existential unforgeability of server-aided verification signatures and considered collusion between a signer and a server, who collaboratively prove an invalid signature to be valid. In addition, under their security models, they introduced the server-aided verification for the Waters signature [21] and the BLS signature [18], respectively.Though the existing server-aided verification signature schemes above have been devoted many efforts to their security models, they only considered the soundness to protect the malicious server who may try to prove an invalid signature of a message to be valid. However, in some applications where the message-signature to be verified contains some sensitive information, for example, the message contains important business secrets or is related to medical information, the verifier does not want the server learn anything about the message and/or the signature to protect its privacy. So, the message privacy of the server-aided verification protocol is also desired besides the soundness. Though in Wu et al. [15], based on Waters Signature [21] and BLS signature [18], two SA verification signature schemes (see Section  4 in [15]) were presented in which the message to be verified is not revealed to the server, the schemes cannot achieve the soundness under collusion and adaptively chosen message attacks.In this paper, we will present two privacy definitions for server-aided verification signature under collusion by the server and the signer and adaptive chosen message attacks. A server-aided verification signature scheme with privacy also consists of a digital signature scheme and a server-aided verification protocol.(1)
The first privacy definition for the server-aided verification signature is about message privacy; namely, the server cannot learn anything about the message to be verified during the server-aided verification protocol even if it possesses the secret key of the signer. Generally, when the verifier wants the server to verify a message-signature pair, it will “blind” this message at the beginning of the server-aided verification protocol so that the server cannot obtain any information about this message, while it can verify the validity of the message-signature pair by using the server’s responses.
(2)
The second privacy definition for the server-aided verification signature is about message-signature privacy which is stronger than the first one, and in this definition, the server can learn nothing about the message-signature pair to be verified even if it colludes with the signer. To achieve this privacy, similarly, the verifier will “blind” the message-signature pair at the beginning of the server-aided verification protocol so that the server cannot obtain any information about the message or the signature; however it can verify the validity of the message-signature pair after the server responds.For the two privacy notions, we present detailed and strict security models. Then, under the security models, we present two concrete constructions for server-aided verification signature based on Waters signature [21] and BLS signature [18] which, respectively, achieve message privacy and message-signature privacy. The soundness of the two constructions is proved under the strong definition of [15] assuming that the malicious server may collude with the signer and obtain the secret key of the signer. In addition, the efficiency analysis of the server-aided verification protocols shows that our two concrete server-aided verification signature schemes are both computation saving. Computation saving is probably the most obvious property that can distinguish a server-aided verification signature scheme SAV-Σ from an ordinary signature scheme Σ. This property enables the verifier in SAV-Σ to check the validity of signatures in a more computationally efficient way than that in Σ.Organization. This paper is organized as follows. In Section 2, we will review some fundamental backgrounds, the definition of server-aided verification signatures and the security notions defined in [15] including existential unforgeability and soundness against collusion and adaptive chosen message attacks. In Section 3, we will present the message privacy of server-aided verification signatures, give a concrete construction based on Waters signature scheme, and prove its security under our security model for message privacy. In Section 4, a stronger privacy of server-aided verification signatures named message-signature privacy will be defined and a provably secure concrete construction will be presented based on BLS signature scheme. Finally we conclude in Section 5.


## 2. Preliminaries

### 2.1. Syntax

Throughout the paper, ifA is a randomized algorithm, then y
←
A
(
x
) denotes the assignment to y of the output of A on input x. Unless noted, all algorithms are probabilistic polynomial-time (PPT) and we implicitly assume that they take an extra parameter κ in their input, where κ is a security parameter.


### 2.2.  Bilinear Maps

LetG
1, G
T be two (multiplicative) cyclic groups such that |
G
1
|
=
|
G
T
|
=
p, where p is a large prime. Let g be a generator of G
1, and e be an admissible bilinear map: G
1
×
G
1
→
G
T, satisfying (
1
) for all a
,
b
∈
Z
p; it holds that e
(
g
a
,
g
b
)
=
e
(
g
,
g
)
a
b; (
2
)  e
(
g
,
g
)
≠
1; and (
3
) it is efficiently computable.We say that (G
1
,
G
T) are bilinear groups if there exists the bilinear map e
:
G
1
×
G
1
→
G
T as above, and the group action in G
1 and G
T can be computed efficiently. Such groups can be built from Weil pairing or Tate pairing on elliptic curves.


### 2.3.  Server-Aided Verification Signature

A server-aided verification signature scheme SAV-Σ consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify. The first four algorithms are the same as those in an ordinary signature scheme Σ. SAV-Σ contains three parties, respectively, a signer, a verifier, and a server.(i)
p
a
r
a
m
←
ParamGen. This algorithm takes a security parameter κ and returns a string p
a
r
a
m as input, which denotes the common scheme parameters, including the description of the message space M and the signature space Ω.
(ii)
(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
p
a
r
a
m
). This algorithm takes p
a
r
a
m as input and outputs a key pair (
p
k
,
s
k
), where s
k is the signing key and p
k is the verification key.
(iii)
σ
←
S
i
g
n
(
p
a
r
a
m
,
m
,
s
k
,
p
k
). The signer takes a message m
∈
M, the system parameter p
a
r
a
m and the key pair (
s
k
,
p
k
) as inputs, outputs a signature σ.
(iv)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
V
e
r
i
f
y
(
p
a
r
a
m
,
m
,
σ
,
p
k
). The verifier takes the parameter p
a
r
a
m, a message-signature pair (
m
,
σ
) and the public key p
k, outputsValid/Invalid to indicate that σ is a valid/invalid signature on m under p
k.
(v)
V
S
t
r
i
n
g
←
S
A
-
V
e
r
i
f
i
e
r
-
S
e
t
u
p
(
p
a
r
a
m
). The verifier takes as input the system parameter p
a
r
a
m and outputs a stringVString which contains the information which can be precomputed by it.
(vi)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
S
A
-
V
e
r
i
f
y
(
Server
p
a
r
a
m
,
Verifier
(
m
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
). This is an interactive protocol between the server and the verifier where the server takes p
a
r
a
m as input and the verifier takes (
m
,
σ
,
p
k
,
V
S
t
r
i
n
g
) as inputs. Finally, the verifier outputsValid if the server can convince it that σ is a valid signature on m. Otherwise, the verifier outputsInvalid.In a SA verification signature scheme, we assume that the verifier has a limited computational ability and is not able to perform all computations inVerify alone. So, a SA verification signature scheme must satisfy an important property called computation saving property, which requires that the computations performed by the verifier inSA-Verify must be less than those performed inVerify.


### 2.4.  Security Model for Server-Aided Verification Signature

In the following, we will first present the security model for SAV-Σ with message privacy. As for the existential unforgeability of SAV-Σ, we will adopt existential unforgeability of SAV-Σ defined in [15], including the existential unforgeability against adaptive chosen message attacks of Σ defined in [24] and the soundness against collusion and adaptive chosen message attacks ofSA-Verify. In the following, we will present the existential unforgeability of SAV-Σ as [15]. It requires that the adversary should not be (computationally) capable of producing a signature of a new message which can be proved as valid bySA-Verify, even if the adversary acts as a server.Definition 1 (existential unforgeability against adaptive chosen message attacks ofΣ).
The adversaryA and the challenger C play the following game. (i)
Setup. The challenger C runs the algorithmsParamGen andKeyGen to obtain system parameter p
a
r
a
m and one key pair (
s
k
,
p
k
). The adversary A is given p
a
r
a
m and p
k.
(ii)
Queries. The adversary A is allowed to make at most q
s sign queries. For each sign query m
i
∈
{
m
1
,
…
,
m
q
s
}, the challenger C returns  σ
i
=
S
i
g
n
(
p
a
r
a
m
,
m
i
,
s
k
,
p
k
) as the response.
(iii)
Output. Eventually, the adversary A outputs a pair (
m
*
,
σ
*
) and wins the game if:
(1)
m
*
∉
{
m
1
,
…
,
m
q
s
};
(2)
Verify
(
p
a
r
a
m
,
m
*
,
σ
*
,
p
k
) =Valid.
An adversaryA is said to (
t
,
q
s
,
ε
)-break a signature scheme Σ if A runs in time at most t and makes at most q
s signature queries and the success probability Σ
-
A
d
v
A to win the game above is at most ε.
We say thatΣ is existentially unforgeable against adaptive chosen message attacks if there exists an adversary that (
t
,
q
s
,
ε
)-breaks it.In the following, we will present the soundness against collusion and adaptive chosen message attacks ofSA-Verify which means that the server cannot prove an invalid signature to be valid even if it colludes with the signer.Definition 2 (soundness against collusion and adaptive chosen message attacks ofS
A
-
V
e
r
i
f
y).
The adversaryA and the challenger C play the following game. (i)
Setup. The challenger C runs the algorithmsParamGen,KeyGen, andSA-Verifier-Setup to obtain the system parameter p
a
r
a
m, one key pair (
s
k
,
p
k
) and VString. The adversary A is given p
a
r
a
m and (
s
k
,
p
k
).
(ii)
Queries. Proceeding adaptively, the adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, where the adversary A acts as the server and the challenger C acts as the verifier. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary A.
(iii)
Output. Eventually, the adversary A outputs a message m
*. The challenger C chooses a random invalid signature σ
* on the message m
*. Namely, it chooses a random element σ
* in Ω
∖
Ω
m
*, where Ω and Ω
m
* are, respectively, the signature space and the set of valid signatures of m
*. We say that A wins the game if(1)
S
A
-
V
e
r
i
f
y
A
,
C
m
*
,
σ
*
,
p
k
,
V
S
t
r
i
n
g
=
V
a
l
i
d
.
An adversaryA is said to (
t
,
q
v
,
ε
)-breakSA-Verify’s soundness against collusion and chosen message attacks if A runs in time at most t, makes at most q
v server-aided verification queries and the success probability Adv
A
E
U to win the game above is at least ε.We say thatSA-Verify is (
t
,
q
v
,
ε
)-sound against collusion and chosen message attacks if there exists no adversary that (
t
,
q
v
,
ε
)-breaks it.


## 2.1. Syntax

Throughout the paper, ifA is a randomized algorithm, then y
←
A
(
x
) denotes the assignment to y of the output of A on input x. Unless noted, all algorithms are probabilistic polynomial-time (PPT) and we implicitly assume that they take an extra parameter κ in their input, where κ is a security parameter.


## 2.2.  Bilinear Maps

LetG
1, G
T be two (multiplicative) cyclic groups such that |
G
1
|
=
|
G
T
|
=
p, where p is a large prime. Let g be a generator of G
1, and e be an admissible bilinear map: G
1
×
G
1
→
G
T, satisfying (
1
) for all a
,
b
∈
Z
p; it holds that e
(
g
a
,
g
b
)
=
e
(
g
,
g
)
a
b; (
2
)  e
(
g
,
g
)
≠
1; and (
3
) it is efficiently computable.We say that (G
1
,
G
T) are bilinear groups if there exists the bilinear map e
:
G
1
×
G
1
→
G
T as above, and the group action in G
1 and G
T can be computed efficiently. Such groups can be built from Weil pairing or Tate pairing on elliptic curves.


## 2.3.  Server-Aided Verification Signature

A server-aided verification signature scheme SAV-Σ consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify. The first four algorithms are the same as those in an ordinary signature scheme Σ. SAV-Σ contains three parties, respectively, a signer, a verifier, and a server.(i)
p
a
r
a
m
←
ParamGen. This algorithm takes a security parameter κ and returns a string p
a
r
a
m as input, which denotes the common scheme parameters, including the description of the message space M and the signature space Ω.
(ii)
(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
p
a
r
a
m
). This algorithm takes p
a
r
a
m as input and outputs a key pair (
p
k
,
s
k
), where s
k is the signing key and p
k is the verification key.
(iii)
σ
←
S
i
g
n
(
p
a
r
a
m
,
m
,
s
k
,
p
k
). The signer takes a message m
∈
M, the system parameter p
a
r
a
m and the key pair (
s
k
,
p
k
) as inputs, outputs a signature σ.
(iv)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
V
e
r
i
f
y
(
p
a
r
a
m
,
m
,
σ
,
p
k
). The verifier takes the parameter p
a
r
a
m, a message-signature pair (
m
,
σ
) and the public key p
k, outputsValid/Invalid to indicate that σ is a valid/invalid signature on m under p
k.
(v)
V
S
t
r
i
n
g
←
S
A
-
V
e
r
i
f
i
e
r
-
S
e
t
u
p
(
p
a
r
a
m
). The verifier takes as input the system parameter p
a
r
a
m and outputs a stringVString which contains the information which can be precomputed by it.
(vi)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
S
A
-
V
e
r
i
f
y
(
Server
p
a
r
a
m
,
Verifier
(
m
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
). This is an interactive protocol between the server and the verifier where the server takes p
a
r
a
m as input and the verifier takes (
m
,
σ
,
p
k
,
V
S
t
r
i
n
g
) as inputs. Finally, the verifier outputsValid if the server can convince it that σ is a valid signature on m. Otherwise, the verifier outputsInvalid.In a SA verification signature scheme, we assume that the verifier has a limited computational ability and is not able to perform all computations inVerify alone. So, a SA verification signature scheme must satisfy an important property called computation saving property, which requires that the computations performed by the verifier inSA-Verify must be less than those performed inVerify.


## 2.4.  Security Model for Server-Aided Verification Signature

In the following, we will first present the security model for SAV-Σ with message privacy. As for the existential unforgeability of SAV-Σ, we will adopt existential unforgeability of SAV-Σ defined in [15], including the existential unforgeability against adaptive chosen message attacks of Σ defined in [24] and the soundness against collusion and adaptive chosen message attacks ofSA-Verify. In the following, we will present the existential unforgeability of SAV-Σ as [15]. It requires that the adversary should not be (computationally) capable of producing a signature of a new message which can be proved as valid bySA-Verify, even if the adversary acts as a server.Definition 1 (existential unforgeability against adaptive chosen message attacks ofΣ).
The adversaryA and the challenger C play the following game. (i)
Setup. The challenger C runs the algorithmsParamGen andKeyGen to obtain system parameter p
a
r
a
m and one key pair (
s
k
,
p
k
). The adversary A is given p
a
r
a
m and p
k.
(ii)
Queries. The adversary A is allowed to make at most q
s sign queries. For each sign query m
i
∈
{
m
1
,
…
,
m
q
s
}, the challenger C returns  σ
i
=
S
i
g
n
(
p
a
r
a
m
,
m
i
,
s
k
,
p
k
) as the response.
(iii)
Output. Eventually, the adversary A outputs a pair (
m
*
,
σ
*
) and wins the game if:
(1)
m
*
∉
{
m
1
,
…
,
m
q
s
};
(2)
Verify
(
p
a
r
a
m
,
m
*
,
σ
*
,
p
k
) =Valid.
An adversaryA is said to (
t
,
q
s
,
ε
)-break a signature scheme Σ if A runs in time at most t and makes at most q
s signature queries and the success probability Σ
-
A
d
v
A to win the game above is at most ε.
We say thatΣ is existentially unforgeable against adaptive chosen message attacks if there exists an adversary that (
t
,
q
s
,
ε
)-breaks it.In the following, we will present the soundness against collusion and adaptive chosen message attacks ofSA-Verify which means that the server cannot prove an invalid signature to be valid even if it colludes with the signer.Definition 2 (soundness against collusion and adaptive chosen message attacks ofS
A
-
V
e
r
i
f
y).
The adversaryA and the challenger C play the following game. (i)
Setup. The challenger C runs the algorithmsParamGen,KeyGen, andSA-Verifier-Setup to obtain the system parameter p
a
r
a
m, one key pair (
s
k
,
p
k
) and VString. The adversary A is given p
a
r
a
m and (
s
k
,
p
k
).
(ii)
Queries. Proceeding adaptively, the adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, where the adversary A acts as the server and the challenger C acts as the verifier. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary A.
(iii)
Output. Eventually, the adversary A outputs a message m
*. The challenger C chooses a random invalid signature σ
* on the message m
*. Namely, it chooses a random element σ
* in Ω
∖
Ω
m
*, where Ω and Ω
m
* are, respectively, the signature space and the set of valid signatures of m
*. We say that A wins the game if(1)
S
A
-
V
e
r
i
f
y
A
,
C
m
*
,
σ
*
,
p
k
,
V
S
t
r
i
n
g
=
V
a
l
i
d
.
An adversaryA is said to (
t
,
q
v
,
ε
)-breakSA-Verify’s soundness against collusion and chosen message attacks if A runs in time at most t, makes at most q
v server-aided verification queries and the success probability Adv
A
E
U to win the game above is at least ε.We say thatSA-Verify is (
t
,
q
v
,
ε
)-sound against collusion and chosen message attacks if there exists no adversary that (
t
,
q
v
,
ε
)-breaks it.


## 3. Server-Aided Verification Signature with Message Privacy

In this section, we will present the definition of message privacy forSA-Verify, and then, based on Waters signature scheme [21], present a concrete server-aided verification scheme with this privacy property. This privacy property is calledmessage privacy against collusion and adaptive chosen message attacks. In this definition, the server is allowed to collude with the signer. Concretely, the server can obtain the key pair (
p
k
,
s
k
) of the signer and therefore can create the signature on any message. In addition, we will assume that the server cannot obtain the message-signature pairs that have been created by the signer before, alternatively, the signer will not store any message-signature pair that it has created. (Actually, this can be achieved by performing blind signature scheme presented in [25] between the signer and the verifier instead of performing the ordinary signature scheme. After the blind signature scheme, the verifier can obtain the ordinary message-signature pair without the signer learning anything about this pair. Then the verifier lets the server to verify the message-signature pair by performingSA-Verify. In this sense, even if the server colludes with the signer, it cannot obtain more information about the signed messages from the signer than it can obtain on its own. To clarify our privacy definition below more clearly, we simply assume that the server cannot obtain any message-signature pair which the signer has created for the verifier before.)


### 3.1. Definition of Message Privacy

A server-aided verification signature scheme with message privacy SAV-Σ also consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify. The following is the definition of message privacy for the server-aided verification protocol under the collusion and adaptive chosen message attacks. In this definition, the server cannot obtain any information about the message to be verified under the collusion and adaptive chosen message attacks.Definition 3 (message privacy ofS
A
-
V
e
r
i
f
y).
We say thatSA-Verify satisfies (
t
,
q
v
,
ε
)-message privacy against collusion and adaptive chosen message attacks if there exists no adversary A who runs in time at most t, makes at most q
v server-aided verification queries, and succeeds with probability at least ε in the following game with the challenger C. The game is defined as follows. (i)
Setup. The challenger C runs the algorithmsParamGen,KeyGen andSA-Verifier-Setup to obtain system parameterparam, one key pair (
s
k
,
p
k
), and VString. The adversary A is givenparam and (
s
k
,
p
k
). Note that A can generate any message-signature pair with the secret-public key pair (
s
k
,
p
k
); however as we assumed, it cannot obtain any message-signature pair that has been created by the signer before.
(ii)
Queries. Proceeding adaptively, the adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, where the adversary A acts as the server and the challenger C acts as the verifier. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary A.
(iii)
Challenge. A outputs two messages m
0, m
1, and sends them to the challenger C. C chooses a bit b
∈
{
0,1
} at random and also chooses an element σ either randomly from Ω
m
0 or randomly from Ω
m
1, where Ω
m
0 and Ω
m
1 are, respectively, the signature space of m
0 and m
1. Then C and A interact with each other by runningSA-Verify
(
A
,
C
(
m
b
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
), where A plays as a server and C plays as a verifier. After the interaction, C sends the output ofSA-Verify
(
A
,
C
(
m
b
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
) to A.
(iv)
Output. Finally, A outputs a bit b
′
∈
{
0,1
}. We say that A wins the game with probability ε if(2)
Pr
⁡
[
b
=
b
′
]
≥
ε
.Similar to Wu et al. [15], in the protocol Setup of the game above,VString is not provided to the adversary who now is acting as a server sinceVString might contain some private information of the verifier, which must be kept secret in server-aided verification signatures. In the definition, adversary A acts as the server and the challenger C acts as the verifier which will help A to extract some information fromVString.


### 3.2.  Concrete SA Verification Signature with Message Privacy

In the following, we will first present a concrete SA verification signature scheme with message privacy based on Waters signature [21]. The SA verification signature scheme with message privacy SAV-Σ consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify. The first four algorithms are the same as those in Waters signature scheme [21]. As we know that, due to the elegant properties of pairing computation on elliptic curves, pairing has been widely employed as a building block for lots of cryptographic schemes, in particular in the construction of digital signatures. However, performing a pairing on an elliptic curve requires much more computational cost than executing both an exponentiation and a multiplication [16, 26–30], and for a power-constrained verifier who must execute multiple pairing computations during the verification of a message-signature pair, reducing the computational load of it is a meaningful task. In Waters signature [21], the verifier has to compute two pairings; however in SAV-Σ, its computational load is reduced and it will not compute any pairing. The concrete SA verification signature with message privacy based on Waters signature is described in detail as follows.(i)
p
a
r
a
m
←
ParamGen. Let κ be a security parameter, (
G
1
,
G
T
) be bilinear groups where |
G
1
|
=
|
G
T
|
=
p for some prime number p
≥
2
κ and g be a generator of G
1. e
:
G
1
×
G
1
→
G
T is a bilinear mapping. The system parameters are p
a
r
a
m
=
(
κ
,
G
1
,
G
T
,
p
,
g
,
e
) and the message space is M
=
{
0,1
}
n.
(ii)
(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
p
a
r
a
m
). Given the system parameters (
κ
,
G
1
,
G
T
,
p
,
g
,
e
), the signer chooses a random element x
∈
Z
p, generates the public key p
k as (
V
→
,
P
K
) and s
k
=
x where V
→ is a vector consisting of n
+
1 elements V
0
,
V
1
,
…
,
V
n randomly selected in G
1 and P
K
=
e
(
g
,
g
)
x.
(iii)
σ
←
S
i
g
n
(
p
a
r
a
m
,
m
,
s
k
,
p
k
). For an n-bit message m
∈
{
0,1
}
n, let M
⊆
{
1,2
,
…
,
n
} be the set of all i for which the ith bit of m is 1. The signer selects a random element t
∈
Z
p and generates the signature σ as (
σ
1
,
σ
2
)
=
(
g
x
(
V
0
∏
i
∈
M
‍
V
i
)
t
,
g
t
).
(iv)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
V
e
r
i
f
y
(
p
a
r
a
m
,
m
,
σ
,
p
k
). The verifier takes as input a claimed message-signature pair (
m
,
σ
), and outputs Valid if and only if e
(
σ
1
,
g
)
=
P
K
·
e
(
V
0
∏
i
∈
M
‍
V
i
,
σ
2
). Otherwise it outputs Invalid.
(v)
V
S
t
r
i
n
g
←
S
A
-
V
e
r
i
f
y-Setup
(
p
a
r
a
m
). The verifier takes as inputs the system parameters (
κ
,
G
1
,
G
T
,
p
,
g
,
e
) and computes K
1
=
e
(
g
,
g
) asVString.
(vi)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
S
A
-
V
e
r
i
f
y
(
Server
(
p
a
r
a
m
)
,
Verifier
(
m
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
). This is an interactive protocol between the server and the verifier which is shown in Algorithm 1.
(1)
Verifier, for a message-signature pair(
m
,
σ
=
(
σ
1
,
σ
2
)
) to be verified, first computes M
=
V
0
∏
i
∈
M
‍
V
i; then selects randomly r
,
d
∈
Z
p
*, and blinds the message by computing M
′
=
M
·
g
r, σ
1
′
=
σ
1
·
g
d
·
σ
2
r; finally sends (
M
′
,
σ
1
′
,
σ
2
) to the verifier.
(2)
Server computesK
2
=
e
(
σ
1
′
,
g
), K
3
=
e
(
M
′
,
σ
2
) and returns K
2
,
K
3 to the verifier.
(3)
Verifier checks the equationK
2
=
K
3
·
P
K
·
K
1
d, and outputsValid if it holds, and otherwise outputsInvalid.Algorithm 1:
S
A
-
V
e
r
i
f
y with message privacy based on Waters signature.
Verifier (param, K
1)        Server (param)
Input: (m, σ = (σ
1, σ
2)), pk = (V
→, PK)
M = V
0
∏
i
∈
M
V
i,
r
,
d
∈
R
Z
p
*, M
′ = M
·
g
r
,
σ
1
′
=
σ
1
·
g
d
·
σ
2
r
→
M
′
,
σ
1
′
,
σ
2
K
2 = e
(
σ
1
′, g
),
K
3 = e
(
M
′, σ
2)
←
K
2
,
K
3
Output:
V
a
l
i
d, if K
2 = K
3
·
P
K
·
K
1
d;
I
n
v
a
l
i
d, if otherwise.Correctness of
S
A
-
V
e
r
i
f
y. For a claimed message-signature pair (
m
,
σ
), when the verifier and the server are both honest, namely, the verifier correctly computes M
′ and σ
1
′ and the server correctly computes K
2 and K
3, then the verification equation K
2
=
P
K
·
K
3
·
K
1
d holds if the message-signature pair (
m
,
σ
) is valid and otherwise does not hold. In the following, we denote (
σ
1
,
σ
2
)
=
(
g
x
(
V
0
∏
i
∈
M
‍
V
i
)
t
,
g
t
):(3)
K
2
=
e
σ
1
′
,
g
=
e
σ
1
,
g
·
e
g
,
g
d
·
e
σ
2
r
,
g
=
e
M
,
g
t
·
P
K
·
K
1
d
·
e
g
t
r
,
g
=
e
M
·
g
r
,
g
t
·
P
K
·
K
1
d
=
e
M
′
,
σ
2
·
P
K
·
K
1
d
=
K
3
·
P
K
·
K
1
d
.In the following, by Theorems4 and 5, we will show that our SA verification signature scheme above is secure under our security model; namely, the SA verification protocol described in Algorithm 1 is sound against collusion and adaptive chosen message attacks and also satisfies message privacy against collusion and adaptive chosen message attacks.Since Waters signature scheme has been proved existentially unforgeable against adaptive chosen message attacks, in order to prove that our SA verification signature scheme above is secure, we need only to prove that the SA verification protocol described in Algorithm1 satisfies soundness against collusion and adaptive chosen message attacks defined in Definition 2 and message privacy against collusion and adaptive chosen message attacks.Theorem 4.
The SA verification protocol described in Algorithm1 satisfies (
t
,
q
v
,
1
/
p
-
1
)-soundness against collusion and adaptive chosen message attacks.Proof.
In order to prove that the SA verification protocol in Algorithm1 is (
t
,
q
v
,
1
/
p
-
1
)-sound against collusion and adaptive chosen message attacks, we will show that the adversary can only prove an invalid signature as valid with at most probability 1
/
p
-
1. The challenger and the adversary play the following game.(i)
Setup. The challenger generates the system parameters (
κ
,
G
1
,
G
T
,
p
,
g
,
e
), chooses a random element x
∈
Z
p, and sets s
k
=
x and p
k
=
(
V
→
,
P
K
) where V
→ is a vector consisting of n
+
1 elements V
0
,
V
1
,
…
,
V
n randomly selected in G
1 and P
K
=
e
(
g
,
g
)
x. Then it also computes K
1
=
e
(
g
,
g
). Finally the challenger sends (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
s
k
,
p
k
) to the adversary.
(ii)
Queries. The adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, where the adversary A acts as the server and the challenger C acts as the verifier. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary A.
(iii)
Output. Eventually, the adversary A outputs a message m
*. The challenger C chooses a random element σ
*
=
(
σ
1
,
σ
2
) in G
1
2
∖
Ω
m
*, where Ω and Ω
m
* are, respectively, the signature space and the set of valid signatures of m
*. Then they interact with each other as described in theSA-Verify protocol. Concretely, the challenger chooses two random elements r
*
,
d
*
∈
Z
p
*, computes M
=
V
0
∏
i
∈
M
‍
V
i, M
′
=
M
·
g
r
* and σ
1
′
=
σ
1
·
g
d
*
·
σ
2
r
*, and sends (
M
′
,
σ
1
′
,
σ
2
) to the adversary. Then the adversary returns K
2
* and K
3
* to the challenger.
In the following, we will show thatK
2
*
=
K
3
*
·
P
K
·
K
1
d
* happens with probability 1
/
p
-
1.
The challenger sends(
M
′
,
σ
1
′
,
σ
2
) to A such that(4)
M
′
=
M
·
g
r
*
,
σ
1
′
=
σ
1
·
g
d
*
·
σ
2
r
*
⇓
(5)
D
L
g
M
′
=
D
L
g
M
+
r
*
,
D
L
g
σ
1
′
=
D
L
g
σ
1
+
d
*
+
D
L
g
σ
2
·
r
*
.
Since the adversary can only obtain(
M
′
,
σ
1
′
,
σ
2
) from the challenger, from the equation set (5), we can see that the adversary can only obtain d
* with probability 1
/
p
-
1. Furthermore, from (6) below, we can directly deduce (7) as follows:(6)
K
2
*
=
K
3
*
·
P
K
·
K
1
d
*
⇓
(7)
D
L
e
g
,
g
K
2
*
K
3
*
=
D
L
e
(
g
,
g
)
P
K
+
d
*
.
Since the adversary can only guessd
* with probability 1
/
(
p
-
1
), and (
K
2
*
/
K
3
*
) is uniquely determined by d
*, the adversary can only give out a pair (
K
2
*
,
K
3
*
) satisfying (6) with probabitity 1
/
(
p
-
1
). This completes the proof of Theorem 4.Theorem 5.
The SA verification protocol in Algorithm1 satisfies (
t
,
q
v
,
1
/
2
)-message privacy against collusion and adaptive chosen message attacks.Proof.
In order to prove that the SA verification protocol in Algorithm1 satisfies (
t
,
q
v
,
1
/
2
)-message privacy against collusion and adaptive chosen message attacks, we will show that the adversary can only succeed with at most the probability 1
/
2 in the game with the challenger described as follows.(i)
Setup. The challenger generates the system parameter (
κ
,
G
1
,
G
T
,
p
,
g
,
e
), and the secret key s
k
=
x and public key p
k
=
(
V
→
,
P
K
), where V
→ is a vector consisting of n
+
1 elements V
0
,
V
1
,
…
,
V
n randomly selected in G
1 and P
K
=
e
(
g
,
g
)
x. Then it also computes K
1
=
e
(
g
,
g
). Finally the challenger sends (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
s
k
,
p
k
) to the adversary.
(ii)
Queries. The adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, and, at the end of each execution, returns the output ofSA-Verify to the adversary A.
(iii)
Challenge. A outputs two messages m
0 and m
1 and sends them to the challenger C. C chooses a bit b
∈
{
0,1
} at random and also chooses σ
=
(
σ
1
,
σ
2
) either randomly from Ω
m
0 or randomly from Ω
m
1, where Ω
m
0 and Ω
m
1 are, respectively, the signature spaces of m
0 and m
1. Then C and A interact with each other by running S
A
-
V
e
r
i
f
y
(
A
,
C
(
m
b
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
), where A plays as a server and C plays as a verifier. Concretely, the challenger chooses two random elements r
*
,
d
*
∈
Z
p
*, computes M
=
V
0
∏
i
∈
M
‍
V
i, M
′
=
M
·
g
r
*, and σ
1
′
=
σ
1
·
g
d
*
·
σ
2
r
*, and sends (
M
′
,
σ
1
′
,
σ
2
) to the adversary. Then the adversary returns K
2
* and K
3
* to the challenger. After the interaction, C sends the output ofSA-Verify(
A
,
C
(
m
b
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
) to A.
(iv)
Output. Finally, A outputs a bit b
′
∈
{
0,1
}. We will show that A can only succeed with probability 1
/
2.
From the equation set (5) in the proof of Theorem 4, we can see that there exist two pairs (
M
0
,
r
0
*
) and (
M
1
,
r
1
*
) satisfying M
′
=
M
b
·
g
r
b
* for b
=
0,1, and for each r
b
*, there exist p
-
1 pairs (
σ
1
,
d
*
) satisfying σ
1
′
=
σ
1
·
g
d
*
·
σ
2
r
b
* for b
=
0,1. So the adversary cannot obtain anything about (
M
,
σ
1
). Though the adversary learns σ
2 which may correspond to m
0 or m
1, it only guess b correctly with probability 1
/
2. This completes the proof of Theorem 4.Efficiency Analysis. The SA verification signature with privacy based on Waters signature above is computation saving and efficient. In the following, we will analyze the efficiency ofSA-Verify algorithm by comparing that of Waters signature scheme. In Waters signature scheme [21], to verify a message-signature pair (
m
,
σ
=
(
σ
1
,
σ
2
)
), the verifier needs to compute M
=
V
0
∏
i
∈
M
‍
V
i which takes n multiplications in G
1, P
K
·
e
(
m
,
σ
2
) which takes 1 multiplication in G
T, and two pairings e
(
m
,
σ
2
) and e
(
σ
1
,
g
). However, in our server-aided verification signature scheme, the verifier can first precompute a pairing e
(
g
,
g
) which can be used by multipleSA-Verify protocols. Then in aSA-Verify protocol, we can see that the verifier needs to compute totally 3 exponentiations in G
1 and 1 exponentiation in G
T as well as 3
+
n multiplications in G
1 and 3 multiplications in G
T. As we know that, performing a pairing on an elliptic curve requires much more computational cost than executing both an exponentiation and a multiplication. So our SA verification signature scheme based on Waters signature is computation saving and efficient.The concrete computation cost comparison of the verifier in the verification of Waters Signature [21] and ourSA-Verify in Algorithm 1 is shown in Table 1.Table 1
Efficiency of the SA verification signature scheme.
Verification
Pairing
Exponentiation
Multiplication
Waters [21]
2
0
n
(
G
1)
Our Scheme
0
3
(
G
1
)
+
1
(
G
T
)
(
3
+
n
)
(
G
1
)
+
3
(
G
T
)


## 3.1. Definition of Message Privacy

A server-aided verification signature scheme with message privacy SAV-Σ also consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify. The following is the definition of message privacy for the server-aided verification protocol under the collusion and adaptive chosen message attacks. In this definition, the server cannot obtain any information about the message to be verified under the collusion and adaptive chosen message attacks.Definition 3 (message privacy ofS
A
-
V
e
r
i
f
y).
We say thatSA-Verify satisfies (
t
,
q
v
,
ε
)-message privacy against collusion and adaptive chosen message attacks if there exists no adversary A who runs in time at most t, makes at most q
v server-aided verification queries, and succeeds with probability at least ε in the following game with the challenger C. The game is defined as follows. (i)
Setup. The challenger C runs the algorithmsParamGen,KeyGen andSA-Verifier-Setup to obtain system parameterparam, one key pair (
s
k
,
p
k
), and VString. The adversary A is givenparam and (
s
k
,
p
k
). Note that A can generate any message-signature pair with the secret-public key pair (
s
k
,
p
k
); however as we assumed, it cannot obtain any message-signature pair that has been created by the signer before.
(ii)
Queries. Proceeding adaptively, the adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, where the adversary A acts as the server and the challenger C acts as the verifier. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary A.
(iii)
Challenge. A outputs two messages m
0, m
1, and sends them to the challenger C. C chooses a bit b
∈
{
0,1
} at random and also chooses an element σ either randomly from Ω
m
0 or randomly from Ω
m
1, where Ω
m
0 and Ω
m
1 are, respectively, the signature space of m
0 and m
1. Then C and A interact with each other by runningSA-Verify
(
A
,
C
(
m
b
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
), where A plays as a server and C plays as a verifier. After the interaction, C sends the output ofSA-Verify
(
A
,
C
(
m
b
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
) to A.
(iv)
Output. Finally, A outputs a bit b
′
∈
{
0,1
}. We say that A wins the game with probability ε if(2)
Pr
⁡
[
b
=
b
′
]
≥
ε
.Similar to Wu et al. [15], in the protocol Setup of the game above,VString is not provided to the adversary who now is acting as a server sinceVString might contain some private information of the verifier, which must be kept secret in server-aided verification signatures. In the definition, adversary A acts as the server and the challenger C acts as the verifier which will help A to extract some information fromVString.


## 3.2.  Concrete SA Verification Signature with Message Privacy

In the following, we will first present a concrete SA verification signature scheme with message privacy based on Waters signature [21]. The SA verification signature scheme with message privacy SAV-Σ consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify. The first four algorithms are the same as those in Waters signature scheme [21]. As we know that, due to the elegant properties of pairing computation on elliptic curves, pairing has been widely employed as a building block for lots of cryptographic schemes, in particular in the construction of digital signatures. However, performing a pairing on an elliptic curve requires much more computational cost than executing both an exponentiation and a multiplication [16, 26–30], and for a power-constrained verifier who must execute multiple pairing computations during the verification of a message-signature pair, reducing the computational load of it is a meaningful task. In Waters signature [21], the verifier has to compute two pairings; however in SAV-Σ, its computational load is reduced and it will not compute any pairing. The concrete SA verification signature with message privacy based on Waters signature is described in detail as follows.(i)
p
a
r
a
m
←
ParamGen. Let κ be a security parameter, (
G
1
,
G
T
) be bilinear groups where |
G
1
|
=
|
G
T
|
=
p for some prime number p
≥
2
κ and g be a generator of G
1. e
:
G
1
×
G
1
→
G
T is a bilinear mapping. The system parameters are p
a
r
a
m
=
(
κ
,
G
1
,
G
T
,
p
,
g
,
e
) and the message space is M
=
{
0,1
}
n.
(ii)
(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
p
a
r
a
m
). Given the system parameters (
κ
,
G
1
,
G
T
,
p
,
g
,
e
), the signer chooses a random element x
∈
Z
p, generates the public key p
k as (
V
→
,
P
K
) and s
k
=
x where V
→ is a vector consisting of n
+
1 elements V
0
,
V
1
,
…
,
V
n randomly selected in G
1 and P
K
=
e
(
g
,
g
)
x.
(iii)
σ
←
S
i
g
n
(
p
a
r
a
m
,
m
,
s
k
,
p
k
). For an n-bit message m
∈
{
0,1
}
n, let M
⊆
{
1,2
,
…
,
n
} be the set of all i for which the ith bit of m is 1. The signer selects a random element t
∈
Z
p and generates the signature σ as (
σ
1
,
σ
2
)
=
(
g
x
(
V
0
∏
i
∈
M
‍
V
i
)
t
,
g
t
).
(iv)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
V
e
r
i
f
y
(
p
a
r
a
m
,
m
,
σ
,
p
k
). The verifier takes as input a claimed message-signature pair (
m
,
σ
), and outputs Valid if and only if e
(
σ
1
,
g
)
=
P
K
·
e
(
V
0
∏
i
∈
M
‍
V
i
,
σ
2
). Otherwise it outputs Invalid.
(v)
V
S
t
r
i
n
g
←
S
A
-
V
e
r
i
f
y-Setup
(
p
a
r
a
m
). The verifier takes as inputs the system parameters (
κ
,
G
1
,
G
T
,
p
,
g
,
e
) and computes K
1
=
e
(
g
,
g
) asVString.
(vi)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
S
A
-
V
e
r
i
f
y
(
Server
(
p
a
r
a
m
)
,
Verifier
(
m
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
). This is an interactive protocol between the server and the verifier which is shown in Algorithm 1.
(1)
Verifier, for a message-signature pair(
m
,
σ
=
(
σ
1
,
σ
2
)
) to be verified, first computes M
=
V
0
∏
i
∈
M
‍
V
i; then selects randomly r
,
d
∈
Z
p
*, and blinds the message by computing M
′
=
M
·
g
r, σ
1
′
=
σ
1
·
g
d
·
σ
2
r; finally sends (
M
′
,
σ
1
′
,
σ
2
) to the verifier.
(2)
Server computesK
2
=
e
(
σ
1
′
,
g
), K
3
=
e
(
M
′
,
σ
2
) and returns K
2
,
K
3 to the verifier.
(3)
Verifier checks the equationK
2
=
K
3
·
P
K
·
K
1
d, and outputsValid if it holds, and otherwise outputsInvalid.Algorithm 1:
S
A
-
V
e
r
i
f
y with message privacy based on Waters signature.
Verifier (param, K
1)        Server (param)
Input: (m, σ = (σ
1, σ
2)), pk = (V
→, PK)
M = V
0
∏
i
∈
M
V
i,
r
,
d
∈
R
Z
p
*, M
′ = M
·
g
r
,
σ
1
′
=
σ
1
·
g
d
·
σ
2
r
→
M
′
,
σ
1
′
,
σ
2
K
2 = e
(
σ
1
′, g
),
K
3 = e
(
M
′, σ
2)
←
K
2
,
K
3
Output:
V
a
l
i
d, if K
2 = K
3
·
P
K
·
K
1
d;
I
n
v
a
l
i
d, if otherwise.Correctness of
S
A
-
V
e
r
i
f
y. For a claimed message-signature pair (
m
,
σ
), when the verifier and the server are both honest, namely, the verifier correctly computes M
′ and σ
1
′ and the server correctly computes K
2 and K
3, then the verification equation K
2
=
P
K
·
K
3
·
K
1
d holds if the message-signature pair (
m
,
σ
) is valid and otherwise does not hold. In the following, we denote (
σ
1
,
σ
2
)
=
(
g
x
(
V
0
∏
i
∈
M
‍
V
i
)
t
,
g
t
):(3)
K
2
=
e
σ
1
′
,
g
=
e
σ
1
,
g
·
e
g
,
g
d
·
e
σ
2
r
,
g
=
e
M
,
g
t
·
P
K
·
K
1
d
·
e
g
t
r
,
g
=
e
M
·
g
r
,
g
t
·
P
K
·
K
1
d
=
e
M
′
,
σ
2
·
P
K
·
K
1
d
=
K
3
·
P
K
·
K
1
d
.In the following, by Theorems4 and 5, we will show that our SA verification signature scheme above is secure under our security model; namely, the SA verification protocol described in Algorithm 1 is sound against collusion and adaptive chosen message attacks and also satisfies message privacy against collusion and adaptive chosen message attacks.Since Waters signature scheme has been proved existentially unforgeable against adaptive chosen message attacks, in order to prove that our SA verification signature scheme above is secure, we need only to prove that the SA verification protocol described in Algorithm1 satisfies soundness against collusion and adaptive chosen message attacks defined in Definition 2 and message privacy against collusion and adaptive chosen message attacks.Theorem 4.
The SA verification protocol described in Algorithm1 satisfies (
t
,
q
v
,
1
/
p
-
1
)-soundness against collusion and adaptive chosen message attacks.Proof.
In order to prove that the SA verification protocol in Algorithm1 is (
t
,
q
v
,
1
/
p
-
1
)-sound against collusion and adaptive chosen message attacks, we will show that the adversary can only prove an invalid signature as valid with at most probability 1
/
p
-
1. The challenger and the adversary play the following game.(i)
Setup. The challenger generates the system parameters (
κ
,
G
1
,
G
T
,
p
,
g
,
e
), chooses a random element x
∈
Z
p, and sets s
k
=
x and p
k
=
(
V
→
,
P
K
) where V
→ is a vector consisting of n
+
1 elements V
0
,
V
1
,
…
,
V
n randomly selected in G
1 and P
K
=
e
(
g
,
g
)
x. Then it also computes K
1
=
e
(
g
,
g
). Finally the challenger sends (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
s
k
,
p
k
) to the adversary.
(ii)
Queries. The adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, where the adversary A acts as the server and the challenger C acts as the verifier. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary A.
(iii)
Output. Eventually, the adversary A outputs a message m
*. The challenger C chooses a random element σ
*
=
(
σ
1
,
σ
2
) in G
1
2
∖
Ω
m
*, where Ω and Ω
m
* are, respectively, the signature space and the set of valid signatures of m
*. Then they interact with each other as described in theSA-Verify protocol. Concretely, the challenger chooses two random elements r
*
,
d
*
∈
Z
p
*, computes M
=
V
0
∏
i
∈
M
‍
V
i, M
′
=
M
·
g
r
* and σ
1
′
=
σ
1
·
g
d
*
·
σ
2
r
*, and sends (
M
′
,
σ
1
′
,
σ
2
) to the adversary. Then the adversary returns K
2
* and K
3
* to the challenger.
In the following, we will show thatK
2
*
=
K
3
*
·
P
K
·
K
1
d
* happens with probability 1
/
p
-
1.
The challenger sends(
M
′
,
σ
1
′
,
σ
2
) to A such that(4)
M
′
=
M
·
g
r
*
,
σ
1
′
=
σ
1
·
g
d
*
·
σ
2
r
*
⇓
(5)
D
L
g
M
′
=
D
L
g
M
+
r
*
,
D
L
g
σ
1
′
=
D
L
g
σ
1
+
d
*
+
D
L
g
σ
2
·
r
*
.
Since the adversary can only obtain(
M
′
,
σ
1
′
,
σ
2
) from the challenger, from the equation set (5), we can see that the adversary can only obtain d
* with probability 1
/
p
-
1. Furthermore, from (6) below, we can directly deduce (7) as follows:(6)
K
2
*
=
K
3
*
·
P
K
·
K
1
d
*
⇓
(7)
D
L
e
g
,
g
K
2
*
K
3
*
=
D
L
e
(
g
,
g
)
P
K
+
d
*
.
Since the adversary can only guessd
* with probability 1
/
(
p
-
1
), and (
K
2
*
/
K
3
*
) is uniquely determined by d
*, the adversary can only give out a pair (
K
2
*
,
K
3
*
) satisfying (6) with probabitity 1
/
(
p
-
1
). This completes the proof of Theorem 4.Theorem 5.
The SA verification protocol in Algorithm1 satisfies (
t
,
q
v
,
1
/
2
)-message privacy against collusion and adaptive chosen message attacks.Proof.
In order to prove that the SA verification protocol in Algorithm1 satisfies (
t
,
q
v
,
1
/
2
)-message privacy against collusion and adaptive chosen message attacks, we will show that the adversary can only succeed with at most the probability 1
/
2 in the game with the challenger described as follows.(i)
Setup. The challenger generates the system parameter (
κ
,
G
1
,
G
T
,
p
,
g
,
e
), and the secret key s
k
=
x and public key p
k
=
(
V
→
,
P
K
), where V
→ is a vector consisting of n
+
1 elements V
0
,
V
1
,
…
,
V
n randomly selected in G
1 and P
K
=
e
(
g
,
g
)
x. Then it also computes K
1
=
e
(
g
,
g
). Finally the challenger sends (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
s
k
,
p
k
) to the adversary.
(ii)
Queries. The adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, and, at the end of each execution, returns the output ofSA-Verify to the adversary A.
(iii)
Challenge. A outputs two messages m
0 and m
1 and sends them to the challenger C. C chooses a bit b
∈
{
0,1
} at random and also chooses σ
=
(
σ
1
,
σ
2
) either randomly from Ω
m
0 or randomly from Ω
m
1, where Ω
m
0 and Ω
m
1 are, respectively, the signature spaces of m
0 and m
1. Then C and A interact with each other by running S
A
-
V
e
r
i
f
y
(
A
,
C
(
m
b
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
), where A plays as a server and C plays as a verifier. Concretely, the challenger chooses two random elements r
*
,
d
*
∈
Z
p
*, computes M
=
V
0
∏
i
∈
M
‍
V
i, M
′
=
M
·
g
r
*, and σ
1
′
=
σ
1
·
g
d
*
·
σ
2
r
*, and sends (
M
′
,
σ
1
′
,
σ
2
) to the adversary. Then the adversary returns K
2
* and K
3
* to the challenger. After the interaction, C sends the output ofSA-Verify(
A
,
C
(
m
b
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
) to A.
(iv)
Output. Finally, A outputs a bit b
′
∈
{
0,1
}. We will show that A can only succeed with probability 1
/
2.
From the equation set (5) in the proof of Theorem 4, we can see that there exist two pairs (
M
0
,
r
0
*
) and (
M
1
,
r
1
*
) satisfying M
′
=
M
b
·
g
r
b
* for b
=
0,1, and for each r
b
*, there exist p
-
1 pairs (
σ
1
,
d
*
) satisfying σ
1
′
=
σ
1
·
g
d
*
·
σ
2
r
b
* for b
=
0,1. So the adversary cannot obtain anything about (
M
,
σ
1
). Though the adversary learns σ
2 which may correspond to m
0 or m
1, it only guess b correctly with probability 1
/
2. This completes the proof of Theorem 4.Efficiency Analysis. The SA verification signature with privacy based on Waters signature above is computation saving and efficient. In the following, we will analyze the efficiency ofSA-Verify algorithm by comparing that of Waters signature scheme. In Waters signature scheme [21], to verify a message-signature pair (
m
,
σ
=
(
σ
1
,
σ
2
)
), the verifier needs to compute M
=
V
0
∏
i
∈
M
‍
V
i which takes n multiplications in G
1, P
K
·
e
(
m
,
σ
2
) which takes 1 multiplication in G
T, and two pairings e
(
m
,
σ
2
) and e
(
σ
1
,
g
). However, in our server-aided verification signature scheme, the verifier can first precompute a pairing e
(
g
,
g
) which can be used by multipleSA-Verify protocols. Then in aSA-Verify protocol, we can see that the verifier needs to compute totally 3 exponentiations in G
1 and 1 exponentiation in G
T as well as 3
+
n multiplications in G
1 and 3 multiplications in G
T. As we know that, performing a pairing on an elliptic curve requires much more computational cost than executing both an exponentiation and a multiplication. So our SA verification signature scheme based on Waters signature is computation saving and efficient.The concrete computation cost comparison of the verifier in the verification of Waters Signature [21] and ourSA-Verify in Algorithm 1 is shown in Table 1.Table 1
Efficiency of the SA verification signature scheme.
Verification
Pairing
Exponentiation
Multiplication
Waters [21]
2
0
n
(
G
1)
Our Scheme
0
3
(
G
1
)
+
1
(
G
T
)
(
3
+
n
)
(
G
1
)
+
3
(
G
T
)


## 4. Server-Aided Verification Signature with Message-Signature Privacy

In this section, we will present a stronger definition of privacy, namely, message-signature privacy against collusion and adaptive chosen message attacks. Then based on BLS signature scheme [18], a concrete server-aided verification scheme with this privacy property will be presented. We assume that the server can obtain the key pair (
p
k
,
s
k
) of the signer and cannot obtain the message-signature pairs that have been created by the signer. Under this assumption, the server cannot obtain anything about the message-signature pair.


### 4.1. Definition of Message-Signature Privacy

A server-aided verification signature scheme with message-signature privacy SAV-Σ also consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify.Definition 6 (message-signature privacy ofS
A
-
V
e
r
i
f
y).
We say thatSA-Verify satisfies (
t
,
q
v
,
ε
)-message-signature privacy against collusion and adaptive chosen message attacks if there exists no adversary A who runs in time at most t, makes at most q
v server-aided verification queries, and succeeds with probability at least ε in the following game with the challenger C. The game is defined as follows. (i)
Setup. The challenger C runs the algorithmsParamGen,KeyGen, andSA-Verifier-Setup to obtain the system parameter p
a
r
a
m, one key pair (
s
k
,
p
k
), andVString. The adversary A is given p
a
r
a
m and (
s
k
,
p
k
). Similar to the definition of message privacy for SA verification signature, A can generate any message-signature pair with the key pair (
s
k
,
p
k
); however as we assumed, it cannot obtain any message-signature pair that has been created by the signer before.
(ii)
Queries. Proceeding adaptively, the adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, where the adversary A acts as the server and the challenger C acts as the verifier. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary A.
(iii)
Challenge. A outputs two pairs (
M
0
,
σ
0
) and (
M
1
,
σ
1
), where σ
i is a valid signature on M
i for i
=
1,2. Then A sends them to the challenger C. C chooses a bit b
∈
{
0,1
} at random and interacts with A by runningSA-Verify(
A
,
C
(
M
b
,
σ
b
,
p
k
,
V
S
t
r
i
n
g
)
) where A plays as a server and C plays as a verifier. After the interaction, C sends the output ofSA-Verify(
A
,
C
(
M
b
,
σ
b
,
p
k
,
V
S
t
r
i
n
g
)
) to A.
(iv)
Output. Finally, A outputs a bit b
′
∈
{
0,1
}. We say that A wins the game with probability ε if(8)
Pr
⁡
b
=
b
′
≥
ε
.


### 4.2. Concrete SA Verification Signature with Message-Signature Privacy

In this section, we will present a SA verification signature scheme which satisfies message-signature privacy against collusion and adaptive chosen message attacks. This scheme is constructed based on BLS signature [18], which also consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify. The first four algorithms are the same as those in BLS signature scheme [18]. By executing theSA-Verifier-Setup andSA-Verifyalgorithms, the computational load of the verifier can be reduced. In BLS signature [18], the verifier has to compute two pairings; however in the following SAV-Σ, it needs only to compute a pairing.(i)
p
a
r
a
m
←
ParamGen. Let κ be a security parameter, (
G
1
,
G
T
) be bilinear groups, where |
G
1
|
=
|
G
T
|
=
p for some prime number p
≥
2
κ, and g be a generator of G
1. e
:
G
1
×
G
1
→
G
T is a bilinear mapping. H
:
{
0,1
}
*
→
G
1 is a hash function. The system parameter p
a
r
a
m
=
(
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
).
(ii)
(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
p
a
r
a
m
). Given the system parameters (
κ
,
G
1
,
G
T
,
p
,
g
,
e
), the signer chooses a random element x
∈
Z
p, and sets the public key p
k
=
g
x and the secret key s
k
=
x.
(iii)
σ
←
S
i
g
n
(
p
a
r
a
m
,
m
,
s
k
,
p
k
). For a message, the signer generates the signature σ
=
H
(
m
)
x.
(iv)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
V
e
r
i
f
y
(
p
a
r
a
m
,
m
,
σ
,
p
k
). The verifier takes as inputs a claimed message-signature pair (
m
,
σ
), and outputsValid if and only if e
(
σ
,
g
)
=
e
(
H
(
m
)
,
p
k
), and otherwise outputsInvalid.
(v)
V
S
t
r
i
n
g
←
S
A
-
V
e
r
i
f
y-Setup
(
p
a
r
a
m
). The verifier takes as inputs the system parameter (
κ
,
G
1
,
G
T
,
p
,
g
,
e
) and computes K
1
=
e
(
g
,
g
) as  V
S
t
r
i
n
g.
(vi)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
S
A
-
V
e
r
i
f
y
(
Server
(
p
a
r
a
m
), and Verifier
(
m
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
). This is an interactive protocol between the server and the verifier which is shown in Algorithm 2.
(1)
Verifier, for a message-signature pair(
m
,
σ
), blinds the pair by selecting randomly r
,
t
∈
Z
p
* and computing m
′
=
H
(
m
)
·
g
t, σ
′
=
σ
·
g
r; K
2
=
e
(
g
,
p
k
), and sends (
m
′
,
σ
′
) to the verifier.
(2)
Server computesK
3
=
e
(
σ
′
,
g
), K
4
=
e
(
m
′
,
p
k
) and returns K
3
,
K
4 to the verifier.
(3)
Verifier checks the equationK
3
=
K
1
r
·
K
2
-
t
·
K
4, and outputsValid if it holds, and otherwise outputsInvalid.Algorithm 2:SA verification Signature with message-signature privacy based on BLS signature.
Verifier (param, K
1)        Server (param)
Input: (m, σ), pk
r
,
t
∈
R
Z
p
*, m
′ = H
(
m
)
·
g
t,
σ
′
=
σ
·
g
r; K
2
=
e
(
g
,
p
k
)
→
m
′
,
σ
′
K
3
=
e
(
σ
′
,
g
);
K
4
=
e
(
m
′
,
p
k
)
←
K
3
,
K
4
Output:
V
a
l
i
d, if K
3 = K
1
r
·
K
2
-
t
·
K
4;
I
n
v
a
l
i
d, if otherwise.Correctness of
S
A
-
V
e
r
i
f
y
. For a claimed message-signature pair (
m
,
σ
), when the verifier and the server are both honest, namely, the verifier correctly computes m
′, σ
′ and K
2, and the server correctly computes K
3 and K
4; then the verification equation K
3
=
K
1
r
·
K
2
-
t
·
K
4 holds if the message-signature pair (
m
,
σ
) is valid and otherwise does not hold. Consider(9)
K
3
=
e
σ
′
,
g
=
e
(
σ
,
g
)
·
e
(
g
r
,
g
)
=
e
H
m
x
,
g
·
e
g
,
g
r
=
e
H
m
,
p
k
·
K
1
r
=
e
m
′
·
g
-
t
,
p
k
·
K
1
r
=
e
m
′
,
p
k
·
e
g
,
p
k
-
t
·
K
1
r
=
K
4
·
K
2
-
t
·
K
1
r
.In the following, by Theorems7 and 8, we will show that our SA verification signature scheme above is secure under our security model; namely, the SA verification protocol described in Algorithm 2 is sound against collusion and adaptive chosen message attacks and also satisfies message-signature privacy against collusion and adaptive chosen message attacks.Theorem 7.
The SA verification protocol described in Algorithm2 satisfies soundness against collusion and adaptive chosen message attacks.Proof.
In order to prove that the SA verification protocol in Algorithm2 is (
t
,
q
v
,
1
/
(
p
-
1
)
)-sound against collusion and adaptive chosen message attacks, we will show that the adversary can only prove an invalid signature as valid with at most probability 1
/
(
p
-
1
). The challenger and the adversary play the following game.
(i)
Setup. The challenger generates the system parameter (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
), chooses a random element x
∈
Z
p, and sets s
k
=
x and p
k
=
g
x. Then it also computes K
1
=
e
(
g
,
g
). Finally the challenger sends (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
,
s
k
,
p
k
) to the adversary.
(ii)
Queries. The adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary.
(iii)
Output. Eventually, the adversary A outputs a message m
*. The challenger C chooses a random element σ
* in G
1
∖
Ω
m
*, where Ω
m
* is the set of valid signatures of m
*. Then they interact with each other as described in theSA-Verify protocol. Concretely, the challenger chooses two random elements r
*
,
t
*
∈
Z
p
*, computes m
′
=
H
(
m
)
·
g
t
*, σ
′
=
σ
·
g
r
* and K
2
=
e
(
g
,
p
k
), and sends (
m
′
,
σ
′
) to the adversary. Then the adversary returns K
3
* and K
4
* to the challenger.
In the following, we will show thatK
3
*
=
K
1
r
*
·
K
2
-
t
*
·
K
4
* happens with probability 1
/
(
p
-
1
).
From (10), we can directly deduce (11):(10)
m
′
=
H
m
·
g
t
*
,
σ
′
=
σ
·
g
r
*
⇓
(11)
D
L
g
m
′
=
D
L
g
H
m
+
t
*
,
D
L
g
σ
′
=
D
L
g
σ
+
r
*
.
Since(
t
*
,
r
*
) is chosen randomly from Z
p
*, from the equation set (7), we can see that the adversary can only obtain m and σ with probability 1
/
(
p
-
1
). Furthermore, from the following, (13) can be deduced:(12)
K
3
*
=
K
1
r
*
·
K
2
-
t
*
·
K
4
*
⇓
(13)
D
L
e
g
,
g
K
3
*
K
4
*
=
D
L
e
(
g
,
g
)
K
1
*
·
r
*
-
D
L
e
g
,
g
K
2
*
·
t
*
.
We can see thatK
3
*
/
K
4
* is determined by r
* and t
*. Since D
L
e
(
g
,
g
)
K
1
*
·
r
*
-
D
L
e
(
g
,
g
)
K
2
*
·
t
* is a random element in Z
p
*, the adversary can only give out a pair (
K
3
*
,
K
4
*
) satisfying (11) with probabitity 1
/
(
p
-
1
). This completes the proof of Theorem 7.Theorem 8.
The SA verification protocol described in Algorithm2 satisfies message-signature privacy against collusion and adaptive chosen message attacks.Proof.
In order to prove that the SA verification protocol in Algorithm2 satisfies (
t
,
q
v
,
1
/
2
)-message-signature privacy against collusion and adaptive chosen message attacks, we will show that the adversary can only succeed with at most probability 1
/
2 in the game with the challenger described as follows.(i)
Setup. The challenger generates the system parameter (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
), and the secret key s
k
=
x and the public key p
k
=
g
x. Then it also computes K
1
=
e
(
g
,
g
). Finally the challenger sends (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
,
s
k
,
p
k
) to the adversary.
(ii)
Queries. The adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, and, at the end of each execution, returns the output ofSA-Verify to the adversary A.
(iii)
Challenge. A outputs two pairs (
m
0
,
σ
0
) and (
m
1
,
σ
1
), where σ
i is a valid signature on m
i for i
=
1,2. Then it sends them to the challenger C. C chooses a bit b
∈
{
0,1
} at random and interacts with A by runningSA-Verify(
A
,
C
m
b
,
σ
b
,
p
k
,
V
S
t
r
i
n
g
). Concretely, the challenger chooses two random elements r
*
,
t
*
∈
Z
p
*, computes m
b
′
=
H
(
m
b
)
·
g
t
*, σ
b
′
=
σ
b
·
g
r
* and K
2
=
e
(
g
,
p
k
), and sends (
m
b
′
,
σ
b
′
) to the adversary. Then the adversary returns K
3
* and K
4
* to the challenger. After the interaction, C sends the output ofSA-Verify(
A
,
C
(
m
b
,
σ
b
,
p
k
,
V
S
t
r
i
n
g
)
) to A.
(iv)
Output. Finally, A outputs a bit b
′
∈
{
0,1
}. We will show that A can only succeed with probability 1
/
2.
From the equation set (10) in the proof of Theorem 4, we can see that there exist two pairs (
m
0
,
t
0
*
) and (
m
1
,
t
1
*
) satisfying m
′
=
H
(
m
b
)
·
g
t
b
* for c
=
0,1, and there exist two pairs (
σ
0
,
r
0
*
) and (
σ
1
,
r
1
*
) satisfying σ
′
=
σ
b
·
g
r
* for c
=
0,1. So the adversary cannot obtain anything about (
m
b
,
σ
b
), and it only guesses b correctly with probability 1
/
2. This completes the proof of Theorem 8.Efficiency Analysis. In the following, we will show that our SA verification signature scheme based on BLS signature above is computation saving and efficient. We will analyze the efficiency ofSA-Verify algorithm by comparing that of BLS Signature scheme [18]. In BLS signature scheme [18], to verify a message-signature pair (
m
,
σ
), the verifier needs to compute H
(
m
) which takes 1 hash function and two bilinear pairings e
(
H
(
m
)
,
p
k
) and e
(
σ
,
g
). However, in our server-aided verification signature scheme, the verifier can first precompute a pairing e
(
g
,
g
) which can be used by multipleSA-Verify protocols. Then in aSA-Verify protocol, the verifier needs to compute totally 2 exponentiations in G
1 and 2 exponentiation in G
T as well as 2 multiplications in G
1 and 2 multiplications in G
T and 1 hash function. From the comparison, we can see that our SA verification signature scheme based on BLS signature is computation saving. The concrete computation cost comparison of the verifier in the verification of BLS signature andSA-Verify in Algorithm 2 is shown in Table 2.Table 2
Efficiency of the SA verification signature scheme.
Verification
Pairing
Exponentiation
Multiplication
Hash
BLS [18]
2
0
0
1
Our scheme
1
2
(
G
1
)
+
2
(
G
T
)
2
(
G
1
)
+
2
(
G
T
)
1


## 4.1. Definition of Message-Signature Privacy

A server-aided verification signature scheme with message-signature privacy SAV-Σ also consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify.Definition 6 (message-signature privacy ofS
A
-
V
e
r
i
f
y).
We say thatSA-Verify satisfies (
t
,
q
v
,
ε
)-message-signature privacy against collusion and adaptive chosen message attacks if there exists no adversary A who runs in time at most t, makes at most q
v server-aided verification queries, and succeeds with probability at least ε in the following game with the challenger C. The game is defined as follows. (i)
Setup. The challenger C runs the algorithmsParamGen,KeyGen, andSA-Verifier-Setup to obtain the system parameter p
a
r
a
m, one key pair (
s
k
,
p
k
), andVString. The adversary A is given p
a
r
a
m and (
s
k
,
p
k
). Similar to the definition of message privacy for SA verification signature, A can generate any message-signature pair with the key pair (
s
k
,
p
k
); however as we assumed, it cannot obtain any message-signature pair that has been created by the signer before.
(ii)
Queries. Proceeding adaptively, the adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, where the adversary A acts as the server and the challenger C acts as the verifier. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary A.
(iii)
Challenge. A outputs two pairs (
M
0
,
σ
0
) and (
M
1
,
σ
1
), where σ
i is a valid signature on M
i for i
=
1,2. Then A sends them to the challenger C. C chooses a bit b
∈
{
0,1
} at random and interacts with A by runningSA-Verify(
A
,
C
(
M
b
,
σ
b
,
p
k
,
V
S
t
r
i
n
g
)
) where A plays as a server and C plays as a verifier. After the interaction, C sends the output ofSA-Verify(
A
,
C
(
M
b
,
σ
b
,
p
k
,
V
S
t
r
i
n
g
)
) to A.
(iv)
Output. Finally, A outputs a bit b
′
∈
{
0,1
}. We say that A wins the game with probability ε if(8)
Pr
⁡
b
=
b
′
≥
ε
.


## 4.2. Concrete SA Verification Signature with Message-Signature Privacy

In this section, we will present a SA verification signature scheme which satisfies message-signature privacy against collusion and adaptive chosen message attacks. This scheme is constructed based on BLS signature [18], which also consists of six algorithms:ParamGen,KeyGen,Sign,Verify,SA-Verifier-Setup, andSA-Verify. The first four algorithms are the same as those in BLS signature scheme [18]. By executing theSA-Verifier-Setup andSA-Verifyalgorithms, the computational load of the verifier can be reduced. In BLS signature [18], the verifier has to compute two pairings; however in the following SAV-Σ, it needs only to compute a pairing.(i)
p
a
r
a
m
←
ParamGen. Let κ be a security parameter, (
G
1
,
G
T
) be bilinear groups, where |
G
1
|
=
|
G
T
|
=
p for some prime number p
≥
2
κ, and g be a generator of G
1. e
:
G
1
×
G
1
→
G
T is a bilinear mapping. H
:
{
0,1
}
*
→
G
1 is a hash function. The system parameter p
a
r
a
m
=
(
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
).
(ii)
(
p
k
,
s
k
)
←
K
e
y
G
e
n
(
p
a
r
a
m
). Given the system parameters (
κ
,
G
1
,
G
T
,
p
,
g
,
e
), the signer chooses a random element x
∈
Z
p, and sets the public key p
k
=
g
x and the secret key s
k
=
x.
(iii)
σ
←
S
i
g
n
(
p
a
r
a
m
,
m
,
s
k
,
p
k
). For a message, the signer generates the signature σ
=
H
(
m
)
x.
(iv)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
V
e
r
i
f
y
(
p
a
r
a
m
,
m
,
σ
,
p
k
). The verifier takes as inputs a claimed message-signature pair (
m
,
σ
), and outputsValid if and only if e
(
σ
,
g
)
=
e
(
H
(
m
)
,
p
k
), and otherwise outputsInvalid.
(v)
V
S
t
r
i
n
g
←
S
A
-
V
e
r
i
f
y-Setup
(
p
a
r
a
m
). The verifier takes as inputs the system parameter (
κ
,
G
1
,
G
T
,
p
,
g
,
e
) and computes K
1
=
e
(
g
,
g
) as  V
S
t
r
i
n
g.
(vi)
{
V
a
l
i
d
,
I
n
v
a
l
i
d
}
←
S
A
-
V
e
r
i
f
y
(
Server
(
p
a
r
a
m
), and Verifier
(
m
,
σ
,
p
k
,
V
S
t
r
i
n
g
)
). This is an interactive protocol between the server and the verifier which is shown in Algorithm 2.
(1)
Verifier, for a message-signature pair(
m
,
σ
), blinds the pair by selecting randomly r
,
t
∈
Z
p
* and computing m
′
=
H
(
m
)
·
g
t, σ
′
=
σ
·
g
r; K
2
=
e
(
g
,
p
k
), and sends (
m
′
,
σ
′
) to the verifier.
(2)
Server computesK
3
=
e
(
σ
′
,
g
), K
4
=
e
(
m
′
,
p
k
) and returns K
3
,
K
4 to the verifier.
(3)
Verifier checks the equationK
3
=
K
1
r
·
K
2
-
t
·
K
4, and outputsValid if it holds, and otherwise outputsInvalid.Algorithm 2:SA verification Signature with message-signature privacy based on BLS signature.
Verifier (param, K
1)        Server (param)
Input: (m, σ), pk
r
,
t
∈
R
Z
p
*, m
′ = H
(
m
)
·
g
t,
σ
′
=
σ
·
g
r; K
2
=
e
(
g
,
p
k
)
→
m
′
,
σ
′
K
3
=
e
(
σ
′
,
g
);
K
4
=
e
(
m
′
,
p
k
)
←
K
3
,
K
4
Output:
V
a
l
i
d, if K
3 = K
1
r
·
K
2
-
t
·
K
4;
I
n
v
a
l
i
d, if otherwise.Correctness of
S
A
-
V
e
r
i
f
y
. For a claimed message-signature pair (
m
,
σ
), when the verifier and the server are both honest, namely, the verifier correctly computes m
′, σ
′ and K
2, and the server correctly computes K
3 and K
4; then the verification equation K
3
=
K
1
r
·
K
2
-
t
·
K
4 holds if the message-signature pair (
m
,
σ
) is valid and otherwise does not hold. Consider(9)
K
3
=
e
σ
′
,
g
=
e
(
σ
,
g
)
·
e
(
g
r
,
g
)
=
e
H
m
x
,
g
·
e
g
,
g
r
=
e
H
m
,
p
k
·
K
1
r
=
e
m
′
·
g
-
t
,
p
k
·
K
1
r
=
e
m
′
,
p
k
·
e
g
,
p
k
-
t
·
K
1
r
=
K
4
·
K
2
-
t
·
K
1
r
.In the following, by Theorems7 and 8, we will show that our SA verification signature scheme above is secure under our security model; namely, the SA verification protocol described in Algorithm 2 is sound against collusion and adaptive chosen message attacks and also satisfies message-signature privacy against collusion and adaptive chosen message attacks.Theorem 7.
The SA verification protocol described in Algorithm2 satisfies soundness against collusion and adaptive chosen message attacks.Proof.
In order to prove that the SA verification protocol in Algorithm2 is (
t
,
q
v
,
1
/
(
p
-
1
)
)-sound against collusion and adaptive chosen message attacks, we will show that the adversary can only prove an invalid signature as valid with at most probability 1
/
(
p
-
1
). The challenger and the adversary play the following game.
(i)
Setup. The challenger generates the system parameter (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
), chooses a random element x
∈
Z
p, and sets s
k
=
x and p
k
=
g
x. Then it also computes K
1
=
e
(
g
,
g
). Finally the challenger sends (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
,
s
k
,
p
k
) to the adversary.
(ii)
Queries. The adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A. At the end of each execution, the challenger returns the output ofSA-Verify to the adversary.
(iii)
Output. Eventually, the adversary A outputs a message m
*. The challenger C chooses a random element σ
* in G
1
∖
Ω
m
*, where Ω
m
* is the set of valid signatures of m
*. Then they interact with each other as described in theSA-Verify protocol. Concretely, the challenger chooses two random elements r
*
,
t
*
∈
Z
p
*, computes m
′
=
H
(
m
)
·
g
t
*, σ
′
=
σ
·
g
r
* and K
2
=
e
(
g
,
p
k
), and sends (
m
′
,
σ
′
) to the adversary. Then the adversary returns K
3
* and K
4
* to the challenger.
In the following, we will show thatK
3
*
=
K
1
r
*
·
K
2
-
t
*
·
K
4
* happens with probability 1
/
(
p
-
1
).
From (10), we can directly deduce (11):(10)
m
′
=
H
m
·
g
t
*
,
σ
′
=
σ
·
g
r
*
⇓
(11)
D
L
g
m
′
=
D
L
g
H
m
+
t
*
,
D
L
g
σ
′
=
D
L
g
σ
+
r
*
.
Since(
t
*
,
r
*
) is chosen randomly from Z
p
*, from the equation set (7), we can see that the adversary can only obtain m and σ with probability 1
/
(
p
-
1
). Furthermore, from the following, (13) can be deduced:(12)
K
3
*
=
K
1
r
*
·
K
2
-
t
*
·
K
4
*
⇓
(13)
D
L
e
g
,
g
K
3
*
K
4
*
=
D
L
e
(
g
,
g
)
K
1
*
·
r
*
-
D
L
e
g
,
g
K
2
*
·
t
*
.
We can see thatK
3
*
/
K
4
* is determined by r
* and t
*. Since D
L
e
(
g
,
g
)
K
1
*
·
r
*
-
D
L
e
(
g
,
g
)
K
2
*
·
t
* is a random element in Z
p
*, the adversary can only give out a pair (
K
3
*
,
K
4
*
) satisfying (11) with probabitity 1
/
(
p
-
1
). This completes the proof of Theorem 7.Theorem 8.
The SA verification protocol described in Algorithm2 satisfies message-signature privacy against collusion and adaptive chosen message attacks.Proof.
In order to prove that the SA verification protocol in Algorithm2 satisfies (
t
,
q
v
,
1
/
2
)-message-signature privacy against collusion and adaptive chosen message attacks, we will show that the adversary can only succeed with at most probability 1
/
2 in the game with the challenger described as follows.(i)
Setup. The challenger generates the system parameter (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
), and the secret key s
k
=
x and the public key p
k
=
g
x. Then it also computes K
1
=
e
(
g
,
g
). Finally the challenger sends (
κ
,
G
1
,
G
T
,
p
,
g
,
e
,
H
,
s
k
,
p
k
) to the adversary.
(ii)
Queries. The adversary A is allowed to make at most q
v server-aided verification queries. The challenger C responds by executingSA-Verify with the adversary A, and, at the end of each execution, returns the output ofSA-Verify to the adversary A.
(iii)
Challenge. A outputs two pairs (
m
0
,
σ
0
) and (
m
1
,
σ
1
), where σ
i is a valid signature on m
i for i
=
1,2. Then it sends them to the challenger C. C chooses a bit b
∈
{
0,1
} at random and interacts with A by runningSA-Verify(
A
,
C
m
b
,
σ
b
,
p
k
,
V
S
t
r
i
n
g
). Concretely, the challenger chooses two random elements r
*
,
t
*
∈
Z
p
*, computes m
b
′
=
H
(
m
b
)
·
g
t
*, σ
b
′
=
σ
b
·
g
r
* and K
2
=
e
(
g
,
p
k
), and sends (
m
b
′
,
σ
b
′
) to the adversary. Then the adversary returns K
3
* and K
4
* to the challenger. After the interaction, C sends the output ofSA-Verify(
A
,
C
(
m
b
,
σ
b
,
p
k
,
V
S
t
r
i
n
g
)
) to A.
(iv)
Output. Finally, A outputs a bit b
′
∈
{
0,1
}. We will show that A can only succeed with probability 1
/
2.
From the equation set (10) in the proof of Theorem 4, we can see that there exist two pairs (
m
0
,
t
0
*
) and (
m
1
,
t
1
*
) satisfying m
′
=
H
(
m
b
)
·
g
t
b
* for c
=
0,1, and there exist two pairs (
σ
0
,
r
0
*
) and (
σ
1
,
r
1
*
) satisfying σ
′
=
σ
b
·
g
r
* for c
=
0,1. So the adversary cannot obtain anything about (
m
b
,
σ
b
), and it only guesses b correctly with probability 1
/
2. This completes the proof of Theorem 8.Efficiency Analysis. In the following, we will show that our SA verification signature scheme based on BLS signature above is computation saving and efficient. We will analyze the efficiency ofSA-Verify algorithm by comparing that of BLS Signature scheme [18]. In BLS signature scheme [18], to verify a message-signature pair (
m
,
σ
), the verifier needs to compute H
(
m
) which takes 1 hash function and two bilinear pairings e
(
H
(
m
)
,
p
k
) and e
(
σ
,
g
). However, in our server-aided verification signature scheme, the verifier can first precompute a pairing e
(
g
,
g
) which can be used by multipleSA-Verify protocols. Then in aSA-Verify protocol, the verifier needs to compute totally 2 exponentiations in G
1 and 2 exponentiation in G
T as well as 2 multiplications in G
1 and 2 multiplications in G
T and 1 hash function. From the comparison, we can see that our SA verification signature scheme based on BLS signature is computation saving. The concrete computation cost comparison of the verifier in the verification of BLS signature andSA-Verify in Algorithm 2 is shown in Table 2.Table 2
Efficiency of the SA verification signature scheme.
Verification
Pairing
Exponentiation
Multiplication
Hash
BLS [18]
2
0
0
1
Our scheme
1
2
(
G
1
)
+
2
(
G
T
)
2
(
G
1
)
+
2
(
G
T
)
1


## 5. Conclusion

In this paper, we studied the SA verification signature schemes with message-signature privacy for mobile computing. A power-constrained mobile device can outsource the verification of a signature to a server with powerful resources in order to reduce its computational load. We first present two definitions for privacy of server-aided verification protocol, respectively, named message privacy and message-signature privacy under collusion and adaptive chosen message attacks. Then under our security models, two concrete constructions based on existing signature schemes were presented and proved secure. By efficiency analysis, we showed that the two concrete schemes are both computation saving and efficient.



---

*Source: 626415-2015-03-11.xml*