(m) (m) (m)

Set p ← H2 (b1 |b2 |...|b|S| ), where the global order among players can be deter-

mined e.g. by hashing the message broadcasted by players in the previous round. (If

two players broadcast the same message, the order between them can be arbitrary.)

Set h ← H3 (m, p) and Compute zi ← hxi and Bi ← hki ;

Construct NIZK proof πi that DLg (yi ) = DLh (zi ) and DLg (Ai ) = DLh (Bi ):

r

Pick r ← Zq , set u ← g r , v ← hr and (ei , fi ) ← H4 (g, h, yi , zi , Ai , Bi , u, v);

Compute ti ← r + ei xi + fi ki and set πi ← (ei , fi , ti );

Broadcast (Ai , Bi , zi , πi ).

4.3 Receive (Aj , Bj , zj , πj ) for all Pj ∈ S/{Pi }; Let πj = (ej , fj , tj );

’e ’f ’e ’f

Abort if (ej , fj ) = H4 (g, h, yj , zj , Aj , Bj , g tj yj j Aj j , htj zj j Bj j ) or CAj =

É É É É

H1 (Aj ) for any Pj ∈ S/{Pi }.

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

È

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

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

É

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

Parse σ as (z, e, s, p) and each pki as yi . Set y ← n yi and h ← H3 (m, p);

i=1

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

Fig. 4. MCDH multisignature scheme

Proof. Let A be an adversary that attacks the multisignature scheme MCDH, depicted

in ¬gure 4, in time t and with success probability and makes qs signing queries and

at most qh hash queries and produces a forgery on behalf of n ¤ nmax players. We

construct an algorithm B, that given oracle access to A, solves CDH problem in group

ˆ ˆ

G, i.e. given (g, y1 , h) ∈ G3 where y1 = g x1 it outputs hx1 in expected time t and with

success probability . Assume A makes qG1 , qG2 , qH1 , qH2 , qH3 , qH4 and qH5 queries

to G1 , G2 , H1 , H2 , H3 , H4 and H5 respectively and qG1 + qG2 + qH1 + qH2 + qH3 +

qH4 + qH5 ¤ qh , the total number of hash queries. In what follows we show how the

ˆ

CDH-attacker B proceeds given a CDH challenge (g, y1 , h).

Multisignatures Using Proofs of Secret Key Possession 229

Initialization: The algorithm B sets up tables G1 , G2 , H1 , H2 , H3 , H4 and H5 to sim-

ulate the hash functions G1 , G2 , H1 , H2 , H3 , H4 and H5 respectively which are ¬lled

out throughout the simulation. It also uses table B to store the bits b(m) assigned to each

message m. The algorithm B then sets the public parameters and the honest player™s

r

public key as par = g and pk1 = y1 respectively. Algorithm B picks βy1 ← Zq and

assigns G1 [y1 ] = g βy1 . It then computes z1 ← (y1 )βy1 and produces a simulated NIZK

proof of DL-equality between DLg (y1 ) and DLh (z1 ) where h = G1 [y1 ]. To simulate

’e ’e

r

this proof, B picks e, s ← Zq and assigns G2 [(g, h, y1 , z1 , g s y1 , hs z1 )] = e. Fi-

nally, B executes A on input (par, pk1 , π1 ) where π1 = (s, e). Note that G1 [y1 ] and

’e ’e

G2 [(g, h, y1 , z1 , g s y1 , hs z1 )] are set before the execution of A starts. Note also that

indeed DLg (y1 ) = DLh (z1 ) since z1 = (y1 )βy1 = g x1 βy1 = hx1 .

Answering hash queries: If a query has been made before, then B returns the appropriate

entry from the appropriate table e.g. if A queries G1 on y, B responds with G1 [y].

If A makes a new query to G2 , H1 , H4 and H5 , B answers with an element chosen

uniformly at random from the appropriate domain. If A makes a new query y to G1 , B

answers with ˆ βy where βy ← Zq . If A makes a new query b = b1 |...|b|S| to H2 , B

r

h

answers with an element chosen uniformly at random form {0, 1}2κ except when the

following failure cases happen: (a) If a collision happens in H2 then the simulator sets

a ¬‚ag bad1 ← true, stops and returns “fail”. (b) If A queries H2 for the ¬rst time on

b = b1 |...|b|S| and H2 (b) = p for some previous query (m, p) to H3 then the simulator

sets a ¬‚ag bad2 ← true, stops and returns “fail”. If A makes a new query (m, p) to H3 ,

the simulator looks up the table H2 : (a) If there exists no entry in H2 corresponding to

ˆ

r

p then the simulator picks ±(m,p) ← Zq and answers the query as h±(m,p) ; (b) If the

simulator ¬nds an entry b = b1 |...|b|S| corresponding to p in H2 then it assigns a bit

b1 (m) to message m if it has not been yet assigned, picks ±(m,p) ← Zq and checks

r

whether the ¬rst element of the vector b is equal to b1 (m) : If so, the simulator responds

ˆ

to the query as g ±(m,p) and otherwise it responds to the query as h±(m,p) .

Answering signature queries: To answer each signature query, simulator runs the ad-

versary twice after step 4.1. In the ¬rst execution, B runs the adversary to the point that

it can learn Aj , Bj and zj for all Pj ∈ S, but it does not complete this execution since

it will not know how to correctly create the response s1 in the zero-knowledge proof on

behalf of player P1 . The simulator then rewinds the adversary and uses the values it has

learned in the ¬rst execution to simulate the proof-of-knowledge protocol on behalf of

player P1 . If the adversary uses the same values {Aj , Bj , zj }Pj ∈S in both executions

then the simulator knows the query H5 (g, h, y, z, A, B) into which it should embed its

chosen challenge e. The only way this simulation can fail is if the adversary changes

his values zj , Aj and Bj for Pj ∈ S/{P1 } in the second execution. However due

to the soundness property of NIZK proof of DL-equality and the collision resistance

property of H1 , this can happen with only a negligible probability. This is because the

adversary has revealed yj ™s and committed to Aj ™s in the ¬rst round. Moreover, the

adversary gives a NIZK proof that DLg (yj ) = DLh (zj ) and DLg (Aj ) = DLh (Bj ) for

all Pj ∈ S/{P1 }. The details of the signature query simulation on input m are given

bellow. We point out that if the adversary aborts and/or sends values which do not pass

230 A. Bagherzandi and S. Jarecki

veri¬cation procedures in any point in the simulation below then the simulator stops

this instance of the multisignature generation protocol, just like an honest player P1 .

(m) (m) r

Step 1. If bit b1 has not been chosen for message m, pick b1 ← {0, 1}; Otherwise

(m)

r

use the previously chosen value. Pick CA1 ← {0, 1}2κ. Send (b1 , y1 , CA1 )

to A.

(m)

Step 2,3. Upon receiving (bj , yj , CAj ) for all Pj ∈ S/{P1 }, verify whether for

all Pj ∈ S/{P1 }, CAj = CA1 ; Abort if veri¬cation fails. Set p ←

(m) (m) (m)

H2 (b1 |b2 |...|b|S| ) and h ← H3 (m, p). Retrieve ±(m,p) assigned to

±

(m, p) in the simulation of this query to H3 and compute z1 ← y1 (m,p) . Note

that our simulation procedure for H3 ensures that h = H3 (m, p) = g ±(m,p)

±

and thus z1 = y1 (m,p) = g x1 ±(m,p) = hx1 .

(1) (1) (1)

Run SIMR as a subroutine and let {(Aj , Bj , zj )}Pj ∈S/{P1 } be

the values it returns. If SIMR did not stop, rewind the adversary to the

point where SIMR is called, and run SIML as a subroutine on input

(1) (1) (1)

{(Aj , Bj , zj )}Pj ∈S/{P1 } .

Step 4. Compute the multisignature from appropriate values gained in SIMR simu-

lation.

Procedure SIMR :

(1) (1) (1)

r

Step 2™. Pick k1 ← Zq and compute A1 ← g k1 , B1 ← hk1 . If H1 [A1 ] is not set,

(1)

assign H1 [A1 ] ← CA1 ; Otherwise set bad3 ← true, stop and return “fail”.

(1)

Simulate the NIZK proof that DLg (y1 ) = DLh (z1 ) and DLg (A1 ) =

(1)

DLh (B1 ):

(1)

’e ’e

r

Pick e1 , f1 , t1 ← Z3 , set u1 ← g t1 y1 1 (A1 )’f1 , v1 ← ht1 z1 1

q

(1)

(B1 )’f1 .

(1) (1)

If H4 [(g, h, y1 , z1 , A1 , B1 , u1 , v1 )] is not set, set it to (e1 , f1 );

Otherwise set bad4 ← true, stop and return “fail”.

(1) (1)

Send (A1 , B1 , z1 , (e1 , f1 , t1 )) to A.