cure according to our notion implies a scheme secure in the model of [MOR01, BN06]

if players execute the MSign protocol on the concatenation of message m and the set of

public keys PKSet of the participating players, as in item (4) above.

4 Three-Round DDH-Based Multisignature Scheme

We describe a multisignature scheme denoted MDDH, presented in Figure 3, with a

tight security reduction from the DDH problem. The MDDH scheme is a multisignature

version of the signature scheme of Katz and Wang [KW03], which also has an exact

security reduction from the DDH problem. The MDDH scheme takes three rounds and

226 A. Bagherzandi and S. Jarecki

1. Setup(1κ ): Let G be a multiplicative group of prime order q and let g be a generator of

G. Consider the following hash functions: G1 : G6 ’ Zq , H1 : G ’ {0, 1}2κ and

r

H2 : G6 — {0, 1}— ’ Zq . Pick g, h ← G. Set par ← (g, h, q).

2. KGen(par): Player Pi picks his (ski , pki , πi ) tuple as follows:

r

Pick xi ← Zq , compute yi ← g xi , zi ← hxi and set pki ← (yi , zi ), ski ← xi ;

Construct a “proof of possession” of xi , i.e. a NIZK proof of DLg (yi ) = DLh (zi ):

r

Pick k ← Zq and compute u ← g k , v ← hk ;

Set e ← G1 (g, h, yi , zi , u, v), compute s ← k + exi and set πi ← (s, e).

3. KVrfy(par, pk, π): Let pk=(y, z), π=(s, e). Accept if e = G1 (g, h, y, z, g s y ’e , hs z ’e )

4. Protocol MSign: Let S where S ¤ nmax be the set of players that participate in the

protocol. Each player can determine the set S after the ¬rst protocol step. Player Pi on

inputs (par, m, ski ), performs the following steps:

r

4.1 Pick ki ← Zq , compute Ai ← g ki , Bi ← hki , CAi ← H1 (Ai ), CBi ← H1 (Bi );

Broadcast (yi , zi , CAi , CBi ).

4.2 Receive (CAj , CBj ) for all Pj ∈ S/{Pi } and broadcast (Ai , Bi ).

4.3 Receive (Aj , Bj , yj , zj ) for all Pj ∈ S/{Pi };

É É É É

Abort if CAj = H1 (Aj ) or CBj = H1 (Bj ) for any Pj ∈ S/{Pi };

Compute y ← Pj ∈S yj , z ← Pj ∈S zj , A ← Pj ∈S Aj , B ← Pj ∈S Bj ;

È

Set e ← H2 (g, h, y, z, A, B, m), compute si ← exi + ki and broadcast si .

4.4 Output multisignature σ = (e, s), where s = Pj ∈S sj .

É É

5. Vrfy(par, m, {pk1 , pk2 , ..., pkn }, σ):

Parse σ as (e, s) and each pki as (yi , zi ). Compute y ← n yi and z ← n zi ;

i=1 i=1

If e = H2 (g, h, y, z, g s y ’e , hs z ’e , m) then accept otherwise reject.

Fig. 3. MDDH multisignature scheme

has fast signing and veri¬cation procedures. It requires only two group exponentiations

per party for signing and two double-exponentiations for veri¬cation. The length of

the MDDH signature is 2|q|, which can be 320 bits, only twice the size of shortest

multisignature schemes [RY07, BGLS03], which, however, are based on a potentially

stronger assumption of GapDH on a group with a bilinear map.

Theorem 1. If DDH problem is (t , )-hard in group G, then multisignature MDDH

in Figure 3 is (t, , nmax , qs , qh )-secure in ROM where

qh 2 + 2qs (qh + nmax ) qs qh qh

¤ + + +

22κ q ’ qh q

t ≥ t ’ 2.4(qs + nmax )te ’ 4qs nmax tm

and tm and te are the times of one multiplication and one q-bit exponentiation in G.

Proof sketch. Due to space constraints we relegate the formal proof of this theorem to

the full version of this paper [BJ08], but we give a rough sketch of the proof here. Given

an adversary A against the MDDH scheme we construct an algorithm B that solves

the DDH problem in group G as follows: The reduction embeds its DDH challenge

(g, h, y1 , z1 ) into the public key of the sole honest player P1 by setting par = (g, h)

and pk1 = (y1 , z1 ). Note that the multisignature protocol performed by each player

Multisignatures Using Proofs of Secret Key Possession 227

is a version of a standard HVZK proof system for DL-equality, with the ¬rst message

Ai , Bi in this proof system preceded by a round of ROM-based commitments CAi , CBi .

As observed in [BN06], this round of commitment enables straight-line simulation of

this HVZK proof system: Namely, B picks both the challenge e and P1 ™s response s1

’e ’e

uniformly at random in Zq , computes A1 = g s1 y1 and B1 = hs1 z1 , pretends to

commit to these values by sending random CA1 , CB1 values, and thanks to the fact that

the adversary commits to his contributions Ai and Bi for Pi ∈ S/{P1 }, the reduction

B can compute the values A and B before she publishes his own contribution A1 , B1

in step 4.2. In this way B can embed the challenge e in the output to the appropriate

query (g, h, y, z, A, B, m) made by A to H2 . This reduction fails only if (1) A man-

ages to change one of his committed values; (2) A manages to decommit any of his

commitments C to some X s.t. C = H1 (X) without querying H1 on X; (3) A makes

query (g, h, y, z, A, B, m) to H2 before the reduction embeds challenge e in the answer.

However, all these cases happen with at most negligible probability in ROM. Finally,

the special soundness property of the above proof system ensures that if both the mul-

tisignature veri¬cation and all the key veri¬cation procedures pass then both (g, h, y, z)

where y = i∈S (yi ) and z = i∈S (xi ) and (g, h, yi , zi ) for each Pi are DH tuples,

and hence so must be the input tuple (g, h, y1 , z1 ). We leave the details of this proof to

the full version [BJ08].

5 Three-Round CDH-Based Multisignature Scheme

We describe a multisignature scheme, denoted MCDH and presented in Figure 4, whose

security is tightly related to the expected-time hardness of the CDH problem in the

Key Veri¬cation model. The MCDH scheme is a multisignature version of the CDH-

based signature of [KW03] and [GJ03]. It takes three rounds, the multisignature is

(|G| + 2|q| + 2κ)-bit long, and its veri¬cation procedure requires only two exponenti-

ations. We note, however, that the low round complexity and a tight reduction from the

(expected time) CDH problem comes at the following non-standard cost: Each player

in the multisignature generation procedure must verify ZK proofs issued by the other

players, and thus the computational cost of the signing algorithm is O(n) exponentia-

tions where n is the size of the signing group. This, however, will not be an important

drawback as long as the number of signers is modest or if the communication costs

in n-sized group of signers dominate the O(n)-exponentiations cost for each signer. As

we discuss at the end of this section, this cost can be avoided if one tolerates an increase

in the number of protocol rounds.

Theorem 2. If there is no adversary that can solve the CDH problem in group G in

expected time t with probability , then the multisignature scheme MCDH, described

in ¬gure 4 is (t, , nmax , qs , qh )-secure in random oracle model where

2

2qh + 4qs qh (2qs + 3)qh qs qh

¤2 + + +

2κ

2 q ’ qh

q

1

t ≥ (t ’ (qh ’ 6(nmax + 1)(qs + 1))te ’ 4qs nmax tm )

2

where tm and te are the times of one multiplication and one q-bit exponentiation in G.

228 A. Bagherzandi and S. Jarecki

1. Setup(1κ ) : Let G be a multiplicative group of prime order q and let g be a generator of

G. Consider the following hash functions: G1 : G ’ G, G2 : G6 ’ Zq , H1 : G ’

{0, 1}2κ , H2 : {0, 1}— ’ {0, 1}2κ , H3 : {0, 1}— — {0, 1}2κ ’ G, H4 : G8 ’ Z2 and q

6

H5 : G ’ Zq . Set par ← (g, q);

2. KGen(par): Player Pi picks an (ski , pki , πi ) tuple as follows:

r

Pick xi ← Zq , compute yi ← g xi and set pki ← yi and ski ← xi ;

Construct πi as “proof of possession” of xi :

Set h ← G1 (yi ), z ← hxi and construct a NIZK proof of DLg (yi ) = DLh (z):

r

Pick k ← Zq and compute u ← g k , v ← hk ;

Set e ← G2 (g, h, yi , z, u, v), compute s ← k + exi and set πi ← (z, s, e);

3. KVrfy(par, pk, π): Let pk = y, π = (z, s, e) and h ← G1 (y).

Accept if e = G2 (g, h, y, z, g s y ’e , hs z ’e ).

4. Protocol MSign: Let S where S ¤ nmax be the set of players that participate in the

protocol. Each player can determine the set S after the ¬rst protocol step. Player Pi on

inputs (par, m, ski ), performs the following steps:

r (m)

4.1 Pick ki ← Zq , compute Ai ← g ki and set CAi ← H1 (Ai ). If bit bi is not set,

(m) r (m)

pick bi ← {0, 1}. Broadcast (bi , yi , CAi ).

(m)