Aggregate and Verifiably Encrypted Signatures from Bilinear Maps
Dan Boneh
dabo@cs.stanford.edu

Craig Gentry
cgentry@docomolabs-usa.com

Ben Lynn
blynn@cs.stanford.edu

Hovav Shacham
hovav@cs.stanford.edu

Abstract
An aggregate signature scheme is a digital signature that supports aggregation: Given nsignatures on n distinct messages from n distinct users, it is possible to aggregate all thesesignatures into a single short signature. This single signature (and the n original messages)
will convince the verifier that the n users did indeed sign the n original messages (i.e., user isigned message Mi for i = 1, . . . , n). In this paper we introduce the concept of an aggregate
signature, present security models for such signatures, and give several applications for aggregate
signatures. We construct an efficient aggregate signature from a recent short signature scheme
based on bilinear maps due to Boneh, Lynn, and Shacham. Aggregate signatures are usefulfor reducing the size of certificate chains (by aggregating all signatures in the chain) and for
reducing message size in secure routing protocols such as SBGP. We also show that aggregate
signatures give rise to verifiably encrypted signatures. Such signatures enable the verifier to test
that a given ciphertext C is the encryption of a signature on a given message M . Verifiably
encrypted signatures are used in contract-signing protocols. Finally, we show that similar ideas
can be used to extend the short signature scheme to give simple ring signatures.

1

Introduction

Many real-world applications involve signatures on many different messages generated by manydifferent users. For example, in a Public Key Infrastructure (PKI) of depth n, each user is givena chain of n certificates. The chain contains n signatures by n Certificate Authorities (CAs) onn distinct certificates. Similarly, in the Secure BGP protocol (SBGP) [18] each router receives alist of n signatures attesting to a certain path of length n in the network. A router signs its own
segment in the path and forwards the resulting list of n + 1 signatures to the next router. As
a result, the number of signatures in routing messages is linear in the length of the path. Bothapplications would benefit from a method for compressing the list of signatures on distinct messages
issued by distinct parties. Specifically, X.509 certificate chains could be shortened by compressing
the n signatures in the chain into a single signature.
An aggregate signature scheme enables us to achieve precisely this type of compression. Suppose
each of n users has a public-private key pair (PKi , SKi ). User ui signs message Mi to obtain asignature σi . Then there is a public aggregation algorithm that takes as input all of σ 1 , . . . , σn andoutputs a short compressed signature σ. Anyone can aggregate the n signatures. Moreover, theaggregation can be performed incrementally. That is, signatures σ 1 , σ2 can be aggregated into σ12
which can then be further aggregated with σ3 to obtain σ123 . When aggregating signatures in a
certificate chain, each CA can incrementally aggregate its own signature into the chain. There isalso an aggregate verification algorithm that takes P K1 , . . . , P Kn , M1 , . . . , Mn , and σ and decides
1whether the aggregate signature is valid. Intuitively, the security requirement is that the aggregate
signature σ is declared valid only if the aggregator who created σ was given all of σ 1 , . . . , σn . Precise
security definitions are given in Sect. 3.2. Thus, an aggregate signature provides non-repudiation
at once on many different messages by many users.
We construct an aggregate signature scheme based on a recent short signature due to Boneh,
Lynn, and Shacham (BLS) [6]. This signature scheme works in any group where the Decision DiffieHellman problem (DDH) is easy, but the Computational Diffie-Hellman problem (CDH) is hard.
We refer to such groups as gap groups [6, 26]. Recently there have been a number of constructions
using such gap groups [6, 19, 8, 4]. Surprisingly, general gap groups are insufficient for constructing
efficient aggregate signatures. Instead, our construction uses a pair of groups G 1 , GT and a bilinear
map e : G1 × G1 → GT where CDH is hard in G1 . Joux and Nguyen [17] showed that the map e
can be used to solve DDH in G1 , and so G1 is a gap group. It is the extra structure provided by
the bilinear map that enables us to construct an efficient aggregate signature scheme. We do notknow how to build efficient aggregate signatures from general gap groups. Thus, our construction
is an example where the bilinear map provides extra functionality beyond a simple algorithm forsolving DDH. Bilinear maps were previously used for three-way Diffie-Hellman [16], Identity-Based
Encryption (IBE) [5], and Hierarchical IBE [15, 13].
Aggregate signatures are related to multisignatures [20, 25, 24, 4]. In multisignatures, a set ofusers all sign the same message and the result is a single signature. Recently, Micali et al. [20]defined a security model for multisignatures and gave some constructions and applications. Multisignatures are insufficient for the applications we have in mind, such as certificate chains andSBGP. For these applications we must be able to aggregate signatures on distinct messages. We
note that recently Boldyreva [4] showed that general gap groups are sufficient for constructing multisignatures from BLS signatures. As noted above, to obtain aggregate signatures, one needs theextra structure provided by bilinear maps.
Our application of aggregate signatures to compressing certificate chains is related to an open
problem posed by Micali and Rivest [21]: Given a certificate chain and some special additionalsignatures, can intermediate links in the chain be cut out? Aggregate signatures allow the compression of certificate chains without any additional signatures, but a verifier must still be awareof all intermediate links in the chain. We note that batch RSA [9] also provides some signaturecompression, but only for signatures produced by a single signer.
As a further application for aggregate signatures we show in Sect. 4 that certain aggregate
signature schemes give rise to simple verifiably encrypted signatures. These signatures enable user
Alice to give Bob a signature on a message M encrypted using a third party’s public key and Bob toverify that the encrypted signature is valid. Verifiably encrypted signatures are used in optimistic
contract signing protocols [1, 2] to enable fair exchange. Previous constructions [1, 27] require zeroknowledge proofs to verify an encrypted signature. The verifiably encrypted signatures in Section 4
are short and can be validated efficiently. We note that the resulting contract signing protocol is
not abuse-free in the sense of [10].
As a third application of these ideas we construct in Sect. 5 a simple ring signature [28] usingbilinear maps. As above, the construction using a bilinear map is simpler and more efficient thanconstructions that only make use of gap groups.

2

Signature Schemes Based on Co-Gap Diffie-Hellman

We first review a few concepts related to bilinear maps and Gap Diffie-Hellman signatures [6].
Throughout the paper we use the following notation:
2

1. G1 and G2 are two (multiplicative) cyclic groups of prime order p;
2. g1 is a generator of G1 and g2 is a generator of G2 ;3. ψ is a computable isomorphism from G2 to G1 , with ψ(g2 ) = g1 ; and4. e is a computable bilinear map e : G1 × G2 → GT as described below.
The isomorphism ψ is mostly needed for the proofs of security. To keep the discussion general, we
simply assume that ψ exists and is efficiently computable. When G1 , G2 are subgroups of the groupof points of an elliptic curve E/Fq , the trace map on the curve can be used as this isomorphism(we assume G1 ⊆ E(Fq ) and G2 ⊆ E(Fqr )).
Throughout the paper, we consider bilinear maps e : G1 ×G2 → GT where all groups G1 , G2 , GT
are multiplicative and of prime order p. One could set G1 = G2 . However, we allow for the moregeneral case where G1 6= G2 so that our constructions can make use of certain families of nonsupersingular elliptic curves defined by Miyaji et al. [22]. These curves give rise to very short
signatures [6]. This will lead in turn to short aggregate signatures, ring signatures, etc. To handle
the case G1 6= G2 we define the co-CDH and co-DDH problems [6]. When G1 = G2 , these problems
reduce to the standard CDH and DDH problems. Hence, for the remainder of the paper, although
we handle arbitrary G1 , G2 , for simplicity, the reader may assume G1 = G2 , g1 = g2 , and ψ = I,
the identity map.
With this setup we obtain natural generalizations of the CDH and DDH problems:Computational Co-Diffie-Hellman. Given g2 , g2a ∈ G2 and h ∈ G1 compute ha ∈ G1 .
Decision Co-Diffie-Hellman. Given g2 , g2a ∈ G2 and h, hb ∈ G1 output yes if a = b and nootherwise. When the answer is yes we say that (g2 , g2a , h, ha ) is a co-Diffie-Hellman tuple.
When G1 = G2 and g1 = g2 , these problems reduce to the standard CDH and DDH. Next we define
co-GDH gap groups to be group pairs G1 and G2 on which co-DDH is easy but co-CDH is hard.
Definition 2.1. Two groups (G1 , G2 ) are a decision group pair for co-Diffie-Hellman if the group
action on G1 , the group action on G2 , and the map ψ from G2 to G1 can be computed in one time
unit, and Decision co-Diffie-Hellman on (G1 , G2 ) can be solved in one time unit.
Definition 2.2. The advantage of an algorithm A in solving the Computational co-Diffie-Hellman
problem in groups G1 and G2 is
i
h
def
R
R
Adv co-CDHA = Pr A(g2 , g2a , h) = ha : a ← Zp , h ← G1 .
The probability is taken over the choice of a, h, and A’s coin tosses. An algorithm A (t, )-breaks
Computational co-Diffie-Hellman on G1 and G2 if A runs in time at most t, and Adv co-CDHA isat least . Two Groups (G1 , G2 ) are a (t, )-co-GDH group pair if they are a decision group pairfor co-Diffie-Hellman and no algorithm (t, )-breaks Computational co-Diffie-Hellman on them.

2.1

Bilinear Maps

Let G1 and G2 be two groups as above, with an additional group GT such that |G1 | = |G2 | = |GT |.
A bilinear map is a map e : G1 × G2 → GT with the following properties:
1. Bilinear: for all u ∈ G1 , v ∈ G2 and a, b ∈ Z, e(ua , v b ) = e(u, v)ab .
3

2. Non-degenerate: e(g1 , g2 ) 6= 1.
These properties imply two more: for any u1 , u2 ∈ G1 , v ∈ G2 , e(u1 u2 , v) = e(u1 , v) · e(u2 , v); andfor any u, v ∈ G2 , e(ψ(u), v) = e(ψ(v), u).
Definition 2.3. Two groups (G1 , G2 ) are a bilinear group pair if the group action on either can becomputed in one time unit, the map ψ from G2 to G1 can be computed in one time unit, a bilinear
map e : G1 × G2 → GT exists, and e is computable in one time unit.
Definition 2.4. Two groups (G1 , G2 ) are a (t, )-bilinear group pair for co-Diffie-Hellman if they
are a bilinear group pair and no algorithm (t, )-breaks Computational co-Diffie-Hellman on them.
Joux and Nguyen [17] showed that an efficiently-computable bilinear map e provides an algorithm for solving the decision co-Diffie-Hellman problem. For a tuple (g2 , g2a , h, hb ) we havea = b mod pe(h, g2a ) = e(hb , g2 ) .

⇐⇒Consequently, if two groups (G1 , G2 ) are a (t, )-bilinear group pair for co-Diffie-Hellman, then they
are also a (t/2, )-co-GDH group pair. The converse is probably not true.

2.2

The Co-GDH Signature Scheme

We review the signature scheme of [6], which can be based on any gap group. It comprises threealgorithms, KeyGen, Sign, and Verify, and uses a full-domain hash function H : {0, 1} ∗ → G1 ,viewed as a random oracle [3].
R

Key Generation. Pick random x ← Zp , and compute v ← g2x . The public key is v ∈ G2 . The
secret key is x ∈ Zp .
Signing. Given a secret key x and a message M ∈ {0, 1}∗ , compute h ← H(M ), where h ∈ G1 ,and σ ← hx . The signature is σ ∈ G1 .
Verification. Given a public key v, a message M , and a signature σ, compute h ← H(M ) andverify that (g2 , v, h, σ) is a valid co-Diffie-Hellman tuple.
A co-GDH signature is a single element of G1 . On certain elliptic curves these signatures are very
short: they are half the size of DSA signatures with similar security. Theorem 1 of [6] proves theexistential unforgeability of the scheme under a chosen message attack [14] in the random oracle
model assuming (G1 , G2 ) is a co-gap group pair for Diffie-Hellman.

3

Aggregate Signatures

We define aggregate signatures and describe an aggregate signature scheme based on co-GDH
signatures. Unlike the co-GDH scheme, aggregate signatures require the existence of a bilinear
map. We define security models and provide proofs of security for aggregate signatures.
Consider a set U of users. Each user u ∈ U has a signing keypair (PKu , SKu ). We wish toaggregate the signatures of some subset U ⊆ U. Each user u ∈ U produces a signature σ u on amessage Mu of her choice. These signatures are then combined into a single aggregate σ by anaggregating party. The aggregating party, who can be different from and untrusted by the users
in U , has access to the users’ public keys, to the messages, and to the signatures on them, but not4to any private keys. The result of this aggregation is an aggregate signature σ whose length is thesame as that of any of the individual signatures. This aggregate has the property that a verifier
given σ along with the identities of the parties involved and their respective messages is convincedthat each user signed her respective message.

3.1

Bilinear Aggregate Signatures

We describe a bilinear aggregate signature scheme based on the co-GDH scheme presented above.
Individual signatures in the aggregate signature scheme are created and verified precisely as are
signatures in the co-GDH scheme (Sect. 2.2). Aggregate verification makes use of a bilinear map
on G1 and G2 .
The aggregate signature scheme allows the creation of signatures on arbitrary distinct messages
Mi ∈ {0, 1}∗ . An individual signature σi is an element of G1 . The base groups G1 and G2 , theirrespective generators g1 and g2 , the computable isomorphism ψ from G2 to G1 , and the bilinear
map e : G1 × G2 → GT , with target group GT , are system parameters.
The scheme comprises five algorithms: KeyGen, Sign, Verify, Aggregate, and AggregateVerify.
The first three are as in ordinary signature schemes; the last two provide the aggregation capability.
The scheme employs a full-domain hash function H : {0, 1}∗ → G1 , viewed as a random oracle.
R

Key Generation. For a particular user, pick random x ← Zp , and compute v ← g2x . The user’s
public key is v ∈ G2 . The user’s secret key is x ∈ Zp .
Signing. For a particular user, given the secret key x and a message M ∈ {0, 1} ∗ , computeh ← H(M ), where h ∈ G1 , and σ ← hx . The signature is σ ∈ G1 .
Verification. Given user’s public key v, a message M , and a signature σ, compute h ← H(M );accept if e(σ, g2 ) = e(h, v) holds.
Aggregation. For the aggregating subset of users U ⊆ U, assign to each user an index i, ranging
from 1 to k = |U |. Each user ui ∈ U provides a signature σi ∈ G1 on Q
a message Mi ∈ {0, 1}∗of his choice. The messages Mi must all be distinct. Compute σ ← ki=1 σi . The aggregate
signature is σ ∈ G1 .
Aggregate Verification. We are given an aggregate signature σ ∈ G1 for an aggregating subset
of users U , indexed as before, and are given the original messages Mi ∈ {0, 1}∗ and publickeys vi ∈ G2 for all users ui ∈ U . To verify the aggregate signature σ,
1. ensure that the messages Mi are all distinct, and reject otherwise; andQ
2. compute hi ← H(Mi ) for 1 ≤ i ≤ k = |U |, and accept if e(σ, g2 ) = ki=1 e(hi , vi ) holds.

A bilinear aggregate signature, like a co-GDH signature, is a single element of G 1 . Note that
aggregation can be done incrementally.
The intuition behind bilinear aggregate signatures is as follows. Each user u i has a secretxi
key xi ∈ Zp and a public key vi = g2xi . User ui ’s signature, if correctly formed, is σi =Q hi , whereQ xhi iis the hash of the user’s chosen message, Mi . The aggregate signature σ is thus σ = i σi = i hi .
Using the properties of the bilinear map, the left-hand side of the verification equation expands:
Y
Y
Y
Y x
e(hi , vi ) ,e(hi , g2xi ) =e(hi , g2 )xi =hi i , g2 ) =e(σ, g2 ) = e(
i

i

i

i

which is the right-hand side, as required. It remains to prove the security of the scheme.
53.2

Aggregate Signature Security

Informally, the security of aggregate signature schemes is equivalent to the nonexistence of an adversary capable, within the confines of a certain game, of existentially forging an aggregate signature.
Existential forgery here means that the adversary attempts to forge an aggregate signature, on
messages of his choice, by some set of users.
We formalize this intuition as the aggregate chosen-key security model. In this model, theadversary A is given a single public key. His goal is the existential forgery of an aggregate signature.
We give the adversary power to choose all public keys except the challenge public key. The adversaryis also given access to a signing oracle on the challenge key. His advantage, Adv AggSig A , is defined
to be his probability of success in the following game.
Setup. The aggregate forger A is provided with a public key PK1 , generated at random.
Queries. Proceeding adaptively, A requests signatures with PK1 on messages of his choice.
Response. Finally, A outputs k − 1 additional public keys PK2 , . . . , PKk . Here k is at
most N , a game parameter. These keys, along with the initial key PK1 , will be included
in A’s forged aggregate. A also outputs messages M1 , . . . , Mk ; and, finally, an aggregate
signature σ by the k users, each on his corresponding message.
The forger wins if the aggregate signature σ is a valid aggregate on messages M 1 , . . . , Mk
under keys PK1 , . . . , PKk , and σ is nontrivial, i.e., A did not request a signature on M1
under PK1 . The probability is over the coin tosses of the key-generation algorithm and of A.
Definition 3.1. An aggregate forger A (t, qH , qS , N, )-breaks an N -user aggregate signature scheme
in the aggregate chosen-key model if: A runs in time at most t; A makes at most q H queries to thehash function and at most qS queries to the signing oracle; Adv AggSig A is at least ; and the forgedaggregate signature is by at most N users. An aggregate signature scheme is (t, q H , qS , N, )-secureagainst existential forgery in the aggregate chosen-key model if no forger (t, q H , qS , N, )-breaks it.
A potential attack on aggregate signatures. The adversary’s ability in the chosen-key model
to generate keys suggests the following attack, previously considered in the context of multisignatures [20, 4]. Alice publishes her public key vA . Bob generates a private key x0B and a public
x0

0 = g B , but publishes as his public key v = v 0 /v , a value whose discrete log he does not
key vBB
2
B A
0
know. Then H(M )xB verifies as an aggregate signature on M by both Alice and Bob. Note thatin this forgery Alice and Bob both sign the same message M .
One countermeasure is to require the adversary to prove knowledge of the discrete logarithms(to base g2 ) of his published public keys. For example, Boldyreva, in her multisignature scheme [4],requires, in effect, that the adversary disclose the corresponding private keys x 2 , . . . , xk . Micali etal. [20] discuss a series of more sophisticated approaches based on zero-knowledge proofs, again withthe effect that the adversary is constrained in his key selection. These defenses apply equally wellto our aggregate signature scheme. For aggregate signatures, though, there is a simpler defense.

A simple defense for aggregate signatures. In the context of aggregate signatures we candefend against the attack above by simply requiring that an aggregate signature is valid only if
it is an aggregation of signatures on distinct messages. This restriction, codified in Step 1 ofAggregateVerify, suffices to prove the security of the bilinear aggregate signature scheme in thechosen-key model. There is no need for zero-knowledge proofs or the disclosure of private keys.

6

The requirement that all messages in an aggregate be distinct is naturally satisfied for theapplications to certificate chains and SBGP we have in mind. Even in more general environments
it is easy to ensure that all messages are distinct: The signer simply prepends her public key toevery message she signs prior to the application of the hash function H. The implicit prefix neednot be transmitted with the signature, so signature and message length is unaffected.
The next theorem shows that this simple constraint is sufficient for proving security in thechosen-key model.
Theorem 3.2. Let (G1 , G2 ) be a (t0 , 0 )-bilinear group pair for co-Diffie-Hellman, with each groupof order p, with respective generators g1 and g2 , with an isomorphism ψ computable from G2 to G1 ,and with a bilinear map e : G1 × G2 → GT . Then the bilinear aggregate signature scheme on(G1 , G2 ) is (t, qH , qS , N, )-secure against existential forgery in the aggregate chosen-key model for
all t and  satisfying
 ≥ e(qS + N ) · 0andt ≤ t0 − cG1 (qH + 2qS + N + 4) − (N + 1) ,where e is the base of natural logarithms, and exponentiation and inversion on G 1 take time cG1 .
Proof. Suppose A is a forger algorithm that (t, qS , qH , N, )-breaks the signature scheme. We show
how to construct a t0 -time algorithm C that solves co-CDH in (G1 , G2 ) with probability at least 0 .
This will contradict the fact that (G1 , G2 ) are a (t0 , 0 )-co-GDH group pair.
Let g2 be a generator of G2 . Algorithm C is given g2 , u ∈ G2 and h ∈ G1 , where u = g2a . Its goal
is to output ha ∈ G1 . Algorithm C simulates the challenger and interacts with forger A as follows.
Setup. Algorithm C starts by giving A the generator g2 and the public key v1 = u · g2r ∈ G2 , wherer is random in Zp .
Hash Queries. At any time algorithm A can query the random oracle H. To respond to these
queries, C maintains a list of tuples hM (i) , w(i) , b(i) , c(i) i as explained below. We refer tothis list as the H-list. The list is initially empty. When A queries the oracle H at a pointM ∈ {0, 1}∗ , algorithm C responds as follows:
1. If the query M already appears on the H-list in some tuple hM, w, b, ci then algorithm C
responds with H(M ) = w ∈ G1 .
2. Otherwise, C generates a random coin c ∈ {0, 1} so that Pr[c = 0] = 1/(q S + N ).
3. Algorithm C picks a random b ∈ Zp . If c = 0 holds, C computes w ← h · ψ(g2 )b ∈ G1 . If
c = 1 holds, C computes w ← ψ(g2 )b ∈ G1 .
4. Algorithm C adds the tuple hM, w, b, ci to the H-list and responds to A as H(M ) = w.
Note that, either way, w is uniform in G1 and is independent of A’s current view as required.
Signature queries. Algorithm A requests a signature on some message M under the challenge
key v1 . Algorithm C responds to this query as follows:
1. Algorithm C runs the above algorithm for responding to H-queries on M , obtaining thecorresponding tuple hM, w, b, ci on the H-list. If c = 0 holds then C reports failure andterminates.
2. We know that c = 1 holds and hence w = ψ(g2 )b ∈ G1 . Let σ = ψ(u)b · ψ(g2 )rb ∈ G1 .
Observe that σ = w a+r and therefore σ is a valid signature on M under the public key
v1 = u · g2r = g2a+r . Algorithm C gives σ to algorithm A.
7

Output. Finally, A halts. It either concedes failure, in which case so does C, or it returns avalue k (where k ≤ N ), k − 1 public keys v2 , . . . , vk ∈ G2 , k messages M1 , . . . Mk , and aforged aggregate signature σ ∈ G1 . The messages Mi must all be distinct, and A must nothave requested a signature on M1 . Algorithm C runs its hash algorithm at each Mi , 1 ≤ i ≤ k,obtaining the k corresponding tuples hMi , wi , bi , ci i on the H-list.
Algorithm C now proceeds only if c1 = 0 and, for 2 ≤ i ≤ k, ci = 1; otherwise C declares
failure and halts. Since c1 = 0, it follows that w1 = h · ψ(g2 )b1 . For i > 1, since ci = 1, itbifollows that wi = ψ(gaggregate verification
Q2k) . The aggregate signature σ must satisfy theequation, e(σ, g2 ) = i=1 e(wi , vi ). For each i > 1, C sets σi ← ψ(vi )bi . Then, for i > 1,e(σi , g2 ) = e(ψ(vi )bi , g2 ) = e(ψ(vi ), g2 )bi = e(ψ(g2 ), vi )bi = e(ψ(g2 )bi , vi ) = e(wi , vi ) ,So σi is a valid signature on Mi (whose hash is wi ) by the key whose public component is vi .
Q
−1
Now C constructs a value σ1 : σ1 ← σ · ( ki=2 σi ) . Thene(σ1 , g2 ) = e(σ, g2 ) ·kYe(σi , g2 )−1 =

k
Y
i=1

i=2

e(wi , vi ) ·kYe(wi , vi )−1 = e(w1 , v1 ) .

i=2Thus σ1 is a valid co-GDH signature by key v1 = u·g2r = g2a+r on a message whose hash is w1 =h·ψ(g2 )b1 . Then C calculates and outputs the required ha as ha ← σ1 ·(ψ(u)b1 ·hr ·ψ(g2 )rb1 )−1 .
This completes the description of algorithm C. It remains to show that C solves the given instanceof the co-CDH problem in (G1 , G2 ) with probability at least 0 . To do so, we analyze the three
events needed for C to succeed:
E1 : C does not abort as a result of any of A’s signature queries.
E2 : A generates a valid and nontrivial aggregate signature forgery (k, v 2 , . . . , vk , M1 , . . . , Mk , σ).
E3 : Event E2 occurs, and, in addition, c1 = 0, and, for 2 ≤ i ≤ k, ci = 1, where for each i ci is the
c-component of the tuple containing Mi on the H-list.
C succeeds if all of these events happen. The probability Pr[E1 ∧ E3 ] decomposes as
Pr[E1 ∧ E3 ] = Pr[E1 ] · Pr[E2 | E1 ] · Pr[E3 | E1 ∧ E2 ].

(1)

The following claims give a lower bound for each of these terms.
Claim 3.3. The probability that algorithm C does not abort as a result of A’s aggregate signature
queries is at least (1 − 1/(qS + N ))qS . Hence, Pr[E1 ] ≥ (1 − 1/(qS + N ))qS .
Proof. Without loss of generality we assume that A does not ask for the signature of the samemessage twice. We prove by induction that after A makes ` signature queries the probability
that C does not abort is at least (1 − 1/(qS + N ))` . The claim is trivially true for ` = 0. Let M (`)
be A’s `’th signature query and let hM (`) , w(`) , b(`) , c(`) i be the corresponding tuple on the H-list.
Then, prior to A’s issuing the query, the bit c(`) is independent of A’s view — the only value that
could be given to A that depends on c(`) is H(M (`) ), but the distribution of H(M (`) ) is the same
whether c(`) = 0 or c(`) = 1. Therefore, the probability that this query causes C to abort is at most
1/(qS + N ). Using the inductive hypothesis and the independence of c(`) , the probability that C
does not abort after this query is at least (1 − 1/(qS + N ))` . This proves the inductive claim.
Since A makes at most qS signature queries the probability that C does not abort as a result of all
signature queries is at least (1 − 1/(qS + N ))qS .
8

Claim 3.4. If algorithm C does not abort as a result of A’s queries then algorithm A’s view is
identical to its view in the real attack. Hence, Pr[E2 | E1 ] ≥ .
Proof. The public key given to A is from the same distribution as public keys produced by algorithm KeyGen. Responses to hash queries are as in the real attack since each response is uniformly
and independently distributed in G1 . Since C did not abort as a result of A’s signature queries, all
its responses to those queries are valid. Therefore A will produce a valid and nontrivial aggregate
signature forgery with probability at least . Hence Pr[E2 | E1 ] ≥ .
Claim 3.5. The probability that algorithm C does not abort after A outputs a valid and nontrivial
forgery is at least (1 − 1/(qS + N ))N −1 · 1/(qS + N ).
Hence, Pr[E3 | E1 ∧ E2 ] ≥ (1 − 1/(qS + N ))N −1 · 1/(qS + N ).
Proof. Events E1 and E2 have occurred, and A has generated some valid and nontrivial forgery(k, v2 , . . . , vk , M1 , . . . , Mk , σ). For each i, 1 ≤ i ≤ k, let hMi , wi , bi , ci i be the tuple corresponding
to Mi on the H-list. Algorithm C will abort unless A generates a forgery such that c 1 = 0 and, fori > 1, ci = 1.
Since all the messages M1 , M2 , . . . , Mk are distinct, the values c1 , c2 , . . . , ck are all independentof each other; as before, H(Mi ) = wi is independent of ci for each i.
Since its forgery is nontrivial, A cannot have asked for a signature on M1 under key v1 . It
can thus have no information about the value of c1 ; in the forged aggregate, c1 = 0 occurs withprobability 1/(qS + N ). For each i > 1, A either asked for a signature under key v1 on Mi , in whichcase ci = 1 with probability 1, or it didn’t, and ci = 1 with probability 1 − 1/(qS + N ). Regardless,the probability that ci = 1 for all i, 2 ≤ i ≤ k, is at least (1−1/(qS + N ))k−1 ≥ (1−1/(qS + N ))N −1 .
Therefore Pr[E3 | E1 ∧ E2 ] ≥ (1 − 1/(qS + N ))N −1 · 1/(qS + N ), as required.
To complete the proof of Theorem 3.2, we use the bounds from the claims above in equation (1).
Algorithm C produces the correct answer with probability at least1
1−
qS + NqS +N −1

·

/e
1
·≥
≥ 0 ,
qS + NqS + N

as required.
Algorithm C’s running time is the same as A’s running time plus the time is takes to respond to(qH + qS ) hash queries and qS signature queries, and the time to transform A’s final forgery into theco-CDH solution. Each query requires an exponentiation in G1 . The output phase requires at mostN additional hash computations, two inversions, two exponentiations, and N + 1 multiplications.
We assume that exponentiation and inversion in G1 take time cG1 . Hence, the total running timeis at most t + cG1 (qH + 2qS + N + 4) + N + 1 ≤ t0 as required. This completes the proof of
Theorem 3.2.
Aggregate verification time. Let σ be an aggregate of the n signatures σ1 , . . . , σn . The time toverify the aggregate signature σ is linear in n. In the special case when all n signatures are issued
by theQn same public key v, aggregate verification is faster. One need only verify that e(σ, g 2 ) =e(v, i=1 H(Mi )) holds, where M1 , . . . , Mn are the signed messages.

94

Verifiably Encrypted Signatures

Next, we show an application of aggregate signatures to verifiably encrypted signatures. Verifiably
encrypted signatures are used in applications such as online contract signing [1, 2]. Suppose Alicewants to show Bob that she has signed a message, but does not want Bob to possess her signatureof that message. (Alice will give her signature to Bob only when a certain event has occurred, e.g.,
Bob has given Alice his signature on the same message.) Alice can achieve this by encrypting her
signature using the public key of a trusted third party, and sending this to Bob along with a proof
that she has given him a valid encryption of her signature. Bob can verify that Alice has signed themessage, but cannot deduce any information about her signature. Later in the protocol, if Alice isunable or unwilling to reveal her signature, Bob can ask the third party to reveal Alice’s signature.
We note that the resulting contract signing protocol is not abuse-free in the sense of [10].
We show that a variant of the bilinear aggregate signature scheme allows the creation of very
efficient verifiably encrypted signatures.

4.1

Verifiably Encrypted Signature Security

A verifiably encrypted signature scheme comprises seven algorithms. Three, KeyGen, Sign, andVerify, are analogous to those in ordinary signature schemes. The others, AdjKeyGen, VESigCreate,
VESigVerify, and Adjudicate, provide the verifiably encrypted signature capability. The algorithms
are described below. We refer to the trusted third party as the adjudicator.
Key Generation, Signing, Verification. As in standard signature schemes.
Adjudicator Key. Generate a public-private key pair (APK, ASK) for the adjudicator.
VESig Creation. Given a secret key SK, a message M , and an adjudicator’s public key APK,
compute (probabilistically) a verifiably encrypted signature ω on M .
VESig Verification. Given a public key PK, a message M , an adjudicator’s public key APK,
and a verifiably encrypted signature ω, verify that ω is a valid verifiably encrypted signature
on M under key PK.
Adjudication. Given an adjudicator’s keypair (APK, ASK), a certified public key PK, and averifiably encrypted signature ω on some message M , extract and output σ, an ordinary
signature on M under PK.
Besides the ordinary notions of signature security in the signature component, we require three
security properties of verifiably encrypted signatures: validity, unforgeability, and opacity. We
describe these properties in the single user setting.
Validity requires that verifiably encrypted signatures verify, and that adjudicated verifiably
encrypted signatures verify as ordinary signatures, i.e., that VESigVerify(M, VESigCreate(M )) and
Verify(M, Adjudicate(VESigCreate(M )) hold for all M and for all properly-generated keypairs andadjudicator keypairs. (The keys provided to the algorithms are here omitted for brevity.)
Unforgeability requires that it be difficult to forge a valid verifiably encrypted signature. The
advantage in existentially forging a verifiably encrypted signature of an algorithm F, given accessto a verifiably-encrypted-signature creation oracle S and an adjudication oracle A, along with a10hash oracle, isVESigVerify(PK, APK, M, ω) = valid :R(PK, SK) ← KeyGen,



 .
R
(APK, ASK) ← AdjKeyGen, 
RS,A(M, ω) ← F (PK, APK)
Adv VSigFF = Pr 


def



The probability is taken over the coin tosses of the key-generation algorithms, of the oracles, andof the forger. The forger is additionally constrained in that its forgery on M must be nontrivial: It
must not previously have queried either oracle at M . Note that an ordinary signing oracle is notprovided; it can be simulated by a call to S followed by a call to A.
Definition 4.1. A verifiably encrypted signature forger F (t, qH , qS , qA , )-forges a verifiably encrypted signature if: Algorithm F runs in time at most t; F makes at most qH queries to the hashfunction, at most qS queries to the verifiably-encrypted-signature creation oracle S, at most q A
queries to the adjudication oracle A; and Adv VSigFF is at least . A verifiably encrypted signaturescheme is (t, qH , qS , qA , )-secure against existential forgery if no forger (t, qH , qS , qA , )-breaks it.
Opacity requires that it be difficult, given a verifiably encrypted signature, to extract an ordinary
signature on the same message. The advantage in extracting a verifiably encrypted signature of analgorithm E, given access to a verifiably-encrypted-signature creation oracle S and an adjudication
oracle A, along with a hash oracle, isVerify(PK, M, σ) = valid :


R


(PK, SK) ← KeyGen,
def

 .
Adv VSigEE = Pr R
(APK, ASK) ← AdjKeyGen, 


R
S,A
(M, σ) ← E (PK, APK)
The probability is taken over the coin tosses of the key-generation algorithms, of the oracles, and of
the forger. The extraction must be nontrivial: the adversary must not have queried the adjudication
oracle A at M . (It is allowed, however, to query S at M .) Verifiably encrypted signature extractionis thus no more difficult than forgery in the underlying signature scheme.
Definition 4.2. An algorithm E (t, qH , qS , qA , )-extracts a verifiably encrypted signature if E runsin time at most t, makes at most qH queries to the hash function, at most qS queries to theverifiably-encrypted-signature creation oracle S, at most qA queries to the adjudication oracle, andAdv VSigEE is at least . A verifiably encrypted signature scheme is (t, qH , qS , qA , )-secure against
extraction if no algorithm (t, qH , qS , qA , )-extracts it.

4.2

Aggregate Extraction

Our verifiably encrypted signature scheme depends on the assumption that given an aggregate
signature of k signatures it is difficult to extract the individual signatures.
Consider the bilinear aggregate signature scheme on a group pair (G 1 , G2 ). We posit that it isdifficult to recover the individual signatures σi given their aggregate σ, the public keys, and themessage hashes. In fact, we posit that it is difficult to recover an aggregate σ 0 of any proper subsetof the signatures. This we term the k-element aggregate extraction problem.

11

We formalize this assumption as follows. Let (G1 , G2 ) be a bilinear group pair for co-DiffieHellman, each of order p, with respective generators g1 and g2 , a computable isomorphism ψ :G2 → G1 such that g1 = ψ(g2 ), and a computable bilinear map e : G1 × G2 → GT .
Consider a k-user aggregate in this setting. Each user has a private key x i ∈ Zp and a public
key vi = g2xi ∈ G2 . Each user selects a distinct message Mi ∈ {0, 1}∗ whose hash is hQ
i ∈ G1 andcreates a signature σi = hxi i ∈ G1 . Finally, the signatures are aggregated, yielding σ = i σi ∈ G1 .
Let I be the set {1, . . . , k}. Each public key vi can be expressed as P
g2xi , each hash hi as g1yi , eachsignature σi as g1xi yi , and the aggregate signature σ as g1z , where z = i∈I xi yi . The advantage ofan algorithm E in extracting a subaggregate from a k-element aggregate isP(
0 x i yi )(∅ 6= I 0 ( I) ∧ (σ 0 = g1 i∈I
) :
P
def


(
x i yi )R
Adv k-ExtrE = Pr 
x1 , . . . , xk , y1 , . . . , yk ← Zp , σ ← g1 i∈I,  .
R(σ 0 , I 0 ) ← E(g2x1 , . . . , g2xk , g1y1 , . . . , g1yk , σ)The probability is taken over the choices of all xi and yi , and the coin tosses of E.
Definition 4.3. An algorithm E (t, k, )-extracts a subaggregate from an k-element bilinear aggregate signature if E runs in time at most t and Adv k-Extr E is at least . An instantiation of thebilinear aggregate signature scheme is (t, k, )-secure against aggregate extraction if no algorithm(t, k, )-extracts it.
We will be particularly concerned with the case k = 2. In this case, the aggregate extraction
problem reduces to this one: given g2a , g2b , g1u , g1v , and g1au+bv , calculate g1au . (If the extractor
outputs g1bv instead, we may recover g1au as g1au+bv/g1bv .)4.3

Verifiably Encrypted Signatures via Aggregation

We motivate our construction for verifiably encrypted signatures by considering aggregate signatures as a launching point. An aggregate signature scheme can give rise to a verifiably encryptedsignature scheme if it is difficult to extract individual signatures from an aggregate, but easy toforge existentially under the adjudicator’s key. Consider the following:
1. Alice wishes to create a verifiably encrypted signature, which Bob will verify; Carol is the adjudicator. Alice and Carol’s keys are both generated under the underlying signature scheme’s
key-generation algorithm.
2. Alice creates a signature σ on M under her public key. She forges a signature σ 0 on somerandom message M 0 under Carol’s public key. She then combines σ and σ 0 , obtaining an
aggregate ω. The verifiably encrypted signature is the pair (ω, M 0 ).
3. Bob validates Alice’s verifiably encrypted signature (ω, M 0 ) on M by checking that ω is avalid aggregate signature by Alice on M and by Carol on M 0 .
4. Carol adjudicates, given a verifiably encrypted signature (ω, M 0 ) on M by Alice, by computing
a signature σ 0 on M 0 under her key, and removing σ 0 from the aggregate; what remains is
Alice’s ordinary signature σ.
In the bilinear aggregate signature scheme, it is difficult to extract individual signatures, under
the aggregate extraction assumption. Moreover, existential forgery is easy when the random oracle
hash function is set aside: Given a public key v ∈ G2 and r ∈ Zp , ψ(v)r is a valid signature on amessage whose hash is ψ(g2 )r = g1r . Below, we formalize and prove the security of the verifiably
encrypted signature scheme created in this way.
12

4.4

The Bilinear Verifiably-Encrypted Signature Scheme

The bilinear verifiably encrypted signature scheme is built on the bilinear aggregate signaturescheme of the previous section. It shares the key-generation algorithm with the underlying aggregate
scheme. Moreover, the adjudicator’s public and private information is simply an aggregate-signature
keypair. The scheme comprises the seven algorithms described below:
Key Generation. KeyGen and AdjKeyGen are the same as KeyGen in the co-GDH signaturescheme.
Signing, Verification. Sign and Verify are the same as in the co-GDH signature scheme.
VESig Creation. Given a secret key x ∈ Zp a message M ∈ {0, 1}∗ , and an adjudicator’s public
key v 0 ∈ G2 , compute h ← H(M ), where h ∈ G1 , and σ ← hx . Select r at random from Zp
and set µ ← ψ(g2 )r and σ 0 ← ψ(v 0 )r . Aggregate σ and σ 0 as ω ← σσ 0 ∈ G1 . The verifiably
encrypted signature is the pair (ω, µ). (This can also be viewed as ElGamal encryption of σ
under the adjudicator’s key.)
VESig Verification. Given a public key v, a message M , an adjudicator’s public key v 0 , and averifiably encrypted signature (ω, µ), set h ← H(M ); accept if e(ω, g2 ) = e(h, v) · e(µ, v 0 )holds.
Adjudication. Given an adjudicator’s public key v 0 and corresponding private key x0 ∈ Zp , acertified public key v, and a verifiably encrypted signature (ω, µ) on some message M , ensure0that the verifiably encrypted signature is valid; then output σ = ω/µx .
If the adjudicator does not first validate a purported verifiably encrypted signature, a malicious user
can trick him into signing arbitrary messages under his adjudication key. Similarly, the adjudicator
should only adjudicate for certified public keys v; we assume that the CA, in issuing a certificate
on v, verifies that the user knows the private key for v.
It is easy to see that validity holds. A verifiably encrypted signature correctly validates under
VESigVerify, which is simply the aggregate signature verification algorithm. Moreover, for any valid00verifiably encrypted signature, e(ω/µx , g2 ) = e(ω, g2 ) · e(µ, g2 )−x = e(h, v) · e(µ, v 0 ) · e(µ, v 0 )−1 =e(h, v), so the output of Adjudicate is a valid signature on message M under the key v.
The next two theorems prove the unforgeability and opacity of the scheme.
Theorem 4.4. Let G1 and G2 be cyclic groups of prime order p, with respective generators g1 andg2 , with a computable bilinear map e : G1 × G2 → GT . Suppose that the co-GDH signature scheme
0 , q 0 , 0 )-secure against existential forgery on (G , G ). Then the bilinear verifiably encryptedis (t0 , qH
1
2
S
0 ,
signature scheme is (t, qH , qS , qA , )-secure against existential forgery on (G1 , G2 ), for all qH ≤ qH
0
0
0
qS ≤ qS ,  ≥  , and all t satisfying t ≤ t − 2cG1 (qS + qA + 1) , where exponentiation and inversion
on G1 take time cG1 .
Proof. Given a verifiably-encrypted-signature forger algorithm V, we construct a forger algorithm F
for the underlying co-GDH signature scheme.
We assume that V is well-behaved in the sense that it always requests the hash of a message M
before it requests a verifiably encrypted signature or an adjudication involving M , and that itnever requests adjudication on a message M on which it had not previously asked for a verifiably
encrypted signature. It is trivial to modify any forger algorithm V to have the first property. The
second property is reasonable since the input to the adjudication oracle in this case would be a
nontrivial verifiably encrypted signature forgery; V can be modified simply to output it and halt.
13

The co-GDH forger F is given a public key v, and has access to a signing oracle for v and ahash oracle. It simulates the challenger and runs interacts with V as follows.
R

Setup. Algorithm F generates a key, (x0 , v 0 ) ← KeyGen, which serves as the adjudicator’s key.
Now F runs V, providing as input the public keys v and v 0 .
Hash Queries. Algorithm V requests a hash on some string M . Algorithm F makes a query on M
to its own hash oracle, receiving some value h ∈ G1 , with which it responds to V’s query.
VerSig Creation Queries. Algorithm V requests a signature on some string M . (It will havealready queried the hash oracle at M .) F queries its signing oracle (for v) at M , obtainingσ ∈ G1 . It then selects r at random from Zp , and returns to V the pair (σ · ψ(v 0 )r , ψ(g2 )r ).
Adjudication Queries. Algorithm V requests adjudication for (ω, µ), a verifiably encrypted signature on a message M under key v and adjudicator key v 0 . Algorithm F checks that the0verifiably encrypted signature is valid, then returns ω/µx .
Output. Finally, V halts, either declaring failure, in which case F, too, declares failure and halts,
or providing a valid and nontrivial verifiably encrypted signature (ω ∗ , µ∗ ) on a message M ∗ .
0
F sets σ ∗ ← ω ∗/(µ∗ )x which, by the validity property, is a valid co-GDH signature on M ∗under key v.
That the forgery is nontrivial means that V did not query the verifiably encrypted signatureoracle at M ∗ , from which it follows that F did not query its signing oracle at M ∗ . Thus
(M ∗ , σ ∗ ) is a nontrivial co-GDH forgery; algorithm F outputs it and halts.
It remains only to analyze the success probability and running time of F. Algorithm F succeeds
whenever V does, that is, with probability at least .
Algorithm F’s running time is the same as V’s running time plus the time it takes to respond
to qH hash queries, qS verifiably-encrypted signature queries, and qA adjudication queries, and thetime to transform V’s final verifiably-encrypted signature forgery into a co-GDH signature forgery.
Hash queries impose no overhead. Each verifiably-encrypted signature query requires F to perform
two exponentiations in G1 . Each adjudication query requires F to perform an exponentiation andan inversion in G1 . The output phase also requires an exponentiation and an inversion. We assume
that exponentiation and inversion in G1 take time cG1 . Hence, the total running time is at mostt + 2cG1 (qS + qA + 1).
F queries its hash oracle whenever V queries its hash oracle, and its signing oracle whenever V
queries its verifiably encrypted signature oracle.
Combining all this, we see that if V (t, qH , qS , qA , )-forges a bilinear verifiably encrypted signature on (G1 , G2 ), then F (t + 2cG1 (qS + qA + 1), qH , qS , )-breaks the co-GDH signature scheme on
0 , q 0 , 0 )-secure, then the bilinear ver(G1 , G2 ). Conversely, if the co-GDH signature scheme is (t0 , qH
S
0 , q 0 , q , 0 )-secure against existential
ifiably encrypted signature scheme is (t0 − 2cG1 (qS + qA + 1), qH
A
S
forgery.
Theorem 4.5. Let G1 and G2 be cyclic groups of prime order p, with respective generators g1 andg2 , with a computable isomorphism ψ : G2 → G1 such that ψ(g2 ) = g1 and a computable bilinear
map e : G1 × G2 → GT . Suppose that the bilinear aggregate signature scheme on (G1 , G2 ) is
(t0 , 2, 0 )-secure against aggregate extraction. Then the bilinear verifiably encrypted signature schemeis (t, qH , qS , qA , )-secure against extraction on (G1 , G2 ) for all t and  satisfying
 ≥ e(qA + 1) · 0andt ≤ t0 − cG1 (qH + 4qS + 2qA + 3) ,14

where e is the base of natural logarithms, and exponentiation and inversion on G 1 take time cG1 .
Proof. Given a verifiably-encrypted-signature extractor algorithm V, we construct an aggregate extractor algorithm A. The co-GDH forger A is given values g2α and g2β in G2 , g1γ , g1δ , and g1αγ+βδ in G1 .
It runs V, answering its oracle calls, and uses V’s verifiably encrypted signature extraction to calculate g1αγ , the answer to its own extraction challenge.
Let g1 be a generator of G1 , and g2 of G2 , such that ψ(g2 ) = g1 . Algorithm A is given g2α , g2β ∈ G2
and g1γ , g1δ , g1αγ+βδ ∈ G1 . Its goal is to output g1αγ ∈ G1 . Algorithm A simulates the challenger andinteracts with verifiably-encrypted-signature extractor V as follows.
Setup. Algorithm A sets v ← g2α , the signer’s public key, and v 0 ← g2β , the adjudicator’s public
key. It gives v and v 0 to V.
Hash Queries. At any time algorithm V can query the random oracle H. To respond to these
queries, A maintains a list of tuples hM (i) , w(i) , b(i) , c(i) i as explained below. We refer tothis list as the H-list. The list is initially empty. When V queries the oracle H at a pointM ∈ {0, 1}∗ , algorithm A responds as follows:
1. If the query M already appears on the H-list in some tuple hM, w, b, ci then algorithm A
responds with H(M ) = w ∈ G1 .
2. Otherwise, A generates a random coin c ∈ {0, 1} so that Pr[c = 0] = 1/(q A + 1).
3. Algorithm A picks a random b ∈ Zp . If c = 0 holds, A computes w ← g1γ · g1b ∈ G1 . If
c = 1 holds, A computes w ← g1b ∈ G1 .
4. Algorithm A adds the tuple hM, w, b, ci to the H-list and responds to V as H(M ) = w.
VerSig Creation Queries. V requests a verifiably-encrypted signature on some string M underchallenge key v and adjudicator key v 0 . Algorithm A responds to this query as follows:
1. Algorithm A runs the above algorithm for responding to H-queries on M , obtaining thecorresponding tuple hM, w, b, ci on the H-list.
2. A selects x at random from Zp . If c equals 0, A computes and returns (ω, µ) = (ψ(g2α )b ·g1αγ+βδ · ψ(g2β )x , g1δ · g1x ). If c equals 1, A computes and returns (ω, µ) = (ψ(g2α )b ·ψ(g2β )x , g2x ). It is easy to verify that (, µ) is in either case a correct verifiably encryptedsignature on the message with hash w.
Adjudication Queries. Algorithm V requests adjudication for (ω, µ), a verifiably encrypted signature on a message M under key v and adjudicator key v 0 . Algorithm A responds to thisquery as follows:
1. Algorithm A runs the above algorithm for responding to H-queries on M , obtaining thecorresponding tuple hM, w, b, ci on the H-list.
2. Algorithm A checks that the verifiably encrypted signature is valid. If it is not, A
returns ?, a placeholder value.
3. If c equals 0, A declares failure and halts. Otherwise, it computes and returns σ ←ψ(g2α )b . It is easy to verify that σ is the correct co-GDH signature under key v on themessage with hash w.

15

Output. Finally, V halts. It either concedes failure, in which case so does A, or returns a nontrivial
extracted signature σ ∗ on some message M ∗ . For the extraction to be nontrivial, V must nothave asked for adjudication on a verifiably encrypted signature of M ∗ . Algorithm A runs its
hash algorithm at M ∗ , obtaining the k corresponding tuples hM ∗ , w∗ , b∗ , c∗ i on the H-list.
A now proceeds only if c∗ = 0; otherwise it declares failure and halts. Since c∗ = 0, it follows∗
that w∗ = g1γ · g1b . The extracted signature σ ∗ must satisfy the co-GDH verification equation,∗e(σ ∗ , g2 ) = e(h∗ , v). A sets σ ← σ ∗/ψ(v)b . Then∗e(σ, g2 ) = e(σ ∗ , g2 ) · e(ψ(v), g2 )−b = e(w∗ , v) · e(ψ(g2 ), v)−b∗= e(g1γ , v) · e(g1 , v)b · e(g1 , v)−b = e(g1γ , g2α ).
∗∗Where in the last equality we substitute v = g2α . Thus (g2 , g2α , g1γ , σ) is a valid co-DiffieHellman tuple, so σ equals g2αγ , the answer to the aggregate extraction problem; algorithm A
outputs it and halts.
This completes the description of algorithm A. It remains to show that A solves the given instanceof the aggregate extraction problem on (G1 , G2 ) with probability at least 0 . To do so, we analyze
the three events needed for A to succeed:
E1 : A does not abort as a result of any of V’s adjudication queries.
E2 : V generates a valid and nontrivial verifiably-encrypted signature extraction (M ∗ , σ ∗ ).
E3 : Event E2 occurs, and c∗ = 0 holds, where c∗ is the c-component of the tuple containing M ∗ on
the H-list.
A succeeds if all of these events happen. The probability Pr[E1 ∧ E3 ] decomposes as
Pr[E1 ∧ E3 ] = Pr[E1 ] · Pr[E2 | E1 ] · Pr[E3 | E1 ∧ E2 ].

(2)

The following claims give a lower bound for each of these terms.
Claim 4.6. The probability that algorithm A does not abort as a result of V’s adjudication queries
is at least 1/e. Hence, Pr[E1 ] ≥ 1/e.
Proof. Without loss of generality we assume that V does not ask for adjudication of the samemessage twice. We prove by induction that after V makes ` signature queries the probability
that A does not abort is at least (1 − 1/(qA + 1))` . The claim is trivially true for ` = 0. Let V’s`’th adjudication query be for verifiably encrypted signature (ω (`) , µ(`) ), on message M (`) under thechallenge key v, and let hM (`) , w(`) , b(`) , c(`) i be the corresponding tuple on the H-list. Then prior toissuing the query, the bit c(`) is independent of V’s view — the only values that could be given to V
that depend on c(`) are H(M (`) ) and verifiably-encrypted signatures on M (`) , but the distributions
on these values are the same whether c(`) = 0 or c(`) = 1. Therefore, the probability that this querycauses A to abort is at most 1/(qA + 1). Using the inductive hypothesis and the independence ofc(`) , the probability that A does not abort after this query is at least (1 − 1/(q A + 1))` . This proves
the inductive claim. Since V makes at most qA adjudication queries the probability that A does
not abort as a result of all signature queries is at least (1 − 1/(q A + 1))qA ≥ 1/e.
Claim 4.7. If algorithm A does not abort as a result of V’s adjudication queries then V’s view is
identical to its view in the real attack. Hence, Pr[E2 | E1 ] ≥ .
16

Proof. The challenge public key v given to V is from the same distribution as public keys producedby KeyGen; the adjudicator’s public key v 0 given to V is from the same distribution as the adjudicator keys produces by AdjKeyGen. Responses to hash queries are as in the real attack sinceeach response is uniformly and independently distributed in G1 . Responses to verifiably-encryptedsignature queries are also as in the real attack: They are valid, and their µ components are uniformly and independently distributed in G1 . Since A did not abort as a result of V’s adjudication
queries, all its responses to those queries are valid. Therefore V will produce a valid and nontrivial
verifiably-encrypted signature extraction with probability at least . Hence Pr[E 2 | E1 ] ≥ .
Claim 4.8. The probability that algorithm A does not abort after V outputs a valid and nontrivial
verifiably-encrypted signature extraction is at least 1/(qA + 1) Hence, Pr[E3 | E1 ∧ E2 ] ≥ 1/(qA + 1).
Proof. Given that events E1 and E2 happened, algorithm A will abort only if V generates a forgery(M ∗ , σ ∗ ) for which the tuple hM ∗ , w∗ , b∗ , c∗ i on the H-list has c = 1. Since its extraction isnontrivial, V could not have requested adjudication on any verifiably encrypted signature on M ∗ ,and c∗ must be independent of V’s current view. Therefore Pr[c∗ = 0 | E1 ∧ E2 ] ≥ 1/(qA + 1) as
required.
Using the bounds from the claims above in equation (2) shows that A produces the correct
answer with probability at least /e(qA + 1) ≥ 0 as required.
Algorithm A’s running time is the same as V’s running time plus the time is takes to respond to
A’s oracle queries and to transform V’s verifiably-encrypted signature extraction into an aggregate
extraction. Each verifiably-encrypted signature query, each adjudication query, and the output
phase requires A to run its H-algorithm. It must therefore run this algorithm (q H +qS +qA +1) times.
Each run requires an exponentiation in G1 . Algorithm A must run its verifiably-encrypted signingalgorithm qS times, and each run requires at most three exponentiation in G1 . Finally, A’s output
phase requires at most one exponentiation and one inversion in G1 . We assume that exponentiationand inversion in G1 take time cG1 . Hence, the total running time is at most t + cG1 (qH + 4qS +2qA + 3) ≤ t0 as required.

4.5

Observations on Verifiably Encrypted Signatures

We note some extensions of the verifiably encrypted signature scheme discussed above. Some ofthese rely for security on the k-element aggregate extraction assumption with k > 2.
• Anyone can convert an ordinary unencrypted signature to a verifiably encrypted signature.
The same applies to unencrypted aggregate signatures.
• An adjudicator’s private key can be shared amongst n parties using k-of-n threshold cryptography [12, 11], so that k parties are needed to adjudicate a verifiably encrypted signature.
• A message-signature pair in the co-GDH signature scheme is of the same form as an identity–
private-key pair in the Boneh-Franklin Identity-Based Encryption Scheme [5]. Thus the verifiably encrypted signature scheme can potentially be modified to yield a verifiably encrypted
encryption scheme for IBE private keys. Verifiably encrypted private keys have many applications [27].

175Ring Signatures

Rivest, Shamir and Tauman define ring signature schemes and construct some using RSA and
Rabin cryptosystems [28]. Naor defines the closely-related notion of deniable ring authenticationand proposes such a scheme that relies only on the existence of a strong encryption function [23].
We shall see that co-GDH signatures give rise to natural ring signatures.

5.1

Ring Signatures

Consider a set U of users. Each user u ∈ U has a signing keypair (PKu , SKu ). A ring signature
on U is a signature that is constructed using all the public keys of the users in U , and a single
private key of any user in U . A ring signature has the property that a verifier is convinced that thesignature was produced using one of the private keys of U , but is not able to determine which one.
This property is called signer-ambiguity [28]. Applications for ring signatures include authenticated(yet repudiable) communication and leaking secrets [28].
Zhang and Kim [29] devised a bilinear ring signature in an identity-based setting. Our scheme
differs from theirs, as our goal is to extend co-GDH signatures to obtain efficient ring signatures;the system parameters and key generation algorithm in our system are identical to those of theco-GDH scheme.

5.2

Bilinear Ring Signatures

The ring signature scheme comprises three algorithms: KeyGen, RingSign, and RingVerify. Recall
g1 , g2 are generators of groups G1 , G2 respectively, and e : G1 × G2 → GT is a bilinear map, and acomputable isomorphism ψ : G2 → G1 exists, with ψ(g2 ) = g1 . Again we use a full-domain hashfunction H : {0, 1}∗ → G1 . The security analysis views H as a random oracle.
R

Key Generation. For a particular user, pick random x ← Zp , and compute v ← g2x . The user’s
public key is v ∈ G2 . The user’s secret key is x ∈ Zp .
Ring Signing. Given public keys v1 , . . . , vn ∈ G2 , a message M ∈ {0, 1}∗ , and a private key xRcorresponding to one of the public keys vs for some s, choose random ai ← Zp for all i 6= s.
Compute h ← H(M ) ∈ G1 and set
σs ←



h/ψ

Y
i6=s

viai

1/x

.

For all i 6= s let σi ← g1ai . Output the ring signature σ = hσ1 , . . . , σn i ∈ Gn1 .
Ring Verification. Given public keys v1 , . . . , vn ∈ G2 , a message
M ∈ {0, 1}∗ , and a ring signaQn
ture σ, compute h ← H(M ) and verify that e(h, g2 ) = i=1 e(σi , vi ).
Using the bilinearity and nondegeneracy of the pairing e, it is easy to show that a signature
produced by the RingSign algorithm will verify under the RingVerify algorithm.

5.3

Security

There are two aspects a security analysis for ring signatures we must consider. Firstly, signer
ambiguity must be ensured. We show that the identity of the signer is unconditionally protected.
18

Theorem 5.1. For any algorithm A, any set of users U , and a random u ∈ U , the probability
Pr[A(σ) = u] is at most 1/|U |, where σ is any ring signature on U generated with private key SK u .
Proof. The theorem follows from a simple probability argument: for any h ∈ G 1 , and any s,
QnRai
1 ≤ s ≤ n, the distribution {g1a1 , . . . , g1an : aQi ← Zp for i 6= s, as chosen such thati=1 g1 = h} is
n
ai
a1
an
identical to the distribution {g1 , . . . , g1 : i=1 g1 = h}, since the value of any one of the ai ’s isuniquely determined by the values of the other ai ’s.
Secondly, we need to examine the scheme’s resistance to forgery. We adopt the security modelof Rivest, Shamir and Tauman [28]. Consider the following game played between an adversary anda challenger. The adversary is given the public keys v1 , . . . , vn of a set of users U , and is given
oracle access to h and a ring-signing oracle. The adversary may work adaptively. The goal of theadversary is to output a valid ring signature on U of a message M subject to the condition that
M has never been presented to the ring-signing oracle. An adversary A’s advantage Adv RingSig A
in existentially forging a bilinear ring signature is the probability, taken over the coin tosses of the
key-generation algorithm and of the forger, that A succeeds in creating a valid ring signature in
the above game.
Theorem 5.2. Suppose F is a (t0 , 0 )-algorithm that can produce a forgery of a ring signature on aset of users of size n. Then there exists an (t, )-algorithm that can solve the co-CDH problem wheret ≤ 2t0 + 2cG2 (2n + qH + nqS ) and  ≥ ((0 /e)(1 + qS ))2 , where F issues at most qS ring-signature
queries and at most qH hash queries, and exponentiation and inversion on G2 take time cG2 .
Proof. The co-CDH problem can be solved by first solving two random instances of the following
problem: Given g1ab , g2a (and g1 , g2 ), compute g1b . We shall construct an algorithm A that solves
this problem. This is easy if a = 0. In what follows, we assume a 6= 0.
Initially A picks x2 , . . . , xn at random from Zp and sets x1 = 1. It sets vi = (g2a )xi . Algorithm
F is given the public keys v1 , . . . , vn . Without loss of generality we may assume F submits distinct
queries (as previous replies can be cached); that for every ring-signing query on a message M , F
has previously issued a hash query for M ; and that F issues a hash query on the message on which
it attempts to forge a signature some time before giving its final output.
On a hash query, A flips a coin that shows 0 with probability p and 1 otherwise (p shall beRdetermined later). Then A picks a random r ← Zp , and if the coins shows 0, A returns (g1ab )r ,otherwise it returns ψ(g2a )r .
Suppose F issues a ring sign query for a message M . By assumption, A has previously issued ahash query for M . If the coin A flipped for this h-query showed 0, then A fails and exits. OtherwiseR
A had returned H(M ) = ψ(g2a )r for some r. In this case A chooses random a2 , . . . , an ← Zp ,computes a1 = r − (a2 x2 + . . . + an xn ), and returns the signature σ = hg1a1 , . . . , g1an i.
Eventually F outputs a forgery hσ1 , . . . , σn i for a message M . Again by assumption, F has
previously issued a h-query for M . If the coin flipped by A for this query did not show 0 then A
fails. Otherwise H(M ) = g1abr for some r chosen by A, and A outputs the rth root of σ1 σ2 x2 . . . σn xn .
Algorithm F cannot distinguish between A’s simulation and real life. Also, A will not fail withprobability pqS (1 − p) which is maximized when p = qS /(qS + 1), giving a bound of (1/e)(1 + qS ).
If it does not fail and F successfully forges a ring signature then A is successful and outputs g 1b .
Algorithm A requires n exponentiations on G2 in setup, one exponentiation for each of F’s hashqueries, n exponentiations for each of F’s signature queries, and n exponentiations in the output
phase, so its running time is F’s running time plus cG2 (2n + qH + nqS ).

19

5.4

Observations on Ring Signatures

Any ring signature scheme restricts to an ordinary signature scheme when n = 1. Our scheme
restricts to a short signature scheme similar to the co-GDH scheme [6]. In this modified co-GDH
scheme, σ equals h1/x rather than hx , and one verifies that e(h, g2 ) = e(σ, v) rather than thate(σ, g2 ) = e(h, v).
Bresson et al. [7] extend Rivest-Shamir-Tauman ring signatures to obtain threshold and ad-hoc
ring signatures. However, bilinear ring signatures have interesting properties that do not appear
to be shared by ring signatures in general. For any set of users U with u ∈ U , anyone can convert
a modified co-GDH signature by u into a ring signature by U . Specifically, to convert a modified
co-GDH signature σ1 on M for public key v1 into a ring signature σ = hσ10 , . . . , σn0 i on M for public
QR
keys v1 , . . . , vn , we choose ri ← Zp for 2 ≤ i ≤ n, and set σ10 ← σ1 ni=2 ψ(viri ) and σi0 ← ψ(v1−ri )for 2 ≤ i ≤ n. More generally, anyone can further anonymize a ring signature by adding users toU.

6Conclusions

We introduced the concept of aggregate signatures and constructed an efficient aggregate signaturescheme based on bilinear maps. Key generation, aggregation, and verification require no interaction.
We proved security of the system in a model that gives the adversary his choice of public keys andmessages to forge. For security, we introduced the additional constraint that an aggregate signature
is valid only if it is an aggregation of signatures on distinct messages. This constraint is satisfied
naturally for the applications we have in mind. More generally, the constraint can be satisfied by
prepending the public key to the message prior to signing.
We gave several applications for aggregate signatures. For example, they can be used to reduce
the size of certificate chains and reduce communication bandwidth in protocols such as SBGP. We
also showed that our specific aggregate signature scheme gives verifiably encrypted signatures.
Previous signature constructions using bilinear maps [6, 19, 8, 4] only required a gap DiffieHellman group (i.e., DDH easy, but CDH hard). The signature constructions in this paper require
the extra structure provided by the bilinear map. These constructions are an example where abilinear map provides more power than a generic gap Diffie-Hellman group.

Acknowledgments
The authors thank Leonid Reyzin, Liqun Chen, Alice Silverberg, and Cynthia Dwork for helpful
discussions about this work. The first author is supported by darpa, the Packard foundation, andan nsf career award. The third and fourth authors are supported by darpa and nsf.

References[1] N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. IEEE
J. Selected Areas in Comm., 18(4):593–610, April 2000.
[2] F. Bao, R. Deng, and W. Mao. Efficient and practical fair exchange protocols with offline
TTP. In Proceedings of IEEE Symposium on Security and Privacy, pages 77–85, 1998.

20

[3] M. Bellare and P. Rogaway. The exact security of digital signatures: How to sign with RSA and
Rabin. In Proceedings of Eurocrypt ’96, volume 1070 of LNCS, pages 399–416. Springer-Verlag,
1996.
[4] A. Boldyreva. Efficient threshold signature, multisignature and blind signature schemes basedon the gap-Diffie-Hellman-group signature scheme. In Proceedings of PKC 2003, volume 2567
of LNCS, pages 31–46. Springer-Verlag, 2003.
[5] D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. SIAM J. Computing, 32(3):586–615, 2003. Extended abstract in Proceedings of Crypto 2001.
[6] D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In Proceedingsof Asiacrypt 2001, volume 2248 of LNCS, pages 514–32. Springer-Verlag, 2001. Full paper:
http://crypto.stanford.edu/~dabo/pubs.html.
[7] E. Bresson, J. Stern, and M. Szydlo. Threshold ring signatures and applications to ad-hoc
groups. In M. Yung, editor, Proceedings of Crypto 2002, volume 2442 of LNCS, pages 465–80.
Springer-Verlag, 2002.
[8] Y. Dodis. Efficient construction of (distributed) verifiable random functions. In Proceedingsof PKC 2003, volume 2567 of LNCS, pages 1–17. Springer-Verlag, 2003.
[9] A. Fiat. Batch RSA. In Proceedings of Crypto ’89, pages 175–185, 1989.
[10] J. Garay, M. Jakobsson, and P. MacKenzie. Abuse-free optimistic contract signing. In Proceedings of Crypto ’99, volume 1666 of LNCS, pages 449–466. Springer-Verlag, 1999.
[11] P. Gemmel. An introduction to threshold cryptography. RSA CryptoBytes, 2(3):7–12, 1997.
[12] R. Gennaro, T. Rabin, S. Jarecki, and H. Krawczyk. Robust and efficient sharing of RSA
functions. J. Cryptology, 13(2):273–300, 2000.
[13] C. Gentry and A. Silverberg. Hierarchical ID-based cryptography. In Proceedings of Asiacrypt
2002, volume 2501 of LNCS, pages 548–66. Springer-Verlag, 2002.
[14] S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive
chosen-message attacks. SIAM J. Computing, 17(2):281–308, 1988.
[15] J. Horwitz and B. Lynn. Toward hierarchical identity-based encryption. In Proceedings ofEurocrypt 2002, volume 2332 of LNCS, pages 466–81. Springer-Verlag, 2002.
[16] A. Joux. A one round protocol for tripartite Diffie-Hellman. In Proceedings of ANTS IV,
volume 1838 of LNCS, pages 385–94. Springer-Verlag, 2000.
[17] A. Joux and K. Nguyen. Separating Decision Diffie-Hellman from Diffie-Hellman in Cryptographic Groups. Cryptology ePrint Archive, Report 2001/003, 2001. http://eprint.iacr.
org/.
[18] S. Kent, C. Lynn, and K. Seo. Secure border gateway protocol (Secure-BGP). IEEE J. Selected
Areas in Comm., 18(4):582–92, April 2000.
[19] A. Lysyanskaya. Unique signatures and verifiable random functions from the DH-DDH separation. In Proceedings of Crypto 2002, volume 2442 of LNCS, pages 597–612. Springer-Verlag,
2002.
21

[20] S. Micali, K. Ohta, and L. Reyzin. Accountable-subgroup multisignatures (extended abstract).
In Proceedings of CCS 2001, pages 245–54. ACM Press, 2001.
[21] S. Micali and R. Rivest. Transitive signature schemes. In Proceedings of RSA 2002, volume2271 of LNCS, pages 236–43. Springer-Verlag, 2002.
[22] A. Miyaji, M. Nakabayashi, and S. Takano. New explicit conditions of elliptic curve traces for
FR-reduction. IEICE Trans. Fundamentals, E84-A(5):1234–43, May 2001.
[23] M. Naor. Deniable ring authentication. In Proceedings of Crypto 2002, volume 2442 of LNCS,
pages 481–98. Springer-Verlag, 2002.
[24] K. Ohta and T. Okamoto. Multisignature schemes secure against active insider attacks. IEICE
Trans. Fundamentals, E82-A(1):21–31, 1999.
[25] T. Okamoto. A digital multisignature scheme using bijective public-key cryptosystems. ACM
Trans. Computer Systems, 6(4):432–441, 1998.
[26] T. Okamoto and D. Pointcheval. The gap problems: A new class of problems for the security ofcryptographic primitives. In Proceedings of PKC 2001, volume 1992 of LNCS, pages 104–118.
Springer-Verlag, 2001.
[27] G. Poupard and J. Stern. Fair encryption of RSA keys. In Proceedings of Eurocrypt 2000,
volume 1807 of LNCS, pages 172–89. Springer-Verlag, 2000.
[28] R. Rivest, A. Shamir, and Y. Tauman. How to leak a secret. In Proceedings of Asiacrypt 2001,
volume 2248 of LNCS, pages 552–65. Springer-Verlag, 2001.
[29] F. Zhang and K. Kim. ID-based blind signature and ring signature from pairings. In Proceedingsof Asiacrypt 2002, volume 2501 of LNCS, pages 533–47. Springer-Verlag, 2002.

22