“ Completeness

V 1» , x, P(1» , x, w, r), r = 1

Anonymous Proxy Signatures 217

∀ p.p.t. A :

“ Soundness

Pr r ← {0, 1}p(»); (x, π) ← A(r) : x ∈ L § V(1» , x, π, r) = 1

/ = negl(»)

∀ p.p.t. A :

“ Adaptive Single-Theorem Zero Knowledge

Advzk (») := Pr Expzk (») = 1 ’Pr Expzk-S (») = 1 = negl(») with

Π,A Π,A Π,A

Expzk (») Expzk-S (»)

Π,A Π,A

r ← {0, 1}p(») (r, stS ) ← Sim1 (1» )

(x, w, stA ) ← A1 (r) (x, w, stA ) ← A1 (r)

π ← P(x, w, r) π ← Sim2 (stS , x)

return A2 (stA , π) return A2 (stA , π)

“ Simulation Soundness

∀ p.p.t. A : Pr Expss (») = 1 = negl(») with

Π,A

Expss (»)

Π,A

(r, stS ) ← Sim1 (1» )

(y, stA ) ← A1 (r)

π ← Sim2 (stS , y)

(x, π ) ← A2 (stA , π)

if π = π and x ∈ LR and V(1» , x, π , r) = 1 return 1, else return 0.

/

Multisignatures Using Proofs of Secret Key Possession,

as Secure as the Dif¬e-Hellman Problem

Ali Bagherzandi and Stanis‚aw Jarecki

Department of Computer Science,

University of California, Irvine

{zandi,stasio}@ics.uci.edu

Abstract. A multisignature scheme allows a group of n players to produce

a short string which is equivalent to n separate signatures on the same message.

Assuming the Random Oracle Model (ROM), the aggregate signature schemes of

Boneh et al. [BGLS03] and Bellare and Neven [BN06] provide multisignatures

secure in the standard public key setting, but their multisignature veri¬cation

algorithms involve respectively O(n) bilinear maps and O(n) exponentiations.

Ristenpart and Yilek [RY07] recently showed two multisignature schemes rely-

ing on groups with bilinear maps, with just O(1) bilinear maps in multisignature

veri¬cation, which are secure if each public key is accompanied by so-called

“proof of (secret key) possession” (POP). We show how to achieve secure mul-

tisignatures in the POP model using any group where CDH or DDH problems are

hard. Both schemes have multisignature veri¬cation with O(1) exponentiations,

and their POP messages take O(1) group elements and require O(1) exponenti-

ations to verify. Moreover, the security of the proposed schemes is tightly related

to the CDH and DDH problems, in ROM.

1 Introduction

A multisignature scheme allows a group of n players to sign a common message so that

instead of n separate signatures the players produce a short string which can be veri¬ed

against the set of the public keys of the participating players. Such scheme is interesting

if the resulting string is shorter than n separate signatures and/or the veri¬cation time

is faster than n separate signature veri¬cations. Applications of multisignatures include

scenarios where the number of signers is moderate, like co-signing, distribution of cer-

ti¬cate authorities, or aggregation of PKI certi¬cate chains. However, multisignatures

can potentially be useful also in very large groups of signers, e.g. for aggregation of

acknowledgements in response to a broadcast.

Rogue Key Attacks and the KOSK Assumption. Multisignature schemes are possible be-

cause of homomorphic properties of arithmetic operations involved in standard signa-

tures. For example, a BLS signature [BLS04] on message m under public key yi = g xi

is σi = H(m)xi , i.e. a value s.t. (g, yi , H(m), σi ) is a DDH tuple. A correspond-

ing multisignature can be created as σ = n σi , and it can be veri¬ed under the

i=1

Research supported by NSF CyberTrust Grant #0430622.

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 218“235, 2008.

c Springer-Verlag Berlin Heidelberg 2008

Multisignatures Using Proofs of Secret Key Possession 219

combined public key y = n yi , because (g, y, H(m), σ) is also a DDH tuple. Un-

i=1

fortunately, the same homomorphic properties which enable aggregation of signatures

into multisignatures can enable a “rouge key attack” on such schemes. For example,

the above scheme is insecure because an adversary who picks y2 = g x /y1 for some

existing key y1 and any x can use x = DL(g, y1 — y2 ) to issue multisignatures on be-

half of key set {y1 , y2 }. Indeed, as Micali et al. [MOR01] point out, many proposed

multisignature schemes are vulnerable to such rouge key attacks, e.g. [LHL94, Har94],

or their security requires trusted generation of each key, e.g. [OO91, OO99]. Interest-

ingly, rouge key attackers usually do not know the private key corresponding to the

rogue public key. Indeed, under the discrete logarithm assumption it is provably hard

to compute the private key x2 s.t. y2 = g x2 in the above attack. This observation led

Micali, Ohta, and Reyzin [MOR01] to construct the ¬rst multisignature scheme secure

without assuming trusted key generation. However, that scheme requires all potential

signers to engage in an interactive initialization protocol in which every player proves

knowledge of its secret key to all others, and such initialization procedure does not

tolerate dynamic groups and does not scale well to large groups. One way to remove

this initialization procedure is to assume the so-called knowledge of secret key (KOSK)

assumption [Bol03] on key registration process: The KOSK assumption states that if

an adversary registers a public key then the adversary™s algorithm must also explicitly

output a corresponding secret key. Two secure multisignature schemes were proposed

under this assumption using bilinear maps, by Boldyreva [Bol03] in ROM and by Lu et

al. [LOS+ 06] in the standard model (i.e. without ROM).

Multisignatures in the Key Registration Model. One way to realize the KOSK assump-

tion is to employ so-called Key Registration Model (KR) for Public Key Infrastructure

(PKI), introduced in the context of multisignatures by Ristenpart and Yilek [RY07]. In

the KR model for PKI, a CA issues a certi¬cate on a key only if its owner passes a

special key registration protocol. For example, the PKCS#10 [PKC00] standard for CA

operation asks the user to sign a challenge message under its public key. This challenge-

signature pair is called a proof of possession of the secret key (POP) in PKCS#10, but

we™ll use this term more broadly, for any user-generated string veri¬ed by either the

CA or by multisignature veri¬ers (see the “Key Veri¬cation” model below). The intu-

itive goal of the POP mechanism in PKCS#10 was to assure that someone has access to

the secret key corresponding to the public key being certi¬ed, but this mechanism does

not implement the KOSK assumption in general. Indeed, Ristenpart and Yilek [RY07]

showed that the schemes of [Bol03, LOS+ 06] are insecure in the KR model if key reg-

istration is implemented with POPs of PKCS#10. Nevertheless, [RY07] also showed

that using a slight variant of the same POP mechanism the schemes of [Bol03, LOS+ 06]

yield secure multisignature schemes in the KR model, relying on bilinear maps.

Alternatively, one can realize the KOSK model by implementing POPs with con-

currently secure zero-knowledge proofs of knowledge (ZKPK) of a secret key. Such

ZKPK™s can be achieved in ROM by the results of Fischlin [Fis05] using O(log κ)

group elements where κ is the security parameter. Combined with the multisignature

protocol of [MOR01], this implies a multisignature scheme in the KR model secure

under the DL assumption. However, non-constant-sized POPs are less practical if POP

messages are veri¬ed by multisignature receivers instead of by the CA™s (see the “Key

220 A. Bagherzandi and S. Jarecki

Registration vs. Key Veri¬cation” below). Moreover, due to the heavy use of the forking

lemma in the reduction of [MOR01], the exact security of this scheme is not optimal.

Multisignatures in the Plain Public Key Model. One of the drawbacks of multisignatures

in the KR model is that they require modi¬cations to the current operation of the CA™s.

(In addition to imposing non-standard trust requirements on CA™s, as we argue below.)

It is therefore highly interesting to provide multisignature schemes which are secure

in the plain setting where no special registration process is assumed for public keys.