’e ’f

for all Pj ∈ S/{P1 }, (ej , fj ) = H4 (g, h, yj , zj , Aj , Bj , g tj yj j Aj j ,

’e ’f

htj zj j Bj j ) and CAj = H1 (Aj ). If the veri¬cation does not pass,

stop the simulation of this multisignature instance. Otherwise return

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

(1) (1) (1)

Procedure SIML ({(zj , Aj , Bj )}Pj ∈S/{P1 } ):

(2) (2) (2)

’e ’e

r

Step 2. Pick (s1 , e) ← Z2 and compute A1 ← g s1 y1 , B1 ← hs1 z1 . If H1 [A1 ]

q

(2)

is not set, assign H1 [A1 ] ← CA1 ; Otherwise set bad5 ← true, stop and re-

turn “fail”.

(2)

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

(2)

DLh (B1 )

Multisignatures Using Proofs of Secret Key Possession 231

(2)

’e ’e

r

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

q

(2)

(B1 )’f1 .

(2) (2)

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

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

(1) (2)

Compute y ← Pj ∈S yj , z ← z1 Pj ∈S/{P1 } zj , A ← A1 Pj ∈S/{P1 }

(1) (2) (1)

Aj , B ← B1 Pj ∈S/{P1 } Bj . If H5 [(g, h, y, z, A, B)] is not set, set it to

e; Otherwise set bad7 ← true, stop and return “fail”.

(2) (2)

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

Step 3. Upon receiving (Aj , Bj , zj , (ej , fj , tj )) for all Pj ∈ S/{P1 }, verify whether

for all Pj ∈ S/{P1 },

(1)

(a) Aj = Aj ; If not, set bad8 ← true, stop and return “fail”.

(1) (1)

(b) Bj = Bj and zj = zj ; If not, set bad9 ← true, stop and return “fail”.

’e ’f ’e ’f

(c) (ej , fj ) = H4 (g, h, yj , zj , Aj , Bj , g tj yj j Aj j , htj zj j Bj j ) and

CAj = H1 (Aj ); If not stop the simulation of this multisignature instance.

If all the veri¬cations pass, send s1 to A.

Finalization: After receiving a valid forgery (m, σ, {(pki , πi )}Pi ∈S ) from A, the al-

ˆ

gorithm B attempts to output z = hx1 . Let σ = (z, e, s, p) and pki = yi and πi =

ˆ

(zi , ei , si ) for all Pi ∈ S. If in the simulation of H3 for query (m, p), the simulator

¬nds an entry b = b1 |...|b|S| corresponding to p in H2 , and moreover the ¬rst element

(m)

of the vector b is equal to b1 , then it stops and returns “fail”; otherwise B retrieves

±(m,p) assigned to (m, p) in the simulation of H3 and βyi assigned to yi in the simula-

tion to G1 for all Pi ∈ S and returns z where

ˆ

§

⎪ É z (m,p) 1/βy when S/{P1 } = …

1/±

⎨

Pi ∈S/{1} (zi )

i

z=

ˆ

⎪

© 1/±(m,p)

otherwise

z

Note that if (g, y, ˆ ±(m,p) , z) where y = Pi ∈S (yi ) and (g, yi , hβyi , zi ) where Pi ∈

ˆ

h

S/{P1 } are all DH tuples, then (g, y1 , ˆ z ) is also a DH tuple. We will argue that if

h, ˆ

the multisignature veri¬cation passes then with a high probability (g, y, ˆ ±(m,p) , z) is a

h

DH tuple and if the key veri¬cation passes for all of the adversary™s public keys then

with a high probability (g, yi , ˆ βyi , zi )™s are also all DH tuples, in which case z is the

ˆ

h

answer to the reduction™s CDH challenge. But ¬rst let™s look at the probability of failure

events. Let Ei for i = 1..9, denote the failure event that badi = true. The algorithm B

provides a perfect simulation for adversary A conditioned on events Ei where i = 1..9

not happening. More precisely, if events Ei for i = 1..9 do not happen then: Firstly, the

view of the adversary interacting with the simulator in SIMR branch is identical to the

view of the adversary in the real execution conditioned on the event that the simulation

stops in step (3™), i.e. if A™s responses in that step do not pass the veri¬cation procedure.

Secondly, the view of the adversary interacting with the simulator in SIML branch is

identical to the view of the adversary in the real execution conditioned on the event

(1) (1) (1)

that A™s responses in step (3™) are correct, i.e. that values {(zj , Aj , Bj )}Pj ∈S/{P1 }

232 A. Bagherzandi and S. Jarecki

which are input to SIML satisfy the veri¬cation condition. (Note that the SIML branch

executes only under this condition.) We start by upper-bounding the probabilities of all

the “fail” events:

The event E1 corresponds to a collision in H2 . Thus Pr[E1 ] ¤ (qH2 )2 /22κ . To

upper bound E2 , it is enough to upper bound the event that H2 is queried on some

b = b1 |...|b|S| where H2 (b) = p for some previous query (m, p) to H3 . The probability

that any query to H2 hits some p s.t. (m, p) is also queried to H3 is at most qH3 /22κ

and there are at most qH2 queries to H2 , thus Pr[E2 ] ¤ qH2 qH3 /22κ . The events E3

and E5 re¬‚ect the possibility that H1 has been queried on A1 before it is set by B in a

particular signing query. Since no information about A1 is revealed before it is set by B,

thus both of these events can be upper bounded by qs qH1 /22κ . Similarly both E4 and

E6 can be upper bounded by qs qH4 /q. The event E7 re¬‚ects the possibility that H5 has

been queried on (g, h, y, z, A, B) before it is set by B in a particular signing query. Here

we have two cases: either adversary has queried H1 on A1 or B1 in a particular signing

query or he has not. In the ¬rst case which happens with probability at most 2qH1 /22κ ,

the adversary knows both A and B and can easily query H5 on (g, h, y, z, A, B) before

it is set by B. In the second case A still has some information about A and B and can

happen to query H5 on (g, h, y, z, A, B) with probability at most qH5 /(q ’ qH1 ). Thus,

Pr[E7 ] ¤ 2qs qH1 /22κ + qs qH5 /(q ’ qH1 ). The event E8 corresponds to a collision

in H1 . Now since CAj = CA1 for all Pj ∈ S, and CA1 is the only output of H1

that is being manipulated by B in SIMR and SIML , therefore with regards to value

CAj , for any Pj ∈ S/{P1 }, the hash function H1 remains collision resistant across

(1)

these SIML and SIMR executions. Thus the value Aj revealed for CAj in SIMR

and value Aj revealed for CAj in SIML can be different with probability at most

(qH1 )2 /22κ . Hence Pr[E8 ] ¤ (qH1 )2 /22κ . The event E9 re¬‚ects the possibility that A

has cheated on at least one of the NIZK proofs in SIMR or SIML branches. However

due to special soundness property of this double-DL-equality proof system, for given

tuple (g, h, yi , zi , Ai , Bi ) not satisfying double-DL-equality, for any ui , vi ∈ G, there™s

at most q different (e, f ) ∈ Zq pairs that satisfy the veri¬cation equation for some t.

Therefore the probability of hitting such pair in qH4 queries is bounded by qH4 /q. Thus

Pr[E9 ] ¤ 2qH4 /q.

There is also a possibility of failure in reduction after A outputs a valid forgery.

Namely if in the simulation of H3 for query (m, p) where m is in the forgery, the

simulator ¬nds an entry b = b1 |...|b|S| corresponding to p in H2 , and moreover the ¬rst

(m)

element of the vector b is equal to b1 , the query is answered by g ±(m,p) and therefore

is useless for the reduction. However since with probability 1/2, the ¬rst element of

(m)

the vector b is not equal to b1 , therefore with probability at least 1/2 the reduction

proceeds to output z after obtaining a valid forgery from A.

ˆ

Now since Vrfy(g, m, {pki }Pi ∈S , σ) = 1, thus due to special soundness property

of DL-equality proof system, except for a probability of qH5 /q, (g, y, ˆ ±(m,p) , z) is a

h

DH tuple. Similarly Since KVrfy(par, pki , π) = 1 for all Pj ∈ S/{P1 }, except for a

ˆ

probability of qG2 /q, the tuples (g, yj , hβyj , zj ) where Pj ∈ S/{P1 } are all DH tuples.

Therefore, (g, y1 , ˆ z ) is also a DH tuple except for these error probabilities, and thus

h, ˆ

B solves the DH problem with advantage = 1/2( ’ err) where