et al. [BGLS03], with the analysis extended by Bellare et al. [BNN07]), but its mul-

tisignature veri¬cation algorithm requires O(n) bilinear map operations. Bellare and

Neven recently proposed a multisignature secure in the plain setting which does bilin-

ear maps [BN06]. While this scheme has a signi¬cantly smaller cost of multisignature

veri¬cation, it still requires O(n) exponentiations: The way [BN06] avoid KOSK and

KR models is by using independent challenges in the proofs of knowledge of discrete

logarithm performed by each player in the multisignature generation protocol. How-

ever, the multisignature veri¬cation operation then becomes a multi-exponentiation on

n public keys and n different exponents, and to the best of our knowledge the cost of

such multiexponentiation is still O(n) the cost of a single exponentiation.

Key Registration vs. Key Veri¬cation. The fact that current multisignatures in the plain

setting have slower veri¬cation than current schemes secure in the KR model motivates

looking closer at the KR model. For example, to the best of our knowledge it has not

been previously observed that the Key Registration model requires non-standard trust

assumptions among the PKI participants. Consider an application of a multisignature

scheme, where a multisignature is formed by some users certi¬ed by CA™s trusted by

the multisignature veri¬er, and some certi¬ed by CA™s who are unknown to this veri¬er.

Assume that the veri¬er is interested in checking whether or not the message was signed

by all the users of the ¬rst type but does not care if users of the second type have

also contributed to the multisignature. An example is a petition signed by individuals

whose public keys are certi¬ed by different CA™s, some widely known and trusted, some

less so. If a multisignature scheme secure in the KR model is used then the veri¬er

cannot conclude that the message was signed by the users she cares about, certi¬ed by

the CA™s she recognizes and trusts as long as a single participant in the multisignature

is certi¬ed by a CA which she does not recognize and/or trust. This is because the

scheme provides no security guarantees if the prescribed key registration procedure,

e.g. POP veri¬cation, is not followed with regards to even a single key participating in

the multisignature. This imposes a limitation on the use of multisignatures compared

to standard signatures or multisignatures secure in the plain setting, since in either of

the last two cases the veri¬er can decide if the users she cares about signed the petition

whether or not it was also signed by keys certi¬ed by unknown or suspect CA™s.

We propose to remove this limitation in the usage of multisignatures secure in the

KR model by considering an alternative mode of PKI operation which we call the Key

Veri¬cation (KV) Model. In the KV model each private key owner also produces a POP

string, but instead of handing it to the CA during the key registration process she at-

taches it to her key (or a PKI certi¬cate on the key). This POP message is then veri¬ed

by a multisignature receiver instead of by the CA, for example together with veri¬cation

Multisignatures Using Proofs of Secret Key Possession 221

of PKI certi¬cates on that key. We note that in the multisignature schemes we propose

POP veri¬cation costs are comparable to DSA certi¬cate veri¬cation, and this cost can

be further reduced by batching. The Key Veri¬cation model of operation should also

make it easier to adopt multisignature schemes: Since the CA operation does not need

to change, a multisignature scheme secure in the KV model can potentially use exist-

ing private-public keys and certi¬cates. For example, our CDH-based multisignature

scheme can utilize existing DSA or Schnorr signature public keys. We stress that while

the KR and KV models differ in how a multisignature scheme operates, any multisigna-

ture scheme secure in the KV model trivially implies a scheme secure in the KR model,

and any scheme secure in the KR model which has a non-interactive key registration

process (e.g. the schemes given by [RY07]) implies a scheme secure in the KV model.

Our Contributions. We propose two multisignature schemes in the KV (or KR) model,

denoted MDDH and MCDH. Both schemes take three rounds, have multisignature ver-

i¬cation procedures with O(1) exponentiations, do not require bilinear maps, and their

security is tightly related in ROM to, respectively, the CDH and DDH problems. The

POP messages in both schemes take O(1) group elements and their veri¬cation takes

O(1) exponentiations. Figure 1 summarizes the comparison between ours and previous

multisignature schemes. In this table, RY+BLS and RY+Waters refers to the ¬rst and

the second schemes of [RY07] respectively, BGLS refers to the multisignature scheme

implied by the aggregate signature proposed by Boneh et al [BGLS03], MOR+Fischlin

refers to the scheme of Micali et al [MOR01] with its initialization phase replaced by

key registration using Fischlin™s ZKPK™s [Fis05], and BN refers to the scheme proposed

by Bellare and Neven [BN06].

Compared to the two schemes of [RY07] our schemes do not rely on groups with

bilinear maps, but they do so at the cost of relying on the ROM model, which one of

the schemes of [RY07] avoids, and by using an interactive multisignature generation.

This drawback is signi¬cant in many applications but it can be mitigated in applications

where the same set of players is expected to repeatedly engage in several instances of

the multisignature protocol, as long as the multisignature procedure is fast on-line, i.e.

if the signed message is an input to the players only in the last round of the interaction,

which is the case with our DDH-based scheme. (It is an open problem whether the

CDH-based scheme can be made fast on-line without sacri¬cing other parameters.)

In comparison with the DL-based scheme in the Key Veri¬cation model implied

by the combined results of [MOR01, Fis05], our POP messages are shorter and faster

to verify, which is especially important in the Key Veri¬cation model where POP™s

must be attached to public keys and veri¬ed by multisignature recipients. To achieve

280 security the POP size and veri¬cation time in the scheme implied by [MOR01,

Fis05] would be larger by roughly a factor of ten when compared to our CDH-based and

DDH-based schemes. Moreover, the security reduction from the DL problem implied

by these two results is inexact, while our schemes have exact reductions from CDH or

DDH problems, and in many groups of interest the DL and CDH problems are almost

equivalent [MW00].

Finally, compared to the scheme of [BN06] which works in a plain model, our

schemes require a Key Veri¬cation model. This is a drawback, but as discussed in

a subsection above, in many scenarios the Key Veri¬cation model of PKI operation

222 A. Bagherzandi and S. Jarecki

Assumption Degradation Protocol Key Sig.Ver. Signing Signature

MS Scheme

on Security(1) in Security(2) Rounds Setup Time(3) (3)

Length(4)

Time

1/qs |G1 |

GapDH

RY+BLS 1 POP O(1) O(1)

1/qs |G1 | + |G2 |

GapDH

RY+Waters 1 POP O(1) O(1)

1/qs |G1 |

GapDH

BGLS 1 Plain O(n) O(1)

(5) 2

DL 1/qs qh 2|q|

MOR+Fischlin 2 POP O(1) O(1)

(5)

DL 1/qh |G| + |q|

BN 3 Plain O(n) O(1)

DDH 2|q|

MDDH exact 3 POP O(1) O(1)

(6)

CDH O(n) |G| + 2|q| + 2κ

MCDH exact 3 POP O(1)

Fig. 1. (1) All schemes except RY+Waters assume a ROM model; (2) Security degradation is

given as a factor f s.t. if a multisignature adversary succeeds with probability then the reduc-

tion breaks its underlying security assumption with probability ©(f — ) in comparable time. Here

qs and qh denote, respectively, the number of adversary™s signature and hash queries; (3) Compu-

tational costs are the number of modular exponentiations (or bilinear maps for the GapDH-based

schemes); (4) Signature length is measured in bits, where κ is the security parameter, |G| is the

number of bits required to represent elements in group G, q is the group order, and G1 and G2 are

two groups of points on an elliptic curve with asymmetrical bilinear maps. For example κ = 80,

|G| = |q| = |G1 | = 160 and |G2 | = 6 — 160; (5) The reduction for the Fischlin+MOR scheme

is our best estimate. The reduction given in [BN06] for the BN scheme has /qh degradation, but

it seems that one can modify it to provide only 1/qh degradation using the version of the forking

lemma originally given by Pointcheval and Stern [PS00]; (6) For the MCDH protocol we only

give an exact security reduction from the expected-time hardness of the CDH problem.

creates a small overhead in the certi¬cate veri¬cation process. On the other hand, our

schemes have tight reductions from CDH/DDH problems while the security reduction

of [BN06] encounters a security degradation due to the use of the forking lemma, and

our schemes make O(1) exponentiation operations during multisignature veri¬cation

compared to O(n) exponentiation cost in [BN06]. We stress that while it might seem

that our schemes require O(n) veri¬cation, because we require that each multisignature

veri¬er checks all n POP messages attached to the certi¬cates of the n players involved

in the multisignature, the O(1) multisignature veri¬cation in the KV model is better

than O(n) veri¬cation in the plain model for two reasons: (1) Since every entity in PKI

normally would keep a hash table of previously veri¬ed keys, the initial cost of key

veri¬cation amortizes over all multisignature veri¬cations which involve this key. (2)

If the CA™s use DL-based certi¬cates, then the cost of key veri¬cation imposed by our

schemes is only a constant factor higher than the cost of certi¬cate veri¬cation.

In terms of multisignature size, our DDH-based scheme is the same as that of [BN06],

and the multisignature in our CDH-based scheme is about 2 times larger than the mul-

tisignature of [BN06], when implemented over elliptic curves. Note, however, that if

one takes the exact security results into account, the two schemes achieve the same

level of provable security when the scheme of [BN06] is implemented over twice larger

groups, assuming the near equivalence of the DL and CDH problems. Unlike all other

multisignature schemes discussed, our CDH based scheme requires O(n) signing time

per party due to veri¬cation of NIZKs generated by each player. This may or may not