multisignature generation would often trump this computational cost. We point out that

Multisignatures Using Proofs of Secret Key Possession 223

our CDH based scheme has a tight reduction only from expected-time hardness of the

CDH problem. However, in generic groups the expected-time hardness of the CDH is

essentially the same as the ¬xed-time hardness of this problem, i.e. for every algorithm

which solves the CDH problem in a generic group of size q with probability and

√

expected-time T , it holds that T / ¤ q.

Organization. After preliminaries in Section 2 we de¬ne secure multisignatures in the

Key Veri¬cation model in Section 3, and present our DDH-based and CDH-based mul-

tisignature schemes respectively in Sections 4 and 5.

2 Preliminaries: Notation and Assumptions

Let G be a multiplicative group of a prime order q, and let g be its generator. All arith-

metic operations are either modulo q, when involving numbers chosen in Zq , or they

r

are operations in G, when involving group elements. We use notation x ← S to denote

a probabilistic process which assigns to variable x a uniformly chosen value in set S.

We write a|b to denote the concatenation of bit strings a and b.

The computational Dif¬e Hellman (CDH) problem in group G is a problem of com-

puting g xy , given the tuple (g, g x , g y ) for random x, y in Zq , while the decisional Dif¬e

Hellman (DDH) problem in G is the problem of distinguishing between tuples of the

form (g, g x , g y , g xy ) for random x, y in Zq , and (g, g x , g y , g z ) for random x, y, z in Zq .

De¬nition 1. The CDH problem is (t, )-hard in G if for any algorithm B running in

time t, we have AdvCDH (B) ¤ where:

G

AdvCDH (B) = Pr [B(g, g x, g y ) = g xy ]

G r

x,y ←Zq

De¬nition 2. The DDH problem is (t, )-hard in G if for any algorithm B running in

time t, we have AdvDDH(B) ¤ where:

G

AdvDDH (B) = | Pr [B(g, g x , g y , g xy ) = 1] ’ Prr [B(g, g x, g y , g z ) = 1]|

G r

x,y ←Zq x,y,z ←Zq

Hardness of DL problem in G is implied by the hardness of either the DDH problem

or the CDH problem in G, but the converse is not known to be true. However, all these

problems have the same hardness as the DL problem in generic groups [Sho00]. More-

over, by the results of Maurer and Wolf [MW99], the CDH problem is very closely

related to the DL problem in a large class of groups that are commonly used in cryp-

tography. Also, see [Bon98] for various groups where DDH assumption might hold.

3 Multisignature Schemes

We de¬ne a Multisignature Scheme (MS) in the Key Veri¬cation (KV) model as a tuple

(Setup, KGen, KVrfy, MSign, Vrfy) where Setup, KGen, KVrfy and Vrfy are ef¬cient

probabilistic algorithms and MSign is an interactive protocol s.t.

224 A. Bagherzandi and S. Jarecki

“ par ← Setup(1κ ), on input the security parameter κ generates the public parame-

ters par.

“ (sk, pk, π) ← KGen(par), executed by each user on input par, generates this user™s

secret key sk, the corresponding public key pk, and a proof of validity of this public

key, denoted π.

“ {0, 1} ← KVrfy(par, pk, π) veri¬es whether pk is a valid key, given the proof π.

“ MSign is a multisignature protocol executed by a group of players who intend to

sign the same message m. Each player Pi executes MSign on public inputs par,

message m and private input ski , its secret key, and outputs a multisignature σ.

“ {0, 1} ← Vrfy(par, m, PKSet, σ) veri¬es whether σ is a valid multisignature on

message m on behalf of the set of players whose public keys are in set PKSet.

The above set of procedures must satisfy the following correctness property. Let

par be any output of Setup(1κ ). First, any (sk, pk, π) output by KGen(par) satis-

¬es KVrfy(par, pk, π) = 1. Second, for any n ¤ nmax , any message m, and any

(ski , pki , πi ) tuples, i ∈ {1, ..., n}, generated by KGen(par), if one executes n in-

stances of protocol MSign, where the i-th instance executes on inputs (par, m, ski ),

and if all the messages between these instances are correctly delivered, then each in-

stance outputs the same string σ s.t. Vrfy(par, m, {pk1 , pk2 , ...pkn }, σ) = 1.

Multisignature security in Key Veri¬cation model. As in the previous works on mul-

tisignatures, e.g. [MOR01, BN06, RY07], we de¬ne multisignature security as universal

unforgeability under a chosen message attack against a single honest player. Namely, we

de¬ne the adversarial advantage of an adversary A against the multisignature scheme

MS = (Setup, KGen, KVrfy, MSign, Vrfy), i.e. Advuu’cma (A), as a probability that

MS

uu’cma

(A) described in Figure 2 outputs 1,where the probability goes

experiment ExpMS

over the random coins of the adversary A and all the randomness used in the experi-

ment. We call a multisignature scheme (t, , nmax , qs )-secure if Advuu’cma (A) ¤

MS

for every adversary A that runs in time at most t, makes at most qs signature queries,

and where the size of the group of players S on behalf of which the adversary forges

is bounded as |S| ¤ nmax . In the random oracle model we consider also a notion of

(t, , nmax , qs , qh )-secure multisignature scheme, where adversary A is additionally re-

stricted to at most qh hash queries and the probability in the experiment Expuu’cma (A)

MS

is taken also over the random choice of all hash functions.

Experiment Expuu’cma (A)

MS

par ← Setup(1κ ); (sk— , pk— , π — ) ← KGen(par); List ← …;

Run A(par, pk— , π — ), and for every signature query m made by A do the following:

List ← List ∪ {m}; Execute protocol MSign on behalf of an honest player on inputs

(par, m, sk— ), forwarding messages to and from A.

When A halts, parse its output as (m, σ, {(pki , πi )}i∈S ) where S is some set of indexes.

If (m ∈ List) and (pk1 = pk— ) and (KVrfy(par, pki , πi ) = 1 for all i ∈ S) and ¬nally

(Vrfy(par, m, {pki }i∈S , σ)) = 1 then return 1; Otherwise return 0.

Fig. 2. Chosen Message Attack against Multisignature Scheme

Multisignatures Using Proofs of Secret Key Possession 225

Remarks on MS syntax and de¬nition of security: (1) In the security experiment

Expuu’cma above we take the simplifying assumption that the Setup procedure is ex-

MS

ecuted by an honest party. However, the public parameters in the two multisignature

schemes in this paper are needed to de¬ne groups of prime order where the CDH and

DDH assumptions hold, and such parameters can be chosen by a potentially dishonest

party and then veri¬ed by every player. (2) The syntax of a multisignature scheme in the

KV model is a simpli¬cation of the syntax used by [RY07], which modeled potentially

interactive key registration processes. Here we allow only non-interactive proofs, but

such proofs make multisignature schemes more ¬‚exible because they can be veri¬ed

either by the CA™s during the key registration process, as in [RY07], or by multisigna-

ture veri¬ers, e.g. together with veri¬cation of PKI certi¬cates for a given key. (3) Note

that a multisignature in the KV model generalizes multisignatures in the plain-model if

one sets the proofs of public key validity to empty strings and sets the output of KVrfy

on any inputs to 1. (4) However, in contrast to the de¬nition of multisignatures in the

plain model proposed by [MOR01] and [BN06], we do not include the set of partic-

ipants™ identities and/or their public keys as input in the multisignature protocol. The

participating players must be aware of one another in the protocol execution, but this

information is needed only to ensure proper communication, and does not need to be

part of the inputs to the multisignature protocol. Removing this input from the mul-

tisignature protocol gives more ¬‚exibility to applications of multisignatures, because in

some applications signers might care only about the message they are is signing and

not about the identities of other signers. This is the case for example in aggregation of

acknowledgments of broadcast reception. In such applications multisignature schemes

analyzed in the model of [MOR01, BN06] would have to be preceded by an additional

communication round for participants to broadcast their identities and/or public keys.

On the other hand, multisignature schemes which conform to our simpli¬ed model im-

ply schemes in the model of [MOR01, BN06] if the MSign protocol is executed on

the message appended with the list of identities and/or public keys of the participating

players. (5) The notion of multisignature security in [MOR01, BN06] treats a multisig-

nature effectively as a signature on a pair (m, PKSet), and their notion of forgery is

consequently broader than ours since it includes a case where an attacker forges a mul-

tisignature on a message that was previously signed by the honest player, but it was

signed together with a different set of public keys. In our model such adversary would

not be considered a successful forger since in our model an honest player is not required