qH2 (qH2 + qH3 ) + 4qs qH1 + (qH1 )2 2(qs + 1)qH4 + qH5 + qG2 qs qH5

err ¤ + +

22κ q ’ qH1

q

The fact that qG1 + qG2 + qH1 + qH2 + qH3 + qH4 + qH5 ¤ qh yields the desired result.

Calculating the running time of the simulator is little bit complicated due to the

tree-like nature of its execution structure. Let™s focus on “answering to the signature

queries” part since it is the most time consuming part of the execution. Let r1 |r2 |...|ri

be the randomness of the real execution of the protocol in which the randomness of

the j th signature query instance, 1 ¤ j ¤ i, is rj . Therefore r1 |r2 |...|ri determines the

path of real execution up to ith signature query. Accordingly let ti (r1 |r2 |...|ri ) be the

running time of the real execution of the protocol in ith round of answering signature

qs

queries. By assumption we have ∀r1 , r2 , ..., rqs i=1 ti (r1 |r2 |...|ri ) = T where T is

the total running time of the forger in “answering to the signature queries” part.

Let sL and sR be the running times of the simulator in SIML and SIMR branches of

i i

the execution respectively that interact with the adversary in the ith signature query. As

we mentioned before the view of the adversary interacting with the simulator in SIMR

branch is similar to the view of the adversary in real execution of the protocol condi-

tioned on the halting of the adversary except possibly with some negligible factor of fail-

ure. Similarly except for a negligible probability, the view of the adversary interacting

with the simulator in SIML branch is similar to the view of the adversary in real execu-

tion. This can be stated more formally as follows: for all random coins of the adversary,

(A, SIMR )$ SIMR = (A, P )$ P |A aborts and (A, SIML )$ SIML = (A, P )$ P . This

means that there is a one to one correspondence between the randomness of each sig-

nature query in the real execution and the execution of the simulator both in SIML and

in SIMR . Therefore we can calculate the running time of the simulator by calculating

the following:

T = t1 (r1 ) + t1 (r1 ) + ... + tqs (r1 |r2 |...|rqs ’1 |rqs ) + tqs (r1 |r2 |...|rqs ’1 |rqs )

L R LL L L LL L R

Note that there exist random coins that lead to non-constant reduction: Consider an

extreme case in which ∀1¤i¤qs ’1 , ti (r1 |r2 |...|ri ) = 0 and ti (r1 |r2 |...|ri ) = T and

LL L LL R

tqs (r1 |r2 |...|rqs ) = tqs (r1 |r2 |...|rqs ) = 0. In this case T = qs T . However we can

LL L LL L

still get a tight bound on the expected running time of the simulator.

qs

1

E[T ] = ti (r1 |r2 |...|ri ) + ti (r1 |r2 |...|ri )

LL L LL R

22qs κ

2qs κ

LR i=1

r1 ,r1 ,...,rqs ,rqs ←{0,1}2

L R

qs ’1 qs

= tqs (r1 |r2 |...|rqs ) + ti (r1 |r2 |...|ri ) + ti (r1 |r2 |...|ri )

LL R LL L LL L

i=1 i=1

qs ’1

+ ti (r1 |r2 |...|ri ) ’ ti (r1 |r2 |...|ri ) = 2T

LL R LL L

i=1

The last equation is because according to the de¬nition the ¬rst two terms add up to 2T

and for any function f de¬ned on any domain D, x,y∈D2 (f (x) ’ f (y)) = 0.

There are two multi-exponentiations and one single exponentiation in initialization

phase, one single exponentiation per each query to H3 and one single exponentiation

per each query to G1 . The reduction also makes three single exponentiations, at most

234 A. Bagherzandi and S. Jarecki

4nmax + 2 multi-exponentiations and at most 4nmax multiplications per each sign-

ing query in the signing phase, and 2(n ’ 1) multi-exponentiations in KVrfy and two

multi-exponentiations in Vrfy algorithms and nmax single exponentiations in ¬naliza-

tion phase. Therefore, ignoring the cost of hash-table lookups, assuming that a two or

three exponent multi-exponentiation take at most 25% more time than an exponentia-

tion, the total running time of the algorithm B can be upper-bounded as

t ¤ 2t + (qh + 6(nmax + 1)(qs + 1))te + 4qs nmax tm

Note on the Security Reduction. There are two crucial tricks we use which allow us

to compress the protocol to three rounds and maintain exact security reduction. First,

we use the signature randomization technique introduced by Katz and Wang [KW03],

which in the multisignature setting extends the signed message with n bits instead of

just one. This idea allows to replace the 1/qs factor encountered in the security reduc-

tion for the full-domain hash signature with a constant factor of 1/2. However, to make

the exact security reduction to go through, each player must have its own bit for the

reduction to play with, and hence the signature size grows by exactly n bits. However

we use an intermediate hash function to avoid this linear blowup and maintain constant

signature size. Secondly, we use the ZK proofs to ensure that the adversary cannot ma-

nipulate values zj and Bj provided by potentially corrupt players in the second round.

Inclusion of such ZK proofs in the protocol ¬xes these values across instances of the

same adversarial algorithm executing on the same inputs. This enables a very simple

rewinding schedule in the simulation: The simulator attempts the execution once, learns

the adversarial contributions zj , Bj if the adversary reveals them accompanied with a

correct ZK proof, rewinds the adversary, and equipped with the knowledge of the values

the adversary is bound to use again (we are aided here by the fact that the soundness

of the ZK proofs we use is unconditional), the simulator then successfully straight-line

simulates the protocol on behalf of an honest player. If the adversary fails to reveal

correct zj , Bj values, the simulator has an even easier job because the ¬rst execution

already forms a correct simulation, since the honest player would abandon the protocol

if any protocol participant failed in this way. Thus the simulator repeats an execution

of every instance of the signature scheme at most twice. At surface, the time of such

simulation seems to be at most twice the total time of the adversary. However, upon

closer inspection, it is clear that there are adversaries for which the running time of the

simulator is qs times the running time of the adversary. Namely in an extreme scenario

in which the adversary takes its maximum time on the random coins that run it in the

¬rst execution in the simulation and takes zero time on the remaining random coins.

However as we argue in the proof of the theorem 2 the expected running time of the

simulation is at most twice as the expected running time of the adversary.

References

[BGLS03] Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and veri¬ably encrypted

signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS,

vol. 2656, pp. 416“432. Springer, Heidelberg (2003)

[BJ08] Bagherzandi, A., Jarecki, S.: Multisignatures using proofs of secret key possession,

as secure as the dif¬e-hellman problem. ePrint Archive (2008)

[BLS04] Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. J. Cryp-

tology 17(4), 297“319 (2004)

Multisignatures Using Proofs of Secret Key Possession 235

[BN06] Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general

forking lemma. In: ACM Conference on Computer and Communications Security,

pp. 390“399 (2006)

[BNN07] Bellare, M., Namprempre, C., Neven, G.: Unrestricted aggregate signatures. In:

Arge, L., Cachin, C., Jurdzi´ ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS,

n

vol. 4596, pp. 411“422. Springer, Heidelberg (2007)

[Bol03] Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on

the gap-dif¬e-hellman-group signature scheme. In: Desmedt, Y.G. (ed.) PKC 2003.

LNCS, vol. 2567, pp. 31“46. Springer, Heidelberg (2002)

[Bon98] Boneh, D.: The decision dif¬e-hellman problem. In: Buhler, J.P. (ed.) ANTS 1998.

LNCS, vol. 1423, pp. 48“63. Springer, Heidelberg (1998)

[Fis05] Fischlin, M.: Communication-ef¬cient non-interactive proofs of knowledge with on-

line extractors. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 152“168.

Springer, Heidelberg (2005)

[GJ03] Goh, E.-J., Jarecki, S.: A signature scheme as secure as the dif¬e-hellman problem.

In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 401“415. Springer,

Heidelberg (2003)

[Har94] Harn, L.: Group-oriented (t,n) threshold digital signature scheme and digital

multisignature. In: IEEE Proceedings on Computers and Digital Techniques,

vol. 141(5), pp. 307“313 (1994)

[KW03] Katz, J., Wang, N.: Ef¬ciency improvements for signature schemes with tight secu-

rity reductions. In: ACM Conference on Computer and Communications Security,

pp. 155“164 (2003)

[LHL94] Li, C.-M., Hwang, T., Lee, N.-Y.: Threshold-multisignature schemes where sus-

pected forgery implies traceability of adversarial shareholders. In: De Santis, A. (ed.)

EUROCRYPT 1994. LNCS, vol. 950, pp. 194“204. Springer, Heidelberg (1995)

[LOS+ 06] Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate

signatures and multisignatures without random oracles. In: Vaudenay, S. (ed.) EU-

ROCRYPT 2006. LNCS, vol. 4004, pp. 465“485. Springer, Heidelberg (2006)

[MOR01] Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures: extended