# On the Security of Some Aggregate  Signature Schemes

Authors: Baoyuan Kang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Aggregate signature scheme proposed by Boneh, Gentry, Lynn, and Shacham allowsn signatures on n distinct messages from n distinct users to aggregate a single signature that convince any verifier that n users did indeed sign the n messages, respectively. The main benefit of such schemes is that they allow bandwidth and computational savings. In this paper, we question about whether the existing aggregate signature schemes satisfy the basic property that they can convince any verifier that every user indeed signed the message which should be signed by him. We show that Rückert et al.’s scheme, and Shim’s scheme do not satisfy the property. As a comparison, we investigate Boneh et al.’s scheme and show that under the assumption that each signer correctly signs one message, Boneh et al.’s scheme satisfies this property under two users' setting. Furthermore, we propose the concept of inside attack on aggregate signatures and give an improved aggregate signature scheme based on Shim’s scheme. We also prove that the improved scheme is secure against inside attack.


---

## Body

## 1. Introduction

An aggregate signature scheme as introduced by Boneh et al. [1] is a method for combining n signatures from n different signers on n different messages into a single signature. This single signature (and the n original messages) will convince the verifier that the n signers did indeed sign the n original messages (i.e., signer i signed message mi for i=1,…,n). Typical applications for aggregate signatures are, for example, secure routing [2] or certificate chain compression [1]. The main benefit of aggregate signature is that it saves bandwidth, which makes it an optimal solution for networks of small, battery-powered devices that communicate over energy-consuming wireless channels [3].Since Boneh et al.’s aggregate signature scheme, many aggregate signature schemes are proposed [4–10]. There even are aggregate proxy signature [11] and aggregate signcryption schemes [12]. However, about the security of aggregate signature schemes, only traditional unforgeability was discussed in all existing schemes. We question that whether every existing aggregate signature satisfies the basic property proposed by Boneh et al. that it convinces any verifier that, for all 1≤i≤n, signer i indeed signed message mi which should be signed by him; he didnot signed message mj. Because in some situation an aggregate signature may satisfy the verification, even though signer i signed message mj. We call this attack an inside attack on aggregate signatures. We think this is an important issue to aggregate signatures. Shao [13] discussed the security of aggregate signatures, but its issue was another aspect. He pointed that every signer i forges a signature σi·=σi·di on message mi; here σi is the true signature of message mi, when d1·d2·…·dn=1 and S=σ1··σ2··…·σn· also satisfies the aggregate signature verification.Recently, Rückert et al. [6] proposed the first aggregate signature in standard model. The scheme was based on the Boneh-Silverberg signature [14]. They proved its traditional unforgeability in the standard model while maintaining an optimal signature size and reasonable efficiency. However, in this paper, we show that Rückert et al.’s scheme does not satisfy the basic property that a verifier, given the aggregate signature along with the identities if the parties involved and their respective messages, can be convinced that signer i indeed signed message mi which should be signed by him.  In 2010, Shim proposed an efficient ID-based aggregate signature scheme with constant pairing computations [8]. It is the first scheme whose number of pairing computation in verification is independent of the number of users. But, in this paper we point that Shim’s scheme also does not satisfy the basic property. As a comparison, we investigate Boneh et al.’s scheme [1] and show that under the assumption that each signer signs one message correctly, Boneh et al.’s scheme satisfies this property under two users’ setting. Furthermore, we propose an improved scheme based on Shim’s scheme and prove that the improved scheme is secure against the inside attack.The rest of the paper is organized as follows. In Section2 we introduce preliminaries and the computational assumption. Section 3 investigates the security of Rückert et al.’s aggregate signature. Section 4 investigates the security of the aggregate signature of Shim. As a comparison, we study Boneh et al.’s aggregate signature scheme in Section 5. The improved scheme is in Section 6. Section 7 concludes this paper.


## 2. Preliminary

### 2.1. The Bilinear Pairing

LetG1 be a cyclic additive group generated by P, whose order is a prime q, and G2 a cyclic multiplicative group of the same order. Let e:G1×G1→G2 be a pairing map which satisfies the following conditions.(1)
Bilinearity: for anyP,Q,R∈G1, we have e(P+Q,R)=e(P,R)e(Q,R) and
(2.1)e(P,Q+R)=e(P,Q)e(P,R).In particular, for anya,b∈Zq, e(aP,bP)=e(P,P)ab=e(P,abP)=e(abP,P).(2)
Nondegeneracy: there existsP,Q∈G1, such that e(P,Q)≠1.(3)
Computability: there is an efficient algorithm to computee(P,Q) for all P,Q∈G1.The typical way of obtaining such pairings is by deriving them from the Weil-pairing or the Tate-pairing on an elliptic curve over a finite field.


### 2.2. Gap Diffie-Hellman (GDH) Groups

LetG be a cyclic additive group of prime order q, and let P be a generator of G.(1)
The decisional Diffie-Hellman (DDH) problem is to decide whetherc=ab in Z/qZ for given P,aP,bP,cP∈G. If so, (P,aP,bP,cP) is called a valid Diffie-Hellman tuple.(2)
The computational Diffie-Hellman (CDH) problem is to computeabP for given P,aP,bP∈G.Definition 2.1.
The advantage of an algorithmF in solving the computational Diffie-Hellman problem on group G is
(2.2)AdvCDHF=Pr[F(P,aP,bP)=abP:∀a,b∈Zq].
The probability took over the choice of a,b and F’s coin tosses. An algorithm F is said to be (t,ε)-breaks the computational Diffie-Hellman problem on group G if F runs in time at most t, and AdvCDHF is at least ε.Definition 2.2.
A groupG is said to be (t,ε)-gap Diffie-Hellman (GDH) group if the decisional Diffie-Hellman problem in G can be efficiently computable and there exists no algorithm (t,ε)-breaks the computational Diffie-Hellman problem on group G.


### 2.3. Security Model of Aggregate Signature

We take identity-based aggregate signature (IBAS) for example to give the definition of aggregate signature and its security model. An identity-based aggregate signature is composed of five algorithms [5]: key generation by the private key generation center (PKG), private key extraction by the PKG for individual users, signing by an individual user, aggregation of multiple individual signatures, and verification of an identity-based aggregate signature.KeyGen
Take a security parameterλ as input and output system parameters params and master key msk.KeyExt
Take params, msk. and a user identityID as input and output a user private key SID.Sign
Take private keySID and a message M as input and output an individual identity-based signature σID.Agg
Givenn signatures (σ1,…,σn) along with n users’ identities (ID1,…,IDn) and n messages (M1,…,Mn), output an aggregate signature σAgg.Verify
Given an aggregate signatureσAgg, the message, and identities’ pair list {(M1,ID1),…,(Mn,IDn)}, verify the aggregate signature that if it is valid.


#### 2.3.1. Security Model against Traditional Existential Forgery Attack

An IBAS scheme should be secure against traditional existential forgery under an adaptive chosen-message and an adaptive-chosen-identity attack. We formalize the security model as follows. The adversary’s goal is the existential forgery of an aggregate signature. We give the adversary the power to choose the identities on which it wishes to forge a signature, the power to request the identity-based private key on all but one of these identities. The adversary’s advantage is defined as its probability of success in the following game.Setup.
The adversary is given the needed parameters and an identityID1 at random.Extraction Queries
Given an identityIDi (i≠1), the challenger returns the private key SIDi corresponding to IDi.Signature Queries
Proceeding adaptively, the adversary may request signatures with respect to identityIDi on messages of his choice.Response
Finally, the adversary outputsn-1 additional identities (ID2,…,IDn), n messages (M1,…,Mn) and an aggregate signature σ with respect to these n identities, and n messages (M1,…,Mn).The adversary wins if the aggregate signatureσ is a valid signature on (M1,…,Mn) under ID1,ID2,…,IDn and the adversary did not request the private key for ID1 and did not request a signature on M1 under ID1.


#### 2.3.2. Security Model against Inside Existential Forgery Attack

We defined one new secure concept of aggregate signature as inside attack. It means the included signers to generate an aggregate signatureV on messages (Mj1,Mj2…,Mjn) for identities (ID1,…,IDn). But, they claim that they generate an aggregate signature V on messages (M1,M2…,Mn) for identities (ID1,…,IDn), here(1)
(M1,M2…,Mn)≠(Mj1,Mj2…,Mjn),(2)
V really satisfies the aggregate signature verification equation on messages (M1,M2…,Mn) for identities (ID1,…,IDn).The concept of inside attack is closely related to the basic property of aggregate signature that it should convince any verifier that every user indeed signed the message which should be signed by him.


## 2.1. The Bilinear Pairing

LetG1 be a cyclic additive group generated by P, whose order is a prime q, and G2 a cyclic multiplicative group of the same order. Let e:G1×G1→G2 be a pairing map which satisfies the following conditions.(1)
Bilinearity: for anyP,Q,R∈G1, we have e(P+Q,R)=e(P,R)e(Q,R) and
(2.1)e(P,Q+R)=e(P,Q)e(P,R).In particular, for anya,b∈Zq, e(aP,bP)=e(P,P)ab=e(P,abP)=e(abP,P).(2)
Nondegeneracy: there existsP,Q∈G1, such that e(P,Q)≠1.(3)
Computability: there is an efficient algorithm to computee(P,Q) for all P,Q∈G1.The typical way of obtaining such pairings is by deriving them from the Weil-pairing or the Tate-pairing on an elliptic curve over a finite field.


## 2.2. Gap Diffie-Hellman (GDH) Groups

LetG be a cyclic additive group of prime order q, and let P be a generator of G.(1)
The decisional Diffie-Hellman (DDH) problem is to decide whetherc=ab in Z/qZ for given P,aP,bP,cP∈G. If so, (P,aP,bP,cP) is called a valid Diffie-Hellman tuple.(2)
The computational Diffie-Hellman (CDH) problem is to computeabP for given P,aP,bP∈G.Definition 2.1.
The advantage of an algorithmF in solving the computational Diffie-Hellman problem on group G is
(2.2)AdvCDHF=Pr[F(P,aP,bP)=abP:∀a,b∈Zq].
The probability took over the choice of a,b and F’s coin tosses. An algorithm F is said to be (t,ε)-breaks the computational Diffie-Hellman problem on group G if F runs in time at most t, and AdvCDHF is at least ε.Definition 2.2.
A groupG is said to be (t,ε)-gap Diffie-Hellman (GDH) group if the decisional Diffie-Hellman problem in G can be efficiently computable and there exists no algorithm (t,ε)-breaks the computational Diffie-Hellman problem on group G.


## 2.3. Security Model of Aggregate Signature

We take identity-based aggregate signature (IBAS) for example to give the definition of aggregate signature and its security model. An identity-based aggregate signature is composed of five algorithms [5]: key generation by the private key generation center (PKG), private key extraction by the PKG for individual users, signing by an individual user, aggregation of multiple individual signatures, and verification of an identity-based aggregate signature.KeyGen
Take a security parameterλ as input and output system parameters params and master key msk.KeyExt
Take params, msk. and a user identityID as input and output a user private key SID.Sign
Take private keySID and a message M as input and output an individual identity-based signature σID.Agg
Givenn signatures (σ1,…,σn) along with n users’ identities (ID1,…,IDn) and n messages (M1,…,Mn), output an aggregate signature σAgg.Verify
Given an aggregate signatureσAgg, the message, and identities’ pair list {(M1,ID1),…,(Mn,IDn)}, verify the aggregate signature that if it is valid.


### 2.3.1. Security Model against Traditional Existential Forgery Attack

An IBAS scheme should be secure against traditional existential forgery under an adaptive chosen-message and an adaptive-chosen-identity attack. We formalize the security model as follows. The adversary’s goal is the existential forgery of an aggregate signature. We give the adversary the power to choose the identities on which it wishes to forge a signature, the power to request the identity-based private key on all but one of these identities. The adversary’s advantage is defined as its probability of success in the following game.Setup.
The adversary is given the needed parameters and an identityID1 at random.Extraction Queries
Given an identityIDi (i≠1), the challenger returns the private key SIDi corresponding to IDi.Signature Queries
Proceeding adaptively, the adversary may request signatures with respect to identityIDi on messages of his choice.Response
Finally, the adversary outputsn-1 additional identities (ID2,…,IDn), n messages (M1,…,Mn) and an aggregate signature σ with respect to these n identities, and n messages (M1,…,Mn).The adversary wins if the aggregate signatureσ is a valid signature on (M1,…,Mn) under ID1,ID2,…,IDn and the adversary did not request the private key for ID1 and did not request a signature on M1 under ID1.


### 2.3.2. Security Model against Inside Existential Forgery Attack

We defined one new secure concept of aggregate signature as inside attack. It means the included signers to generate an aggregate signatureV on messages (Mj1,Mj2…,Mjn) for identities (ID1,…,IDn). But, they claim that they generate an aggregate signature V on messages (M1,M2…,Mn) for identities (ID1,…,IDn), here(1)
(M1,M2…,Mn)≠(Mj1,Mj2…,Mjn),(2)
V really satisfies the aggregate signature verification equation on messages (M1,M2…,Mn) for identities (ID1,…,IDn).The concept of inside attack is closely related to the basic property of aggregate signature that it should convince any verifier that every user indeed signed the message which should be signed by him.


## 2.3.1. Security Model against Traditional Existential Forgery Attack

An IBAS scheme should be secure against traditional existential forgery under an adaptive chosen-message and an adaptive-chosen-identity attack. We formalize the security model as follows. The adversary’s goal is the existential forgery of an aggregate signature. We give the adversary the power to choose the identities on which it wishes to forge a signature, the power to request the identity-based private key on all but one of these identities. The adversary’s advantage is defined as its probability of success in the following game.Setup.
The adversary is given the needed parameters and an identityID1 at random.Extraction Queries
Given an identityIDi (i≠1), the challenger returns the private key SIDi corresponding to IDi.Signature Queries
Proceeding adaptively, the adversary may request signatures with respect to identityIDi on messages of his choice.Response
Finally, the adversary outputsn-1 additional identities (ID2,…,IDn), n messages (M1,…,Mn) and an aggregate signature σ with respect to these n identities, and n messages (M1,…,Mn).The adversary wins if the aggregate signatureσ is a valid signature on (M1,…,Mn) under ID1,ID2,…,IDn and the adversary did not request the private key for ID1 and did not request a signature on M1 under ID1.


## 2.3.2. Security Model against Inside Existential Forgery Attack

We defined one new secure concept of aggregate signature as inside attack. It means the included signers to generate an aggregate signatureV on messages (Mj1,Mj2…,Mjn) for identities (ID1,…,IDn). But, they claim that they generate an aggregate signature V on messages (M1,M2…,Mn) for identities (ID1,…,IDn), here(1)
(M1,M2…,Mn)≠(Mj1,Mj2…,Mjn),(2)
V really satisfies the aggregate signature verification equation on messages (M1,M2…,Mn) for identities (ID1,…,IDn).The concept of inside attack is closely related to the basic property of aggregate signature that it should convince any verifier that every user indeed signed the message which should be signed by him.


## 3. The Security of the Aggregate Signature Rückert et al.’s Scheme

### 3.1. Brief Review of Rückert et al.’s Scheme

In Rückert et al.’s scheme [6], two groups G1 and G2 of prime order l and a multilinear map e are used; g is a generator of G1.  If a1,…,an∈Z, and x1,…,xn∈G1, then e(x1a1,x2a2,…,xnan)=e(x1,x2,…,xn)a1a2⋯an. Rückert et al.’s scheme comprises five algorithms.Key Generation
The key generation algorithm takes as input the security parameter. It randomly selects2n elements a1,0,a1,1,…,an,0,an,1∈{1,…,l-1}. The algorithm computes
(3.1)u1,0=ga1,0,u1,1=ga1,1,…,un,0=gan,0,un,1=gan,1
and returns the private key and the public key pair:
(3.2)sk=(a1,0,a1,1,…,an,0,an,1),pk=(u1,0,u1,1,…,un,0,un,1).Signature Issue
It accepts as input a messagem=(m1,…,mn)∈{0,1}n as well as signing key sk=(a1,0,a1,1,…,an,0,an,1) and computes the signature σ=g∏i=1nai,mi.Signature Verification
It returns 1 iffe(σ,g,…,g)=e(u1,m1,u2,m2,…,un,mn).Signature Aggregation
It builds an aggregate signatureS on messages m(1),…,m(q), under public keys pk(1),…,pk(q), respectively. It outputs the triple (pk,M,S). Here S=∏i=1qσ(i), pk={pk(1),…,pk(q)}, M={m(1),…,m(q)}, and σ(i) is the signature on message m(i) produced by the user with public key pk(i).Aggregate Verification
It takes as input a set of public keyspk={pk(1),…,pk(q)}, a set of messages M={m(1),…,m(q)}, and an aggregate signature S. It returns 1 iff
(3.3)∏i=1qe(u1,m1(i)(i),u2,m2(i)(i),…,un,mn(i)(i))=e(S,g,…,g).


### 3.2. The Security of Rückert et al.’s Scheme

In Rückert et al.’s scheme, letn=2, two users A1, A2 with private key and pubic key pairs:
(3.4)sk(1)=(a1,0(1),a1,1(1),a2,0(1),a2,1(1)),pk(1)=(u1,0(1),u1,1(1),u2,0(1),u2,1(1)),sk(2)=(a1,0(2),a1,1(2),a2,0(2),a2,1(2)),pk(2)=(u1,0(2),u1,1(2),u2,0(2),u2,1(2)),
respectively.Letm(1)=(m1(1),m2(1)), m(2)=(m1(2),m2(2)) be two messages. Then σ(1)=ga1,m1(1)(1)·a2,m2(1)(1)is the signature on m(1) by A1, σ(2)=ga1,m1(2)(2)·a2,m2(2)(2) is the signature on m(2) by A2. So the aggregate signature produced by users A1, A2 is
(3.5)S=σ(1)·σ(2)=ga1,m1(1)(1)·a2,m2(1)(1)+a1.m1(2)(2)·a2,m2(2)(2).
The aggregate verification equation
(3.6)e(u1,m1(1)(1),u2,m2(1)(1))·e(u1,m1(2)(2),u2,m2(2)(2))=e(g,g)a1,m1(1)(1)·a2,m2(1)(1)+a1,m1(2)(2)·a2,m2(2)(2)=e(S,g)
holds.However, whenm1(1)=m1(2), m2(1)=0, m2(2)=1, a1,m1(1)(1)=a1,m1(2)(2)=1, and a2,0(1)+a2,1(2)=a2,0(2)+a2,1(1), The equation
(3.7)a1,m1(1)(1)·a2,m2(1)(1)+a1,m1(2)(2)·a2,m2(2)(2)=a1,m1(2)(1)·a2,m2(2)(1)+a1,m1(1)(2)·a2,m2(1)(2),
holds. So when the user with public key pk(1) signs m(2), the user with public key pk(2) signs m(1),  they generate aggregate signature
(3.8)S*=ga1,m1(2)(1)·a2,m2(2)(1)+a1.m1(1)(2)·a2,m2(1)(2),
and also satisfies the aggregate verification equation
(3.9)e(u1,m1(1)(1),u2,m2(1)(1))·e(u1,m1(2)(2),u2,m2(2)(2))=e(S*,g).In this situation, the aggregate signature cannot convince the verifier that signeri signed message mi. So Rückert et al.’s aggregate signature is not secure; it does not satisfy the property that a verifier, given the aggregate signature along with the identities if the parties involved and their respective messages, can be convinced that signer i indeed signed message mi which should be signed by him. It is not secure against the inside forgery attack.


## 3.1. Brief Review of Rückert et al.’s Scheme

In Rückert et al.’s scheme [6], two groups G1 and G2 of prime order l and a multilinear map e are used; g is a generator of G1.  If a1,…,an∈Z, and x1,…,xn∈G1, then e(x1a1,x2a2,…,xnan)=e(x1,x2,…,xn)a1a2⋯an. Rückert et al.’s scheme comprises five algorithms.Key Generation
The key generation algorithm takes as input the security parameter. It randomly selects2n elements a1,0,a1,1,…,an,0,an,1∈{1,…,l-1}. The algorithm computes
(3.1)u1,0=ga1,0,u1,1=ga1,1,…,un,0=gan,0,un,1=gan,1
and returns the private key and the public key pair:
(3.2)sk=(a1,0,a1,1,…,an,0,an,1),pk=(u1,0,u1,1,…,un,0,un,1).Signature Issue
It accepts as input a messagem=(m1,…,mn)∈{0,1}n as well as signing key sk=(a1,0,a1,1,…,an,0,an,1) and computes the signature σ=g∏i=1nai,mi.Signature Verification
It returns 1 iffe(σ,g,…,g)=e(u1,m1,u2,m2,…,un,mn).Signature Aggregation
It builds an aggregate signatureS on messages m(1),…,m(q), under public keys pk(1),…,pk(q), respectively. It outputs the triple (pk,M,S). Here S=∏i=1qσ(i), pk={pk(1),…,pk(q)}, M={m(1),…,m(q)}, and σ(i) is the signature on message m(i) produced by the user with public key pk(i).Aggregate Verification
It takes as input a set of public keyspk={pk(1),…,pk(q)}, a set of messages M={m(1),…,m(q)}, and an aggregate signature S. It returns 1 iff
(3.3)∏i=1qe(u1,m1(i)(i),u2,m2(i)(i),…,un,mn(i)(i))=e(S,g,…,g).


## 3.2. The Security of Rückert et al.’s Scheme

In Rückert et al.’s scheme, letn=2, two users A1, A2 with private key and pubic key pairs:
(3.4)sk(1)=(a1,0(1),a1,1(1),a2,0(1),a2,1(1)),pk(1)=(u1,0(1),u1,1(1),u2,0(1),u2,1(1)),sk(2)=(a1,0(2),a1,1(2),a2,0(2),a2,1(2)),pk(2)=(u1,0(2),u1,1(2),u2,0(2),u2,1(2)),
respectively.Letm(1)=(m1(1),m2(1)), m(2)=(m1(2),m2(2)) be two messages. Then σ(1)=ga1,m1(1)(1)·a2,m2(1)(1)is the signature on m(1) by A1, σ(2)=ga1,m1(2)(2)·a2,m2(2)(2) is the signature on m(2) by A2. So the aggregate signature produced by users A1, A2 is
(3.5)S=σ(1)·σ(2)=ga1,m1(1)(1)·a2,m2(1)(1)+a1.m1(2)(2)·a2,m2(2)(2).
The aggregate verification equation
(3.6)e(u1,m1(1)(1),u2,m2(1)(1))·e(u1,m1(2)(2),u2,m2(2)(2))=e(g,g)a1,m1(1)(1)·a2,m2(1)(1)+a1,m1(2)(2)·a2,m2(2)(2)=e(S,g)
holds.However, whenm1(1)=m1(2), m2(1)=0, m2(2)=1, a1,m1(1)(1)=a1,m1(2)(2)=1, and a2,0(1)+a2,1(2)=a2,0(2)+a2,1(1), The equation
(3.7)a1,m1(1)(1)·a2,m2(1)(1)+a1,m1(2)(2)·a2,m2(2)(2)=a1,m1(2)(1)·a2,m2(2)(1)+a1,m1(1)(2)·a2,m2(1)(2),
holds. So when the user with public key pk(1) signs m(2), the user with public key pk(2) signs m(1),  they generate aggregate signature
(3.8)S*=ga1,m1(2)(1)·a2,m2(2)(1)+a1.m1(1)(2)·a2,m2(1)(2),
and also satisfies the aggregate verification equation
(3.9)e(u1,m1(1)(1),u2,m2(1)(1))·e(u1,m1(2)(2),u2,m2(2)(2))=e(S*,g).In this situation, the aggregate signature cannot convince the verifier that signeri signed message mi. So Rückert et al.’s aggregate signature is not secure; it does not satisfy the property that a verifier, given the aggregate signature along with the identities if the parties involved and their respective messages, can be convinced that signer i indeed signed message mi which should be signed by him. It is not secure against the inside forgery attack.


## 4. The Security of Shim’s Aggregate Signature Scheme

### 4.1. Brief Review of Shim’s Scheme

Shim’s scheme [8] comprises five algorithms.Setup.
Given security parameterk∈Z, the algorithm works as follows.(1)
Generate a primeq, a cyclic additive group G1 and a cyclic multiplicative group G2 of prime order q, a generator P in G1 and an admissible pairing e:G1×G1→G2.(2)
Pick a randoms∈Zq· and set Ppub=sP.(3)
Choose cryptographic hash functionsH1:{0,1}*→G1 and H2:{0,1}*→Zq.The system parameters are〈q,G1,G2,e,P,Ppub,H1,H2〉.Extract
For a given stringID∈{0,1}*.(1)
ComputeQID=H1(ID)∈G1.(2)
Set the private keySID to be s·QID, where s is a master secret.Sign
Given a privateSID and a message M∈{0,1}*.(1)
Chooser∈RZq* and compute U=r·P∈G1.(2)
Computeh=H2(ID,M,U)∈Zq and V=SID+h·r·Ppub∈G1. The signature on M is σ=(U,V).Agg
For the aggregating set of usersS, assign to each user an index i, ranging from 1 to k=|S|. (1)
Each userAi∈S computes signature σi=(Ui,VI) on a message Mi∈{0,1}*.(2)
ComputeV=∑i=1kVi and output σ=(U1,…,Uk,V) as an aggregate signature on (M1,…,Mk)for(ID1,…,IDk).AVerify
Given an aggregate signatureσ=(U1,…,Uk,V) as above.(1)
ComputeQi=H1(IDi) and hi=H2(IDi,Mi,Ui) for i=1,…,k.(2)
Verify whethere(V,P)=e(∑i=1k[Qi+hi·Ui],Ppub) holds or not. If it holds, accept the aggregate signature σ=(U1,…,Uk,V).


### 4.2. Attack on Shim’s Scheme

LetID1 be an identity of signer A1 and let ID2 be an identity of signer A2. They claim that they generate an aggregate signature σ=(U1,U2,V) on messages (M1,M2) for identities (ID1,ID2). Then, A1 should sign M1, and A2 should sign M2. That is to say, they should do as following:   (1)
A1 and A2 choose r1,r2∈RZq* and compute U1=r1·P and U2=r2·P, respectively.(2)
A1 and A2 compute
(4.1)V1=S1+H2(ID1,M1,U1)·r1·Ppub,V2=S2+H2(ID2,M2,U2)·r2·Ppub,respectively.(3)
They generate aggregate signatureσ=(U1,U2,V) on messages (M1,M2) for identities (ID1,ID2). Here V=V1+V2.But, if the aggregate signature satisfies the verification equation, can the verifier be convinced thatA1 indeed has signed M1, and A2 indeed has signed M2? They may cooperate to do on purpose as following:   (1)
A1 and A2 Choose r1,r2∈RZq* and compute U1=r1·P and U2=r2·P.(2)
A1 and A2 compute
(4.2)V1*=S1+H2(ID2,M2,U2)·r2·Ppub,V2*=S2+H2(ID1,M1,U1)·r1·Ppubrespectively. They have not signedM1 and M2, respectively.(3)
They claim that they generate aggregate signatureσ=(U1,U2,V*) on messages (M1,M2) for identities (ID1,ID2). Here V*=V1*+V2*.SinceV*=V1*+V2*=V1+V2=V, the verification equation
(4.3)e(V*,P)=e((Q1+h1U1+Q2+h2U2),Ppub)
Holds. A1 and A2 succeed in forging aggregate signature for (ID1,ID2) on (M1,M2).The weakness of Shim’s scheme against this inside forgery attack is due to the separation of the message signed and the private key in the signing equationV=SID+h·r·Ppub∈G1.


## 4.1. Brief Review of Shim’s Scheme

Shim’s scheme [8] comprises five algorithms.Setup.
Given security parameterk∈Z, the algorithm works as follows.(1)
Generate a primeq, a cyclic additive group G1 and a cyclic multiplicative group G2 of prime order q, a generator P in G1 and an admissible pairing e:G1×G1→G2.(2)
Pick a randoms∈Zq· and set Ppub=sP.(3)
Choose cryptographic hash functionsH1:{0,1}*→G1 and H2:{0,1}*→Zq.The system parameters are〈q,G1,G2,e,P,Ppub,H1,H2〉.Extract
For a given stringID∈{0,1}*.(1)
ComputeQID=H1(ID)∈G1.(2)
Set the private keySID to be s·QID, where s is a master secret.Sign
Given a privateSID and a message M∈{0,1}*.(1)
Chooser∈RZq* and compute U=r·P∈G1.(2)
Computeh=H2(ID,M,U)∈Zq and V=SID+h·r·Ppub∈G1. The signature on M is σ=(U,V).Agg
For the aggregating set of usersS, assign to each user an index i, ranging from 1 to k=|S|. (1)
Each userAi∈S computes signature σi=(Ui,VI) on a message Mi∈{0,1}*.(2)
ComputeV=∑i=1kVi and output σ=(U1,…,Uk,V) as an aggregate signature on (M1,…,Mk)for(ID1,…,IDk).AVerify
Given an aggregate signatureσ=(U1,…,Uk,V) as above.(1)
ComputeQi=H1(IDi) and hi=H2(IDi,Mi,Ui) for i=1,…,k.(2)
Verify whethere(V,P)=e(∑i=1k[Qi+hi·Ui],Ppub) holds or not. If it holds, accept the aggregate signature σ=(U1,…,Uk,V).


## 4.2. Attack on Shim’s Scheme

LetID1 be an identity of signer A1 and let ID2 be an identity of signer A2. They claim that they generate an aggregate signature σ=(U1,U2,V) on messages (M1,M2) for identities (ID1,ID2). Then, A1 should sign M1, and A2 should sign M2. That is to say, they should do as following:   (1)
A1 and A2 choose r1,r2∈RZq* and compute U1=r1·P and U2=r2·P, respectively.(2)
A1 and A2 compute
(4.1)V1=S1+H2(ID1,M1,U1)·r1·Ppub,V2=S2+H2(ID2,M2,U2)·r2·Ppub,respectively.(3)
They generate aggregate signatureσ=(U1,U2,V) on messages (M1,M2) for identities (ID1,ID2). Here V=V1+V2.But, if the aggregate signature satisfies the verification equation, can the verifier be convinced thatA1 indeed has signed M1, and A2 indeed has signed M2? They may cooperate to do on purpose as following:   (1)
A1 and A2 Choose r1,r2∈RZq* and compute U1=r1·P and U2=r2·P.(2)
A1 and A2 compute
(4.2)V1*=S1+H2(ID2,M2,U2)·r2·Ppub,V2*=S2+H2(ID1,M1,U1)·r1·Ppubrespectively. They have not signedM1 and M2, respectively.(3)
They claim that they generate aggregate signatureσ=(U1,U2,V*) on messages (M1,M2) for identities (ID1,ID2). Here V*=V1*+V2*.SinceV*=V1*+V2*=V1+V2=V, the verification equation
(4.3)e(V*,P)=e((Q1+h1U1+Q2+h2U2),Ppub)
Holds. A1 and A2 succeed in forging aggregate signature for (ID1,ID2) on (M1,M2).The weakness of Shim’s scheme against this inside forgery attack is due to the separation of the message signed and the private key in the signing equationV=SID+h·r·Ppub∈G1.


## 5. The Security of Boneh et al.’s Aggregate Schemes

We can investigate the security of Boneh et al.’s aggregate signature scheme [1] to provide further illustration to this flaw of about two schemes.


### 5.1.  Brief Review of Boneh et al.’s Scheme

In Boneh et al.’s aggregate signature, two cyclic multiplicative groupsG1 and G2 of prime order and a bilinear map e:G1×G1→G2 are used. g is a generator of G1. The scheme employs a hash function h:{0,1}·→G2.Boneh et al.’s aggregate signature scheme comprises five algorithms.Key Generation
For a user, pick randomx←Zp, and compute v=gx. The user’s public key is v∈G1, and secret key is x∈Zp.Signing
Given the secret keyx and a message m∈{0,1}·, compute h=h(m), and the signature σ=hx.Verification
Given user’s public keyv, a message m, and a signature σ, compute h=h(m); accept if  e(g,σ)=e(v,h) holds.Aggregation
For the aggregating set of usersU, assign to each user an index i, ranging from 1 to k=|U|. Each user ui∈U provides a signature σi∈G2 on a message mi∈{0,1}·of his choice. Compute the aggregate signature σ=∏i=1kσi.Aggregate Verification
Given an aggregate signatureσ for an aggregating set of users U, indexed as before, and given the original messages mi∈{0,1}· and public keys vi for all users ui∈U. Compute hi=h(mi) for 1≤i≤k,  and accept if  e(g,σ)=∏i=1ke(vi,hi) holds.


### 5.2. The Security of Boneh et al.’s Scheme

In Boneh et al.’s scheme, given an aggregate signature of two different messagesm1 and m2 under two users with public keys v1 and v2, respectively, if
(5.1)e(v1,h1)·e(v2,h2)=e(v2,h1)·e(v1,h2),
then, it will be impossible to know whether signer i signed message mi, and Boneh et al.’s scheme will have the same flaw as that of Rückert et al.’s scheme. But if
(5.2)e(v1,h1)·e(v2,h2)=e(v2,h1)·e(v1,h2),
then
(5.3)e(gx1,h1)·e(gx2,h2)=e(gx2,h1)·e(gx1,h2),e(g,h1x1)·e(g,h2x2)=e(g,h1x2)·e(g,h2x1),e(g,h1x1h2x2)=e(g,h1x2h2x1),h1x1h2x2=h1x2h2x1,h1x1-x2=h2x1-x2,h1=h2,h(m1)=h(m2).
So if the hash function h is secured, h(m1)≠h(m2), then, under the assumption that each signer signs one message correctly, Boneh et al.’s scheme does not suffer the same flaw as about two schemes under two users.


## 5.1.  Brief Review of Boneh et al.’s Scheme

In Boneh et al.’s aggregate signature, two cyclic multiplicative groupsG1 and G2 of prime order and a bilinear map e:G1×G1→G2 are used. g is a generator of G1. The scheme employs a hash function h:{0,1}·→G2.Boneh et al.’s aggregate signature scheme comprises five algorithms.Key Generation
For a user, pick randomx←Zp, and compute v=gx. The user’s public key is v∈G1, and secret key is x∈Zp.Signing
Given the secret keyx and a message m∈{0,1}·, compute h=h(m), and the signature σ=hx.Verification
Given user’s public keyv, a message m, and a signature σ, compute h=h(m); accept if  e(g,σ)=e(v,h) holds.Aggregation
For the aggregating set of usersU, assign to each user an index i, ranging from 1 to k=|U|. Each user ui∈U provides a signature σi∈G2 on a message mi∈{0,1}·of his choice. Compute the aggregate signature σ=∏i=1kσi.Aggregate Verification
Given an aggregate signatureσ for an aggregating set of users U, indexed as before, and given the original messages mi∈{0,1}· and public keys vi for all users ui∈U. Compute hi=h(mi) for 1≤i≤k,  and accept if  e(g,σ)=∏i=1ke(vi,hi) holds.


## 5.2. The Security of Boneh et al.’s Scheme

In Boneh et al.’s scheme, given an aggregate signature of two different messagesm1 and m2 under two users with public keys v1 and v2, respectively, if
(5.1)e(v1,h1)·e(v2,h2)=e(v2,h1)·e(v1,h2),
then, it will be impossible to know whether signer i signed message mi, and Boneh et al.’s scheme will have the same flaw as that of Rückert et al.’s scheme. But if
(5.2)e(v1,h1)·e(v2,h2)=e(v2,h1)·e(v1,h2),
then
(5.3)e(gx1,h1)·e(gx2,h2)=e(gx2,h1)·e(gx1,h2),e(g,h1x1)·e(g,h2x2)=e(g,h1x2)·e(g,h2x1),e(g,h1x1h2x2)=e(g,h1x2h2x1),h1x1h2x2=h1x2h2x1,h1x1-x2=h2x1-x2,h1=h2,h(m1)=h(m2).
So if the hash function h is secured, h(m1)≠h(m2), then, under the assumption that each signer signs one message correctly, Boneh et al.’s scheme does not suffer the same flaw as about two schemes under two users.


## 6. An Improvement of Shim’s Identity-Based Aggregate Signature Scheme

### 6.1. The Improved Scheme

The improved scheme comprises five algorithms.Setup.
Given security parameterk∈Z, the algorithm works as follows.(1)
Generate a primeq, a cyclic additive group G1 and a cyclic multiplicative group G2 of prime order q, two random generators P and Q in G1, and an admissible pairing e:G1×G1→G2.(2)
Pick a randoms∈Zq· and set Ppub=sP.(3)
Choose cryptographic hash functionsH1:{0,1}*→G1 and H2:{0,1}*→Zq.The system parameters are〈q,G1,G2,e,P,Ppub,H1,H2〉.Extract
For a given stringID∈{0,1}*.(1)
ComputeQID=H1(ID)∈G1.(2)
Set the private keySID to be s·QID, where s is a master secret.Sign
Given a privateSID and a message M∈{0,1}*.(1)
Chooser∈RZq* and compute U=r·P∈G1.(2)
Computeh=H2(ID,M,U)∈Zq and V=hSID+r·Q∈G1. The signature on M is σ=(U,V).Agg
For the aggregating set of usersS, assign to each user an index i, ranging from 1 to k=|S|. (1)
Each userAi∈S computes signature σi=(Ui,VI) on a message Mi∈{0,1}*.(2)
ComputeV=∑i=1kVi and output σ=(U1,…,Uk,V) as an aggregate signature on (M1,…,Mk)for(ID1,…,IDk).Averify
Given an aggregate signatureσ=(U1,…,Uk,V) as above.(1)
ComputeQi=H1(IDi) and hi=H2(IDi,Mi,Ui) for i=1,…,k.(2)
Verify whethere(V,P)=e(Ppub,∑i=1nhiQIDi)e(Q,∑i=1nUi) holds or not. If it holds, accept the aggregate signature σ=(U1,…,Uk,V).


### 6.2. Security of the Improved Scheme

Following the method in [10], it is easy to prove that the improved scheme is secure against the traditional existential forgery under an adaptive chosen message and an adaptive-chosen identity attack. Here, we only show that our improvement is secure against the inside attack proposed by us.Take two signers as example, letID1 be the identity of signer A1, and ID2 the identity of signer A2. If they cooperate to do as following:(1)
A1 and A2 Choose r1,r2∈RZq* and compute U1=r1·P and U2=r2·P.(2)
A1 and A2 compute
(6.1)V1*=H2(ID2,M2,U2)SID1+r2Q,V2*=H2(ID1,M1,U1)SID2+r1Q,respectively. Note that they have not signedM1 and M2, respectively.(3)
They claim that they generate aggregate signatureσ=(U1,U2,V*) on messages (M1,M2) for identities (ID1,ID2). Here V*=V1*+V2*.But, whenσ=(U1,U2,V*) is a valid aggregate signature on messages (M1,M2) for identities (ID1,ID2), the following equation holds:
(6.2)e(V*,P)=e(H2(ID1,M1,U1)QID1+H2(ID2,M2,U2)QID2,Ppub)e(Q,U1+U2).
In fact
(6.3)e(V*,P)=e(H2(ID2,M2,U2)SID1+r2Q+H2(ID1,M1,U1)SID2+r1Q,P)=e(H2(ID2,M2,U2)QID1+H2(ID1,M1,U1)QID2,Ppub)e(Q,U1+U2).
If
(6.4)e(H2(ID1,M1,U1)QID1+H2(ID2,M2,U2)QID2,Ppub)e(Q,U1+U2)=e(H2(ID2,M2,U2)QID1+H2(ID1,M1,U1)QID2,Ppub)e(Q,U1+U2),
then
(6.5)e(H2(ID1,M1,U1)QID1+H2(ID2,M2,U2)QID2,Ppub)=e(H2(ID2,M2,U2)QID1+H2(ID1,M1,U1)QID2,Ppub).
So
(6.6)H2(ID1,M1,U1)QID1+H2(ID2,M2,U2)QID2=H2(ID2,M2,U2)QID1+H2(ID1,M1,U1)QID2,(H2(ID2,M2,U2)-H(ID1,M1,U1))QID2=(H2(ID2,M2,U2)-H(ID1,M1,U1))QID1QID2=QID1.This is impossible. So the inside attack is not successful in improved scheme in two signers’ setting.Inn signers’ setting, if they generate an aggregate signature V on messages (Mj1,Mj2…,Mjn) for identities (ID1,…,IDn). But they claim that they generate an aggregate signature V on messages (M1,M2…,Mn) for identities (ID1,…,IDn), here  (M1,M2…,Mn)≠(Mj1,Mj2…,Mjn). Then the probability of V satisfying the aggregate signature verification equation on messages (M1,M2…,Mn) for identities (ID1,…,IDn) is equal to the probability of the following equation holding(6.7)(H2(IDj1,Mj1,Uj1)-H(ID1,M1,U1))QID1+(H2(IDj2,Mj2,Uj2)-H(ID2,M2,U2))QID2+⋯+(H2(IDjn,Mjn,Ujn)-H(IDn,Mn,Un))QIDn=O.
Here O denotes the identity of the cyclic additive group G1. So the improved aggregate signature scheme is secured against the inside attack.


## 6.1. The Improved Scheme

The improved scheme comprises five algorithms.Setup.
Given security parameterk∈Z, the algorithm works as follows.(1)
Generate a primeq, a cyclic additive group G1 and a cyclic multiplicative group G2 of prime order q, two random generators P and Q in G1, and an admissible pairing e:G1×G1→G2.(2)
Pick a randoms∈Zq· and set Ppub=sP.(3)
Choose cryptographic hash functionsH1:{0,1}*→G1 and H2:{0,1}*→Zq.The system parameters are〈q,G1,G2,e,P,Ppub,H1,H2〉.Extract
For a given stringID∈{0,1}*.(1)
ComputeQID=H1(ID)∈G1.(2)
Set the private keySID to be s·QID, where s is a master secret.Sign
Given a privateSID and a message M∈{0,1}*.(1)
Chooser∈RZq* and compute U=r·P∈G1.(2)
Computeh=H2(ID,M,U)∈Zq and V=hSID+r·Q∈G1. The signature on M is σ=(U,V).Agg
For the aggregating set of usersS, assign to each user an index i, ranging from 1 to k=|S|. (1)
Each userAi∈S computes signature σi=(Ui,VI) on a message Mi∈{0,1}*.(2)
ComputeV=∑i=1kVi and output σ=(U1,…,Uk,V) as an aggregate signature on (M1,…,Mk)for(ID1,…,IDk).Averify
Given an aggregate signatureσ=(U1,…,Uk,V) as above.(1)
ComputeQi=H1(IDi) and hi=H2(IDi,Mi,Ui) for i=1,…,k.(2)
Verify whethere(V,P)=e(Ppub,∑i=1nhiQIDi)e(Q,∑i=1nUi) holds or not. If it holds, accept the aggregate signature σ=(U1,…,Uk,V).


## 6.2. Security of the Improved Scheme

Following the method in [10], it is easy to prove that the improved scheme is secure against the traditional existential forgery under an adaptive chosen message and an adaptive-chosen identity attack. Here, we only show that our improvement is secure against the inside attack proposed by us.Take two signers as example, letID1 be the identity of signer A1, and ID2 the identity of signer A2. If they cooperate to do as following:(1)
A1 and A2 Choose r1,r2∈RZq* and compute U1=r1·P and U2=r2·P.(2)
A1 and A2 compute
(6.1)V1*=H2(ID2,M2,U2)SID1+r2Q,V2*=H2(ID1,M1,U1)SID2+r1Q,respectively. Note that they have not signedM1 and M2, respectively.(3)
They claim that they generate aggregate signatureσ=(U1,U2,V*) on messages (M1,M2) for identities (ID1,ID2). Here V*=V1*+V2*.But, whenσ=(U1,U2,V*) is a valid aggregate signature on messages (M1,M2) for identities (ID1,ID2), the following equation holds:
(6.2)e(V*,P)=e(H2(ID1,M1,U1)QID1+H2(ID2,M2,U2)QID2,Ppub)e(Q,U1+U2).
In fact
(6.3)e(V*,P)=e(H2(ID2,M2,U2)SID1+r2Q+H2(ID1,M1,U1)SID2+r1Q,P)=e(H2(ID2,M2,U2)QID1+H2(ID1,M1,U1)QID2,Ppub)e(Q,U1+U2).
If
(6.4)e(H2(ID1,M1,U1)QID1+H2(ID2,M2,U2)QID2,Ppub)e(Q,U1+U2)=e(H2(ID2,M2,U2)QID1+H2(ID1,M1,U1)QID2,Ppub)e(Q,U1+U2),
then
(6.5)e(H2(ID1,M1,U1)QID1+H2(ID2,M2,U2)QID2,Ppub)=e(H2(ID2,M2,U2)QID1+H2(ID1,M1,U1)QID2,Ppub).
So
(6.6)H2(ID1,M1,U1)QID1+H2(ID2,M2,U2)QID2=H2(ID2,M2,U2)QID1+H2(ID1,M1,U1)QID2,(H2(ID2,M2,U2)-H(ID1,M1,U1))QID2=(H2(ID2,M2,U2)-H(ID1,M1,U1))QID1QID2=QID1.This is impossible. So the inside attack is not successful in improved scheme in two signers’ setting.Inn signers’ setting, if they generate an aggregate signature V on messages (Mj1,Mj2…,Mjn) for identities (ID1,…,IDn). But they claim that they generate an aggregate signature V on messages (M1,M2…,Mn) for identities (ID1,…,IDn), here  (M1,M2…,Mn)≠(Mj1,Mj2…,Mjn). Then the probability of V satisfying the aggregate signature verification equation on messages (M1,M2…,Mn) for identities (ID1,…,IDn) is equal to the probability of the following equation holding(6.7)(H2(IDj1,Mj1,Uj1)-H(ID1,M1,U1))QID1+(H2(IDj2,Mj2,Uj2)-H(ID2,M2,U2))QID2+⋯+(H2(IDjn,Mjn,Ujn)-H(IDn,Mn,Un))QIDn=O.
Here O denotes the identity of the cyclic additive group G1. So the improved aggregate signature scheme is secured against the inside attack.


## 7. Conclusion

In this paper, we analyse the security of some aggregate signature schemes. We show that Rückert et al.’s scheme cannot convince the verifier that every signer indeed signed the message which should be signed by him. Shim’s scheme also suffers such flaw. As a comparison, we investigate Boneh et al.’s scheme and show that under the assumption that each signer signs one message correctly, Boneh et al.’s aggregate scheme can convince the verifier that every signer indeed signed the message which should be signed by him under two users. Furthermore, we propose the concept of inside attack on aggregate signatures and give an improved scheme based on Shim’s scheme. We also prove that the improved scheme is secured against the inside attack.



---

*Source: 416137-2012-12-26.xml*