# Attribute Based Multisignature Scheme for Wireless Communications

Authors: Ximeng Liu; Hui Zhu; Jianfeng Ma; Qi Li; Jinbo Xiong
Journal: Mobile Information Systems
 (2015)

---

## Abstract

With rapidly development of wireless communication, more mobile devices are used in our daily
life. Although the need for accessing a wireless network is evident, new problems, such as
keeping and preserving user identity’s privacy, should be greatly concerned. Attribute
based signature scheme is an important cryptographic primitive which provides a powerful way
for user to control their privacy. In wireless environment, the capacity of wireless channel is
also valuable resources which is limited. More information can be transmitted through the
wireless channel when the cost of using signature to verify the message becomes less. In order to
reduce the bandwidth needed to transmit attribute based signatures and keep signer’s privacy,
attribute based multisignature scheme (ABMS) was proposed in this paper. Moreover, we
formalize and construct the ABMS. Our scheme is existentially unforgeable against chosen
message attack on Computational Diffie-Hellman (CDH) assumption in the standard model.
The simulation shows that our ABMS scheme is more appropriate for wireless communication
to guarantee integrity of the data.


---

## Body

## 1. Introduction

With the increasing availability of mobile devices, it is convenient for people to make a phone call and surf the internet through the wireless channel. With features of convenient, fast, and easy-to-use, there is a growing demand for consumer to transmit data through the wireless channel. Due to the character of the wireless channel, the data can be easily changed which is affected by transmission channel noise or modified by the malicious attacker. The security and privacy protection of the data collected from wireless devices, either while stored in the data server or during their transmission through the wireless network, is a major concern. Also, preserving identity privacy becomes an increasingly important concern. In Oct. 2013, the attackers are believed to have stolen information on 2.9 million Adobe account holders. That data includes customer names, encrypted credit and debit card numbers, expiration dates, and other customer order information [1]. How to efficiently verify the data integrity and preserve identity privacy is important problem in the wireless environment.Attribute based signatures (ABS) [2] scheme has attracted much attention as a new public key primitive in the recent years because it provides a powerful way for user to control their privacy and keep the integrity of the data, and it also helps to provide fine-grained access control in anonymous authentication systems. The ABS scheme is analogue of attribute based encryption (ABE) [3, 4] which is an important application of the fuzzy identity-based encryption (FIBE) scheme [3]. A user encrypts a message with a set of n attributes such that users whose decryption key has at least t common attributes with the ciphertext attribute set can decrypt the message. We call this scheme threshold attribute based encryption (t-ABE) to describe simplicity. Wang et al. [5] proposed a new fully secure FIBE scheme based on the FIBE [3] scheme and prove its security by using the “dual system encryption” technique. The ABS scheme extends identity-based signature where the signer is associated with a set of attributes instead of a single identity string. It provides a powerful way for users to control their privacy: the user can choose the subset of their attributes relevant to the specific scenario in signing a document. Considering the following scenario, an institution will release a technical report that may involve a professor at age 45 in the computer science department. Any user who has attributes sets that contain all the above attributes could issue the signature. Because ABS scheme has these advantages, different user wants to sign the same document by using ABS scheme. Yang et al. [6] introduced a new cryptographic primitive called fuzzy identity-based signature (FIBS) which the signature analogue of FIBE scheme and Shahandashti and Safavi-Naini [7] proposed a threshold attribute based signature construction for small attribute universe and large attribute universe. Since FIBS scheme lacks controlling the signer’s privacy, Maji et al. [8] introduced ABE scheme which can provide strong privacy guarantee for the signer and strong unforgeability guarantee for the verifier. In order to sign messages with any subset of their attributes issued from an attribute center, Li and Kim [9] gave hidden attribute based signatures without anonymity revocation scheme which can reach anonymity and unforgeability. Li et al. [10] proposed a new construction of ABS supporting flexible threshold predicate which could compact the signature size and improve the verification time. Later, Cao et al. [11] give multiauthority attribute based signature schemes for expressive policy. In their scheme, they use both AND, OR, threshold, and disjunctive normal form to express a policy. Consider the following case; users often use wireless channel to upload file to the data center. Unfortunately, these communication mechanisms are rather expensive for mobile devices in energy consumption and the capacity of wireless channel is limited. In order to increase throughput of message sent to the data center and increase the battery life of the energy-restricted devices, it is better to exploit fewer bits of transmission in wireless communication to data center. Therefore, it is a challenge to design cryptographic primitives to reduce the communication and storage overhead.Multisignatures allow multiple signers to jointly authenticate a message using a single compact signature which was first introduced by [12]. It allows a group of players to sign the same message by generating a short signature which can be verified against the set of these players’ public keys. After that, lots of multisignature schemes were proposed in [13–15]. But these schemes lacked formal security notions for multisignatures. Micali et al. [16] first formalized the strong notion of security for multisignatures and [17] gave a more general construct in random oracle model where their construction did not restrict the subset of signers. The security is based on random oracles. Lu et al. [18] first proposed sequential aggregate signature and multisignature scheme in the standard model. Because the verification information of identity-based signature (IBS) scheme does not include any certificate or any individual public key for the signer, identity-based multisignature (IDMS) scheme was presented by Cheon et al. [19]. This scheme could reduce the signature size into almost a half and efficiently verify multiple signatures. Gentry and Ramzan [20] designed the efficient identity-based (Multi-/Aggregate) signatures. Their schemes employ a group with a bilinear map in the random oracle model. Later, there are several RSA-based IBMS schemes proposed whose security is based on RSA assumption. The computational costs of RSA-based IBMS scheme are slightly lower in signing and verification because RSA exponentiation is less expensive than bilinear map operations. Recently, Liu et al. [21] proposed an attribute based multisignature scheme in the standard model with can reduce the length of signature. However, the performance of this ABMS scheme is not good. Later, Liu et al. [22] proposed another ABMS scheme for the wireless environment. But the authors do not give performance measurement to show their scheme is efficient.In this paper, we first propose a scheme called attribute based multisignature (ABMS) scheme to solve problem mentioned above. The ABMS scheme allows a set of signatures (sign on the same message) to be compressed into a single signature. This kind of signature has less signature length than the original one and less computational cost which is more appropriate for the wireless nature where bandwidth is a bottleneck.Our Contributions. In this work, we make following contributions: (1) We define attribute based multisignature scheme (ABMS), formalize the model, and give security model for ABMS scheme. (2) We give overview of ABMS scheme for wireless communication and a concrete construction of ABMS scheme. (3) We prove that our ABMS scheme is existential unforgeability in the standard model by using the computational Diffie-Hellman problem. (4) We make simulation on a workstation to show that ABMS scheme can greatly decrease the storage overhead in the data center and computational overhead for verifier.Organization. The rest of paper is organized as follows. In Section 2, we review some concept about bilinear pairing, complexity assumption, flexible threshold predicate, and Lagrange interpolation. In Section 3, we give the formal models and its security model of ABMS scheme. In Section 4, we give the specific construction about the ABMS scheme. In Section 5, we give security proof in the standard model for ABMS scheme. In Section 6, we give performance analysis on ABMS scheme, use the workstation to test the performance of ABMS scheme, and analyze the efficiency of the ABMS scheme. And we conclude this paper in Section 7.


## 2. Preliminaries

In this section, we introduce the notions which are used to construct ABMS scheme and prove the security of ABMS scheme.


### 2.1. Bilinear Maps

LetG and G
T be two cyclic groups of prime order p with the multiplication. Let g be a generator of G and e a bilinear map. Let e
:
G
×
G
→
G
T be a bilinear map having the following properties:(1)
bilinearity: For allu
,
v
∈
G and a
,
b
∈
Z
p, we have e
(
u
a
,
v
b
)
=
e
(
u
,
v
)
a
b;
(2)
nondegeneracy:e
(
g
,
g
)
≠
1;
(3)
computability: There is efficient algorithm to compute bilinear mape
:
G
×
G
→
G
T.Notice that the mape is symmetric since e
(
u
a
,
v
b
)
=
e
(
u
,
v
)
a
b
=
e
(
u
b
,
v
a
).


### 2.2. Complexity Assumptions

Definition 1.
The challenger choosesa
,
b
∈
Z
p at random and outputs (
g
,
g
a
,
g
b
). The computational Diffie-Hellman (CDH) problem is to compute g
a
b. An adversary A has at least an ϵ if
(1)
Pr
⁡
[
A
(
g
,
g
a
,
g
b
)
=
g
a
b
]
≥
ϵ
.
The computational (
t
,
ϵ
)-DH assumption holds if no t-time adversary has at least ϵ advantage in solving the above game.


### 2.3. Flexible Threshold Predicate

In this paper, we use predicatesΥ consisting of thresholds gates. All predicates Υ
k
,
ω
*
(
·
)
→
0
/
1 for ω
* with threshold value k. If the number of attribute in ω
′
∩
ω
* exceeds threshold k, it outputs 1. Otherwise, it outputs 0. Consider
(2)
Υ
k
,
ω
*
(
ω
′
)
=
1
,
ω
′
∩
ω
*
≥
k
,
0
,
otherwise
.


### 2.4. Lagrange Interpolation

In this section, we describe Lagrange interpolation which is used in the ABMS schemes. Givend points q
1
,
…
,
q
(
d
) on a d
-
1 degree polynomial, we can use Lagrange interpolation to compute q
(
i
) for any i
∈
Z
p. Let S be a d-element set. We define the Lagrange coefficient Δ
j
,
S
(
i
) of q
(
j
) in the computation of q
(
i
) as
(3)
Δ
j
,
S
(
i
)
=
∏
η
∈
S
,
η
≠
j
‍
i
-
η
j
-
η
.


### 2.5. Symbols & Notations

The following list shows the symbols and notations used in this work:e
(
·
,
·
): bilinear maps,
k: threshold gate,
Υ
k
,
ω
*
(
·
): predicates consisting of threshold gate k,
Δ
j
,
S: Lagrange coefficient with set S,
p
a
r
a
m
s: public parameters,
D: private key,
σ: original signature,
p
σ
p: multisignature,
ω
,
ω
′
,
ω
*
,
ω
^
,
Ω
,
Ω
′: attribute set.


## 2.1. Bilinear Maps

LetG and G
T be two cyclic groups of prime order p with the multiplication. Let g be a generator of G and e a bilinear map. Let e
:
G
×
G
→
G
T be a bilinear map having the following properties:(1)
bilinearity: For allu
,
v
∈
G and a
,
b
∈
Z
p, we have e
(
u
a
,
v
b
)
=
e
(
u
,
v
)
a
b;
(2)
nondegeneracy:e
(
g
,
g
)
≠
1;
(3)
computability: There is efficient algorithm to compute bilinear mape
:
G
×
G
→
G
T.Notice that the mape is symmetric since e
(
u
a
,
v
b
)
=
e
(
u
,
v
)
a
b
=
e
(
u
b
,
v
a
).


## 2.2. Complexity Assumptions

Definition 1.
The challenger choosesa
,
b
∈
Z
p at random and outputs (
g
,
g
a
,
g
b
). The computational Diffie-Hellman (CDH) problem is to compute g
a
b. An adversary A has at least an ϵ if
(1)
Pr
⁡
[
A
(
g
,
g
a
,
g
b
)
=
g
a
b
]
≥
ϵ
.
The computational (
t
,
ϵ
)-DH assumption holds if no t-time adversary has at least ϵ advantage in solving the above game.


## 2.3. Flexible Threshold Predicate

In this paper, we use predicatesΥ consisting of thresholds gates. All predicates Υ
k
,
ω
*
(
·
)
→
0
/
1 for ω
* with threshold value k. If the number of attribute in ω
′
∩
ω
* exceeds threshold k, it outputs 1. Otherwise, it outputs 0. Consider
(2)
Υ
k
,
ω
*
(
ω
′
)
=
1
,
ω
′
∩
ω
*
≥
k
,
0
,
otherwise
.


## 2.4. Lagrange Interpolation

In this section, we describe Lagrange interpolation which is used in the ABMS schemes. Givend points q
1
,
…
,
q
(
d
) on a d
-
1 degree polynomial, we can use Lagrange interpolation to compute q
(
i
) for any i
∈
Z
p. Let S be a d-element set. We define the Lagrange coefficient Δ
j
,
S
(
i
) of q
(
j
) in the computation of q
(
i
) as
(3)
Δ
j
,
S
(
i
)
=
∏
η
∈
S
,
η
≠
j
‍
i
-
η
j
-
η
.


## 2.5. Symbols & Notations

The following list shows the symbols and notations used in this work:e
(
·
,
·
): bilinear maps,
k: threshold gate,
Υ
k
,
ω
*
(
·
): predicates consisting of threshold gate k,
Δ
j
,
S: Lagrange coefficient with set S,
p
a
r
a
m
s: public parameters,
D: private key,
σ: original signature,
p
σ
p: multisignature,
ω
,
ω
′
,
ω
*
,
ω
^
,
Ω
,
Ω
′: attribute set.


## 3. Formal Models and Its Security Model

### 3.1. Formal Models of ABMS Scheme

The attribute based multisignature scheme has six algorithms calledSetup,Extract,StandardSign,StandardVerify,MComb, andMultiVerify. In this section, we describe the six algorithms as follows.Setup. This algorithm is run by the master entity which inputs the security parameter and generates the public parameters p
a
r
a
m
s of the scheme and the master secret key MSK. The master entity publishes p
a
r
a
m
s and keeps the MSK to itself.Extract. Given an attribute set ω, the master key MSK and p
a
r
a
m
s, the master entity will use this algorithm to generate private keys of ω for all entities participating in the scheme and distribute the private keys to their respective owner through a secure channel.StandardSign. Given a message m, an attribute set ω, a private key D, p
a
r
a
m
s, and predicate Υ
ω
*
(
·
), this algorithm generates the signature σ of ω on m. The entity with attribute set ω will use this algorithm for signing.StandardVerify. Given a signature σ, a message m, attribute set ω, and p
a
r
a
m
s, this algorithm outputsaccept if a valid signature on message for attribute set and outputsreject otherwise.MComb. The algorithm is given a signature-public key pair {
(
σ
i
,
p
a
r
a
m
s
i
)
}
i
=
1
l and a message m. The l is the number of user’s signing the message m. It generates and outputs a multisignature p
σ
p.MultiVerify. The algorithm is given the public parameters {
p
a
r
a
m
i
}
i
=
1
l, a message m, and multisignature p
σ
p. The algorithm outputsaccept if it is a valid multisignature and outputsreject otherwise.


### 3.2. Existential Unforgeability of ABMS Scheme

We define security model for attribute based multisignature scheme between a challenger and an adversary.Setup. The challenger runs theSetup algorithm and obtains both the public parameters p
a
r
a
m
s and the master secret key. The challenger gives the p
a
r
a
m
s to adversary and keeps the master secret key by itself.Queries. The adversary adaptively makes a polynomial bounded number of queries to the challenger. Each query can be one of the following.(i)
Extract Query. The adversary can ask for the private key of any attribute set ω. The challenger responds by running theExtract algorithm and gives the private key to adversary.
(ii)
Sign Query. The adversary can ask for the signature of attribute set ω on message m. The challenger responds by first runningExtract algorithm to obtain the private key and running theSign algorithm to obtain a signature which is given to the adversary.Output. Eventually, it will output a forgery σ
* on messages m under public parameters {
p
a
r
a
m
s
i
}
i
=
1
l. The challenger key must appear in {
p
a
r
a
m
s
i
}
i
=
1
l, without loss of generality; we assume that the challenge key appears at index 1. If the condition holds, it outputs 1. Otherwise, it outputs 0.Definition 2.
The attribute based multisignature scheme is(
t
,
q
e
,
q
S
,
ϵ
)-secure against existential forgery in an adaptive chosen-message attack, if no t-time adversary makes q
e
Extract queries, q
S
Sign queries and wins the above game with advantage more than ϵ.


## 3.1. Formal Models of ABMS Scheme

The attribute based multisignature scheme has six algorithms calledSetup,Extract,StandardSign,StandardVerify,MComb, andMultiVerify. In this section, we describe the six algorithms as follows.Setup. This algorithm is run by the master entity which inputs the security parameter and generates the public parameters p
a
r
a
m
s of the scheme and the master secret key MSK. The master entity publishes p
a
r
a
m
s and keeps the MSK to itself.Extract. Given an attribute set ω, the master key MSK and p
a
r
a
m
s, the master entity will use this algorithm to generate private keys of ω for all entities participating in the scheme and distribute the private keys to their respective owner through a secure channel.StandardSign. Given a message m, an attribute set ω, a private key D, p
a
r
a
m
s, and predicate Υ
ω
*
(
·
), this algorithm generates the signature σ of ω on m. The entity with attribute set ω will use this algorithm for signing.StandardVerify. Given a signature σ, a message m, attribute set ω, and p
a
r
a
m
s, this algorithm outputsaccept if a valid signature on message for attribute set and outputsreject otherwise.MComb. The algorithm is given a signature-public key pair {
(
σ
i
,
p
a
r
a
m
s
i
)
}
i
=
1
l and a message m. The l is the number of user’s signing the message m. It generates and outputs a multisignature p
σ
p.MultiVerify. The algorithm is given the public parameters {
p
a
r
a
m
i
}
i
=
1
l, a message m, and multisignature p
σ
p. The algorithm outputsaccept if it is a valid multisignature and outputsreject otherwise.


## 3.2. Existential Unforgeability of ABMS Scheme

We define security model for attribute based multisignature scheme between a challenger and an adversary.Setup. The challenger runs theSetup algorithm and obtains both the public parameters p
a
r
a
m
s and the master secret key. The challenger gives the p
a
r
a
m
s to adversary and keeps the master secret key by itself.Queries. The adversary adaptively makes a polynomial bounded number of queries to the challenger. Each query can be one of the following.(i)
Extract Query. The adversary can ask for the private key of any attribute set ω. The challenger responds by running theExtract algorithm and gives the private key to adversary.
(ii)
Sign Query. The adversary can ask for the signature of attribute set ω on message m. The challenger responds by first runningExtract algorithm to obtain the private key and running theSign algorithm to obtain a signature which is given to the adversary.Output. Eventually, it will output a forgery σ
* on messages m under public parameters {
p
a
r
a
m
s
i
}
i
=
1
l. The challenger key must appear in {
p
a
r
a
m
s
i
}
i
=
1
l, without loss of generality; we assume that the challenge key appears at index 1. If the condition holds, it outputs 1. Otherwise, it outputs 0.Definition 2.
The attribute based multisignature scheme is(
t
,
q
e
,
q
S
,
ϵ
)-secure against existential forgery in an adaptive chosen-message attack, if no t-time adversary makes q
e
Extract queries, q
S
Sign queries and wins the above game with advantage more than ϵ.


## 4. Our Constructions

In this section, we first give the overview of the whole wireless communication system and then give a concrete construction of the ABMS scheme.


### 4.1. Overview of Privacy-Preserving Data Integrity Verification Method for Wireless Communication

Bandwidth is scarce resources in the wireless communication. In order to verify the data integrity, the signature method will be brought into the system. But it will greatly increase the communication cost especially when the number of users involved in the system is huge. Meanwhile, the mobile devices are always energy-restricted, such as mobile phone and wireless sensor nodes. More extra computation will increase the consumption of battery power. The main goal of our attribute based multisignature scheme is to reduce both communication overhead and verification cost in order to keep data integrity in the process of wireless communication. Also, it could allow user to control their identity’s privacy. The whole system model can be showed in Figure1. As Figure 1 shows, there are message provider (
A
1
), a group of signers (
A
2
′
,
A
3
′
,
…
,
A
l
′
), verifier B, and authority involved in the system. The authority first generates the master key and defines a common universe of attributes, such as “headmaster,” “professor,” “age 45,” and “computer science department.” Then the authority uses master key and attribute sets to construct A
1
,
A
2
′
,
…
,
A
l
′’s private key and send it to the corresponding users involved in the system, respectively. Because the message needs to be signed by message provider and a group of signers, the provider first generates the message and the signature associated with the message and then sends it to the group of users. All the users in the same BSS need to sign the message. When signers (
A
2
′
,
A
3
′
,
…
,
A
l
′
) receive the message-signature pair (
m
,
s
i
g
n
m
), they should first verify whether or not the (
m
,
s
i
g
n
m
) is sent by message provider A
1. If  (
m
,
s
i
g
n
m
) passed the verification, it is considered that the message is sent by A
1 and used m to generate his own message and signature pair (
m
,
s
i
g
n
A
k
′
), k
=
2 to l. Then the message and signature pair (
m
,
s
i
g
n
m
) and (
m
,
s
i
g
n
A
k
′
),  k
=
2 to l should be compressed into a single message-multisignature pair (
m
,
s
i
g
n
MS
) and it is sent to data center to store. When another user B needs to use message m, she/he first retrieves the message from the data center and uses signature s
i
g
n
MS to verify the message. If the verification holds, we say this message is integrated which is signed by the user A
k
′
(
k
=
2 to l
). Otherwise, it shows that the message is modified by the third party servers. If we use traditional methods, we need to transmit  l  pairs to the verifier. When we use ABMS scheme, the only thing is to create one message-signature pair to transmit in the network which can greatly decrease the transmitting overhead through the network and reduce the storage cost in the data center. The concrete construction of ABMS scheme will be presented in the next section.Figure 1
ABMS scheme for wireless network.


### 4.2. Attribute Based Multisignature Scheme

In this section, we give a concrete construction of the ABMS scheme which contains six algorithms:Setup,Extract,StandardSign,StandardVerify,MComb,MultiVerify.Setup. This algorithm first defines the attributes in the universe U as the element in Z
p. A d
-
1 default attribute set from Z
p is given as Ω
=
{
Ω
1
,
Ω
2
,
…
,
Ω
d
-
1
}. It selects a random generator g
∈
G and a random α
i
∈
Z
p
* and compute g
1
i
=
g
α
i
∈
G. Next, it picks a random element g
2 and computes A
(
i
)
=
e
(
g
1
i
,
g
2
). For every user i, select a random vector t
=
(
t
1
,
t
2
,
…
,
t
l
+
d
-
1
) from Z
p
l
+
d
-
1 and then compute T
i
=
(
T
1
=
g
t
1
,
T
2
=
g
t
2
,
…
,
T
l
+
d
-
1
=
g
t
l
+
d
-
1
). Finally, the algorithm selects random values y
′ from Z
p and a random vector y
=
(
y
1
,
y
2
,
…
,
y
k
) from Z
p
k and computes U
=
(
u
1
,
u
2
,
…
,
u
k
)
=
(
g
y
1
,
g
y
2
,
…
,
g
y
k
). The public parameters are
(4)
p
a
r
a
m
s
=
(
G
,
G
T
,
e
,
g
,
g
1
,
g
2
,
T
,
U
)
.
Here, for different users, the public keys are denoted as
(5)
P
K
(
i
)
=
A
(
i
)
.
The master keys are
(6)
MS
K
(
i
)
=
α
i
.Extract. This algorithm generates a private key for an attribute set ω related with users involved in the system. It takes the following steps.(1)
Firstly, it chooses ad
-
1 degree polynomial at random with q
(
0
)
=
α
i.
(2)
It then generates a new attribute setω
^
=
ω
∪
Ω. For each i
∈
ω
^, the algorithm chooses and computes d
i
0
=
g
2
q
(
0
)
·
(
g
1
T
i
)
r
i,  d
i
1
=
g
r
i.
(3)
Finally, it outputs(7)
D
=
d
i
0
,
d
i
1
i
∈
ω
^
as the private key.StandardSign. This algorithm inputs a private key for the attribute set ω, message m, and predicate Υ
u
,
ω
*
(
·
). In order to sign message m with predicate Υ
u
,
ω
*
(
·
), that is, to prove the signer owning at least u attribute among the c-elements attribute set ω
*. It selects a u-element from the subset ω
′
⊆
ω
∩
ω
* and works as follows.(1)
First, it selects a default attribute subsetΩ
′
⊆
Ω with |
Ω
′
|
=
d
-
u and chooses c
+
d
-
u random values r
i
′
∈
Z
p for i
∈
ω
*
∪
Ω
′.
(2)
It then computes(8)
σ
0
=
∏
i
∈
ω
′
∪
Ω
′
‍
d
i
0
Δ
i
,
S
0
∏
i
∈
ω
*
∪
Ω
′
‍
g
1
T
i
r
i
′
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
,
σ
i
=
d
i
1
Δ
i
,
S
0
g
r
i
′
i
∈
ω
′
∪
Ω
′
,
σ
i
=
g
r
i
′
i
∈
ω
*
/
ω
′
,
σ
0
′
=
g
r
s
.
(3)
Finally, the algorithm outputs the signature:(9)
σ
=
σ
0
,
σ
i
i
∈
ω
*
∪
Ω
′
,
σ
0
′
.StandardVerify. In order to verify the correctness of the signature σ
=
(
σ
0
,
{
σ
i
}
i
∈
ω
*
∪
Ω
′
,
σ
0
′
) on m with threshold k for attributes set ω
*
∪
Ω
′, it checks if the following equation holds:
(10)
e
(
g
,
σ
0
)
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
1
T
i
,
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
σ
0
′
=
A
(
i
)
.
If the equation holds, it indicates that the signature is indeed from some users with k attributes among ω
*. Otherwise, it denotes the signature is not valid.MComb. For each user in the multisignature, the algorithm inputs a public parameters p
a
r
a
m
s, public key P
K
(
k
), and a signature σ
(
k
). All the signatures are signed on a single message m. Let m be an m
′-bit message to be signed by the original signers A
1
′
,
A
2
′
,
…
,
A
l
′ and m
d denote the dth bit of m, and let M
⊆
{
1,2
,
…
,
m
′
} be the set of all d for which m
d
=
1. Denote P
K
(
k
) as user k’s public keys and its corresponding signature σ
k as σ
(
k
)
=
(
σ
0
(
k
)
,
{
σ
i
}
i
∈
ω
*
∪
Ω
′
(
k
)
,
σ
0
′
(
k
)
). Verify that σ
(
k
) is valid by calling theStandardVerify algorithm. If not, its outputs fail and halt. Otherwise, the algorithm takes following steps.For each user in the multisignature the algorithm inputs a public parametersp
a
r
a
m
s, public key P
K
(
k
), and a signature σ
(
k
). All the signatures are signed on a single message m. Let m be an m
′-bit message to be signed by the original signers A
1
′
,
A
2
′
,
…
,
A
l
′ and m
d denote the dth bit of m, and let M
⊆
{
1,2
,
…
,
m
′
} be the set of all d for which m
d
=
1. Denote P
K
(
k
) as user k’s public keys and its corresponding signature σ
k as σ
(
k
)
=
(
σ
0
(
k
)
,
{
σ
i
}
i
∈
ω
*
∪
Ω
′
(
k
)
,
σ
0
′
(
k
)
). Verify that σ
(
k
) is valid by calling theStandardVerify algorithm. If not, its outputs fail and halt. Otherwise, the algorithm takes following steps.This algorithm first initializesp
σ
p, and sets p
σ
p
0
=
1 and p
σ
p
2
=
1. For every i belong to ω
′
∪
Ω
′ and ω
*
/
ω
′, sets p
σ
i
=
1. Also, the algorithm initializes ω
′
∪
Ω
′
=
∅ and ω
*
/
ω
′
=
∅.Fork
=
1
,
…
,
l, it calculates
(11)
p
σ
p
0
=
p
σ
p
0
·
σ
0
(
k
)
,
p
σ
p
2
=
p
σ
p
2
·
σ
0
′
(
k
)
.
Then for every i
∈
ω
k
′
∪
Ω
k
′, if  i  does not exist in ω
′
∪
Ω
′, it adds attribute  i  to the attribute set ω
′
∪
Ω
′ and sets p
σ
i
=
d
i
1
Δ
i
,
S
k
(
0
)
g
r
i
′. If  i  exists in ω
′
∪
Ω
′, it sets σ
i
(
k
)
=
d
i
1
Δ
i
,
S
k
(
0
)
g
r
i
′ and calculates p
σ
i
=
p
σ
i
·
σ
i
(
k
).For everyi
∈
ω
k
*
/
ω
k
′, if i does not exist in ω
*
/
ω
′, it adds attribute i to the attribute set ω
*
/
ω
′ and sets p
σ
i
=
g
r
i
′. If i exists in ω
*
/
ω
′, it sets σ
i
(
k
)
=
g
r
i
′ and computes p
σ
i
=
p
σ
i
·
σ
i
(
k
).The algorithm finally computes:(12)
p
σ
p
=
(
p
σ
p
0
,
p
σ
i
i
∈
ω
′
∪
Ω
′
,
p
σ
i
i
∈
ω
*
/
ω
′
,
p
σ
p
2
)
.MultiVerify. Given the public parameters, public keys, a message m
∈
{
0,1
}
m
′, and a signature p
σ
p
=
(
p
σ
p
0
,
{
p
σ
i
}
i
∈
ω
′
∪
Ω
′
,
{
p
σ
i
}
i
∈
ω
*
/
ω
′
,
p
σ
p
2
), a verifieraccept
p
σ
p if the following equality holds:
(13)
e
(
p
σ
p
0
,
g
)
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
1
T
i
,
p
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
p
σ
p
2
=
∏
i
=
1
l
‍
A
(
i
)
.Otherwise, it outputsreject.


## 4.1. Overview of Privacy-Preserving Data Integrity Verification Method for Wireless Communication

Bandwidth is scarce resources in the wireless communication. In order to verify the data integrity, the signature method will be brought into the system. But it will greatly increase the communication cost especially when the number of users involved in the system is huge. Meanwhile, the mobile devices are always energy-restricted, such as mobile phone and wireless sensor nodes. More extra computation will increase the consumption of battery power. The main goal of our attribute based multisignature scheme is to reduce both communication overhead and verification cost in order to keep data integrity in the process of wireless communication. Also, it could allow user to control their identity’s privacy. The whole system model can be showed in Figure1. As Figure 1 shows, there are message provider (
A
1
), a group of signers (
A
2
′
,
A
3
′
,
…
,
A
l
′
), verifier B, and authority involved in the system. The authority first generates the master key and defines a common universe of attributes, such as “headmaster,” “professor,” “age 45,” and “computer science department.” Then the authority uses master key and attribute sets to construct A
1
,
A
2
′
,
…
,
A
l
′’s private key and send it to the corresponding users involved in the system, respectively. Because the message needs to be signed by message provider and a group of signers, the provider first generates the message and the signature associated with the message and then sends it to the group of users. All the users in the same BSS need to sign the message. When signers (
A
2
′
,
A
3
′
,
…
,
A
l
′
) receive the message-signature pair (
m
,
s
i
g
n
m
), they should first verify whether or not the (
m
,
s
i
g
n
m
) is sent by message provider A
1. If  (
m
,
s
i
g
n
m
) passed the verification, it is considered that the message is sent by A
1 and used m to generate his own message and signature pair (
m
,
s
i
g
n
A
k
′
), k
=
2 to l. Then the message and signature pair (
m
,
s
i
g
n
m
) and (
m
,
s
i
g
n
A
k
′
),  k
=
2 to l should be compressed into a single message-multisignature pair (
m
,
s
i
g
n
MS
) and it is sent to data center to store. When another user B needs to use message m, she/he first retrieves the message from the data center and uses signature s
i
g
n
MS to verify the message. If the verification holds, we say this message is integrated which is signed by the user A
k
′
(
k
=
2 to l
). Otherwise, it shows that the message is modified by the third party servers. If we use traditional methods, we need to transmit  l  pairs to the verifier. When we use ABMS scheme, the only thing is to create one message-signature pair to transmit in the network which can greatly decrease the transmitting overhead through the network and reduce the storage cost in the data center. The concrete construction of ABMS scheme will be presented in the next section.Figure 1
ABMS scheme for wireless network.


## 4.2. Attribute Based Multisignature Scheme

In this section, we give a concrete construction of the ABMS scheme which contains six algorithms:Setup,Extract,StandardSign,StandardVerify,MComb,MultiVerify.Setup. This algorithm first defines the attributes in the universe U as the element in Z
p. A d
-
1 default attribute set from Z
p is given as Ω
=
{
Ω
1
,
Ω
2
,
…
,
Ω
d
-
1
}. It selects a random generator g
∈
G and a random α
i
∈
Z
p
* and compute g
1
i
=
g
α
i
∈
G. Next, it picks a random element g
2 and computes A
(
i
)
=
e
(
g
1
i
,
g
2
). For every user i, select a random vector t
=
(
t
1
,
t
2
,
…
,
t
l
+
d
-
1
) from Z
p
l
+
d
-
1 and then compute T
i
=
(
T
1
=
g
t
1
,
T
2
=
g
t
2
,
…
,
T
l
+
d
-
1
=
g
t
l
+
d
-
1
). Finally, the algorithm selects random values y
′ from Z
p and a random vector y
=
(
y
1
,
y
2
,
…
,
y
k
) from Z
p
k and computes U
=
(
u
1
,
u
2
,
…
,
u
k
)
=
(
g
y
1
,
g
y
2
,
…
,
g
y
k
). The public parameters are
(4)
p
a
r
a
m
s
=
(
G
,
G
T
,
e
,
g
,
g
1
,
g
2
,
T
,
U
)
.
Here, for different users, the public keys are denoted as
(5)
P
K
(
i
)
=
A
(
i
)
.
The master keys are
(6)
MS
K
(
i
)
=
α
i
.Extract. This algorithm generates a private key for an attribute set ω related with users involved in the system. It takes the following steps.(1)
Firstly, it chooses ad
-
1 degree polynomial at random with q
(
0
)
=
α
i.
(2)
It then generates a new attribute setω
^
=
ω
∪
Ω. For each i
∈
ω
^, the algorithm chooses and computes d
i
0
=
g
2
q
(
0
)
·
(
g
1
T
i
)
r
i,  d
i
1
=
g
r
i.
(3)
Finally, it outputs(7)
D
=
d
i
0
,
d
i
1
i
∈
ω
^
as the private key.StandardSign. This algorithm inputs a private key for the attribute set ω, message m, and predicate Υ
u
,
ω
*
(
·
). In order to sign message m with predicate Υ
u
,
ω
*
(
·
), that is, to prove the signer owning at least u attribute among the c-elements attribute set ω
*. It selects a u-element from the subset ω
′
⊆
ω
∩
ω
* and works as follows.(1)
First, it selects a default attribute subsetΩ
′
⊆
Ω with |
Ω
′
|
=
d
-
u and chooses c
+
d
-
u random values r
i
′
∈
Z
p for i
∈
ω
*
∪
Ω
′.
(2)
It then computes(8)
σ
0
=
∏
i
∈
ω
′
∪
Ω
′
‍
d
i
0
Δ
i
,
S
0
∏
i
∈
ω
*
∪
Ω
′
‍
g
1
T
i
r
i
′
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
,
σ
i
=
d
i
1
Δ
i
,
S
0
g
r
i
′
i
∈
ω
′
∪
Ω
′
,
σ
i
=
g
r
i
′
i
∈
ω
*
/
ω
′
,
σ
0
′
=
g
r
s
.
(3)
Finally, the algorithm outputs the signature:(9)
σ
=
σ
0
,
σ
i
i
∈
ω
*
∪
Ω
′
,
σ
0
′
.StandardVerify. In order to verify the correctness of the signature σ
=
(
σ
0
,
{
σ
i
}
i
∈
ω
*
∪
Ω
′
,
σ
0
′
) on m with threshold k for attributes set ω
*
∪
Ω
′, it checks if the following equation holds:
(10)
e
(
g
,
σ
0
)
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
1
T
i
,
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
σ
0
′
=
A
(
i
)
.
If the equation holds, it indicates that the signature is indeed from some users with k attributes among ω
*. Otherwise, it denotes the signature is not valid.MComb. For each user in the multisignature, the algorithm inputs a public parameters p
a
r
a
m
s, public key P
K
(
k
), and a signature σ
(
k
). All the signatures are signed on a single message m. Let m be an m
′-bit message to be signed by the original signers A
1
′
,
A
2
′
,
…
,
A
l
′ and m
d denote the dth bit of m, and let M
⊆
{
1,2
,
…
,
m
′
} be the set of all d for which m
d
=
1. Denote P
K
(
k
) as user k’s public keys and its corresponding signature σ
k as σ
(
k
)
=
(
σ
0
(
k
)
,
{
σ
i
}
i
∈
ω
*
∪
Ω
′
(
k
)
,
σ
0
′
(
k
)
). Verify that σ
(
k
) is valid by calling theStandardVerify algorithm. If not, its outputs fail and halt. Otherwise, the algorithm takes following steps.For each user in the multisignature the algorithm inputs a public parametersp
a
r
a
m
s, public key P
K
(
k
), and a signature σ
(
k
). All the signatures are signed on a single message m. Let m be an m
′-bit message to be signed by the original signers A
1
′
,
A
2
′
,
…
,
A
l
′ and m
d denote the dth bit of m, and let M
⊆
{
1,2
,
…
,
m
′
} be the set of all d for which m
d
=
1. Denote P
K
(
k
) as user k’s public keys and its corresponding signature σ
k as σ
(
k
)
=
(
σ
0
(
k
)
,
{
σ
i
}
i
∈
ω
*
∪
Ω
′
(
k
)
,
σ
0
′
(
k
)
). Verify that σ
(
k
) is valid by calling theStandardVerify algorithm. If not, its outputs fail and halt. Otherwise, the algorithm takes following steps.This algorithm first initializesp
σ
p, and sets p
σ
p
0
=
1 and p
σ
p
2
=
1. For every i belong to ω
′
∪
Ω
′ and ω
*
/
ω
′, sets p
σ
i
=
1. Also, the algorithm initializes ω
′
∪
Ω
′
=
∅ and ω
*
/
ω
′
=
∅.Fork
=
1
,
…
,
l, it calculates
(11)
p
σ
p
0
=
p
σ
p
0
·
σ
0
(
k
)
,
p
σ
p
2
=
p
σ
p
2
·
σ
0
′
(
k
)
.
Then for every i
∈
ω
k
′
∪
Ω
k
′, if  i  does not exist in ω
′
∪
Ω
′, it adds attribute  i  to the attribute set ω
′
∪
Ω
′ and sets p
σ
i
=
d
i
1
Δ
i
,
S
k
(
0
)
g
r
i
′. If  i  exists in ω
′
∪
Ω
′, it sets σ
i
(
k
)
=
d
i
1
Δ
i
,
S
k
(
0
)
g
r
i
′ and calculates p
σ
i
=
p
σ
i
·
σ
i
(
k
).For everyi
∈
ω
k
*
/
ω
k
′, if i does not exist in ω
*
/
ω
′, it adds attribute i to the attribute set ω
*
/
ω
′ and sets p
σ
i
=
g
r
i
′. If i exists in ω
*
/
ω
′, it sets σ
i
(
k
)
=
g
r
i
′ and computes p
σ
i
=
p
σ
i
·
σ
i
(
k
).The algorithm finally computes:(12)
p
σ
p
=
(
p
σ
p
0
,
p
σ
i
i
∈
ω
′
∪
Ω
′
,
p
σ
i
i
∈
ω
*
/
ω
′
,
p
σ
p
2
)
.MultiVerify. Given the public parameters, public keys, a message m
∈
{
0,1
}
m
′, and a signature p
σ
p
=
(
p
σ
p
0
,
{
p
σ
i
}
i
∈
ω
′
∪
Ω
′
,
{
p
σ
i
}
i
∈
ω
*
/
ω
′
,
p
σ
p
2
), a verifieraccept
p
σ
p if the following equality holds:
(13)
e
(
p
σ
p
0
,
g
)
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
1
T
i
,
p
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
p
σ
p
2
=
∏
i
=
1
l
‍
A
(
i
)
.Otherwise, it outputsreject.


## 5. Security of ABMS Scheme

In this section, we first show the correctness of our ABMS scheme. Then we prove that our ABMS scheme is existential unforgeability by using hard problem introduced in Section2.2.


### 5.1. Correctness

The signaturep
σ
p generated fromMComb algorithm can be easily checked by verifier:
(14)
e
p
σ
p
0
,
g
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
1
T
i
,
p
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
p
σ
p
2
=
e
∏
k
=
1
l
‍
∏
i
∈
ω
k
′
∪
Ω
k
′
‍
d
i
0
Δ
i
,
S
k
0
∏
i
∈
ω
k
*
∪
Ω
k
′
‍
g
1
T
i
r
i
,
k
′
h
h
h
h
h
h
h
h
h
h
∏
i
∈
ω
k
′
∪
Ω
k
′
‍
d
i
0
Δ
i
,
S
k
0
∏
i
∈
ω
k
*
∪
Ω
k
′
‍
g
1
T
i
r
i
,
k
′
·
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
,
k
,
g
·
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
1
T
i
,
p
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
∏
k
=
1
l
‍
g
r
s
,
k
-
1
=
∏
k
=
1
l
‍
e
∏
i
∈
ω
k
′
∪
Ω
k
′
‍
g
2
q
0
Δ
i
,
S
k
0
,
g
=
∏
k
=
1
l
‍
e
(
g
2
a
i
,
g
)
=
∏
i
=
1
l
‍
A
(
i
)
.


### 5.2. Existential Unforgeability

In this section, we show our ABMS scheme which is existential unforgeability by giving the following theorem.Theorem 3.
The attribute based multisignature scheme is(
t
,
q
e
,
q
S
,
ϵ
)-unforgeable if the (
t
′
,
ϵ
′
)-CDH assumption holds where
(15)
ϵ
′
≥
ϵ
4
d
-
1
d
-
k
(
n
m
+
1
)
(
q
S
)
,
t
′
=
t
+
O
d
q
e
+
q
S
+
n
m
·
q
S
ρ
+
d
q
e
+
q
S
+
n
m
·
q
S
τ
,
and ρ and τ are the time for a multiplication and an exponentiation in G, respectively.Proof.
We will assume that adversaryA has advantage ϵ in attacking the scheme. We will construct the algorithm B that solve the CDH with probability at least ϵ
′. The algorithm B will be given a group G, a generator g, and the elements g
a and g
b. In order to use A to compute the g
a
b, B must simulate a challenger for A. Such a simulation can be created in the following way.
Setup. We assume l
m
=
2
q
S. Let the default attribute set be Ω
=
{
Ω
1
,
Ω
2
,
…
,
Ω
d
-
1
} for some predefined integer d. B first define h
i as h
i
=
g
t
i where t
i is randomly chosen from Z
p. Then it chooses a random k
∈
{
0
,
…
,
q
}, and random numbers x
′
,
x
1
,
…
,
x
m
∈
Z
l
m. It also chooses additional random exponents z
′
,
z
1
,
…
,
z
m
∈
Z
p. Consider
(16)
u
′
=
g
2
x
′
-
l
1
k
1
′
g
z
′
,
u
k
=
g
2
x
j
g
z
j
,
1
≤
j
≤
m
.
To make the notion easy to follow, we define two functionsF
(
m
), J
(
m
)
(17)
F
(
m
)
=
x
′
-
k
1
′
l
1
-
∑
j
∈
M
‍
x
j
m
j
,
J
(
m
)
=
z
′
+
∑
j
∈
M
‍
z
j
m
j
.
The master secret key will be g
2
α
=
g
2
a
=
g
a
b and the following equations holds:
(18)
u
′
∏
j
∈
M
‍
u
j
m
j
=
g
2
F
(
m
)
g
J
(
m
)
.
Extract Query. A can make requests for private key on Ω such that ω
∩
ω
*
<
k. We first define three subsets Γ
,
Γ
′
,
S in the following manner: Γ
=
(
ω
∩
ω
*
)
∪
Ω
* and Γ
⊆
Γ
′
⊆
S and Γ
′
=
d
-
1. Let S
=
Γ
′
∪
{
0
}. For i
∈
Γ
′, compute D
i
=
(
g
2
λ
i
(
g
2
g
t
i
)
r
i
,
g
r
i
) where λ
i
,
r
i are randomly chosen in Z
p. For i
∉
Γ
′, it could also simulate as
(19)
D
1
i
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
1
-
t
i
g
2
g
t
i
r
i
′
Δ
0
,
S
i
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
-
a
t
i
g
2
g
t
i
r
i
′
Δ
0
,
S
(
i
)
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
2
a
g
2
g
t
i
-
a
g
2
g
t
i
r
i
′
Δ
0
,
S
(
i
)
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
2
a
g
2
g
t
i
r
i
′
-
a
Δ
0
,
S
(
i
)
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
2
a
Δ
0
,
S
i
g
2
g
t
i
r
i
=
g
2
q
i
g
2
T
i
r
i
,
D
2
(
i
)
=
g
1
-
1
g
r
i
′
Δ
0
,
S
(
i
)
=
g
r
i
′
-
a
Δ
0
,
S
(
i
)
.
Sign Query. Consider the query for a signature of attribute set on m. If  F
(
m
)
=
0
(
mod
⁡
p
), the simulation aborts. Otherwise, B selects a random set Λ such that and |
Λ
|
=
d
-
1. Define g
q
′
i
=
g
λ
i
′ where λ
i
′ is chosen randomly in Z
p. Then it computes g
q
′
i
=
∏
k
=
1
d
-
1
‍
g
λ
k
′
Δ
k
,
ω
u
*
(
i
)
g
a
Δ
0
,
ω
u
*
(
i
) for i
∈
ω
*
-
Λ. B randomly picks r
i
′
,
r
^
s
∈
Z
p and computes the signature as
(20)
σ
=
S
1
,
σ
k
1
i
∈
ω
,
S
3
,
where
(21)
S
1
=
g
1
-
J
m
/
F
m
∏
i
∈
ω
′
∪
Ω
′
‍
g
2
T
i
r
i
Δ
i
,
S
0
·
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
g
J
m
g
2
F
m
r
^
s
=
g
2
a
∏
i
∈
ω
′
∪
Ω
′
‍
g
2
T
i
r
i
Δ
i
,
S
0
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
·
g
J
m
g
2
F
m
r
s
-
a
/
F
(
m
)
=
g
2
a
∏
i
∈
ω
′
∪
Ω
′
‍
g
2
T
i
r
i
Δ
i
,
S
0
·
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
g
J
m
g
2
F
m
r
s
=
g
2
a
∏
i
∈
ω
′
∪
Ω
′
‍
g
2
T
i
r
i
Δ
i
,
S
0
·
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
=
∏
i
∈
ω
′
∪
Ω
′
‍
d
i
0
Δ
i
,
S
0
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
,
S
2
=
d
i
1
Δ
i
,
S
0
g
r
i
′
i
∈
ω
′
∪
Ω
′
,
S
2
=
g
r
i
′
i
∈
ω
*
/
ω
,
S
3
=
g
1
-
1
/
F
(
m
)
g
r
s
.
Output. Finally, A outputs a signature σ
*
=
(
S
1
*
,
{
σ
k
i
*
}
i
∈
ω
,
S
3
*
) on some message M
* with public keys A
(
1
)
,
…
,
A
(
l
) for some l, where A
(
1
) is equal to A as the challenge key. Attribute set ω
c
*
∪
Ω
c
′ contains the attribute from user 2 to l. Attribute set ω
*
∪
Ω
′ contains the attribute from user 1 to l. It outputs the private key for all keys except the challenge key. Algorithm B sets
(22)
S
1
=
S
1
*
∏
i
∈
ω
c
*
∪
Ω
c
′
‍
e
g
2
T
i
,
p
σ
k
i
-
1
∏
k
=
2
l
‍
e
g
,
g
-
α
(
k
)
,
S
3
=
S
3
*
.
Then we have
(23)
e
g
,
S
1
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
S
3
∏
i
∈
ω
1
*
∪
Ω
1
′
‍
e
g
2
T
i
,
p
σ
i
=
e
(
g
,
S
1
)
∏
i
∈
ω
c
*
∪
Ω
c
′
‍
e
g
2
T
i
,
p
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
S
3
h
h
h
h
h
h
h
h
h
h
h
h
·
∏
i
∈
ω
1
*
∪
Ω
1
′
‍
e
g
2
T
i
,
σ
i
-
1
·
∏
k
=
2
l
‍
e
g
,
g
-
α
(
k
)
=
e
g
,
S
1
·
∏
k
=
2
l
‍
e
g
,
g
-
α
k
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
2
T
i
,
p
σ
k
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
S
3
=
∏
k
=
1
l
‍
A
(
k
)
·
∏
k
=
2
l
‍
A
-
(
k
)
=
A
(
1
)
=
A
.
If the equation holds andω
=
ω
′ and F
(
m
*
)
=
0
(
mod
⁡
p
), B computes and outputs:
(24)
S
1
*
∏
i
∈
ω
1
∪
Ω
1
′
‍
S
2
*
f
(
i
)
S
3
*
J
(
m
)
=
g
a
b
,
where
(25)
S
1
*
=
g
2
a
∏
i
∈
ω
1
*
∪
Ω
1
*
‍
g
2
T
i
r
i
Δ
i
,
S
0
+
r
i
′
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
=
g
2
a
∏
i
∈
ω
1
*
∪
Ω
1
*
‍
g
f
i
r
i
Δ
i
,
S
0
g
f
i
r
i
′
g
J
m
r
s
,
S
2
*
=
g
r
i
Δ
i
,
S
(
0
)
+
r
i
′
,
S
3
*
=
g
r
s
.
This is the solution to the given CDH problem.
We will analyze the probability ofB without aborting to complete the description of the simulation. We require that the following cases happen.
We define the eventsA
k
,
A
*
,
B
,
C without abort duringExtract queries,Sign queries,
(26)
A
k
:
F
m
k
≠
0
mod
⁡
l
m
,
A
*
:
F
m
*
=
0
mod
⁡
p
.
From the analysis above, the probability of B not aborting is
(27)
Pr
⁡
[
Not-abort
]
≥
Pr
⁡
[
⋀
k
=
1
q
I
A
k
∧
A
*
]
.
The assumption l
m
(
n
m
+
1
)
<
p implies that if F
(
m
*
)
=
0
(
mod
⁡
p
), then F
(
m
*
)
=
0
(
mod
⁡
l
m
). Consider
(28)
Pr
⁡
⁡
A
*
=
Pr
⁡
⁡
[
F
(
m
*
)
=
0
(
mod
⁡
p
)
∧
F
(
m
*
)
=
0
(
mod
⁡
l
m
)
]
=
Pr
⁡
⁡
F
m
*
=
0
mod
⁡
l
m
·
Pr
⁡
[
F
(
m
*
)
=
0
(
mod
⁡
p
)
∧
F
(
m
*
)
=
0
(
mod
⁡
l
m
)
]
=
1
l
m
n
m
+
1
.
We also have that
(29)
Pr
⁡
[
⋀
k
=
1
q
I
A
k
∣
A
*
]
=
1
-
Pr
⁡
[
⋁
k
=
1
q
I
A
-
k
∣
A
*
]
≥
1
-
∑
k
=
1
q
I
‍
Pr
⁡
[
A
-
k
∣
A
*
]
.
Since the output of F
(
m
i
1
) and F
(
m
i
2
)
(
i
1
≠
i
2
) will differ at least one random chosen value, the event F
(
m
i
1
)
=
0
(
mod
⁡
l
m
) and F
(
m
i
2
)
=
0
(
mod
⁡
l
m
) are independent. The event A
i and A
* are independent for any i. Hence, we have
(30)
Pr
⁡
[
⋀
k
=
1
q
I
A
k
∧
A
*
]
≥
1
l
m
(
n
m
+
1
)
1
-
q
S
l
m
.
Letl
m
=
2
q
S and we get
(31)
Pr
⁡
⁡
Not-abort
≥
Pr
⁡
⁡
⋀
k
=
1
q
I
A
k
∧
A
*
≥
Pr
⁡
[
⋀
k
=
1
q
I
A
k
∧
A
*
]
≥
1
4
(
n
m
+
1
)
q
S
.
If the simulation does not abort, the probability for correct guess ofd
-
k elements subset Ω
* from d
-
1 element set Ω is 1
/
d
-
1
d
-
k. Therefore, the advantage for solving CDH problem is
(32)
ϵ
′
≥
ϵ
4
d
-
1
d
-
k
(
n
m
+
1
)
(
q
S
)
.
AlgorithmB’s running time is of A plus the overhead in handling A’s q
S
Sign queries. The time complexity of B is
(33)
t
′
=
t
+
O
d
q
e
+
q
S
+
n
m
·
q
S
ρ
+
d
q
e
+
q
S
+
n
m
·
q
S
τ
where ρ and τ are the time for a multiplication and an exponentiation in G, respectively.


## 5.1. Correctness

The signaturep
σ
p generated fromMComb algorithm can be easily checked by verifier:
(14)
e
p
σ
p
0
,
g
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
1
T
i
,
p
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
p
σ
p
2
=
e
∏
k
=
1
l
‍
∏
i
∈
ω
k
′
∪
Ω
k
′
‍
d
i
0
Δ
i
,
S
k
0
∏
i
∈
ω
k
*
∪
Ω
k
′
‍
g
1
T
i
r
i
,
k
′
h
h
h
h
h
h
h
h
h
h
∏
i
∈
ω
k
′
∪
Ω
k
′
‍
d
i
0
Δ
i
,
S
k
0
∏
i
∈
ω
k
*
∪
Ω
k
′
‍
g
1
T
i
r
i
,
k
′
·
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
,
k
,
g
·
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
1
T
i
,
p
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
∏
k
=
1
l
‍
g
r
s
,
k
-
1
=
∏
k
=
1
l
‍
e
∏
i
∈
ω
k
′
∪
Ω
k
′
‍
g
2
q
0
Δ
i
,
S
k
0
,
g
=
∏
k
=
1
l
‍
e
(
g
2
a
i
,
g
)
=
∏
i
=
1
l
‍
A
(
i
)
.


## 5.2. Existential Unforgeability

In this section, we show our ABMS scheme which is existential unforgeability by giving the following theorem.Theorem 3.
The attribute based multisignature scheme is(
t
,
q
e
,
q
S
,
ϵ
)-unforgeable if the (
t
′
,
ϵ
′
)-CDH assumption holds where
(15)
ϵ
′
≥
ϵ
4
d
-
1
d
-
k
(
n
m
+
1
)
(
q
S
)
,
t
′
=
t
+
O
d
q
e
+
q
S
+
n
m
·
q
S
ρ
+
d
q
e
+
q
S
+
n
m
·
q
S
τ
,
and ρ and τ are the time for a multiplication and an exponentiation in G, respectively.Proof.
We will assume that adversaryA has advantage ϵ in attacking the scheme. We will construct the algorithm B that solve the CDH with probability at least ϵ
′. The algorithm B will be given a group G, a generator g, and the elements g
a and g
b. In order to use A to compute the g
a
b, B must simulate a challenger for A. Such a simulation can be created in the following way.
Setup. We assume l
m
=
2
q
S. Let the default attribute set be Ω
=
{
Ω
1
,
Ω
2
,
…
,
Ω
d
-
1
} for some predefined integer d. B first define h
i as h
i
=
g
t
i where t
i is randomly chosen from Z
p. Then it chooses a random k
∈
{
0
,
…
,
q
}, and random numbers x
′
,
x
1
,
…
,
x
m
∈
Z
l
m. It also chooses additional random exponents z
′
,
z
1
,
…
,
z
m
∈
Z
p. Consider
(16)
u
′
=
g
2
x
′
-
l
1
k
1
′
g
z
′
,
u
k
=
g
2
x
j
g
z
j
,
1
≤
j
≤
m
.
To make the notion easy to follow, we define two functionsF
(
m
), J
(
m
)
(17)
F
(
m
)
=
x
′
-
k
1
′
l
1
-
∑
j
∈
M
‍
x
j
m
j
,
J
(
m
)
=
z
′
+
∑
j
∈
M
‍
z
j
m
j
.
The master secret key will be g
2
α
=
g
2
a
=
g
a
b and the following equations holds:
(18)
u
′
∏
j
∈
M
‍
u
j
m
j
=
g
2
F
(
m
)
g
J
(
m
)
.
Extract Query. A can make requests for private key on Ω such that ω
∩
ω
*
<
k. We first define three subsets Γ
,
Γ
′
,
S in the following manner: Γ
=
(
ω
∩
ω
*
)
∪
Ω
* and Γ
⊆
Γ
′
⊆
S and Γ
′
=
d
-
1. Let S
=
Γ
′
∪
{
0
}. For i
∈
Γ
′, compute D
i
=
(
g
2
λ
i
(
g
2
g
t
i
)
r
i
,
g
r
i
) where λ
i
,
r
i are randomly chosen in Z
p. For i
∉
Γ
′, it could also simulate as
(19)
D
1
i
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
1
-
t
i
g
2
g
t
i
r
i
′
Δ
0
,
S
i
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
-
a
t
i
g
2
g
t
i
r
i
′
Δ
0
,
S
(
i
)
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
2
a
g
2
g
t
i
-
a
g
2
g
t
i
r
i
′
Δ
0
,
S
(
i
)
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
2
a
g
2
g
t
i
r
i
′
-
a
Δ
0
,
S
(
i
)
=
∏
j
∈
Γ
′
‍
g
2
λ
j
Δ
j
,
S
i
g
2
a
Δ
0
,
S
i
g
2
g
t
i
r
i
=
g
2
q
i
g
2
T
i
r
i
,
D
2
(
i
)
=
g
1
-
1
g
r
i
′
Δ
0
,
S
(
i
)
=
g
r
i
′
-
a
Δ
0
,
S
(
i
)
.
Sign Query. Consider the query for a signature of attribute set on m. If  F
(
m
)
=
0
(
mod
⁡
p
), the simulation aborts. Otherwise, B selects a random set Λ such that and |
Λ
|
=
d
-
1. Define g
q
′
i
=
g
λ
i
′ where λ
i
′ is chosen randomly in Z
p. Then it computes g
q
′
i
=
∏
k
=
1
d
-
1
‍
g
λ
k
′
Δ
k
,
ω
u
*
(
i
)
g
a
Δ
0
,
ω
u
*
(
i
) for i
∈
ω
*
-
Λ. B randomly picks r
i
′
,
r
^
s
∈
Z
p and computes the signature as
(20)
σ
=
S
1
,
σ
k
1
i
∈
ω
,
S
3
,
where
(21)
S
1
=
g
1
-
J
m
/
F
m
∏
i
∈
ω
′
∪
Ω
′
‍
g
2
T
i
r
i
Δ
i
,
S
0
·
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
g
J
m
g
2
F
m
r
^
s
=
g
2
a
∏
i
∈
ω
′
∪
Ω
′
‍
g
2
T
i
r
i
Δ
i
,
S
0
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
·
g
J
m
g
2
F
m
r
s
-
a
/
F
(
m
)
=
g
2
a
∏
i
∈
ω
′
∪
Ω
′
‍
g
2
T
i
r
i
Δ
i
,
S
0
·
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
g
J
m
g
2
F
m
r
s
=
g
2
a
∏
i
∈
ω
′
∪
Ω
′
‍
g
2
T
i
r
i
Δ
i
,
S
0
·
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
=
∏
i
∈
ω
′
∪
Ω
′
‍
d
i
0
Δ
i
,
S
0
∏
i
∈
ω
*
∪
Ω
′
‍
g
2
T
i
r
i
′
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
,
S
2
=
d
i
1
Δ
i
,
S
0
g
r
i
′
i
∈
ω
′
∪
Ω
′
,
S
2
=
g
r
i
′
i
∈
ω
*
/
ω
,
S
3
=
g
1
-
1
/
F
(
m
)
g
r
s
.
Output. Finally, A outputs a signature σ
*
=
(
S
1
*
,
{
σ
k
i
*
}
i
∈
ω
,
S
3
*
) on some message M
* with public keys A
(
1
)
,
…
,
A
(
l
) for some l, where A
(
1
) is equal to A as the challenge key. Attribute set ω
c
*
∪
Ω
c
′ contains the attribute from user 2 to l. Attribute set ω
*
∪
Ω
′ contains the attribute from user 1 to l. It outputs the private key for all keys except the challenge key. Algorithm B sets
(22)
S
1
=
S
1
*
∏
i
∈
ω
c
*
∪
Ω
c
′
‍
e
g
2
T
i
,
p
σ
k
i
-
1
∏
k
=
2
l
‍
e
g
,
g
-
α
(
k
)
,
S
3
=
S
3
*
.
Then we have
(23)
e
g
,
S
1
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
S
3
∏
i
∈
ω
1
*
∪
Ω
1
′
‍
e
g
2
T
i
,
p
σ
i
=
e
(
g
,
S
1
)
∏
i
∈
ω
c
*
∪
Ω
c
′
‍
e
g
2
T
i
,
p
σ
i
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
S
3
h
h
h
h
h
h
h
h
h
h
h
h
·
∏
i
∈
ω
1
*
∪
Ω
1
′
‍
e
g
2
T
i
,
σ
i
-
1
·
∏
k
=
2
l
‍
e
g
,
g
-
α
(
k
)
=
e
g
,
S
1
·
∏
k
=
2
l
‍
e
g
,
g
-
α
k
∏
i
∈
ω
*
∪
Ω
′
‍
e
g
2
T
i
,
p
σ
k
e
u
′
∏
j
∈
M
‍
u
j
m
j
,
S
3
=
∏
k
=
1
l
‍
A
(
k
)
·
∏
k
=
2
l
‍
A
-
(
k
)
=
A
(
1
)
=
A
.
If the equation holds andω
=
ω
′ and F
(
m
*
)
=
0
(
mod
⁡
p
), B computes and outputs:
(24)
S
1
*
∏
i
∈
ω
1
∪
Ω
1
′
‍
S
2
*
f
(
i
)
S
3
*
J
(
m
)
=
g
a
b
,
where
(25)
S
1
*
=
g
2
a
∏
i
∈
ω
1
*
∪
Ω
1
*
‍
g
2
T
i
r
i
Δ
i
,
S
0
+
r
i
′
u
′
∏
j
∈
M
‍
u
j
m
j
r
s
=
g
2
a
∏
i
∈
ω
1
*
∪
Ω
1
*
‍
g
f
i
r
i
Δ
i
,
S
0
g
f
i
r
i
′
g
J
m
r
s
,
S
2
*
=
g
r
i
Δ
i
,
S
(
0
)
+
r
i
′
,
S
3
*
=
g
r
s
.
This is the solution to the given CDH problem.
We will analyze the probability ofB without aborting to complete the description of the simulation. We require that the following cases happen.
We define the eventsA
k
,
A
*
,
B
,
C without abort duringExtract queries,Sign queries,
(26)
A
k
:
F
m
k
≠
0
mod
⁡
l
m
,
A
*
:
F
m
*
=
0
mod
⁡
p
.
From the analysis above, the probability of B not aborting is
(27)
Pr
⁡
[
Not-abort
]
≥
Pr
⁡
[
⋀
k
=
1
q
I
A
k
∧
A
*
]
.
The assumption l
m
(
n
m
+
1
)
<
p implies that if F
(
m
*
)
=
0
(
mod
⁡
p
), then F
(
m
*
)
=
0
(
mod
⁡
l
m
). Consider
(28)
Pr
⁡
⁡
A
*
=
Pr
⁡
⁡
[
F
(
m
*
)
=
0
(
mod
⁡
p
)
∧
F
(
m
*
)
=
0
(
mod
⁡
l
m
)
]
=
Pr
⁡
⁡
F
m
*
=
0
mod
⁡
l
m
·
Pr
⁡
[
F
(
m
*
)
=
0
(
mod
⁡
p
)
∧
F
(
m
*
)
=
0
(
mod
⁡
l
m
)
]
=
1
l
m
n
m
+
1
.
We also have that
(29)
Pr
⁡
[
⋀
k
=
1
q
I
A
k
∣
A
*
]
=
1
-
Pr
⁡
[
⋁
k
=
1
q
I
A
-
k
∣
A
*
]
≥
1
-
∑
k
=
1
q
I
‍
Pr
⁡
[
A
-
k
∣
A
*
]
.
Since the output of F
(
m
i
1
) and F
(
m
i
2
)
(
i
1
≠
i
2
) will differ at least one random chosen value, the event F
(
m
i
1
)
=
0
(
mod
⁡
l
m
) and F
(
m
i
2
)
=
0
(
mod
⁡
l
m
) are independent. The event A
i and A
* are independent for any i. Hence, we have
(30)
Pr
⁡
[
⋀
k
=
1
q
I
A
k
∧
A
*
]
≥
1
l
m
(
n
m
+
1
)
1
-
q
S
l
m
.
Letl
m
=
2
q
S and we get
(31)
Pr
⁡
⁡
Not-abort
≥
Pr
⁡
⁡
⋀
k
=
1
q
I
A
k
∧
A
*
≥
Pr
⁡
[
⋀
k
=
1
q
I
A
k
∧
A
*
]
≥
1
4
(
n
m
+
1
)
q
S
.
If the simulation does not abort, the probability for correct guess ofd
-
k elements subset Ω
* from d
-
1 element set Ω is 1
/
d
-
1
d
-
k. Therefore, the advantage for solving CDH problem is
(32)
ϵ
′
≥
ϵ
4
d
-
1
d
-
k
(
n
m
+
1
)
(
q
S
)
.
AlgorithmB’s running time is of A plus the overhead in handling A’s q
S
Sign queries. The time complexity of B is
(33)
t
′
=
t
+
O
d
q
e
+
q
S
+
n
m
·
q
S
ρ
+
d
q
e
+
q
S
+
n
m
·
q
S
τ
where ρ and τ are the time for a multiplication and an exponentiation in G, respectively.


## 6. Performance Analysis

To analyze the performance of our proposed cryptosystem, we compare our ABMS scheme with Li et al.’s scheme in terms of storage, communication, and computational overheads. We define each type of overheads as follows.Storage Overhead. The number of key materials holds by each entity and the size of signatures which are stored in the data center.Computation Overhead. The computation resources which are occupied by the verifier and the total system.


### 6.1. Storage Overhead

Storage overheads are categorized into following types: the number of public parameters (p
a
r
a
m
s), private key available in the system, the number of private key D
(
k
)
(
k
=
1
:
l
) which is held by each signing owner, and the size of signature storage in the data center. The total length of public parameters is smaller than Li’s scheme. The length of private key held by each signer is the same as Li’s scheme. The signature size stored in the data center is greatly decreased by using ABMS scheme than Li’s scheme. The signature length of Li’s scheme increases linear growth along with the number of users. While in our ABMS scheme, the lower bound of signature size is associated with the signer who have the maximum number of the attributes compared with other signers. The upper bound of the signature is associated with the number of universal attributes involved in the system. We can aggregate l users signature into one short signature which can greatly decrease the storage overhead in the data center, especially when the number of uses involved in the system is huge. Here we compare our scheme with other schemes [23]. We let l be the number of signer, |
c
i
+
d
i
-
u
i
| the size of the attribute set ω
i
*
∪
Ω
i
′, and |
U
| the size of the universal of attribute set. φ is pairing running time in theMultiVerify algorithm. We make the comparison to list in Table 1. In the next section, we use a real workstation to simulate the ABMS scheme.Table 1
Performance analysis.
Functionality/scheme
Signature size
Verification
Li et al. [10]
2
l

+

∑
i
=
1
l
c
i

+

d
i
-
u
i
O


2
l

+

∑
i
=
1
l
c
i

+

d
i
-
u
i


φ
Our upper bound
2
+
U
O
2
+
U
φ
Our lower bound
2

+

max
1
≤
i
≤
l
⁡
c
i

+

d
i
-
u
i
O

2

+

max
1
≤
i
≤
l
⁡
c
i
+
d
i
-
u
i

φ


### 6.2. Computation Overhead

Li’s scheme uses hash function to calculate the attribute. While in our ABMS scheme, we useT
i to construct ABMS scheme which can be proved in the standard model. The number of exponentiation to calculate T
i is associated with the security parameter. When two signers have the same attribute,MComb algorithm increases one more multiplication but decreases one pairing computation for the verifier by runningMultiVerify algorithm. The computation cost of multiplication operation is greatly lower than the pairing operation. The computation cost for verification node to verify the signature can be greatly decreased because of the less pairing operations. The total computation cost of the whole system is also decreased because the multiplication operation cost is lower than the pairing operation.


### 6.3. The Performance Measurements

We now provide some information on the performance achieved by PBC (Pairing-Based Cryptography) library underlying pairing-based cryptosystems. In our experiment, the process is implemented on a workstation with an Inter Pentium CPU running at 2.40 GHz, 6 GB of RAM, and a 5400 RPM 320 GB Serial ATA drive. The OS on the test machine is Ubuntu 12.04 LTS 64-bits with kernel version 3.2.0-23-generic. We use type A pairings which are constructed on the 160-bits elliptic curve group based on the supersingular curvey
2
=
x
3
+
x over a 512-bits finite field. On the test machine, we begin by estimating the cost in terms of basic cryptographic operations. The compute pairings in approximately 1.389 ms and exponentiations in G and G
T take about 1.994 ms and 0.187 ms, and multiplication in G and G
T takes about 0.005 ms and 0.002 ms. All of the computation is running by 10000 times for average. In our simulation system, there are 100 signers involved in the system and the total number of the attributes initialized by theSetup algorithm is 70. The maximum number of attributes belonging to individual signer is 7. We test the total running time and verification time between our ABMS scheme and Li’s scheme [10] and we make the comparison in Figure 2. In Figure 2(a), we show the ABMS scheme’s upper and lower bound of verification time and Li’s ABS verification time. If all the users in the system share the same attribute set, the black line can be achieved which indicate the lower bound verification time of our ABMS scheme. If the attributes associated with users are all different, the blue line can be achieved which indicate the upper bound verification time of our ABMS scheme. When we run theMcomb algorithm, it will introduce some multiplication in G. Because the cost of multiplication in G is greatly smaller than the exponentiation and pairing operations, it will not bring much computation cost to the system. When total numbers of attributes belonging to different users do not reach the number of universe attribute set, the verification time of ABMS scheme is almost similar to the original Li’s scheme. If the number of attribute belonging to a group of signers reached the number of universe attributes set, the verification time can be greatly decreased due to the less pairing computation. In Figure 2(b), we test the total running time between ABMS scheme and Li’s scheme. The analysis is similar to the verification time analytic. From both verification and total running time, this algorithm can greatly decrease the computation cost as it can be showed in our simulation.The simulation results.
(a)
The verification time
(b)
The total running time


## 6.1. Storage Overhead

Storage overheads are categorized into following types: the number of public parameters (p
a
r
a
m
s), private key available in the system, the number of private key D
(
k
)
(
k
=
1
:
l
) which is held by each signing owner, and the size of signature storage in the data center. The total length of public parameters is smaller than Li’s scheme. The length of private key held by each signer is the same as Li’s scheme. The signature size stored in the data center is greatly decreased by using ABMS scheme than Li’s scheme. The signature length of Li’s scheme increases linear growth along with the number of users. While in our ABMS scheme, the lower bound of signature size is associated with the signer who have the maximum number of the attributes compared with other signers. The upper bound of the signature is associated with the number of universal attributes involved in the system. We can aggregate l users signature into one short signature which can greatly decrease the storage overhead in the data center, especially when the number of uses involved in the system is huge. Here we compare our scheme with other schemes [23]. We let l be the number of signer, |
c
i
+
d
i
-
u
i
| the size of the attribute set ω
i
*
∪
Ω
i
′, and |
U
| the size of the universal of attribute set. φ is pairing running time in theMultiVerify algorithm. We make the comparison to list in Table 1. In the next section, we use a real workstation to simulate the ABMS scheme.Table 1
Performance analysis.
Functionality/scheme
Signature size
Verification
Li et al. [10]
2
l

+

∑
i
=
1
l
c
i

+

d
i
-
u
i
O


2
l

+

∑
i
=
1
l
c
i

+

d
i
-
u
i


φ
Our upper bound
2
+
U
O
2
+
U
φ
Our lower bound
2

+

max
1
≤
i
≤
l
⁡
c
i

+

d
i
-
u
i
O

2

+

max
1
≤
i
≤
l
⁡
c
i
+
d
i
-
u
i

φ


## 6.2. Computation Overhead

Li’s scheme uses hash function to calculate the attribute. While in our ABMS scheme, we useT
i to construct ABMS scheme which can be proved in the standard model. The number of exponentiation to calculate T
i is associated with the security parameter. When two signers have the same attribute,MComb algorithm increases one more multiplication but decreases one pairing computation for the verifier by runningMultiVerify algorithm. The computation cost of multiplication operation is greatly lower than the pairing operation. The computation cost for verification node to verify the signature can be greatly decreased because of the less pairing operations. The total computation cost of the whole system is also decreased because the multiplication operation cost is lower than the pairing operation.


## 6.3. The Performance Measurements

We now provide some information on the performance achieved by PBC (Pairing-Based Cryptography) library underlying pairing-based cryptosystems. In our experiment, the process is implemented on a workstation with an Inter Pentium CPU running at 2.40 GHz, 6 GB of RAM, and a 5400 RPM 320 GB Serial ATA drive. The OS on the test machine is Ubuntu 12.04 LTS 64-bits with kernel version 3.2.0-23-generic. We use type A pairings which are constructed on the 160-bits elliptic curve group based on the supersingular curvey
2
=
x
3
+
x over a 512-bits finite field. On the test machine, we begin by estimating the cost in terms of basic cryptographic operations. The compute pairings in approximately 1.389 ms and exponentiations in G and G
T take about 1.994 ms and 0.187 ms, and multiplication in G and G
T takes about 0.005 ms and 0.002 ms. All of the computation is running by 10000 times for average. In our simulation system, there are 100 signers involved in the system and the total number of the attributes initialized by theSetup algorithm is 70. The maximum number of attributes belonging to individual signer is 7. We test the total running time and verification time between our ABMS scheme and Li’s scheme [10] and we make the comparison in Figure 2. In Figure 2(a), we show the ABMS scheme’s upper and lower bound of verification time and Li’s ABS verification time. If all the users in the system share the same attribute set, the black line can be achieved which indicate the lower bound verification time of our ABMS scheme. If the attributes associated with users are all different, the blue line can be achieved which indicate the upper bound verification time of our ABMS scheme. When we run theMcomb algorithm, it will introduce some multiplication in G. Because the cost of multiplication in G is greatly smaller than the exponentiation and pairing operations, it will not bring much computation cost to the system. When total numbers of attributes belonging to different users do not reach the number of universe attribute set, the verification time of ABMS scheme is almost similar to the original Li’s scheme. If the number of attribute belonging to a group of signers reached the number of universe attributes set, the verification time can be greatly decreased due to the less pairing computation. In Figure 2(b), we test the total running time between ABMS scheme and Li’s scheme. The analysis is similar to the verification time analytic. From both verification and total running time, this algorithm can greatly decrease the computation cost as it can be showed in our simulation.The simulation results.
(a)
The verification time
(b)
The total running time


## 7. Conclusion

In this paper, we propose a scheme called attribute based multisignature in order to verify integrity of data efficiently. The ABMS scheme can compress multiple signatures into a single one in order to reduce the bandwidth needed to transmit signatures and the space needed to storage them. It can also provide signer’s anonymity in which we use attributes set instead of identity. Our ABMS scheme is secure against existential unforgeability in an adaptive chosen-message attack under CDH problem. Even more important, ABMS scheme is more appropriate for wireless network communication than traditional ABS scheme.



---

*Source: 827320-2015-02-09.xml*