On the Security of Some Aggregate Signature Schemes

Abstract

Aggregate signature scheme proposed by Boneh, Gentry, Lynn, and Shacham allows nsignatures on ndistinct messages from ndistinct users to aggregate a single signature that convince any verifier that nusers did indeed sign the nmessages, 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.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Recommended by Tak-Wah Lam

School of Computer Science and Software, Tianjin Polytechnic University, Tianjin 300387, China

Received 11 September 2012; Revised 22 November 2012; Accepted 6 December 2012

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 _{m i} 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 ...4;i ...4;n , signer i indeed signed message _{m i} which should be signed by him; he didnot signed message _{m j} . Because in some situation an aggregate signature may satisfy the verification, even though signer i signed message _{m j} . 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} · _{d i} on message _{m i} ; here _{σ i} is the true signature of message _{m i} , when _{d 1} · _{d 2} · ... · _{d n} =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 _{m i} 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 Section 2we introduce preliminaries and the computational assumption. Section 3investigates the security of Rückert et al.'s aggregate signature. Section 4investigates 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 7concludes this paper.

2. Preliminary

2.1. The Bilinear Pairing

Let _{G 1} be a cyclic additive group generated by P , whose order is a prime q , and _{G 2} a cyclic multiplicative group of the same order. Let e : _{G 1} × _{G 1} [arrow right] _{G 2} be a pairing map which satisfies the following conditions.

(1) Bilinearity: for any P ,Q ,R ∈ _{G 1} , we have e (P +Q ,R ) =e (P ,R )e (Q ,R ) and [figure omitted; refer to PDF]

: In particular, for any a ,b ∈ _{Z q} , e (aP ,bP ) =e (P ,P ^{) ab} =e (P ,abP ) =e (abP ,P ) .

(2) Nondegeneracy: there exists P ,Q ∈ _{G 1} , such that e (P ,Q ) ...0;1 .

(3) Computability: there is an efficient algorithm to compute e (P ,Q ) for all P ,Q ∈ _{G 1} .

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

Let G 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 whether c =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 compute abP for given P ,aP ,bP ∈G .

Definition 2.1.

The advantage of an algorithm F in solving the computational Diffie-Hellman problem on group G is [figure omitted; refer to PDF] The probability took over the choice of a ,b and F 's coin tosses. An algorithm F is said to be (t , [straight epsilon] ) -breaks the computational Diffie-Hellman problem on group G if F runs in time at most t , and AdvCDH_F is at least [straight epsilon] .

Definition 2.2.

A group G is said to be (t , [straight epsilon] ) -gap Diffie-Hellman (GDH) group if the decisional Diffie-Hellman problem in G can be efficiently computable and there exists no algorithm (t , [straight epsilon] ) -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 identity ID as input and output a user private key _{S ID} .

Sign

Take private key _{S ID} and a message M as input and output an individual identity-based signature _{σ ID} .

Agg

Given n signatures ( _{σ 1} , ... , _{σ n} ) along with n users' identities ( _{ID 1} , ... , _{ID n} ) and n messages ( _{M 1} , ... , _{M n} ) , output an aggregate signature _{σ Agg} .

Verify

Given an aggregate signature _{σ Agg} , the message, and identities' pair list { ( _{M 1} ,I _{D 1} ) , ... , ( _{M n} ,I _{D n} ) } , 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 identity _{ID 1} at random.

Extraction Queries

Given an identity _{ID i} ( i ...0;1 ), the challenger returns the private key _{S ID i} corresponding to _{ID i} .

Signature Queries

Proceeding adaptively, the adversary may request signatures with respect to identity _{ID i} on messages of his choice.

Response

Finally, the adversary outputs n -1 additional identities ( _{ID 2} , ... ,I _{D n} ) , n messages ( _{M 1} , ... , _{M n} ) and an aggregate signature σ with respect to these n identities, and n messages ( _{M 1} , ... , _{M n} ) .

The adversary wins if the aggregate signature σ is a valid signature on ( _{M 1} , ... , _{M n} ) under _{ID 1} , _{ID 2} , ... , _{ID n} and the adversary did not request the private key for I _{D 1} and did not request a signature on _{M 1} under I _{D 1} .

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 signature V on messages ( _{M j 1} , _{M j 2} ... , _{M j n} ) for identities (I _{D 1} , ... ,I _{D n} ) . But, they claim that they generate an aggregate signature V on messages ( _{M 1} , _{M 2} ... , _{M n} ) for identities (I _{D 1} , ... ,I _{D n} ) , here

(1) ( _{M 1} , _{M 2} ... , _{M n} ) ...0; ( _{M j 1} , _{M j 2} ... , _{M j n} ) ,

(2) V really satisfies the aggregate signature verification equation on messages ( _{M 1} , _{M 2} ... , _{M n} ) for identities (I _{D 1} , ... ,I _{D n} ) .

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 _{G 1} and _{G 2} of prime order l and a multilinear map e are used; g is a generator of _{G 1} . If _{a 1} , ... , _{a n} ∈Z , and _{x 1} , ... , _{x n} ∈ _{G 1} , then e ( ^{x 1 _{a 1}} , ^{x 2 _{a 2}} , ... , ^{x n _{a n}} ) =e ( _{x 1} , _{x 2} , ... , _{x n} ^{) _{a 1 a 2} ... _{a n}} . Rückert et al.'s scheme comprises five algorithms.

Key Generation

The key generation algorithm takes as input the security parameter. It randomly selects 2n elements _{a 1,0} , _{a 1,1} , ... , _{a n ,0} , _{a n ,1} ∈ {1 , ... ,l -1 } . The algorithm computes [figure omitted; refer to PDF] and returns the private key and the public key pair: [figure omitted; refer to PDF]

Signature Issue

It accepts as input a message m = ( _{m 1} , ... , _{m n} ) ∈ {0,1 ^{} n} as well as signing key sk = ( _{a 1,0} , _{a 1,1} , ... , _{a n ,0} , _{a n ,1} ) and computes the signature σ = ^{g ∏ i =1 n _{a i , m i}} .

Signature Verification

It returns 1 iff e ( σ ,g , ... ,g ) =e ( _{u 1 , m 1} , _{u 2 , m 2} , ... , _{u n , m n} ) .

Signature Aggregation

It builds an aggregate signature S on messages ^{m (1 )} , ... , ^{m (q )} , under public keys ^{pk (1 )} , ... , ^{pk (q )} , respectively. It outputs the triple (pk ,M ,S ) . Here S = ^{∏ i =1 q σ (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 keys pk = { ^{pk (1 )} , ... , ^{pk (q )} } , a set of messages M = { ^{m (1 )} , ... , ^{m (q )} } , and an aggregate signature S . It returns 1 iff [figure omitted; refer to PDF]

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

In Rückert et al.'s scheme, let n =2 , two users _{A 1} , _{A 2} with private key and pubic key pairs: [figure omitted; refer to PDF] respectively.

Let ^{m (1 )} = ( ^{m 1 (1 )} , ^{m 2 (1 )} ) , ^{m (2 )} = ( ^{m 1 (2 )} , ^{m 2 (2 )} ) be two messages. Then ^{σ (1 )} = ^{g a 1 , m 1 (1 ) (1 ) · a 2 , m 2 (1 ) (1 )} is the signature on ^{m (1 )} by _{A 1} , ^{σ (2 )} = ^{g a 1 , m 1 (2 ) (2 ) · a 2 , m 2 (2 ) (2 )} is the signature on ^{m (2 )} by _{A 2} . So the aggregate signature produced by users _{A 1} , _{A 2} is [figure omitted; refer to PDF] The aggregate verification equation [figure omitted; refer to PDF] holds.

However, when ^{m 1 (1 )} = ^{m 1 (2 )} , ^{m 2 (1 )} =0 , ^{m 2 (2 )} =1 , ^{a 1 , m 1 (1 ) (1 )} = ^{a 1 , m 1 (2 ) (2 )} =1 , and ^{a 2,0 (1 )} + ^{a 2,1 (2 )} = ^{a 2,0 (2 )} + ^{a 2,1 (1 )} , The equation [figure omitted; refer to PDF] holds. So when the user with public key p ^{k (1 )} signs ^{m (2 )} , the user with public key p ^{k (2 )} signs ^{m (1 )} , they generate aggregate signature [figure omitted; refer to PDF] and also satisfies the aggregate verification equation [figure omitted; refer to PDF]

In this situation, the aggregate signature cannot convince the verifier that signer i signed message _{m i} . 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 _{m i} 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 parameter k ∈Z , the algorithm works as follows.

(1) Generate a prime q , a cyclic additive group _{G 1} and a cyclic multiplicative group _{G 2} of prime order q , a generator P in _{G 1} and an admissible pairing e : _{G 1} × _{G 1} [arrow right] _{G 2} .

(2) Pick a random s ∈ ^{Z q ·} and set _{P pub} =sP .

(3) Choose cryptographic hash functions _{H 1} : {0,1 ^{} *} [arrow right] _{G 1} and _{H 2} : {0,1 ^{} *} [arrow right] _{Z q} .

The system parameters are Y9; q , _{G 1} , _{G 2} ,e ,P , _{P pub} , _{H 1} , _{H 2} YA; .

Extract

For a given string ID ∈ {0,1 ^{} *} .

(1) Compute _{Q ID} = _{H 1} (ID ) ∈ _{G 1} .

(2) Set the private key _{S ID} to be s · _{Q ID} , where s is a master secret.

Sign

Given a private _{S ID} and a message M ∈ {0,1 ^{} *} .

(1) Choose r _{∈ R} ^{Z q *} and compute U =r ·P ∈ _{G 1} .

(2) Compute h = _{H 2} (ID ,M ,U ) ∈ _{Z q} and V = _{S ID} +h ·r · _{P pub} ∈ _{G 1} . The signature on M is σ = (U ,V ) .

Agg

For the aggregating set of users S , assign to each user an index i , ranging from 1 to k = | S | .

(1) Each user _{A i} ∈S computes signature _{σ i} = ( _{U i} , _{V I} ) on a message _{M i} ∈ {0,1 ^{} *} .

(2) Compute V = ^{∑ i =1 k} _{V i} and output σ = ( _{U 1} , ... , _{U k} ,V ) as an aggregate signature on ( _{M 1} , ... , _{M k} ) for ( I _{D 1} , ... ,I _{D k} ) .

AVerify

Given an aggregate signature σ = ( _{U 1} , ... , _{U k} ,V ) as above.

(1) Compute _{Q i} = _{H 1} ( _{ID i} ) and _{h i} = _{H 2} (I _{D i} , _{M i} , _{U i} ) for i =1 , ... ,k .

(2) Verify whether e (V ,P ) =e ( ^{∑ i =1 k} [ _{Q i} + _{h i} · _{U i} ] , _{P pub} ) holds or not. If it holds, accept the aggregate signature σ = ( _{U 1} , ... , _{U k} ,V ) .

4.2. Attack on Shim's Scheme

Let I _{D 1} be an identity of signer _{A 1} and let I _{D 2} be an identity of signer _{A 2} . They claim that they generate an aggregate signature σ = ( _{U 1} , _{U 2} ,V ) on messages ( _{M 1} , _{M 2} ) for identities (I _{D 1} ,I _{D 2} ) . Then, _{A 1} should sign _{M 1} , and _{A 2} should sign _{M 2} . That is to say, they should do as following:

(1) _{A 1} and _{A 2} choose _{r 1} , _{r 2 ∈ R} ^{Z q *} and compute _{U 1} = _{r 1} ·P and _{U 2} = _{r 2} ·P , respectively.

(2) _{A 1} and _{A 2} compute [figure omitted; refer to PDF]

: respectively.

(3) They generate aggregate signature σ = ( _{U 1} , _{U 2} ,V ) on messages ( _{M 1} , _{M 2} ) for identities (I _{D 1} ,I _{D 2} ) . Here V = _{V 1} + _{V 2} .

But, if the aggregate signature satisfies the verification equation, can the verifier be convinced that _{A 1} indeed has signed _{M 1} , and _{A 2} indeed has signed _{M 2} ? They may cooperate to do on purpose as following:

(1) _{A 1} and _{A 2} Choose _{r 1} , _{r 2 ∈ R} ^{Z q *} and compute _{U 1} = _{r 1} ·P and _{U 2} = _{r 2} ·P .

(2) _{A 1} and _{A 2} compute [figure omitted; refer to PDF]

: respectively. They have not signed _{M 1} and _{M 2} , respectively.

(3) They claim that they generate aggregate signature σ = ( _{U 1} , _{U 2} , ^{V *} ) on messages ( _{M 1} , _{M 2} ) for identities (I _{D 1} ,I _{D 2} ) . Here ^{V *} = ^{V 1 *} + ^{V 2 *} .

Since ^{V *} = ^{V 1 *} + ^{V 2 *} = _{V 1} + _{V 2} =V , the verification equation [figure omitted; refer to PDF] Holds. _{A 1} and _{A 2} succeed in forging aggregate signature for (I _{D 1} ,I _{D 2} ) on ( _{M 1} , _{M 2} ) .

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 equation V = _{S ID} +h ·r · _{P pub} ∈ _{G 1} .

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 groups _{G 1} and _{G 2} of prime order and a bilinear map e : _{G 1} × _{G 1} [arrow right] _{G 2} are used. g is a generator of _{G 1} . The scheme employs a hash function h : {0,1 ^{} ·} [arrow right] _{G 2} .

Boneh et al.'s aggregate signature scheme comprises five algorithms.

Key Generation

For a user, pick random x [arrow left] _{Z p} , and compute v = ^{g x} . The user's public key is v ∈ _{G 1} , and secret key is x ∈ _{Z p} .

Signing

Given the secret key x and a message m ∈ {0,1 ^{} ·} , compute h =h (m ) , and the signature σ = ^{h x} .

Verification

Given user's public key v , a message m , and a signature σ , compute h =h (m ) ; accept if e (g , σ ) =e (v ,h ) holds.

Aggregation

For the aggregating set of users U , assign to each user an index i , ranging from 1 to k = | U | . Each user _{u i} ∈U provides a signature _{σ i} ∈ _{G 2} on a message _{m i} ∈ {0,1 ^{} ·} of his choice. Compute the aggregate signature σ = ^{∏ i =1 k} _{σ i} .

Aggregate Verification

Given an aggregate signature σ for an aggregating set of users U , indexed as before, and given the original messages _{m i} ∈ {0,1 ^{} ·} and public keys _{v i} for all users _{u i} ∈U . Compute _{h i} =h ( _{m i} ) for 1 ...4;i ...4;k , and accept if e (g , σ ) = ^{∏ i =1 k} e ( _{v i} , _{h i} ) holds.

5.2. The Security of Boneh et al.'s Scheme

In Boneh et al.'s scheme, given an aggregate signature of two different messages _{m 1} and _{m 2} under two users with public keys _{v 1} and _{v 2} , respectively, if [figure omitted; refer to PDF] then, it will be impossible to know whether signer i signed message _{m i} , and Boneh et al.'s scheme will have the same flaw as that of Rückert et al.'s scheme. But if [figure omitted; refer to PDF] then [figure omitted; refer to PDF] So if the hash function h is secured, h ( _{m 1} ) ...0;h ( _{m 2} ) , 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 parameter k ∈Z , the algorithm works as follows.

(1) Generate a prime q , a cyclic additive group _{G 1} and a cyclic multiplicative group _{G 2} of prime order q , two random generators P and Q in _{G 1} , and an admissible pairing e : _{G 1} × _{G 1} [arrow right] _{G 2} .

(2) Pick a random s ∈ ^{Z q ·} and set _{P pub} =sP .

(3) Choose cryptographic hash functions _{H 1} : {0,1 ^{} *} [arrow right] _{G 1} and _{H 2} : {0,1 ^{} *} [arrow right] _{Z q} .

The system parameters are Y9; q , _{G 1} , _{G 2} ,e ,P , _{P pub} , _{H 1} , _{H 2} YA; .

Extract

For a given string ID ∈ {0,1 ^{} *} .

(1) Compute _{Q ID} = _{H 1} (ID ) ∈ _{G 1} .

(2) Set the private key _{S ID} to be s · _{Q ID} , where s is a master secret.

Sign

Given a private _{S ID} and a message M ∈ {0,1 ^{} *} .

(1) Choose r _{∈ R} ^{Z q *} and compute U =r ·P ∈ _{G 1} .

(2) Compute h = _{H 2} (ID ,M ,U ) ∈ _{Z q} and V =h _{S ID} +r ·Q ∈ _{G 1} . The signature on M is σ = (U ,V ) .

Agg

For the aggregating set of users S , assign to each user an index i , ranging from 1 to k = | S | .

(1) Each user _{A i} ∈S computes signature _{σ i} = ( _{U i} , _{V I} ) on a message _{M i} ∈ {0,1 ^{} *} .

(2) Compute V = ^{∑ i =1 k} _{V i} and output σ = ( _{U 1} , ... , _{U k} ,V ) as an aggregate signature on ( _{M 1} , ... , _{M k} ) for (I _{D 1} , ... ,I _{D k} ) .

Averify

Given an aggregate signature σ = ( _{U 1} , ... , _{U k} ,V ) as above.

(1) Compute _{Q i} = _{H 1} (I _{D i} ) and _{h i} = _{H 2} (I _{D i} , _{M i} , _{U i} ) for i =1 , ... ,k .

(2) Verify whether e (V ,P ) =e ( _{P pub} , ^{∑ i =1 n} _{h i Q I D i} )e (Q , ^{∑ i =1 n} _{U i} ) holds or not. If it holds, accept the aggregate signature σ = ( _{U 1} , ... , _{U k} ,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, let I _{D 1} be the identity of signer _{A 1} , and I _{D 2} the identity of signer _{A 2} . If they cooperate to do as following:

(1) _{A 1} and _{A 2} Choose _{r 1} , _{r 2 ∈ R} ^{Z q *} and compute _{U 1} = _{r 1} ·P and _{U 2} = _{r 2} ·P .

(2) _{A 1} and _{A 2} compute [figure omitted; refer to PDF]

: respectively. Note that they have not signed _{M 1} and _{M 2} , respectively.

(3) They claim that they generate aggregate signature σ = ( _{U 1} , _{U 2} , ^{V *} ) on messages ( _{M 1} , _{M 2} ) for identities (I _{D 1} ,I _{D 2} ) . Here ^{V *} = ^{V 1 *} + ^{V 2 *} .

But, when σ = ( _{U 1} , _{U 2} , ^{V *} ) is a valid aggregate signature on messages ( _{M 1} , _{M 2} ) for identities (I _{D 1} ,I _{D 2} ) , the following equation holds: [figure omitted; refer to PDF] In fact [figure omitted; refer to PDF] If [figure omitted; refer to PDF] then [figure omitted; refer to PDF] So [figure omitted; refer to PDF]

This is impossible. So the inside attack is not successful in improved scheme in two signers' setting.

In n signers' setting, if they generate an aggregate signature V on messages ( _{M j 1} , _{M j 2} ... , _{M j n} ) for identities (I _{D 1} , ... ,I _{D n} ) . But they claim that they generate an aggregate signature V on messages ( _{M 1} , _{M 2} ... , _{M n} ) for identities (I _{D 1} , ... ,I _{D n} ) , here ( _{M 1} , _{M 2} ... , _{M n} ) ...0; ( _{M j 1} , _{M j 2} ... , _{M j n} ) . Then the probability of V satisfying the aggregate signature verification equation on messages ( _{M 1} , _{M 2} ... , _{M n} ) for identities (I _{D 1} , ... ,I _{D n} ) is equal to the probability of the following equation holding [figure omitted; refer to PDF] Here O denotes the identity of the cyclic additive group _{G 1} . 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.

References

[1] D. Boneh, C. Gentry, H. Shacham, B. Lynn, "Aggregate and verifiably encrypted signatures from bilinear maps," in Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRPYT '03), vol. 2656, of Lecture Notes in Computer Science, pp. 416-432, Springer, Warsaw, Poland, May 2003.

[2] S. T. Kent, C. Lynn, J. Mikkelson, K. Seo, "Secure border gateway protocol (S-BGP)-real world performance and deployment issues," in Proceedings of the Network and Distributed System Security Symposium (NDSS '00), Internet Society, 2000.

[3] G. Neven, "Efficient sequential aggregate signed date," in Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRPYT '08), vol. 4965, of Lecture Notes in Computer Science, pp. 52-69, Springer, 2008.

[4] X. Cheng, J. Liu, X. Wang, "Identity-based aggregate and verifiably encrypted signatures from bilinear pairing," in Proceedings of the International Conference on Computational Science and Its Applications (ICCSA '05), vol. 3483, pp. 1046-1054, May 2005.

[5] C. Gentry, Z. Ramzan, "Identity-based aggregate signature," in Proceedings the 9th International Workshop on Theory and Practice in Public Key Cryptography (PKC '06), vol. 3958, of Lecture Notes in Computer Science, pp. 257-273, Springer, 2006.

[6] M. Rückert, D. Schröde, "Aggregate and verifiably encrypted signatures from multilinear maps without random oracles," in Proceedings of the the 3rd International Conference on Information Security and Assurance (ISA'09), vol. 5576, of Lecture Notes in Computer Science, pp. 750-759, Springer, 2009.

[7] R. Sakai, K. Ohgishi, M. Kasahara, "Cryptosystems based on pairing," in Proceedings of the Symposium on Cryptography and Information Security, pp. 26-28, Okinawa, Japan, 2000.

[8] K. A. Shim, "An ID-based aggregate signature scheme with constant pairing computations," The Journal of Systems and Software , vol. 83, no. 10, pp. 1873-1880, 2010.

[9] L. Zhang, F. Zhang, "A new certificateless aggregate signature scheme," Computer Communications , vol. 32, no. 6, pp. 1079-1085, 2009.

[10] Y. Yu, X. Zheng, H. Sun, "An identity based aggregate signature from pairings," Journal of Networks , vol. 6, no. 4, pp. 631-637, 2011.

[11] J. Li, K. Kim, F. Zhang, X. Chen, "Aggregate proxy signature and verifiably encrypted proxy signature," in Proceedings of the International Conference (ProvSec '07), vol. 4784, of Lecture Notes in Computer Science, pp. 208-217, Springer, 2007.

[12] S. Selvi, S. Vivek, J. Shriram, S. Kalaivani, "Identity based aggregate signcryption schemes," in Proceedings of the 10th International Conference on Cryptology in India (INDOCRYPT '09), vol. 5922, of Lecture Notes in Computer Science, pp. 378-397, Springer, 2009.

[13] Z. Shao :, "Enhanced aggregate signature from pairings," in Proceedings of the Conference on Iformation Security and Cryptology (CISC '05), vol. 3822, of Lecture Notes in Computer Science, pp. 140-149, Springer, 2005.

[14] D. Boneh, A. Silverberg, "Applications of multilinear forms to cryptography," Toptic in Algebraic and Noncommutative Geometry, Contemporary Mathematics , vol. 324, pp. 71-90, 2003.

[]