A preliminary version of this paper appears in Advances in Cryptology – EUROCRYPT 2007,
Lecture Notes in Computer Science Vol. 4515, pp. 228–245, M. Naor ed., Springer-Verlag, 2007.
This is the full version.

The Power of Proofs-of-Possession:
Securing Multiparty Signatures against Rogue-Key Attacks
Thomas Ristenpart∗

Scott Yilek†

Abstract
Multiparty signature protocols need protection against rogue-key attacks, made possible
whenever an adversary can choose its public key(s) arbitrarily. For many schemes, provablesecurity has only been established under the knowledge of secret key (KOSK) assumption where
the adversary is required to reveal the secret keys it utilizes. In practice, certifying authorities
rarely require the strong proofs of knowledge of secret keys required to substantiate the KOSK
assumption. Instead, proofs of possession (POPs) are required and can be as simple as justa signature over the certificate request message. We propose a general registered key model,
within which we can model both the KOSK assumption and in-use POP protocols. We showthat simple POP protocols yield provable security of Boldyreva’s multisignature scheme [11],the LOSSW multisignature scheme [28], and a 2-user ring signature scheme due to Bender,
Katz, and Morselli [10]. Our results are the first to provide formal evidence that POPs can stop
rogue-key attacks.
Keywords: Proofs of possession, PKI, multisignatures, ring signatures, bilinear maps∗
Dept. of Computer Science & Engineering 0404, University of California San Diego, 9500 Gilman Drive, La
Jolla, CA 92093-0404, USA. Email: tristenp@cs.ucsd.edu. URL: http://www-cse.ucsd.edu/users/tristenp.
Supported in part by NSF grant CNS-0524765.
†
Dept. of Computer Science & Engineering 0404, University of California San Diego, 9500 Gilman Drive, La Jolla,
CA 92093-0404, USA. Email: syilek@cs.ucsd.edu. URL: http://www-cse.ucsd.edu/users/syilek. Supported inpart by NSF grant CNS-0430595 and a Jacobs School Fellowship.

1

Contents
1 Introduction

3

2 Preliminaries

5

3 The Registered Key Model

6

4 Multisignatures using POPs
7
4.1 Multisignatures Based on BLS Signatures . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Multisignatures Based on Waters Signatures . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 Attacks against Standardized Key Registration Protocols . . . . . . . . . . . . . . . 15
4.4 Other POP Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5 Ring Signatures in the Registered Key Model
5.1 Ring Signature Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Unforgeability Implications for κ-user Schemes . . . . . . . . . . . . . . . . . . . . .
5.3 KOSK Improves Unforgeability Guarantees . . . . . . . . . . . . . . . . . . . . . . .
5.4 Ring Signatures with POPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16
16
18
25
27

A Ring Signature Anonymity Definitions

35

2

1

Introduction

We refer to any scheme that generates signatures bound to a group of parties as a multiparty
signature scheme. We focus on schemes that are both adaptive and decentralized: the set of
potential signers is dynamic and no group manager is directly involved in establishing eligibility ofparticipants. Examples include multisignatures, ring signatures, designated-verifier signatures, andaggregate signatures. These schemes require special care against rogue-key attacks, which can bemounted whenever adversaries are allowed to choose their public keys arbitrarily. Typical attacks
have the adversary use a public key that is a function of an honest user’s key, allowing him to
produce forgeries easily. Rogue-key attacks have plagued the development of multiparty signatureschemes [26, 20, 22, 30, 32, 33, 25, 11, 28, 37, 31].
One method for preventing rogue-key attacks is to require, during public key registration with acertificate authority (CA), that a party proves knowledge of its secret key. This setting has typically
been formalized as the knowledge of secret key (KOSK) assumption [11]: schemes are analyzed in asetting where adversaries must reveal their secret keys directly. This abstraction has lead to simple
schemes and straightforward proofs of security. To name a few: Boldyreva’s multisignature scheme[11] (we call it BMS), the LOSSW multisignature scheme [28] (we call it WMS for brevity and its
basis on Waters signatures [39]), the LOSSW sequential aggregate signature scheme [28], and many
designated-verifier signature schemes [23, 38, 27, 24]. Since simple rogue-key attacks against theseschemes are known, it might appear that the security of these schemes actually depends on parties
performing proofs of knowledge during registration.
Drawbacks of the KOSK assumption. Unfortunately, there are substantial drawbacks tousing the KOSK assumption. Bellare and Neven discuss this in detail [7]; we briefly recall some of
their discussion. First and foremost, the KOSK assumption is not realized by existing public key
infrastructures (PKI). Registration protocols specified by the most widely used standards (RSA
PKCS#10 [35], RFC 4210 [1], RFC 4211 [36]) do not specify that CA’s should require proofs ofknowledge. Thus, to use schemes proven secure under the KOSK assumption, one would be facedwith the daunting task of upgrading existing (and already complex) PKI. This would likely require
implementing clients and CA’s that support zero-knowledge (ZK) proofs of knowledge that haveextraction guarantees in fully concurrent settings [4]. Non-interactive ZK proofs of knowledge [17,16, 19] could also be utilized, but these are more computationally expensive.
The plain setting. In the context of multisignatures, Bellare and Neven [7] show that it ispossible to dispense with the KOSK assumption. They provide a multisignature scheme which issecure, even against rogue-key attacks, in the plain public-key setting, where registration with a
CA ensures nothing about a party’s possession or knowledge of a secret key. In this paper we areinterested in something different, namely investigating the security of schemes (that are not securein the plain setting) under more realistic key registration protocols, discussed next.
Proofs of possession. Although existing PKIs do not require proofs of knowledge, standards
mandate the inclusion of a proof of possession (POP) during registration. A POP attests that a
party has access to the secret key associated with his/her public key, which is typically accomplishedusing the functionality of the key pair’s intended scheme. For signature schemes, the simplest POP
has a party sign its certificate request message and send both the message and signature to the CA.
The CA checks that the signature verifies under the public key being registered. In general, suchproofs of possession (POPs) are clearly not sufficient for substantiating the KOSK assumption. In
fact, POPs have not (previously) lead to any formal guarantees of security against rogue key attacks,even though intuitively they might appear to stop adversaries from picking arbitrary public keys.
This logical gap has contributed to contention regarding the need for POPs in PKI standards [2].

3

Our contributions. We suggest analyzing the security of multiparty signature schemes in aregistered key model, which allows modeling a variety of key registration assumptions including
those based on POPs. Using the new model, we analyze the security of the BMS and WMS
multisignature schemes under POP protocols. We show that, interestingly, requiring the in-use
and standardized POP protocol described above still admits rogue-key attacks. This implies theintuition mentioned above is flawed. On the positive side, we show how a slight change to thestandardized POP protocol admits proofs of security for these schemes. We also investigate thesetting of ring signatures. We describe how the key registration model can be utilized to resultin improved unforgeability guarantees. In particular we show that the Bender, Katz, and Morselli
2-user ring signature scheme based on Waters signatures [10] is secure against rogue-key attacks
under a simple POP protocol. We now look at each of these contributions in more detail.
The registered key model. A key registration protocol is a pair of interactive algorithms(RegP, RegV), the former executed by a registrant and the latter executed by a certifying authority(CA). We lift security definitions to the registered key model by giving adversaries an additional key
registration oracle, which, when invoked, executes a new instance of RegV. The security game canthen restrict adversarial behavior based on whether successful registration has occurred. Security
definitions in the registered key model are thus parameterized by a registration protocol. Thisapproach allows us to straightforwardly model a variety of registration assumptions, including the
KOSK assumption, the plain setting and POP-based protocols.
Multisignatures under POP. A multisignature scheme allows a set of parties to jointly generate
a compact signature for some message. These schemes have numerous applications, e.g. contract
signing, distribution of a certificate authority, or co-signing. The BMS and WMS schemes are
simple multisignature schemes that are based directly on the short signature schemes of Boneh,
Lynn, and Shacham (BLS) [14] and Waters [39]. (That is, a multisignature with group of size one
is simply a BLS or Waters signature.) These schemes give short multisignatures (just 160 bits for
BMS). Moreover, multisignature generation is straightforward: each party produces its BLS or
Waters signature on the message, and the multisignature is just the (component-wise) product ofthese signatures. Both schemes fall prey to straightforward rogue-key attacks, but have proofs ofsecurity under the KOSK assumption [11, 28].
We analyze these schemes when key registration requires POPs. We show that the standardized
POP mechanism described above, when applied to these schemes, does not lead to secure multisignatures. Both schemes fall to rogue-key attacks despite the use of the standardized POPs. We
present a straightforward and natural fix for this problem: simply use separate hash functions forPOPs and multisignatures. We prove the security of BMS and WMS multisignatures under such
POP mechanisms, giving the first formal justification that these desirable schemes can be usedin practice. Both proofs reduce to the same computational assumptions used in previous KOSK
proofs and the reductions are just as tight.
Ring signatures under POP. Ring signatures allow a signer to choose a group of public keys
and sign a message so that it is verifiable that some party in the group signed it, but no adversary can determine which party it was. The canonical application of ring signatures is leaking
secrets [34]. Bender, Katz, and Morselli (BKM) have given a hierarchy of anonymity and unforgeability definitions for ring signature schemes [10]. For κ-user schemes, where only rings of size κ
are allowed, we point out that the ability to mount rogue-key attacks (as opposed to the ability tocorrupt honest parties) is a crucial distinguisher of the strength of unforgeability definitions. We
introduce new security definitions that facilitate a formal analysis of this fact. BKM also propose
two 2-user ring signature schemes that do not rely on random oracles, and prove them to meet the
weaker unforgeability guarantee. As pointed out by Shacham and Waters, these schemes do not4meet the stronger definition due to rogue-key attacks [37].
We show that the KOSK assumption provably protects against rogue-key attacks for a naturalclass of ring signature schemes (both the BKM 2-user schemes fall into this class). We go on toprove the security of the BKM 2-user scheme based on Waters signatures under a simple POP-based
registration protocol.
Schemes in the plain setting. We briefly overview some schemes built for the plain setting.
The Micali, Ohta, and Reyzin multisignature scheme [31] was the first to be proven secure in theplain setting, but it requires a dedicated key setup phase after which the set of potential signers
is necessarily static. The multisignature scheme of Bellare and Neven [7] does not require a key
setup phase, and is proven secure in the plain setting. While computationally efficient, it requires
several rounds of communication between all co-signers, which is more than the “non-interactive”
BMS and WMS schemes.
Bender, Katz, and Morselli introduced the first ad-hoc ring signature scheme that provably
resists rogue-key attacks [10]. Their scheme is not efficient, requiring semantically-secure encryption
for each bit of a message. The ring signature scheme of Shacham and Waters [37] is more efficient
but still not as efficient as the BKM schemes for rings of size two. Particularly, their ring signatures
are at least three times as long as those given by the BKM scheme based on Waters signatures
and they require more computational overhead. Of course, their solution works on rings with size
greater than two.
Finally, aggregate signature schemes due to Boneh et al. [13] and Lysyanskaya et al. [29] aresecure in the plain setting.
Related work and open problems. Boldyreva et al. [12] investigate certified encryption andsignature schemes. They utilize a POP-based protocol to show the security of traditional certified
signatures. They do not consider multiparty signatures. Many schemes beyond those treatedhere rely on the KOSK assumption and finding POP-based protocols for such schemes, if possible,
constitutes an important set of open problems. A few examples are the LOSSW sequential aggregate
signature scheme [28], the StKD encryption scheme due to Bellare, Kohno, and Shoup [5], andvarious designated-verifier signature schemes [23, 38, 27, 24].

2

Preliminaries

Basic notation. For a set S, we write Pκ (S) to mean the set of all subsets of size κ that exist
in S. A multiset S is a set that allows multiple copies of elements. The size of a multiset is denoted|S|. We write Multiset union S1 ∪ S2 combines two multisets, including any duplicates. Thus,∪|S1 ∪ S2 | = |S1 | + |S2 |. We write S ←s to add (another copy of) s to S, i.e. S ← S ∪ {s}. Multiset
subtraction S − {s} denotes removing one instance of s from S. Multiset difference S1 \S2 resultsin the multiset formed by repeatedly executing S1 − {s} for each s ∈ S2 (note this is done once foreach element, including duplicates). Multiset equality, containment, inequality, and intersection
are defined in the natural ways. We abuse notation by using multiset notation also as boolean
operators: “If S1 ⊆ S2 then” evaluates the statement following ‘then’ if S1 is a subset of S2 anddoes not otherwise. Other boolean multiset-operators are defined in the natural way.
$$
We define s ← S as sampling uniformly from S and s ← A(x1 , x2 , . . .) assigns to s the resultof running A on fresh random coins and the inputs x1 , x2 , . . .. We denote concatenation of strings
M and M 0 by M || M 0 . For any string M , let M [i] denote the ith bit of M . We often write (xi )η1
to denote a vector of η values: (x1 , . . . , xη ). For a table Hs , let Hs [s] denote the element associatedwith s. We write Time(A) = max{t1 , t2 , . . .} where A = (A1 , A2 , . . .) is a tuple of algorithms and5

t1 , t2 , . . . are their respective worst case running times.
Bilinear maps and co-CDH. The schemes we consider use bilinear maps. Let G1 , G2 , and GT
be groups, each of prime order p. Then G∗1 , G∗2 , and G∗T represent the set of all generators of thegroups (respectively). Let e: G1 ×G2 → GT be an efficiently computable bilinear map (also called apairing). For the multisignature schemes we consider, we use the asymmetric setting [14, 13] whereG1 6= G2 and there exists an efficiently computable isomorphism ψ: G2 → G1 . The asymmetry
allows for short signatures, while ψ is needed in the proofs. For the ring signature schemes weconsider, we instead use the symmetric setting [10, 37] where G1 = G2 . Let n represent the numberof bits needed to encode an element of G1 ; for the asymmetric setting n is typically 160. Finallylet g be a generator in G2 . For the rest of the paper we treat G1 , G2 , GT , p, g, e as fixed, globallyknown parameters. Then we define the advantage of an algorithm A in solving the Computational
co-Diffie-Hellman (co-CDH) problem in the groups (G1 , G2 ) as
h
i
$
$
x
x
Advco-cdh
(A)
=
Pr
A(g,
g
,
h)
=
h
:
x
←
Z
;
h
←
G
p
1
(G1 ,G2 )where the probability is over the random choices of x and h and the coins used by A. Here Zp isthe set of integers modulo p. Note that in the symmetric setting this is just the CDH problem.
For a group element g, we write hgi to mean some canonical encoding of g as a bit string of
the appropriate length. We write hgin to mean the first n bits of hgi. We use the shorthand ~u(resp. w)~ to mean a list of group elements u1 , . . . , un (resp. w1 , . . . , wn ). Let tE , tψ , and te be
the maximum times to compute an exponentiation in G1 , compute ψ on an element in G2 , andcompute the pairing.
Signature schemes. A signature scheme S = (Pg, Kg, Sign, Ver) consists of an parameter generation algorithm, a key generation algorithm, a signing algorithm that outputs a signature given
a secret key and a message, and a verification algorithm that outputs a bit given a public key,
message, and signature. If Pg is omitted, this means there are no public parameters requiring
trusted setup; in this case the implicit Pg algorithm just outputs an empty string. We requirethat Ver(pk, M, Sign(sk, M )) = 1 for all allowed M and valid pk, sk. Following [18], we define theadvantage of an adversary A in forging against S in a chosen message attack as"#$(pk, sk) ← Kg;
uf
AdvS (A) = Pr Ver(pk, M, σ) = 1 :$(M, σ) ← ASign(sk,·) (pk)
where the probability is over the coins used by Kg, Sign, and A. We only consider adversaries that
output forgeries on a message M which was not queried to the oracle.

3

The Registered Key Model

Key registration protocols. Let P and S be sets and K ⊆ P × S be a relation on the sets
(representing public keys, secret keys, and valid key pairs, respectively). A key registration protocol
is a pair of interactive algorithms (RegP, RegV). A party registering a key runs RegP with inputs
pk ∈ P and sk ∈ S. A certifying authority (CA) runs RegV. We restrict our attention (without
loss of generality) to protocols in which the last message is from RegV to RegP and contains eithera pk ∈ P or a distinguished symbol ⊥. We require that running RegP(pk, sk) with RegV results in
RegV’s final message being pk whenever (pk, sk) ∈ K.
We give several examples of key registration protocols. The plain registration protocol Plain =(PlainP, PlainV) has the registrant running PlainP(pk, sk) send pk to the CA. The CA running

6

PlainV, upon receiving a public key pk, simply replies with pk. This protocol will be used tocapture the plain model, where no checks on public keys are performed by a CA. To model the
KOSK assumption, we specify the registration protocol Kosk = (KoskP, KoskV). Here KoskP(pk, sk)
sends (pk, sk) to the CA. Upon receiving (pk, sk), the KoskV algorithm checks that (pk, sk) ∈ K.
(We assume that such a check is efficiently computable; this is the case for key pairs we consider.)If so, it replies with pk and otherwise with ⊥.
We refer to registration protocols that utilize the key’s intended functionality as proof-ofpossession based. For example, let S = (Kg, Sign, Ver) be a signature scheme. Define the registration
protocol S-Pop = (PopP, PopV) as follows. Running PopP on inputs pk, sk results in sending themessage pk || Sign(sk, hpki) to the CA. Upon receiving message pk || σ, a CA running PopV replies
with pk if Ver(pk, hpki, σ) = 1 and otherwise replies with ⊥. This corresponds to the simplest POPs
for signature schemes specified in PKCS#10 and RFCs 4210/4211.
The registered key model. We consider security definitions that are captured by a gamebetween an adversary and an environment. To lift such security definitions to the registered key
model, we use the following general approach. Adversaries are given an additional key registration oracle OKReg that, once invoked, runs a new instance of RegV for some key registration
protocol (RegP, RegV). If the last message from RegV is a public key pk, then pk is added to atable R. This table can now be used to modify winning conditions or restrict which public keys
are utilized by the adversary in interactions with the environment. Security of schemes under the
new definition is therefore always with respect to some registration protocol.
The key registration protocols mentioned so far are two round protocols: the registrant sends
a first message to the CA, which replies with a second message being either pk or ⊥. For any tworound protocol Reg = (RegP, RegV), the OKReg oracle can be simplified as follows. An adversary
queries with a first message, at which point RegP is immediately run and supplied with the message.
The oracle halts RegP before it sends its reply message. The message is added to R if it is not ⊥.
The oracle finally returns pk or ⊥ appropriately.

4

Multisignatures using POPs

The goal of a multisignature scheme is for a group of parties, each with its own public and secretkeys, to jointly create a compact signature on some message. Following the formulation in [7], amultisignature scheme is a tuple of algorithms MS = (MPg, MKg, MSign, MVf). A trusted central
authority runs the parameter generation algorithm MPg to create a parameter string par that is
published globally. The key generation algorithm MKg, independently run by each party, outputs
a key pair (pk, sk). The MSign interactive protocol is run by some group of players. Each party
locally runs MSign on input being a secret key sk, a multiset of public keys V, and a message M . It
may consist of multiple rounds, though the protocols we consider here only require a single round:a request broadcast to all parties and the response(s). Finally, the verification algorithm MVf takes
as input a tuple (V, M, σ), where V is a multiset of public keys, M is a message, and σ is a signature,and returns a bit. We require that MVf(V, M, MSign(sk, V, M )) = 1 for any M and where every
participant correctly follows the algorithms. For schemes that do not require any trusted setup,
we write the scheme as just a triple of algorithms (MKg, MSign, MVf) where the now implicit MPg
algorithm returns an empty string.
Multisignature security. Let MS = (MPg, MKg, MSign, MVf) be a multisignature scheme,
Reg = (RegP, RegV) be a key registration protocol, and A be an adversary. Figure 1 displays
the security game Expmsuf-kr
MS,Reg (A). The experiment simulates one honest player with public key
pk ∗ . The goal of the adversary is to produce a multisignature forgery: a tuple (V, M, σ) that7

Experiment Expmsuf-kr
MS,Reg (A)$$par ← MPg; (pk ∗ , sk ∗ ) ← MKg(par); Q ← ∅; R ← ∅Run A(par, pk ∗ ) handling oracle queries as follows∪
OMSign(V, M ), where pk ∗ ∈ V: Q ←M ; Simulate a new instance of MSign(sk ∗ , V, M ),forwarding messages to and from A appropriately.

OKReg: Simulate a new instance of algorithm RegV, forwarding messages to and∪from A. If the instance’s final message is pk 6= ⊥, then R ←pk.
A halts with output (V, M, σ)
If ( pk ∗ ∈ V ) ∧ ( M ∈/ Q ) ∧ ( MVf(V, M, σ) = 1 ) ∧ ( (V − {pk ∗ }) \ R = ∅ ) thenReturn 1
Return 0
Figure 1: Multisignature security experiment in the registered key model.
satisfies the following four conditions. First, the honest public key pk ∗ is in the multiset V atleast once. Second, the message M was not queried to the multisignature oracle. Third, thesignature verifies. Fourth, each public key in V − {pk ∗ } must be in R, where V − {pk ∗ } means themultiset V with one occurrence of the honest key removed. We define the msuf-kr-advantage ofan adversary A against
multisignature scheme MS with respect to registration protocol Reg as
 a msuf-kr
msuf-kr
AdvMS,Reg (A) = Pr ExpMS,Reg (A) ⇒ 1 . The probability is taken over the random coins used in
the course of running the experiment, including those used by A. The definitions can be lifted to
the random oracle model [8] in the natural way. It is easy to show that our definition is equivalent
to the definition in [7] when Reg = Plain and equivalent to the definition in [11] when Reg = Kosk.
An adversary A is legitimate if: (1) it only queries OMSign on a set of public keys V suchthat pk ∗ ∈ V; and (2) outputs a forgery attempt (V, M, σ) for which pk ∗ ∈ V and M ∈/ Q and(V − {pk ∗ })\R = ∅ (all adversarially-chosen keys have been previously registered). Without loss ofgenerality, we will from now on only consider legitimate adversaries.
We now prove the security of the BMS and WMS multisignature schemes relative to POP-based
protocols that differ from current standards only by use of a distinct hash function. In Section 4.3
we discuss attacks against the schemes when standardized registration protocols are utilized.

4.1

Multisignatures Based on BLS Signatures

BLS signatures and multisignatures. Let Hs : {0, 1}∗ → G1 be a random oracle and let
G1 , G2 , GT , p, g, e be pairing parameters. Boneh, Lynn, and Shacham [14] specify a signaturescheme BLS = (B-Kg, B-Sign, B-Vf). The algorithms work as follows:
B-Kg:$
sk ← Zp ; pk ← g sk
Return (pk, sk)

B-SignHs (sk, M ):Return Hs (M )sk

B-VfHs (pk, M, σ):If e(Hs (M ), pk) = e(σ, g) thenReturn 1
Return 0

The BMS = (B-MKg, B-MSign, B-MVf) multisignature scheme [11] is a simple extension of BLS
signatures. Key generation is equivalent to B-Kg. Multisignature generation for participants labeled
1, . . . , v, public keys V = {pk1 , . . . , pkv }, and a message M proceeds as follows. Each participant i$computes
Qv σi ← B-Sign(ski , M ) and broadcasts σi to all other participants. The multisignature isσ ← i=1 σi . On input V, M, σ for V = {pk1 , . . . , pkv } the verification algorithm B-MVf computes
8

Q
P K = vi=1 pki and then runs B-VfHs (P K, M, σ), returning its output. Boldyreva proved thescheme secure under the KOSK assumption [11].
The B-Pop protocol. We now specify a POP-based key registration protocol under which we
can prove BMS secure. Let Hp : {0, 1}∗ → G1 be a random oracle. Then we define the B-Pop =(B-PopP, B-PopV) protocol as follows. Algorithm B-PopP(pk, sk) sends pk || B-SignHp (sk, hpki)and algorithm B-PopV, upon receiving (pk, π) computes B-VfHp (pk, hpki, π) and if the result is 1
replies with pk and otherwise with ⊥. We point out that one can use the same random oracle(and underlying instantiating hash function) for both Hs and Hp as long as domain separation isenforced. The following theorem captures the security of BMS with respect to this key registration
protocol.
Theorem 4.1 Let Hs , Hp : {0, 1}∗ → G1 be random oracles. Let A be an msuf-kr-adversary, withrespect to the B-Pop propocol, that runs in time t, makes qh , qpop , qs , and qk queries to Hs , Hp ,the signing oracle, and the key registration oracle, and outputs a multisignature forgery on a groupof size at most v. Then there exists an adversary B such thatco-cdhAdvmsuf-kr
BMS,B-Pop (A) ≤ e(qs + 1) · Adv(G1 ,G2 ) (B)

where B runs in time at most t + O((qh + qpop + v)tE + te ).
Proof: We construct a co-CDH adversary B, which on input X ∈ G2 and h ∈ G1 utilizes alegitimate msuf-kr adversary A (with respect to the B-Pop protocol) to help it compute hx wherex = logg X. We adapt a game-playing [9] approach due to Bellare for proving the security of BLS
signatures [3]. Recall that since BMS is a single-round protocol the signing oracle simply returns
a BLS signature over the message. We make several simplifying assumptions about A that arewithout loss of generality. First, A always queries Hs (M ) before querying OMSign(M ) for any
message M . Second, A always queries Hp (hpki) before querying OKReg(pk, π) for any π. Third,
A only queries OKReg on pairs (pk, π) for which B-VfHp (pk, hpki, π) = 1.
Figure 2 details the adversary B. It first applies the isomorphism ψ to g and X and setsa counter c to zero. It runs A on input X, which is then the trusted public key of the BMS
instance A is to attack. Adversary B uses four tables, Hs , Hp , B, and P. All four are initiallyeverywhere undefined. Queries to Hs are sometimes responded to with values that include hδand sometimes not, depending on a δ-biased coin (we notate flipping such a coin by δc ←{0, 1}).
Intuitively, the δc values correspond to guessing which Hs query will correspond to the forgery
message. Adversary B responds to Hp queries with values that always include h. This is so thatthe adversarially-supplied POPs can be used to help extract the co-CDH solution from a forgery.
Queries to OKReg simply record the supplied POP in P. Eventually A halts outputing a forgery
attempt (V, M, σ). Adversary B checks if the forgery verifies and if so attempts to extract fromit the value hx . Here (X, pk1 , . . . , pkd ) ← V means parse V into the sequence of public keys
X, pk1 , . . . , pkd which enumerates all those in V. (Since A is legitimate X must be in V.) Notethat extraction of hx is only possible if the forgery message had its Hs response programmed toinclude h.
We now proceed through a sequence of games to lower bound the probability that B succeeds
in computing hx . The first game is G0, shown in Figure 2 with boxed statements omitted. It is
exactly like B except that it generates the co-CDH instance itself (first line of Initialize). The
outputs G0(A) and B are thus distributed identically. More-over, if their output is not ⊥ then it
is hx . To see this, let us fix some notation related to the variables in the Finalize procedure of G0.
Define ski = logg pki and πi = P[pki ] for each i ∈ [1 .. d]. Then ψ(pki ) = g1ski holds for each i. Define9procedure Initialize

G0

Adversary B(X, h)$x ← Zp ; X ← g x ; h ← G1

g1 ← ψ(g); X1 ← ψ(X); c ← 0
Run A(X), answering queries by

g1 ← ψ(g); X1 ← ψ(X); c ← 0
Ret X

G1

$

query Hs (M )procedure Hs (M )c ← c + 1; Mc ← M$δαc ← Zp ; δc ←{0, 1}
If δc = 1 then Hs [M ] ← g1αc
Else Hs [M ] ← hg1αc
Ret Hs [M ]c ← c + 1; Mc ← M$
δ{0, 1}αc ← Zp ; δc ←If δc = 1 then Hs [M ] ← g1αc
Else Hs [M ] ← hg1αc
Ret Hs [M ]query Hp (N )$B[N ]B[N ] ← Zp ; Ret Hp [N ] ← hg1

procedure Hp (N )query OMSign(M )procedure OMSign(M )Let k be s.t. M = Mk ; Sk ← ⊥If δk = 1 then Sk ← X1αk

Let k be s.t. M = Mk ; Sk ← ⊥If δk = 1 then Sk ← X1αkElse bad ← true
Ret SkElse bad ← true ; Sk ← Hs [M ]x
Ret Skquery OKReg(pk, π)

procedure OKReg(pk, π)

P[pk] ← π; Ret pk

P[pk] ← π; Ret pk

$

B[N ]

B[N ] ← Zp ; Ret Hp [N ] ← hg1

A finishes, outputing (V, M, σ)
If B-MVf(V, M, σ) = 0 then Ret ⊥(X, pk1 , . . . , pkd ) ← V
Let k be s.t. M = Mk ; α ← αk
For each i ∈ [1 .. d] do γi ← α − B[hpki i]w←⊥
If δk = 0 then Qw ← σX1−α di=1 (P[pki ]−1 ψ(pki )−γi )procedure Finalize(V, M, σ)
If B-MVf(V, M, σ) = 0 then Ret ⊥(X, pk1 , . . . , pkd ) ← V
Let k be s.t. M = Mk ; α ← αk
For each i ∈ [1 .. d] do γi ← α − B[hpki i]w←⊥
If δk = 0 then Qw ← σX1−α di=1 (P[pki ]−1 ψ(pki )−γi )Else bad ← true
Ret w

Else bad ← true ; w ← hx
Ret w

Figure 2: Adversary B and games G0 and G1 used in the proof of Theorem 4.1. Game G0 omits
the boxed statements while G1 includes them.
βi = α − γi = B[pki ]. Because A is legitimate we necessarily have that e(Hs [M ], P K) = e(σ, g) andthat e(Hp [hpki i], pki ) = e(πi , g) for each i ∈ [1 .. d]. Applying the properties of pairings to theseequivalences gives that σ = (hg1α )x+sk1 +...+skd and πi = (hg1βi )ski for each i ∈ [1 .. d]. Thenw = σX1−αdY
i=1πi−1 ψ(pki )−γi =(hg1α )x+sk1 +...+skdx
Q βi sk ski α−β = h .
αiiX1 · (hg1 ) (g1 )(1)Therefore we have that
Advco-cdh(G1 ,G2 ) (B) = Pr [G0(A) ; ⊥](2)

The next game is G1, shown in Figure 2 with the boxed statements included. Games G0 and G1

10

procedure Initialize

G3

$

$
x ← Zp ; X ← g x ; h ← G1 ; c ← 0

Ret X
procedure Hs (M )δ
{0, 1}c ← c + 1; Mc ← M ; δc ←$Ret Hs [M ] ← G1

procedure Hp (N )$procedure Initialize$

Ret Hp [N ] ← G1

G2$

procedure OMSign(M )x ← Zp ; X ← g x ; h ← G1 ; c ← 0
Ret X

Let k be s.t. M = Mk
If δk 6= 1 then bad ← true
Ret Hs [M ]xprocedure Hs (M )c ← c + 1; Mc ← M$δαc ← Zp ; δc ←{0, 1}
If δc = 1 then Hs [M ] ← g1αc
Else Hs [M ] ← hg1αc
Ret Hs [M ]procedure OKReg(pk, π)
P[pk] ← π; Ret pk
procedure Finalize(V, M, σ)
If B-MVf(V, M, σ) = 0 then Ret ⊥Let k be s.t. M = Mk
If δk 6= 0 then bad ← true
Ret hx

procedure Hp (N )
B[N ]

$

B[N ] ← Zp ; Ret Hp [N ] ← hg1
procedure OMSign(M )procedure Initialize

Let k be s.t. M = Mk
If δk 6= 1 then bad ← true
Ret Hs [M ]x

Ret X

procedure OKReg(pk, π)

procedure Hs (M )P[pk] ← π; Ret pk

Ret Hs [M ] ← G1

procedure Finalize(V, M, σ)procedure Hp (N )If B-MVf(V, M, σ) = 0 then Ret ⊥Let k be s.t. M = Mk
If δk 6= 0 then bad ← true
Ret hxRet Hp [N ] ← G1

G4

$

$
x ← Zp ; X ← g x ; h ← G1 ; c ← 0$$procedure OMSign(M )c ← c + 1; Ret Hs [M ]xprocedure OKReg(pk, π)
P[pk] ← π; Ret pk
procedure Finalize(V, M, σ)
If B-MVf(V, M, σ) = 0 then Ret ⊥For each j ∈ [1 .. c] doδδj ←{0, 1}; If δj = 0 then bad ← trueδ
δj+1 ←{0, 1}; If δj+1 = 1 then bad ← true
Ret hxFigure 3: Games G2 and G3 used in the proof of Theorem 4.1.

11

are identical-until-bad. Let Goodi be the event that Gi(A) does not set bad. Then by a variant [6]of the fundamental lemma of game-playing [9] we have thatPr [G0(A) ; ⊥] ≥ Pr [G0(A) ; ⊥ ∧ Good0 ] = Pr [G1(A) ; ⊥ ∧ Good1 ] .

(3)In game G1 note that signing queries always return Hs [M ]x . This is true because
X1αk = ψ(g x )αk = (g1x )αk = (g1αk )x = Hs [M ]x .
(4)xAdditionally Finalize, as per (1), always returns h if A’s forgery verifies. Game G2 rewrites
OMSign and Finalize to make these facts explicit, and also omits computing g1 and X1 which
are no longer needed. We have thatPr [G1(A) ; ⊥ ∧ Good1 ] = Pr [G2(A) ; ⊥ ∧ Good2 ] .

(5)In game G2 all uses of hash range points are via Hs [M ] and Hp [M ] (i.e., we no longer utilize
the special structure of the range points). Game G3 therefore dispenses with the special way inwhich Hs and Hp choose range points, now choosing them directly at random from G1 . In both G2and G3 the range points have the same (uniform) distribution, meaning that the code is equivalentand thus
Pr [G2(A) ; ⊥ ∧ Good2 ] = Pr [G3(A) ; ⊥ ∧ Good3 ] .

(6)

In G3 the setting of bad does not impact any other random variables in the game, and so in game G4
we defer its setting until Finalize. Furthermore, not all of the δ values can actually set bad: only
those that end up being referenced during signing queries and the one extra for the forgery. Thus
G4 moves incrementing the counter c to signing queries, and in Finalize only performs δ-biased
coin tosses c + 1 times: one for each signature query and one for the forgery. This justifies thatPr [G3(A) ; ⊥ ∧ Good3 ] = Pr [G4(A) ; ⊥ ∧ Good4 ] .

(7)In game G4, the event G4(A) ; ⊥ and the event Good4 are independent. This is because theevents do not rely on any shared random variables. The variable c is in fact not a random variable,
because it will always equal qs , the number of signing queries A uses. This justifies thatPr [G4(A) ; ⊥ ∧ Good4 ] = Pr [G4(A) ; ⊥]·Pr [Good4 ] .

(8)where Pr [Good4 ] ≥ (e(qs + 1))−1 (this is standard, see e.g. [6, 15]). Finally, G4 exactly simulates
for A the ruf3-kr experiment, meaning
i
h
(A)
⇒
1
= Advruf3-kr
Pr [G4(A) ; ⊥] = Pr Expruf3-kr(9)
BMS,B-Pop (A)BMS,B-Pop
Combining (2), (3), (5), (6), (7), (8), (9), and the lower bound on Pr [Good4 ] yields
1
Advruf3-kr
Advco-cdh
BMS,B-Pop (A)(G1 ,G2 ) (B) ≥e(qs + 1)
which implies the theorem statement.
Adversary B runs A. Additionally B must perform an exponentiation for each Hs and Hp queryand one for each key in the forgery set V. Finally B must perform a pairing to verify the forgery.
Thus B runs in time at most t + O((qh + qpop + v)tE + te ) where |V| = v.

4.2

Multisignatures Based on Waters Signatures

Waters signatures and multisignatures. Let G1 , G2 , GT , p, g, e be pairing parameters. We
define the signature scheme W = (W-Pg, W-Kg, W-Sign, W-Vf), as given in [28] and which is aslight variant of the original Waters signature scheme in [39]. The parameter generation algorithm$
W-Pg selects values h, u, u1 , . . . , un ← Gn+2
and publishes them globally. The other algorithms are
1
defined below.

12

W-Kg

W-SignHu,~u (sk, M )$r ← Zp ; ρ ← g r
σ ← sk · Hu,~u (M )rReturn (σ, ρ)α ← Zppk ← g α ; sk ← hα
Return (pk, sk)

W-VfHu,~u (pk, M, (σ, ρ))$If e(h, pk) · e(Hu,~u (M ), ρ) = e(σ, g) thenReturn 1
Return 0Q
M [i]The function Hu,~u : {0, 1}n → G1 is defined by Hu,~u (M ) = u · ni=1 ui
for any u, ~u ∈ Gn+1.
1n
For simplicity the message space as defined is restricted to {0, 1} , but in practice one can use acollision-resistant hash function to expand the domain.
The WMS = (W-Pg, W-MKg, W-MSign, W-MVf) multisignature scheme [28] is a straightforward
extension of the Waters’ signature scheme. Parameter generation and key generation are the sameas in W. To generate a multisignature for multiset V = {pk1 , . . . , pkv }, each participant i computes
QQ$(σi , ρi ) ← W-SignHu,~u (ski , M ) and broadcasts (σi , ρi ). The multisignature is ( vi=1 σi , vi=1 ρi ).
To verify
M and public keys V = {pk1 , . . . , pkv }, simply let
Qav multisignature (σ, ρ) for a messageHu,~u
P K ← i=1 pki and then return W-Vf
(P K, M, (σ, ρ)). This scheme was proven secure using
the KOSK assumption in [28].
$The WM-Pop protocol. Let w, w1 , . . . , wn ← Gn+1
be global parameters with associated hash1function Hw,w~ . These parameters require trusted setup, particularly because the CA should notknow their discrete logs. (One might therefore have the trusted party that runs W-Pg also generatew, w.)~ We define the following key registration protocol WM-Pop = (WM-PopP, WM-PopV): Algorithm WM-PopP takes as input (pk, sk) and sends pk || (π, $) where (π, $) = W-SignHw,w~ (sk, hpkin ).
Algorithm WM-PopV receives pk || (π, $) and then runs W-VfHw,w~ (pk, hpkin , (π, $)) and if the result is 1, replies with pk and else replies with ⊥. The following theorem combined with [28, Theorem2] (security of WMS under the KOSK assumption) establishes the security of WMS under WM-Pop.
Theorem 4.2 Let A be an msuf-kr-adversary, with respect to the WM-Pop protocol, that runs intime t, makes qs multisignature queries, qk registration queries, and outputs a forgery for a groupof size at most v. Then there exists an adversary B such thatmsuf-kr
Advmsuf-kr
WMS,WM-Pop (A) ≤ AdvWMS,Kosk (B)and where B runs in time t + O(ntE + (tE + tψ )qk ) and makes qs signature queries.
Proof: Let A be a legitimate adversary against WMS. Like in the proof for BMS, we note that forthe scheme WMS, a multisignature session oracle is equivalent to a Waters signature signing oracle
for the trusted party. We therefore deal with the latter, which is simpler.
We wish to construct an adversary B which uses A to create a forgery against the WMS multisignature scheme with the Kosk key registration protocol. Adversary B will receive as input
system parameters (h, g, u, u1 , . . . , um ) and target public key pk ∗ , where h is a generator of G1 ,u, u1 , . . . , um are all elements of G1 , g is a generator of G2 , and pk ∗ = g α for some random α ∈ Zp .
The adversary is also given a signing oracle OMSign-B and a key registration oracle OKReg-B.
Its goal is to produce a valid multisignature forgery which verifies under some set of keys that
includes pk ∗ . Since A is an adversary against WMS with WM-Pop key registration, it must takeadditional input w, w
~ (for key registration) and B must simulate for it a signing oracle OMSign-A
and a key registration oracle OKReg-A. The adversary B operates as follows:• Let g1 = ψ(g). Choose z, z1 , . . . , zn ← Zn+1
and let (w, w1 , . . . , wn ) ← (g1z , g1z1 , . . . , g1zn ). Choosep$$s ← Zp . Run the WMS multisignature adversary A on input pk = pk ∗ , par = (h, g, u, ~u, w, w).
~
13• On oracle query OMSign-A(Mi ) from A, query OMSign-B(Mi ). Upon receiving a signature(σi , ρi ), forward it back to A.
• When A queries OKReg-A(pki , (πi , $i )), let ski ← πi /ψ($i )z+
OKReg-B(pki , ski ).

Pn

j=1 zj ·hpki i[j]. Then query• When A outputs an attempted forgery (V, M, (σ, ρ)), output (V, M, (σ, ρ)).
We now show that whenever A forges against the WMS multisignature scheme with WM-Pop key
registration, B forges against the WMS mulsignature scheme with Kosk key registration (WMS wasproven secure under the KOSK assumption in [28]). To do this we first claim that B perfectly
simulates the environment for A. This is clear since the public key and system parameters given to
A directly correspond to the public key and parameters given to B (namely h, g, u, u1 , . . . , un ) andthus the sign oracle provided by B is correct. Since B forwards all of A’s sign oracle queries to theenvironment and B makes no other sign oracle queries, it is also clear that if A did not query its
forgery message to the sign oracle provided by B, then B also did not query its sign oracle on thatmessage. Lastly, we show that every time A sends a valid POP to the registration oracle provided
by B, B is able to ‘extract’ the secret key to send to its own Kosk registration oracle. To see thisrecall that a valid POP (πi , $i ) for key pki is such thate(h, pki ) · e(Hw,w~ (hpki in ), $i ) = e(πi , g).

(10)

Also, note that (pki , ski ) is a valid key pair if and only ife(ski , g) = e(h, pki ).

(11)Now, rearranging equation 10:e(h, pki ) ==e(πi , g)e(Hw,w~ (hpki in ), $i )e(πi , g)
z+
e(g1

Pn

j=1 zj hpki i[j], $i )e(πi , g)=z+e(ψ($i )Pn

j=1 zj hpki i[j]= e(πi · (ψ($i )z+

Pn

, g)

j=1 zj hpki i[j])−1 , g)= e(ski , g)which from equation 11 means that (pki , ski ) is a valid key pair. This shows that each timeadversary A is able to register a key, B is able to ‘extract’ the corresponding secret key and use it
for KOSK key registration.
Now, whenever A forges, it must have properly registered the keys used in the forgery. Since wejust showed that a proper key registration by A equates to a proper key registration for B, it follows
that whenever A forges, B also forges. So,
msuf-kr
Advmsuf-kr
WMS,WM-Pop (A) ≤ AdvWMS,Kosk (B).

In addition to running A, B must must perform one isomorphism and n + 1 exponentiations
before starting A, plus qk isomorphisms and qk exponentiations. Thus the running time of B ist + O(ntE + (tE + tψ ) · qk ) where t is the running time of A.

14

4.3

Attacks against Standardized Key Registration Protocols

We show how the standardized proof-of-possession based key registration protocols (as per PKCS#10[35] and RFCs 4210/4211 [1, 36]) fail to prevent rogue key attacks. Let BadPop = (BadP, BadV) be
the standardized key registration protocol for BMS and let the algorithms be as follows: Algorithm
BadP, on input (pk, sk) sends pk || B-SignH (sk, hpki) and algorithm BadV, upon receiving (pk, π),runs B-VfH (pk, hpki, π) and replies with pk if the result is 1 and ⊥ otherwise. Here H is the samehash function as used in B-MSign and B-MVf.
We define a simple msuf-kr adversary A that successfully mounts a rogue-key attack against BMS
with respect to the BadPop registration protocol. Adversary A gets the honest party’s public key pk ∗∗∗$which is equal to g sk . It then chooses s ← Zp . Its public key is set to pk = g s /pk ∗ = g s−sk . The
forgery on any message M and multiset {pk ∗ , pk} is simply H(M )s , which clearly verifies under thetwo public keys given. Now to register its key, the adversary makes the query OMSign({pk ∗ }, hpki),∗
receiving σ = H(hpki)sk . Then A sets π ← H(hpki)s /σ and registers with pk || π. It is easy to seethat this verifies, and thus A can always output a multisignature forgery: its msuf-kr advantage isone.
An analogous key registration protocol could be defined for WMS, and again a simple attack
shows its insecurity. Both approaches fall to attacks because the signatures used for key registration and normal multisignatures are calculated in the same manner. This motivated our simple
deviations from standardized registration protocols for the B-Pop and WM-Pop protocols.

4.4

Other POP Variants

Another class of POP-based registration protocols for signature schemes has the CA send a randomchallenge to the registrant. The registrant must then supply a signature over the challenge message.
Our results also apply to such protocols.
We first show that requiring a signature over a random challenge has the exact same pitfalls as
requiring a signature of the key being registered. Let BadRCPop = (BadRCP, BadRCV) be a randomchallenge key registration protocol for BMS with its algorithms as follows: algorithm BadRCP, on
input (pk, sk) sends pk to the CA; algorithm BadRCV receives pk and replies with a random stringc ∈ {0, 1}n ; BadRCP receives c and replies with π = B-SignH (sk, c); finally BadRCV receives πand outputs pk if B-VfH (pk, c, π) = 1 and ⊥ otherwise. Hash function H is the same one used in
B-MSign and B-MVf.
As before, there is a simple msuf-kr adversary A that can mount a rogue-key attack against
BMS with this registration protocol. Adversary A gets the honest party’s public key pk ∗ which is∗∗$equal to g sk . It then chooses s ← Zp . Its public key is set to pk = g s /pk ∗ = g s−sk . The forgery
on any message M and multiset {pk ∗ , pk} is simply H(M )s . To register its key, the adversary
must sign some random challenge c with the rogue key. To do this, the adversary, upon receiving∗c, makes the query OMSign({pk ∗ }, c) and receives σ = H(c)sk . Then A sets π ← H(c)s /σ andsends π as its response.
To prevent the attack above, we again can use a distinct hash function for signing and key
registration. To adapt the proof of Theorem 4.1 to the setting with random challenge key registration, the adversary B simply needs to compute γi ← α − B[ci ], where ci is the random challenge
given when pki was registered. The rest of the proof is the same. The proof of Theorem 4.2 canbe similarly modified. The reason that this works is that the proof of security does not depend on
the choice of string signed in the proof of possession, as long as the string is known to the CA.

15

Experiment Expranon-ind-b(A)RS$
par ← RPg
Run A(par) handling oracle queries as follows
ORSignLR(S, V, M ), where S = (sk0 , sk1 ); V = pk0 , . . . , pkv−1 ; (pk0 , sk0 ), (pk1 , sk1 ) valid:
Ret RSignskb (V, M )A outputs b0
Ret b0Figure 4: Ring signature anonymity experiment.

5

Ring Signatures in the Registered Key Model

A ring signature scheme RS = (RPg, RKg, RSign, RVf) consists of four algorithms. The parameter
generation algorithm generates a parameter string par, which is published globally. The key generation algorithm RKg outputs a key pair (pk, sk). The algorithm RSignsk (V, M ) ≡ RSign(sk, V, M )generates a ring signature on input a secret key sk, a message M, and a multiset of public keys V
such that there exists pk ∈ V for which (pk, sk) is a valid key pair. We further assume that |V| ≥ 2.
Note that we do not require that all elements in V be distinct.1 Lastly the verification algorithm
RVf(V, M, σ) outputs a bit. We require that RVf(V, M, RSignsk (V, M )) = 1 for any message M ,any valid multiset of public keys, and for any valid sk with a pk ∈ V. Ring signatures that only
allow rings of size exactly κ are called κ-user ring signatures.

5.1

Ring Signature Definitions

New anonymity definition. We propose a stronger definition of anonymity than those given by
Bender et al. [10]. Intuitively, our definition requires that no adversary should be able to tell whatsecret key was used to generate a ring signature, even if the adversary itself chooses the secret keys
involved. Formally, let A be an adversary and RS = (RPg, RKg, RSign, RVf) be a ring signaturescheme. Then we define the ranon-ind advantage of an adversary A byhihi
Advranon-ind(A) = Pr Expranon-ind-0(A) ⇒ 1 − Pr Expranon-ind-1(A) ⇒ 1
RS
RS
RS
where the experiment Expranon-ind-b(A) is defined in Figure 4. We say a scheme is perfectly r-anonRS
ind anonymous if the advantage of any adversary is zero.
The ranon-ind definition is stronger than the strongest definition given in [10] (see Appendix A
for details). Even so, it is easy to see that (for example) both of the 2-user ring signature schemes
from [10] meet it, and are, in fact, perfectly ranon-ind anonymous.
Unforgeability definitions. We expand the unforgeability definitions given in [10], drawing a
distinction between attacks where honest parties can be corrupted and rogue-key attacks (where
the adversary can choose public keys). We also lift the strongest unforgeability definition to theregistered key model. Fix some number η, representing the number of trusted potential honest
signers. Let RS = (RPg, RKg, RSign, RVf) be a ring signature scheme and Reg = (RegP, RegV) be aregistration protocol. Then we define the advantages
1
This generalizes previous treatments, e.g. [10]. While a ring signature over a ring with duplicates is equivalentsemantically to one over a ring with all duplicates removed, there is no intrinsic reason not to allow duplicates, andthus we would like definitions to capture this generalization. Of course a particular scheme could require distinct
public keys, for example by removing duplicates before signing.

16

Experiment Expruf3-kr
RS,Reg (A)$$par ← RPg; For i = 1 to η do (pki , ski ) ← RKg(par)Q ← C ← R ← ∅; S ← {pki | i ∈ {1, . . . , η}}
Run A(par, (pki )η1 ) handling oracle queries as follows
ORSign(s, V, M ), where s ∈ [1 .. η] and pks ∈ V:∪
Q←
(V, M ); If ( V \ S ) \ R 6= ∅ then Ret ⊥Ret RSignsks (V, M )∪OCorrupt(i), where i ∈ [1 .. η]: C ←i; Ret ski
OKReg: Simulate a new instance of algorithm RegV, forwarding messages to and∪from A. If the instance’s last message is pk 6= ⊥, then R ←pk.
A outputs (P, M, σ)
V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 ∧ ( (V, M ) ∈/ Q ) ∧ ( P ∩ C = ∅ ) ∧ ( P \{1, . . . , η} = ∅ ) then Ret 1
Ret 0

Figure 5: Ring signature unforgeability experiment in the registered key model. The ruf2 experiment is derived by omitting the OKReg oracle. The ruf1 experiment is derived by omitting both
the OKReg and OCorrupt oracles.
ruf3-kr• Advruf3-kr
RS,Reg (A) = Pr[ExpRS,Reg (A) ⇒ 1] (rogue-key attacks, equivalent to Definition 7 in [10]when Reg = Plain)
ruf2• Advruf2
RS (A) = Pr[ExpRS (A) ⇒ 1] (corruption attacks, similar to a definition in [21])ruf1• Advruf1
RS (A) = Pr[ExpRS (A) ⇒ 1] (chosen subring attacks, Definition 6 in [10])where the Expruf3-kr
RS,Reg (A) experiment is defined in Figure 5 and the others are as follows. Experiment
ruf2
ExpRS (A) is defined by the experiment in Figure 5 except with the OKReg oracle omitted.
Experiment Expruf1
RS (A) is defined by the experiment in Figure 5 except both the OCorrupt and
OKReg oracles are omitted. Note that we have not excluded the possibility that duplicate publickeys are generated by the experiment2 , and in particular V and S might both be multisets in theexperiments. (This better reflects the independent nature of key generation by users, who cannot
necessarily be trusted to ensure all public keys generated are unique.) On the other hand, P must
not have duplicates.
We also define a variant of the ruf3-kr security definition, which pertains to fixed-ring adversaries. These are adversaries which must forge against some ring of public keys selected by theenvironment. Let ν ≥ 2 and assume that RS supports rings of size ν. Define the experimentruf3-kr
Expruf3-kr-fr
RS,Reg (A) by the code for ExpRS,Reg (A) in Figure 5 except with the following changes: η iseverywhere replaced by ν; the forgery output (P, M, σ) must have P = {1, . . . , ν}; and the (nowuseless) OCorrupt oracle is omitted. We define the ruf3-kr-fr advantage of an adversary A by
ruf3-kr-fr• Advruf3-kr-fr
RS,Reg (A) = Pr ExpRS,Reg (A) ⇒ 1
For κ-user schemes necessarily ν = κ. Note that in [10] a similar fixed-ring definition is given, but
it does not allow rogue-keys attacks.
An adversary A is legitimate if: (1) all queries to ORSign(s, V, M ) are such that s ∈ {1, . . . , η};pks ∈ V; and (V \S)\R = ∅; (2) all queries to OCorrupt(i) are such that i ∈ {1, . . . , η} and A never2
This formalization implies that for a scheme to be secure against ruf2 and ruf3-kr adversaries, it must ensurethat honestly generated keys are duplicates only with low probability. If there exists pki = pkj for i 6= j then suchan adversary can simply corrupt i and then forge against j and some other party using ski .

17

repeats a query i to OCorrupt; and (3) A only outputs tuples (P, M, σ) for which P\{1, . . . , η} = ∅(all indices in P are distinct and in the range [1 .. η]) and P ∩ C = ∅ and (V, M ) ∈/ Q. Without lossof generality, we will from now on only consider legitimate adversaries.

5.2

Unforgeability Implications for κ-user Schemes

In this section we focus on κ-user ring signature schemes, giving two results. The first is thatfor κ-user ring signatures meeting the ranon-ind anonymity definition, security against corruption
attacks is implied by security against chosen subring attacks. This shows that (for these schemes)
the ability to corrupt parties offers little benefit to adversaries. The second result shows that κuser schemes secure against fixed-ring rogue-key attacks are also secure against general rogue-key
attacks. Both results will be useful for establishing the security of schemes against rogue-key attacks
when key registration protocols are utilized (as discussed in the next two sections). Additionally,
the lemmas could be of independent interest.
Corruptions don’t help. We now state and prove a lemma which states that the ability tocorrupt parties is of limited usefulness to adversaries attacking κ-user ring signature schemes.
Lemma 5.1 Let RS = (RPg, RKg, RSign, RVf) be a κ-user ring signature scheme. Let η ≥ κ. and
let A be an ruf2 adversary that makes at most qs signature queries, at most qc corruption queries,
and runs in time at most t. Then there exist adversaries Ba and Bu such that
 
 
η
η
ranon-ind
ruf2
Advruf1(Ba ) +AdvRS
AdvRS (A) ≤RS (Bu )κκwhere Ba and Bu uses at most qs queries and run in time at most t + O(qc + (qs + η + 1)Time(RS)).
Proof: Let A be a legitimate ruf2 adversary. We build a legitimate ruf1 adversary Bu that uses A.
See Figure 6. The adversary Bu is given inputs a parameter string and set of honestly-generated
public keys and access to a signing oracle denoted by ORSign-1. Recall that this oracle, whichcorresponds to the ruf1 experiment, does not allow queries on adversarially-generated public keys.
Adversary Bu first selects a set of indices K that represent its guess of which parties will not be
corrupted by A. Then, a new set of keys is generated by Bu . For every index in K the real key
is used. For all others, Bu generates its own public key, secret key pair. Adversary A is run using
the resulting multiset of public keys. (A is given a sequence of keys such that the ith key in thesequence corresponds to pki ). Signing queries ORSign-2(s, V, M ) from A are simulated in one of
two ways. If the keys in V correspond to the guessed subset, then Bu utilizes its own oracle torespond. Otherwise, one of the keys that Bu generated itself is used to answer the query. The
statement “Let j ∈ [1 .. η]\K be s.t. pkj ∈ V” means find a (e.g., the first) key pkj that is bothin V and in the set of public keys generated by Bu . For corruption queries, if the index queried
is not in K then the appropriate secret key is returned (in this case B generated the key itself).
Otherwise ⊥ is returned. Note that by the legitimacy of A and the manner in which signing queries
are handled Bu is also legitimate.
We now proceed through a game-playing sequence to lower bound the advantage of Bu in termsof the advantage of A and, as we’ll see, an ranon-ind adversary Ba . Game G0 represents the first
game, see Figure 6. It is equivalent to the adversary Bu except that it generates the parameter
string and honest public keys itself and answers ORSign queries for the chosen set of public keys
directly. Since the outputs of G0 and Bu are distributed equivalently and Bu forges anytime itdoesn’t output ⊥, we have
Advruf1
RS (Bu ) = Pr [G0(A) ; ⊥] .
18

(12)

procedure Initialize
Adversary Bu (par, (pki )η1 ):G0$

par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)$K ← Pκ ({1 .. η})
For i = 1 to η do
If i ∈/ K then (pki0 , ski0 ) ← RKg(par)Else pki0 ← pki
T ← {pki | i ∈ K}
Ret (par, (pki0 )η1 )$K ← Pκ ({1 .. η})
For i = 1 to η do
If i ∈/ K then (pki0 , ski0 ) ← RKg(par)Else pki0 ← pki
T ← {pki | i ∈ K}
Run A(par, (pki0 )η1 ), answering queries by:query ORSign-2(s, V, M )If V = T then Ret ORSign-1(s, V, M )Let j ∈ {1 .. η}\K be s.t. pkj ∈ V
Ret RSignskj0 (V, M )procedure ORSign-2(s, V, M )If V = T then Ret RSignsks (V, M )Let j ∈ {1 .. η}\K be s.t. pkj ∈ V
Ret RSignskj0 (V, M )query OCorrupt(i)sk ← ⊥
If i ∈/ K then sk ← ski0
Else bad ← true
Ret skprocedure OCorrupt(i)sk ← ⊥
If i ∈/ K then sk ← ski0
Else bad ← true
Ret skA finishes, outputing (P, M, σ)
If P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 thenIf bad 6= true then φ ← (P, M, σ)Ret φprocedure Finalize(P, M, σ)
If P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 thenIf bad 6= true then φ ← (P, M, σ)Ret φFigure 6: Adversary Bu and game G0 used in proof of Lemma 5.1.
Game G1 is shown in Figure 7. It is the same as G0 except that we simplify the initialization
procedure to just pick one set of η key pairs. The view of the adversary is equivalent, since all keys
are distributed as before. Thus
Pr [G0(A) ; ⊥] = Pr [G1(A) ; ⊥] .

(13)

Game G2 modifies the ORSign procedure of G1: in all cases the secret key associated with theindex s is used to answer the response. Otherwise the games are identical. To bound the loss
incurred by this game transition, we build an ranon-ind adversary Ba . This adversary will haveadvantage related to the ability of A to force the output of G1(A) to differ from the output of G2(A).
Figure 7 depicts the adversary. It utilizes its ORSignLR oracle to help answer A’s ORSign-2
queries and returns a one whenever A’s forgery is successful and bad is not set. We have thathihiranon-ind-1
ranon-ind-0
Advranon-ind
(B
)
=
Pr
Exp
(B
)⇒1
−
Pr
Exp
(B
)⇒1
.
(14)
a
a
a
RS
RS
RS
Note that if Ba is run in the ranon-ind-1 experiment, then the secret key sks is always utilized
to answer Ba ’s oracle queries.
Thus Ba returns
 a one whenever G2(A) does not output ⊥,and so we have that Pr Expranon-ind-1(B)⇒
1= Pr [G2(A) ; ⊥]. Similarly, if Ba is run inaRSthe ranon-ind-0 experiment, then the secret key skj is always used to answer Ba ’s queries. So
Pr Expranon-ind-0(B)⇒
1= Pr [G1(A) ; ⊥]. Substituting back into (14) and re-arranging we
a
RS

19

procedure Initialize

G1, G2$par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)$K ← Pκ ({1 .. η})T ← {pki | i ∈ K}
Ret (par, (pki )η1 )procedure ORSign-2(s, V, M )Adversary Ba (par):$par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)$K ← Pκ ({[1 .. η})T ← {pki | i ∈ K}
Run A(par, (pki )η1 ), answering queries by:

G1

If V = T then Ret RSignsks (V, M )Let j ∈ {1 .. η}\K be s.t. pkj ∈ V
Ret RSignskj (V, M )procedure OCorrupt(i)sk ← ⊥
If i ∈/ K then sk ← ski
Else bad ← true
Ret sk

G1, G2

procedure Finalize(P, M, σ)

G1, G2

query ORSign-2(s, V, M )If V = T then Ret RSignsks (V, M )Let j ∈ {1 .. η}\K be s.t. pkj ∈ V
Ret ORSignLR({skj , sks }, V, M )query OCorrupt(i)sk ← ⊥
If i ∈/ K then sk ← ski
Else bad ← true
Ret skIf P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 thenIf bad 6= true then φ ← (P, M, σ)Ret φprocedure ORSign-2(s, V, M )A halts with output (P, M, σ)
If P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 thenIf bad 6= true then φ ← (P, M, σ)
If φ 6= ⊥ then Ret 1
Ret 0

G2

If V = T then Ret RSignsks (V, M )Let j ∈ {1 .. η}\K be s.t. pkj ∈ V
Ret RSignsks (V, M )Figure 7: Games G1 and G2 and adversary Ba used in the proof of Lemma 5.1. Game G2 utilizes
the same Initialize, OCorrupt, and Finalize procedures as G1.
have thatPr [G1(A) ; ⊥] = Pr [G2(A) ; ⊥] − Advranon-ind(Ba ) .
RS

(15)

Game G3 (Figure 8, boxed statements omitted) simplifies the ORSign-2 oracle: the code is different but it implements the same functionality as in G2. As a result of this change, the game nolonger requires T , thus we omit it from Initialize.
Pr [G2(A) ; ⊥] = Pr [G3(A) ; ⊥] .

(16)

Let Goodi be the event that Gi(A) does not set bad. Then we have by (16) thatPr [G2(A) ; ⊥] = Pr [G3(A) ; ⊥] ≥ Pr [G3(A) ; ⊥ ∧ Good3 ] .
Game G4 includes the boxed statements, which assist it in answering ORSign-2 queries and ensurethat G4 only outputs ⊥ if A failed to produce a valid forgery. Games G3 and G4 are identicaluntil-bad. By a variant [6] of the fundamental lemma of game-playing [9] we have thatPr [G3(A) ; ⊥ ∧ Good3 ] = Pr [G4(A) ; ⊥ ∧ Good4 ] .

20

(17)

procedure Initialize

G3

G4

$

par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)$K ← Pκ ({1 .. η})
Ret (par, (pki )η1 )procedure Initialize

G5$par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)$K ← Pκ ({1 .. η})
Ret (par, (pki )η1 )procedure ORSign-2(s, V, M )Ret RSignsks (V, M )procedure ORSign-2(s, V, M )procedure OCorrupt(i)sk ← ⊥
If i ∈/ K then sk ← ski
Else bad ← true ; sk ← ski
Ret skRet RSignsks (V, M )procedure Finalize(P, M, σ)procedure Finalize(P, M, σ)

If P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 thenIf bad 6= true then φ ← (P, M, σ)Else φ ← (P, M, σ)Ret φ

If P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 then φ ← (P, M, σ)Ret φprocedure OCorrupt(i)If i ∈ K then bad ← true
Ret skiprocedure Initialize

G6$par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)Ret (par, (pki )η1 )procedure ORSign-2(s, V, M )Ret RSignsks (V, M )procedure OCorrupt(i)Ret skiprocedure Finalize(P, M, σ)$

K ← Pκ ({1 .. η})
If P =
6 K then bad ← trueφ ← ⊥; V ← {pki | i ∈ P}
If RVf(V, M, σ) = 1 then φ ← (P, M, σ)Ret φFigure 8: Games G3, G4, G5, and G6 used in the proof of Lemma 5.1. Game G3 does not include
the boxed statements, while G4 includes them.

21

Game G5 simplifies G4 in light of always answering corruption queries and always outputing a
successful forgery by A. These changes do not change the implemented functionality of procedures
OCorrupt and Finalize, so Pr [G4(A) ; ⊥ ∧ Good4 ] = Pr [G5(A) ; ⊥ ∧ Good5 ]. Note that ingame G5 anytime bad is set within OCorrupt, necessarily P =6 K during Finalize. This is because
A is legitimate, implying that the set P it outputs does not contain any indices previously queried toOCorrupt. Thus, if bad is set in OCorrupt for an index i ∈ K, then i ∈/ P and so K 6= P. GameG6 therefore dispenses with the (now redundant) setting of bad in OCorrupt and additionallymoves the choice of K to the Finalize procedure (they are no longer used elsewhere in the game).
We have already justified that these changes are without loss, thus Pr [G5(A) ; ⊥ ∧ Good5 ] =Pr [G6(A) ; ⊥ ∧ Good6 ].
In game G6 we note that, in fact, the events Good6 and G6(A) ; ⊥ are independent. Although
the setting of bad and G6(A) ; ⊥ both rely on the adversary’s choice of P, the probability that
bad is set for any set P is the same, meaning that the event Good6 is independent of a particular
choice of P, and hence of G6(A) ; ⊥. Thus we have −1η· Pr [G6(A) ; ⊥]Pr [G6(A) ; ⊥ ∧ Good6 ] = Pr [G6(A) ; ⊥] · Pr [Good6 ] =κwhere the last equation comes from noting that bad is not set if K is chosen to be the set of indicesused in the forgery.
ruf2
Finally we have that G6(A) is equivalent to Expruf2
RS (A), giving that Pr [G6(A) ; ⊥] = AdvRS (A).
Collecting all the previous game transitions we have thatPr [G0(A) ; ⊥] = Pr [G1(A) ; ⊥]= Pr [G2(A) ; ⊥] − Advranon-ind(Ba )RS≥ Pr [G3(A) ; ⊥ ∧ Good] − Advranon-ind(Ba )RS= Pr [G4(A) ; ⊥ ∧ Good] − Advranon-ind(Ba )RS= Pr [G5(A) ; ⊥ ∧ Good] − Advranon-ind(Ba )RS= Pr [G6(A) ; ⊥ ∧ Good] − Advranon-ind(Ba )RS= Pr [Good] · Pr [G6(A) ; ⊥] − Advranon-ind
(Ba )
RS
 −1
η
ranon-ind=· Advruf2(Ba )
RS (A) − AdvRSκwhich, combined with (12), implies the lemma statement.
The running times of both Bu and Ba includes the time to run A plus the overhead associatedwith setting up the additional public keys and answering oracle queries.
Fixed versus arbitrary ring security. The next lemma states that any κ-user ring signaturescheme secure against rogue-key adversaries forging against a particular, fixed ring are also secureagainst the more general ruf3-kr adversaries. This lemma will be useful for simplifying the proofof Theorem 5.4, but we expect that it is also of independent interest.
Lemma 5.2 Let RS = (RPg, RKg, RSign, RVf) be a κ-user ring signature scheme and let Reg =(RegP, RegV) be a registration protocol. Let η ≥ κ. Let A be an ruf3-kr adversary making at mostqs signing queries, at most qc corruption queries, at most qk key registration queries, and runningin time at most t. Then there exists an ruf3-kr-fr adversary B such that ηruf3-kr
AdvRS,Reg (A) ≤Advruf3-kr-fr
RS,Reg (B)κ22procedure Initialize

Adversary B(par, (pki )κ1 )):G0$

par ← RPg$
For i = 1 to κ do (pki , ski ) ← RKg(par)$K ← Pκ ({1 .. η})
For i = 1 to η do
If i ∈/ K then(pki0 , ski0 ) ← RKg(par)Else pki0 ← pkj ; I[i] ← j; j ← j + 1
Ret (par, (pki0 )η1 )$K ← Pκ ({1 .. η})j←1
For i = 1 to η do
If i ∈/ K then(pki0 , ski0 ) ← RKg(par)Register pki0 using OKReg-B
Else pki0 ← pkj ; I[i] ← j; j ← j + 1
Run A(par, (pki0 )η1 ), answering queries by:procedure ORSign-A(s, V, M )query ORSign-A(s, V, M )If s ∈ K then Ret ORSign-B(I[s], V, M )Ret RSignsks0 (V, M )If s ∈ K then sk ← skI[s] ; Ret RSignsk (V, M )Ret RSignsks0 (V, M )query OCorrupt(i)sk ← ⊥
If i 6∈ K then sk ← ski0
Else bad ← true
Ret skprocedure OCorrupt(i)sk ← ⊥
If i 6∈ K then sk ← ski0
Else bad ← true
Ret skprocedure Finalize(P, M, σ)A finishes, outputing (P, M, σ)
If P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 thenIf bad 6= true then φ ← ({1, . . . , κ}, M, σ)Ret φ

If P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 thenIf bad 6= true then φ ← ({1, . . . , κ}, M, σ)Ret φFigure 9: Adversary B and game G0 used in proof of Lemma 5.2.
where B runs in time at most t + O(qc + (η + qs )Time(RS)) and uses at most qs signing queries andat most qk + η − κ registration queries.
Proof: The proof is similar in spirit to the proof of Lemma 5.1. Let A be a legitimate ruf3-kr
adversary. We build a legitimate ruf3-kr-fr adversary B that uses A. See Figure 9. The adversary B
is given inputs a parameter string and a ring of size κ that it must forge against. Adversary B
has access to a signing oracle denoted by ORSign-B and a key registration oracle OKReg. Herethe ORSign-B oracle allows queries on (registered) adversarially-chosen keys, as per the ruf3-kr
experiment. Adversary B first selects a set of indices K that represent its guess of which parties
will be forged against by A. Then, a new set of keys are generated by B. For every index in K
one of the target keys is used. For all others, B generates its own public key, secret key pair andregisters it as a rogue key using its OKReg-B oracle. Adversary A is run using the full set of η
public keys. The table I is used to map between the indices in the set of public keys given to A
and the indices in the set of public keys given to B. Signing queries ORSign-A(s, V, M ) from A
are simulated in one of two ways. If the signing key is one of the target keys, then B queries its
ORSign-B oracle and returns the result. Otherwise the signing key must be one of those generated
by B initially, and so B uses it to generate the requested ring signature. For corruption queries, if
the index queried is not in K then the secret key is returned (in this case B knows the secret key).
Otherwise ⊥ is returned. Key registration invocations, which aren’t explicitly shown in the figure

23

procedure Initialize

G1$par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)$K ← Pκ ({1 .. η})
Ret (par, (pki0 )η1 )procedure ORSign-A(s, V, M )Ret RSignsks (V, M )procedure OCorrupt(i)sk ← ⊥
If i ∈/ K then sk ← ski
Else bad ← true
Ret skprocedure Finalize(P, M, σ)
If P =
6 K then bad ← trueφ ← ⊥; V = {pki | i ∈ P}
If RVf(V, M, σ) = 1 thenIf bad 6= true then φ ← (P, M, σ)Ret φFigure 10: Game G1 used in the proof of Lemma 5.2.
for brevity, are just forwarded to B’s OKReg-B oracle.
We now proceed through a game-playing sequence to lower bound the advantage of B in termsof the advantage of A. Game G0 represents the first game, see Figure 6. It is equivalent to theadversary B except that it generates the parameter string and honest public keys itself and answers
ORSign-A queries with s ∈ K directly via computing RSign. It dispenses with the registrationof the public keys it generates, which is no longer necessary since the game now also simulates
the environment. Key registration queries made by A are handled by simulating a new instanceof RegV (this is not shown in Figure 9 for brevity, nor will it be shown in the rest of the games as
it never changes). Since the outputs of G0(A) and B are distributed equivalently and B forges any
time it doesn’t output ⊥, we have
Advruf3-kr-fr(B) = Pr [G0(A) ; ⊥] .
RS

(18)

Game G1 (Figure 10, boxed statements omitted) simplifies the Initialize procedure by picking
one set of η public keys. This means that the table I is no longer needed, and thus omitted.
The ORSign-A oracle is thus written more simply; the new code implements the same functionality as the ORSign-A oracle of G0. The Finalize procedure outputs (P, M, σ) as opposed to({1, . . . , κ}, M, σ) in G0, but this does not change the probability with which the game outputs ⊥.
We have thatPr [G0(A) ; ⊥] = Pr [G1(A) ; ⊥] .

(19)

The rest of the game sequence (what would be games G1—G4) is similar to the sequence G3—G6
used in the proof of Lemma 5.1 (except for the implicit key registration oracle), see Figure 8. We
therefore omit the next 4 games and their analysis, which can be easily adapted from the games24and analysis in the proof of Lemma 5.1. We conclude that −1
ηPr [G1(A) ; ⊥] ≥·Advruf3-kr
RS,Reg (A)κwhich combined with (18) and (19) implies the lemma statement.
The running time of B is equal to the running time of A plus the overhead of initializing the
public keys and answering oracle queries, leading to the time bound given in the lemma statement.

5.3

KOSK Improves Unforgeability Guarantees

Using the key registration protocol Kosk, any scheme that is unforgeable with respect to corruption
attacks (ruf2) and meets our strong definition of anonymity is also secure against rogue-key attacks(ruf3-kr). Note that this result (unlike those in the last section) applies to any ring signaturescheme, not just κ-user ring signature schemes.
Theorem 5.3 Fix η and let RS = (RPg, RKg, RSign, RVf) be a ring signature scheme. Let A be an
ruf3 adversary with respect to the Kosk protocol that makes at most qs signature queries, at mostqc corruption queries, at most qk registration queries, and runs in time at most t. Then there exist
adversaries Ba and Bu such thatranon-ind
Advruf3-kr(Ba ) + Advruf2
RS,Kosk (A) ≤ AdvRS
RS (Bu )where Ba and Bu both run in time at most t + O(qk + qc + (qs + η + 1)Time(RS)) and make atmost qs sign queries and at most qc corrupt queries.
Before proceeding to the proof we point out that one can apply Lemma 5.1 and then Theorem 5.3 tothe two 2-user ring signature schemes from Bender et al., rendering them secure against rogue-key
attacks when Kosk is used for key registration. Now we prove Theorem 5.3.
Proof: Let A be a legitimate ruf3 adversary with respect to the Kosk key registration protocol. In
this case the key registration oracle registers the public key of any valid (pk, sk) pair queried by A.
We can assume without loss of generality that A never queries its registration oracle with a pair
(pk, sk) that is not a valid key pair. We specify a legitimate ruf2 adversary Bu , shown in Figure 11,that takes input a parameter string and set of public keys and has access to a ruf2 signing oracle(denoted ORSign-2). It utilizes a table P to record the secret keys registered for adversariallychosen public keys (initially, P is everywhere undefined). Adversary Bu runs A and responds to A’s
signing queries in one of two ways. If all the public keys in the query are ones generated by theenvironment, then Bu uses its ORSign-2 oracle to generate the response. Otherwise, it uses thesecret key registered for one of the adversarially-chosen public keys (say, the lexicographically first)
to answer the query. Since A is legitimate, any adversarially-chosen public key used in a signing
query must first have been registered. Adversary Bu is legitimate because A is legitimate andbecause Bu never queries its ORSign-2 oracle with a set of public keys including rogue keys.
We specify a game G0 in Figure 11 which is just like Bu , except that it runs the parameter
string and the public key, secret key generation algorithms itself and answers ORSign-3 andOCorrupt-3 queries directly. Its output is distributed identically to Bu and Bu forges anytime its
output is not ⊥. Thus
Advruf2
RS (Bu ) = Pr [G0(A) ; ⊥] .

(20)

Game G1 combines the Initialize, OCorrupt, OKReg, and Finalize procedures of G0 with the
ORSign-3 procedure (labeled G1) shown in Figure 11. In G1 sks is always utilized to generate25Adversary Bu (par, (pki )η1 )procedure Initialize:S ← {pk1 , . . . , pkη }Run A(par, (pki )η1 ), answering queries by:par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)S ← {pk1 , . . . , pkη }Run A(par, (pki )η1 ), answering queries by:query ORSign-3(s, V, M )If V ⊆ S then Ret ORSign-2(s, V, M )Let pk be s.t. pk ∈ V\S
Ret RSignP[pk] (V, M )procedure ORSign-3(s, V, M )G0

If V ⊆ S then Ret RSignsks (V, M )Let pk be s.t. pk ∈ V\S
Ret RSignP[pk] (V, M )query OCorrupt-3(i)Ret OCorrupt-2(i)query OKReg(pk, sk)
P[pk] ← sk
Return pk

procedure OCorrupt-3(i)G0, G1

Ret skiprocedure OKReg(pk, sk)

A finishes, outputing (P, M, σ)V ← {pki | i ∈ P}
If RVf(V, M, σ) = 1 then Ret (P, M, σ)Ret ⊥procedure ORSign-3(s, V, M )G0, G1$

G0, G1

P[pk] ← sk
Return pk
procedure Finalize(P, M, σ)

G0, G1V ← {pki | i ∈ P}
If RVf(V, M, σ) = 1 then Ret (P, M, σ)
Ret ⊥

G1

If V ⊆ S then Ret RSignsks (V, M )Let pk be s.t. pk ∈ V\S
Ret RSignsks (V, M )procedure Initialize:

G2$

par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)S ← {pk1 , . . . , pkη }Run A(par, (pki )η1 ), answering queries by:Adversary Ba (par, (pki )η1 )):S ← {pk1 , . . . , pkη }Run A(par, (pki )η1 ), answering queries by:query ORSign-3(s, V, M )If V ⊆ S then Ret RSignsks (V, M )Let pk be s.t. pk ∈ V\S
Ret ORSignLR({P[pk], sks }, V, M )procedure ORSign-3(s, V, M )Ret RSignsks (V, M )procedure OCorrupt-3(i)query OCorrupt-3(i)Ret ski

Ret skiquery OKReg(pk, sk)
P[pk] ← sk
Return pk

P[pk] ← sk
Return pk

procedure OKReg(pk, sk)

procedure Finalize(P, M, σ)A finishes, outputing (P, M, σ)V ← {pki | i ∈ P}
If RVf(V, M, σ) = 1 then Ret 1
Ret 0

V ← {pki | i ∈ P}
If RVf(V, M, σ) = 1 then Ret (P, M, σ)Ret ⊥Figure 11: Games and adversaries used in the proof of Theorem 5.3. Game G1 (resp. G2) is fully
specified by replacing the ORSign-3 procedure of G0 with the ORSign-3 labeled with G1 (resp.
G2).

26

responses to signing queries. To bound the loss due to this change, we build an ranon-ind adversary Ba and will relate the difference in the output distributions of G0(A) and G1(A) to theadvantage of Ba . Figure 11 shows the adversary. It behaves exactly like G0 and G1 except that it
utilizes its ORSignLR oracle to respond to some signing queries. By the definition of ranon-ind
advantage we have thathihiAdvranon-ind(Ba ) = Pr Expranon-ind-1(Ba )⇒1 − Pr Expranon-ind-0(Ba )⇒1 .
(21)
RS
RS
RS
Note that if Ba is run in the ranon-ind-1 experiment, then the secret key sks is always utilized
to answer Ba ’s oracle queries.
Thus Ba returns
 a one whenever G1(A) would not output ⊥,and so we have that Pr Expranon-ind-1(B)⇒
1= Pr [G1(A) ; ⊥]. Similarly, if Ba is run inaRSthe ranon-ind-0 experiment, then the secret key P[pk] is always used to answer Ba ’s queries. So
Pr Expranon-ind-0(B)⇒
1= Pr [G0(A) ; ⊥]. Substituting back into (21) and re-arranging weaRShave thatPr [G0(A) ; ⊥] = Pr [G1(A) ; ⊥] − Advranon-ind(Ba ) .
RS

(22)

The final game is G2, which just simplifies the ORSign-3 oracle from game G1. The change
does not change the functionality of the oracle, and thus Pr [G1(A) ; ⊥] = Pr [G2(A) ; ⊥]. Now
it is apparent that G2 simulates for A exactly the experiment Expruf2
RS (A) and so we have that(A).
Combining
all
of
the
above,
wehavethat
Pr [G2(A) ; ⊥] = Advruf2
RS
Advruf3
RS,Kosk (Bu ) = Pr [G0(A) ; ⊥]= Pr [G1(A) ; ⊥] − Advranon-ind(Ba )RS= Pr [G2(A) ; ⊥] − Advranon-ind(Ba )RS
ranon-ind= Advruf2(Ba ) .
RS (A) − AdvRS

The running time of Bu and Ba are (each) the running time of A plus the overhead needed torespond to A’s oracle queries, leading to the time bounds given in the theorem statement.

5.4

Ring Signatures with POPs

For all the reasons already described, we’d like to avoid the KOSK assumption wherever possible. Thus, we give a proof-of-possession based registration protocol for the 2-user scheme basedon Waters signatures from Bender et al. [10]. Let G1 , G2 , GT , p, g, e be pairing parameters with
G1 = G2 = G. Let WRS = (W-RKg, W-RSign, W-RVf) be the ring signature scheme defined as
below.
W-RKg

W-RSign(sk, {pk, pk 0 }, M )W-RVf({pk, pk 0 }, M, (σ, ρ))$(g1 , u, ~u) ← pk
(g10 , u0 , ~u0 ) ← pk 0$
r ← Zp ; ρ ← g r
Y ← Hu,~u (M ) · Hu0 ,~u0 (M )σ ← (g10 )sk · Y r
Return (σ, ρ)(g1 , u, ~u) ← pk
(g10 , u0 , ~u0 ) ← pk 0
Y ← Hu,~u (M ) · Hu0 ,~u0 (M )If e(g1 , g10 ) · e(Y, ρ) = e(σ, g) thenReturn 1
Return 0

sk ← Zp ; g1 ← g sk$
u, u1 , . . . , un ← Gn+1
pk ← (g1 , u, ~u)
Return (pk, sk)

When we write (g1 , u, ~u) ← pk (resp. (g10 , u0 , ~u0 ) ← pk 0 ), we mean that pk (resp. pk 0 ) is parsed
into its constituent parts. In [10] the scheme is proven secure against ruf1 adversaries and we canapply Theorem 5.1 to show security against ruf2 adversaries. Additionally it is easy to see that27

the scheme is perfectly ranon-ind. However, as shown in [37] the scheme is not secure againstrogue-key attacks (in the plain setting). We now show a simple proof-of-possession based registration protocol under which provable security against rogue-key attacks can be achieved. Choose$
global parameters (h0 , h1 , w, w1 , . . . , wn ) ← (G1 )n+3 (this will require trusted setup, since the
CA should not know the discrete logs of these values). Then we specify the registration protocol WR-Pop = (WR-PopP, WR-PopV). Algorithm WR-PopP takes as input (pk, sk) and sends
pk || (π0 , $0 , π1 , $1 ) which is computed by generating the two signatures W-SignHw,w~ (hsk
0 , hpkin )and W-SignHw,w~ (hsk
,
hpki
).
Algorithm
WR-PopV,
upon
receivingthemessage,verifiesthesignan1
tures in the natural way: get g1 from pk and check that both e(g1 , h0 )·e(Hw,w~ (hpkin ), $0 ) = e(π0 , g)and e(g1 , h1 )·e(Hw,w~ (hpkin ), $1 ) = e(π1 , g). If both signatures verify, the algorithm replies with pk
and otherwise ⊥. The following theorem captures the security of WRS with respect to the WR-Pop
registration protocol.
Theorem 5.4 Fix η ≥ 2. Let A be an ruf3-kr adversary with respect to the WR-Pop protocol thatmakes at most qs signature queries, qc corruption queries, qk key registration queries, and runs intime at most t. Then there exists an adversary B such that2uf
Advruf3-kr
WRS,WR-Pop (A) ≤ η AdvW (B)where B makes at most qs signing queries and runs in time at most t+O(qc +(n+qs +1)Time(WRS).
Proof: In fact we consider an ruf3-kr-fr adversary A (with respect to the WR-Pop protocol), and will
later apply Lemma 5.2 to prove the theorem. We use A to build a uf adversary B against the Waters
signature scheme; the adversary B is shown in Figure 12. Adversary B is given input a parameter
string and Waters’ public key and has access to a Waters’ signing oracle OSign. First it parses
the parameter string and Waters’ public key pk ∗ , notated by the code (g1 , u, u1 , . . . , un ) ← pk ∗ . It
generates two WRS public keys. The first, pk0∗ , is composed of g1 and a set of randomly chosengroup elements a, ~a. The second, pk1∗ , is composed of the Waters’ parameter h and a set of groupelements b, ~b chosen to be the Waters’ elements u, ~u component-wise divided by the values a, ~a.
Lastly it generates the public parameters for the WR-Pop protocol, programming the values h0 and
h1 to include the group elements g1 and h, respectively. The values w, w
~ are chosen so that theenvironment knows their discrete logs (base g). The adversary handles A’s queries as follows. For
key registration, the POP is simply recorded in a table P, which is initially undefined everywhere.
Without loss of generality we assume A only sends valid POPs. For signing queries, A will either
query on the set of public keys V including both pk0∗ and pk1∗ or at least one of the two (recall that
because A is legitimate, it will never query on two keys it chose, and all adversarially-chosen keys
queried to ORSign will have been previously registered). If the former, then B uses its signingoracle to generate a response. Otherwise, it utilizes the POP of the adversarially-chosen public key
to assist it in computing a response. The code (pks∗ , pk) ← V means: (1) parse V as two publickeys pk 0 and pk and (2) let s ∈ {0, 1} be such that pk 0 = pks∗ . Finally when A finishes, B outputs
A’s forgery in the case that it verifies and otherwise outputs ⊥.
We now show that if A outputs a successful forgery, then B does also. The forgery is of theform ({pk0∗ , pk1∗ }, M, (σ, ρ)) and if W-RVf verifies then we know that e(g1 , h)·e(Y, ρ) = e(σ, g) where
Y = Ha,~a (M ) · Hb,~b (M ). But we have that for any M ∈ {0, 1}n that

n 
n
n
Y
Y
ui M [i]
u Y
M [i]
ai ·
= u · (ui )M [i] = Hu,~u (M ) . (23)Ha,~a (M ) · Hb,~b (M ) = a · b · (ai bi )= a· ·
a
ai
i=1
Hu,~u

Thus σ, ρ are such that W-Vf

i=1

(pk ∗ , M, (σ, ρ)) = 1.
28

i=1

procedure Initialize

Adversary B(par, g1 )$u, ~u ← Gn+1 ; α, δ ← Zp ; h ← g δ ; g1 ← g α$a, a1 , . . . , an ← Gn+1
pk0∗ ← (g1 , a, a1 , . . . , an )b ← u/a; For j = 1 to n do bj ← uj /aj
pk1∗ ← (h, b, b1 , . . . , bn )$β0 , β1 , x, x1 , . . . , xn ← Zn+3ph0 ← g1 g β0 ; h1 ← hg β1w, w~ ← g x , g x1 , . . . , g xn
Ret (h0 , h1 , w, w,~ (pk0∗ , pk1∗ ))(h, u, u1 , . . . , un ) ← par$a, a1 , . . . , an ← Gn+1
pk0∗ ← (g1 , a, a1 , . . . , an )b ← u/a; For j = 1 to n do bj ← uj /aj
pk1∗ ← (h, b, b1 , . . . , bn )$β0 , β1 , x, x1 , . . . , xn ← Zn+3ph0 ← g1 g β0 ; h1 ← hg β1w, w~ ← g x , g x1 , . . . , g xn
Run A(h0 , h1 , w, w,~ (pk0∗ , pk1∗ )), answering
queries byprocedure ORSign(s, V, M )If V = {pk0∗ , pk1∗ } thenquery ORSign(s, V, M )If V = {pk0∗ , pk1∗ } then Ret OSign(M )(pks∗ , pk) ← V; (ĝ, z, z1 , . . . , zn ) ← pk
(π0 , $0 ), (π1 , $1 ) ← P[pk]
$

x+Σn

G0

$

Ret W-SignHu,~u (hα , M )(pks∗ , pk) ← V; (ĝ, z, z1 , . . . , zn ) ← pk
(π0 , $0 ), (π1 , $1 ) ← P[pk]xj pk[j]x+Σnxj pk[j]r ← Zp ; P ← $s j=1
If s = 0 then Y ← Hz,~z (M ) · Ha,~a (M )Else Y ← Hz,~z (M ) · Hb,~b (M )σ ← πs · Y r · ĝ −βs · P −1
Ret (σ, g r )r ← Zp ; P ← $s j=1
If s = 0 then Y ← Hz,~z (M ) · Ha,~a (M )Else Y ← Hz,~z (M ) · Hb,~b (M )σ ← πs · Y r · ĝ −βs · P −1
Ret (σ, g r )query OKReg(pk, (π0 , $0 , π1 , $1 ))P[pk] ← (π0 , $0 , π1 , $1 ); Ret pk

procedure OKReg(pk, (π0 , $0 , π1 , $1 ))$P[pk] ← (π0 , $0 , π1 , $1 ); Ret pk

A finishes, outputing (P, M, (σ, ρ))φ←⊥
If RVf({pk0∗ , pk1∗ }, M, (σ, ρ)) = 1 thenφ ← (M, (σ, ρ))Ret φprocedure Finalize(P, M, (σ, ρ))φ←⊥
If RVf({pk0∗ , pk1∗ }, M, (σ, ρ)) = 1 thenφ ← (M, (σ, ρ))Ret φFigure 12: Adversary B and game G0 used in the proof of Theorem 5.4.
We proceed through a sequence of games to lower bound B’s advantage. The first game isG0, shown in Figure 12. It is exactly like adversary B except that it produces the Waters’ scheme
parameters and keys itself. Instead of querying an OSign oracle it runs W-Sign directly. The
output of B and G0 are the same, and since B forges against W (as argued above) any time ⊥ isnot output we haveAdvuf
W (B) = Pr [G0(A) ; ⊥] .

(24)
Hu,~u

(hα , M ) it computes

The next game is G1, shown in Figure 13. Instead of computing W-Sign
W-RSign(α, V, M ). Here α corresponds to the secret key of pk0∗ . In fact this change is without loss
because they compute the same values.
σ = hα · Hu,~u (M )r and ρ = g r for The former generates$r ← Zp . The latter generates σ 0 = hα · Ha,~a (M ) · Hb,~b (M )r$and ρ0 = g r for r ← Zp . Applying (23)to σ 0 we have that σ 0 = hα · Hu,~u (M )r = σ and so the computations are equivalent. We have just29

procedure Initialize
$

G1

$

u, ~u ← Gn+1 ; α, δ ← Zp ; h ← g δ ; g1 ← g α$a, a1 , . . . , an ← Gn+1
pk0∗ ← (g1 , a, a1 , . . . , an )b ← u/a; For j = 1 to n do bj ← uj /aj
pk1∗ ← (h, b, b1 , . . . , bn )$β0 , β1 , x, x1 , . . . , xn ← Zn+3ph0 ← g1 g β0 ; h1 ← hg β1w, w~ ← g x , g x1 , . . . , g xn
Ret (h0 , h1 , w, w,~ (pk0∗ , pk1∗ ))procedure Initialize$u, ~u ← Gn+1 ; α, δ ← Zp ; h ← g δ ; g1 ← g α$a, a1 , . . . , an ← Gn+1
pk0∗ ← (g1 , a, a1 , . . . , an )b ← u/a; For j = 1 to n do bj ← uj /aj
pk1∗ ← (h, b, b1 , . . . , bn )$β0 , β1 , x, x1 , . . . , xn ← Zn+3ph0 ← g1 g β0 ; h1 ← hg β1w, w~ ← g x , g x1 , . . . , g xn
Ret (h0 , h1 , w, w,~ (pk0∗ , pk1∗ ))procedure ORSign(s, V, M )If V = {pk0∗ , pk1∗ } then
Ret W-RSign(α, V, M )(pks∗ , pk) ← V; (ĝ, z, z1 , . . . , zn ) ← pk
(π0 , $0 ), (π1 , $1 ) ← P[pk]
$

x+Σn

G2

$

procedure ORSign(s, V, M )If V = {pk0∗ , pk1∗ } then
Ret W-RSign(α, V, M )If s = 0 then Ret W-RSign(α, V, M )Ret W-RSign(δ, V, M )xj pk[j]r ← Zp ; P ← $s j=1
If s = 0 then Y ← Hz,~z (M ) · Ha,~a (M )Else Y ← Hz,~z (M ) · Hb,~b (M )σ ← πs · Y r · ĝ −βs · P −1
Ret (σ, g r )procedure OKReg(pk, (π0 , $0 , π1 , $1 ))P[pk] ← (π0 , $0 , π1 , $1 ); Ret pk
procedure Finalize(P, M, (σ, ρ))φ←⊥
If RVf({pk0∗ , pk1∗ }, M, (σ, ρ)) = 1 thenφ ← (M, (σ, ρ))Ret φprocedure OKReg(pk, (π0 , $0 , π1 , $1 ))P[pk] ← (π0 , $0 , π1 , $1 ); Ret pk
procedure Finalize(P, M, (σ, ρ))φ←⊥
If RVf({pk0∗ , pk1∗ }, M, (σ, ρ)) = 1 thenφ ← (M, (σ, ρ))Ret φFigure 13: Games G1 and G2 used in proof of Theorem 5.4.
argued thatPr [G0(A) ; ⊥] = Pr [G1(A) ; ⊥] .

(25)

Game G2 simplifies handling of signing queries further. Queries on V = {pk0∗ , pk1∗ } are handled
as in game G1. There are two other cases. First if V = {pk0∗ , pk}, the response is computed via
W-RSign(α, V, M ). Second if V = {pk1∗ , pk}, the response is computed via W-RSign(δ, V, M ). (Notethat δ is the discrete log of h base g, and plays the role of sk1∗ .) We focus on the first case, wheres = 0, showing that G1 and G2 implement the same signing functionality when queried by A on
V = {pk0∗ , pk} and a message M for some adversarially-chosen public key pk = (ĝ, z, ~z). (The othercase is argued similarly.) In G1 such a query is answered by
 x+Pn x pk[j] −1jσ = π0 · Y r · ĝ −β0 · $0 j=1(26)$

and a value g r where r ← Zp . Since A is legitimate, the POP tuple (π0 , $0 ) verifies under30

WR-PopV, meaning thate(π0 , g) = e(ĝ, h0 ) · e(Hw,w~ (pk), $0 )= e(ĝ, g1 g β0 ) · e(Hw,w~ (pk), $0 )= e(ĝ, g1 ) · e(ĝ, g β0 ) · e(Hw,w~ (pk), $0 )(27)

and since g1 = g α the properties of e give that e(ĝ, g1 ) = e(ĝ α , g). Substituting this into (27) andrearranging givese(ĝ α , g) =e(π0 , g)βe(ĝ, g 0 ) · e(Hw,w~ (pk), $0 )=e(π0 , g)Pnβe(ĝ, g 0 ) · e(g x+ i=1 xi pk[i] , $0 )=e(π , g)
 0 Pnx+x pk[i],ge(ĝ β0 , g) · e $0 i=1 i=e(π0 , g)Px+ n x pk[i]e ĝ β0 · $0 i=1 i
,g

P

−1 
x+ n
−β0
i=1 xi pk[i]= e π0 · ĝ
· $0
,g .

(28)

Above we have utilized the properties of e to derive the chain of equalities. Equation (28) gives
that
P


x+ n x pk[i] −1ĝ α = π0 · ĝ −β0 · $0 i=1 i.
(29)
and substituting (29) into (26) we see that σ = ĝ α · Y r . Investigating the definition of W-RSign,$
we see that the output of W-RSign(α, V, M ) is (ĝ α · Y r , g r ) when V = {pk0∗ , pk} and where r ← Zp .
Thus the handling of this query in G1 results in the same response as the code handling this queryin G2. The other case can be argued similarly, giving thatPr [G1(A) ; ⊥] = Pr [G2(A) ; ⊥] .

(30)

In game G3, we further simplify the ORSign procedure, always returning exactly the ring signature
requested by A. Since WRS is perfectly ranon-ind anonymous there is no distinction between thehandling of signing queries in G2 and in G3. Thus,
Pr [G2(A) ; ⊥] = Pr [G3(A) ; ⊥] .

(31)

In the final game G4 we re-write the Initialize procedure, computing values as shown in Figure 14.
The distributions of the variables returned by the procedure remain unchanged, giving thatPr [G3(A) ; ⊥] = Pr [G4(A) ; ⊥] .

(32)

Now however we note that G4 exactly implements the ruf3-kr-fr experiment with respect to the
WR-Pop protocol. Thus we have that Pr [G4(A) ; ⊥] = Advruf3-kr-fr
WRS,WR-Pop (A) and combining all the
ruf3-kr-fr
above game transitions we have that AdvWRS,WR-Pop (A) ≤ Advuf
W (B).
The adversary B runs in time at most the running time of A plus the overhead of the simulation. This includes O(n · Time(WRS)) operations, which is the time to initialize the public keys;
O(qs Time(WRS)) operations, for simulating signing queries; O(qc ) operations, for handling registration queries; and a single Time(WRS) for the verification procedure. Thus the total running
time is at most t + O(qc + (n + qs + 1)Time(WRS)).
31

procedure Initialize$

G3
procedure Initialize$u, ~u ← Gn+1 ; α, δ ← Zp ; h ← g δ ; g1 ← g α$a, a1 , . . . , an ← Gn+1
pk0∗ ← (g1 , a, a1 , . . . , an )b ← u/a; For j = 1 to n do bj ← uj /aj
pk1∗ ← (h, b, b1 , . . . , bn )$β0 , β1 , x, x1 , . . . , xn ← Zn+3ph0 ← g1 g β0 ; h1 ← hg β1w, w~ ← g x , g x1 , . . . , g xn
Ret (h0 , h1 , w, w,~ (pk0∗ , pk1∗ ))G4$α, δ ← Zp ; h ← g δ ; g1 ← g α$a, a1 , . . . , an ← Gn+1
pk0∗ ← (g1 , a, a1 , . . . , an )$b, b1 , . . . , bn ← Gn+1
pk1∗ ← (h, b, b1 , . . . , bn )$h0 , h1 , w, w1 , . . . , wn ← Gn+3
Ret (h0 , h1 , w, w,~ (pk0∗ , pk1∗ ))procedure ORSign(s, V, M )procedure ORSign(s, V, M )If s = 0 then Ret W-RSign(α, V, M )Ret W-RSign(δ, V, M )If s = 0 then Ret W-RSign(α, V, M )Ret W-RSign(δ, V, M )procedure OKReg(pk, (π0 , $0 , π1 , $1 ))procedure OKReg(pk, (π0 , $0 , π1 , $1 ))P[pk] ← (π0 , $0 , π1 , $1 ); Ret pk

P[pk] ← (π0 , $0 , π1 , $1 ); Ret pk

procedure Finalize(P, M, (σ, ρ))φ←⊥
If RVf({pk0∗ , pk1∗ }, M, (σ, ρ)) = 1 thenφ ← (M, (σ, ρ))Ret φprocedure Finalize(P, M, (σ, ρ))φ←⊥
If RVf({pk0∗ , pk1∗ }, M, (σ, ρ)) = 1 thenφ ← (M, (σ, ρ))Ret φFigure 14: Games G3 and G4 used in proof of Theorem 5.4.
We can now apply Lemma 5.2, which adds a factor ν 2 but does not require additional time overthat already used by adversary B.

Acknowledgements
The authors thank Mihir Bellare for suggesting that they investigate the security of multisignatureschemes when the proof of knowledge is replaced by a proof of possession akin to ones currently
used in PKIs, and for many useful discussions. The authors thank the anonymous reviewers fortheir helpful comments.

References[1] C. Adams, S. Farrell, T. Kause, T. Mononen. Internet X.509 public key infrastructure certificate management protocols (CMP). Request for Comments (RFC) 4210, Internet Engineering
Task Force (September 2005)[2] N. Asokan, V. Niemi, P. Laitinen. On the usefulness of proof-of-possession. In Proceedings ofthe 2nd Annual PKI Research Workshop. (2003) 122–127[3] M. Bellare. CSE 208: Advanced Cryptography. UCSD course (Spring 2006).
[4] M. Bellare, O. Goldreich. On Defining Proofs of Knowledge. In Advances in Cryptology –CRYPTO ’92. Volume 740 of Lecture Notes in Computer Science, pp. 390–420, E. Brickell ed.,Springer-Verlag, 199332

[5] M. Bellare, T. Kohno, V. Shoup. Stateful public-key cryptosystems: how to encrypt withone 160-bit exponentiation. In Proceedings of the 13th ACM Conference on Computer andCommunications Security (CCS), pp. 380–389, ACM, 2006
[6] M. Bellare, C. Namprempre, G. Neven. Unrestricted aggregate signatures. Cryptology ePrint
Archive, Report 2006/285 (2006) http://eprint.iacr.org/.
[7] M. Bellare, G. Neven. Multi-signatures in the plain public-key model and a generalized forking lemma. In Proceedings of the 13th ACM Conference on Computer and Communications
Security (CCS), pp. 390–399, ACM, 2006[8] M. Bellare, P. Rogaway. Random oracles are practical: a paradigm for designing efficient
protocols. In Proceedings of the 1st ACM Conference on Computer and Communications
Security (CCS), pp. 62–73, ACM, 1993
[9] M. Bellare, P. Rogaway. The security of triple encryption and a framework for code-basedgame-playing proofs. In Advances in Cryptology – EUROCRYPT ’06. Volume 4004 of Lecture
Notes in Computer Science, pp. 409–426, S. Vaudenay ed., Springer-Verlag, 2006[10] A. Bender, J. Katz, R. Morselli. Ring signatures: Stronger definitions, and constructions
without random oracles. In Third Theory of Cryptography Conference – TCC ’06. Volume3876 of Lecture Notes in Computer Science, pp. 60–79, Springer-Verlag, 2006[11] A. Boldyreva. Threshold signatures, multisignatures and blind signatures based on the gapdiffie-hellman-group signature scheme. In Proceedings of the 6th International Workshop on
Theory and Practice in Public Key Cryptography – PKC ’03. Volume 2567 of Lecture Notes in
Computer Science, pp. 31–46, Springer-Verlag, 2003[12] A. Boldyreva, M. Fischlin, A. Palacio, B. Warinschi. A closer look at PKI: security andefficiency. In Proceedings of the 10th International Conference on Practice and Theory in
Public Key Cryptography – PKC ’07, Volume 4450 of Lecture Notes in Computer Science, T.
Okamoto, X. Wang eds., Springer-Verlag, 2007[13] D. Boneh, C. Gentry, B. Lynn, H. Shacham. Aggregate and verifiably encrypted signaturesfrom bilinear maps. In Advances in Cryptology – EUROCRYPT ’03. Volume 2656 of Lecture
Notes in Computer Science, pp. 416–432, E. Biham ed., Springer-Verlag, 2003[14] D. Boneh, B. Lynn, H. Shacham. Short signatures from the weil pairing. In Advances in
Cryptology – ASIACRYPT ’01. Volume 2248 Lecture Notes in Computer Science, pp. 514–
532, C. Boyd ed., Springer-Verlag, 2001[15] J.S. Coron. On the exact security of full domain hash. In Advances in Cryptology – CRYPTO’00. Volume 1880 of Lecture Notes in Computer Science, pp. 229–235, M. Bellare ed., SpringerVerlag, 2000
[16] A. De Santis, G. Persiano. Zero-knowledge proofs of knowledge without interaction (extended
abstract). In 33rd Annual Symposium on Foundations of Computer Science – FOCS ’92, pp.
427–436, IEEE, 1992[17] M. Fischlin. Communication-efficient non-interactive proofs of knowledge with online extractors. In Advances in Cryptology – CRYPTO ’05. Volume 3621 of Lecture Notes in Computer
Science, pp. 152–168, V. Shoup ed., Springer-Verlag, 2005[18] S. Goldwasser, S. Micali, R. Rivest. A Paradoxical Solution to the Signature Problem. In 25th
Annual Symposium on Foundations of Computer Science – FOCS ’84, pp. 441–449, IEEE,
1984[19] J. Groth, R. Ostrovsky, A. Sahai. Perfect non-interactive zero knowledge for NP. In Advancesin Cryptology – EUROCRYPT ’06. Volume 4004 of Lecture Notes in Computer Science, pp.
339–358, C. Dwork ed., Springer-Verlag, 2006[20] L. Harn. Group-oriented (t,n) threshold digital signature scheme and digital multisignature.
Computers and Digital Techniques, IEEE Proceedings 141(5) (1994) 307–313
33

[21] J. Herranz. Some digital signature schemes with collective signers. Ph.D. Thesis, Universitat
Politècnica De Catalunya, Barcelona. April, 2005.
[22] P. Horster, M. Michels, H. Petersen. Meta signature schemes based on the discrete logarithm problem. In IFIP TC11 Eleventh International Conference on Information Security(IFIP/SEC 1995) (1995) 128–141[23] M. Jakobsson, K. Sako, R. Impagliazzo. Designated verifier proofs and their applications.
In Advances in Cryptology – EUROCRYPT ’96. Volume 1070 of Lecture Notes in Computer
Science, pp. 143–154, U. Maurer ed., Springer-Verlag, 1996[24] F. Laguillaumie, D. Vergnaud. Designated verifier signatures: anonymity and efficient construction from any bilinear map. In Security in Communication Networks, 4th International
Conference, SCN 2004. Volume 3352 of Lecture Notes in Computer Science, pp. 105–119,
Springer, 2005[25] S.K. Langford. Weakness in some threshold cryptosystems. In Advances in Cryptology –CRYPTO ’96. Volume 1109 of Lecture Notes in Computer Science, pp. 74–82, N. Koblitz ed.,Springer-Verlag, 1996[26] C.M. Li, T. Hwang, N.Y. Lee. Threshold-multisignature schemes where suspected forgery
implies traceability of adversarial shareholders. In Advances in Cryptology – EUROCRYPT’94. Volume 950 of Lecture Notes in Computer Science, pp. 194–204, A. DeSantis ed., SpringerVerlag, 1995
[27] H. Lipmaa, G. Wang, F. Bao. Designated verifier signature schemes: attacks, new security
notions and a new construction. In 32nd International Colloquium on Automata, Languages
and Programming – ICALP 2005. Volume 3580 Lecture Notes in Computer Science, pp. 459–
471, Springer-Verlag, 2005[28] S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, B. Waters. Sequential aggregate signatures andmultisignatures without random oracles. In Advances in Cryptology – EUROCRYPT ’06.
Volume 4004 of Lecture Notes in Computer Science, pp. 465–485, S. Vaudenay ed., SpringerVerlag, 2006[29] A. Lysyanskaya, S. Micali, L. Reyzin, H. Shacham. Sequential Aggregate Signatures from
Trapdoor Permutations. In Advances in Cryptology – EUROCRYPT ’04. Volume 3027 of
Lecture Notes in Computer Science, pp. 74–90, C. Cachin, J. Camenisch eds., Springer-Verlag,
2004[30] M. Michels, P. Horster. On the risk of disruption in several multiparty signature schemes.
In Advances in Cryptology – ASIACRYPT ’96. Volume 1163 of Lecture Notes in Computer
Science, pp. 334–345, K. Kim, T. Matsumoto eds., Springer-Verlag, 1996[31] S. Micali, K. Ohta, L. Reyzin. Accountable-subgroup multisignatures. In Proceedings of the
8th ACM Conference on Computer and Communications Security – CCS ’01, pp. 245–254,
ACM, 2001[32] K. Ohta, T. Okamoto. A digital multisignature scheme based on the Fiat-Shamir scheme.
In Advances in Cryptology – ASIACRYPT ’91. Volume 739 of Lecture Notes in Computer
Science, pp. 139–148, H. Imai, R. Rivest, T. Matsumoto eds., Springer-Verlag, 1993[33] K. Ohta, T. Okamoto. Multi-signature schemes secure against active insider attacks. IEICE
Transactions on Fundamentals of Electronics Communications and Computer Sciences E82A(1) (1999) 21–31[34] R.L. Rivest, A. Shamir, Y. Tauman. How to leak a secret. In Advances in Cryptology –ASIACRYPT ’01. Volume 2248 of Lecture Notes in Computer Science, pp. 552–565, C. Boyded., Springer-Verlag, 2001[35] RSA Laboratories: RSA PKCS #10 v1.7: Certification Request Syntax Standard ftp://ftp.
rsasecurity.com/pub/pkcs/pkcs-10/pkcs-10v1 7.pdf.
34[36] J. Schaad. Internet X.509 public key infrastructure certificate request message format (CRMF).
Request for Comments (RFC) 4211, Internet Engineering Task Force (September 2005)[37] H. Shacham, B. Waters. Efficient ring signatures without random oracles. In Proceedingsof the 10th International Conference on Practice and Theory in Public Key Cryptography –PKC ’07, Volume 4450 of Lecture Notes in Computer Science, T. Okamoto, X. Wang eds.,
Springer-Verlag, 2007[38] R. Steinfeld, L. Bull, H. Wang, J. Pieprzyk. Universal designated-verifier signatures. In Advances in Cryptology – ASIACRYPT ’03. Volume 2894 of Lecture Notes in Computer Science,
pp. 523–542, C.S. Laih ed., Springer-Verlag, 2003[39] B. Waters. Efficient identity-based encryption without random oracles. In Advances in Cryptology – EUROCRYPT ’05. Volume 3494 of Lecture Notes in Computer Science, pp. 114–127,
R. Cramer ed., Springer-Verlag, 2005

A

Ring Signature Anonymity Definitions

We recall the strongest definition from [10], anonymity with respect to full key exposure. Let
RS = (RPg, RKg, RSign, RVf) be a ring signature scheme and A be an adversary. The experiment
Expranon-fke-b(A) is defined in Figure 15. Note that we only allow adversaries which make one
RSquery to ORSignLR. We define the ranon-fke advantage of A byhihiranon-fke-0
ranon-fke-1
Advranon-fke
(A)
=
Pr
Exp
(A)
⇒
1
−
Pr
Exp
(A)
⇒
1
RS
RS
RS
We compare this definition to the ranon-ind anonymity definition given in Section 5. Recall that,
intuitively, the ranon-ind definition requires that no adversary can determine which secret key wasused to sign, even if the adversary itself chooses all the keys. First we show a separation, that there
exist schemes which are secure in the ranon-fke sense but not in the ranon-ind sense.
Theorem A.1 Let RS = (RPg, RKg, RSign, RVf) be a ring signature scheme and let A, B, and C
be ranon-ind, ranon-fke, and ruf3-kr adversaries, respectively. Then there exists a ring signaturescheme RS0 such that(A) = 1
Advranon-ind
RS0
Advranon-fke(B) = Advranon-fke
(B)
RS
RS0
Advruf3-kr(C) = Advruf3-kr
(C)
RS
RS0
Proof: Let RS = (RPg, RKg, RSign, RVf) be a ring signature scheme. Define a new ring signaturescheme RS0 = (RPg, RKg0 , RSign0 , RVf 0 ) as follows. Parameter generation is equivalent. Key genera$tion first runs (pk, sk) ← RKg and then returns (pk, sk || 0). Signature generation RSignsk || d (V, M )$works by first running σ ← RSignsk (V, M ) and then outputing σ || d. Verification of (V, M, σ 0 )works by first dropping the last bit of σ 0 to get σ, and then returning RVf(V, M, σ).
Now we show that there exists a ranon-ind adversary A that has advantage one against RS0 .
$The adversary runs (pk0 , sk0 ), (pk1 , sk1 ) ← RKg and then lets sk00 = sk0 || 0 and sk10 = sk0 || 1.
It then queries ORSignLR({sk0 , sk1 }, {pk0 , pk1 }, M ) for any message M . The adversary outputs
the last bit of the returned signature. Clearly its advantage is one.
It is easy to verify that any ranon-fke adversary B has equivalent advantage against either RS
or RS0 and similarly for any ruf3-kr adversary C (relative to any key registration protocol).

35

Experiment Expranon-fke
(A)
RS
$
$
b ← {0, 1}; par ← RPg$
For i = 1 to η do (pki , ski ) ← RKg(par)K = {ski | i ∈ [1 .. η]}
Run A(par, (pki )η1 )) handling oracle queries as follows
ORSign(s, V, M ), where s ∈ [1 .. η]; pks ∈ V
Ret RSignsks (V, M )ORSignLR({i0 , i1 }, V, M ), where i0 , i1 ∈ [1 .. η]; i0 6= i1 ; pki0 , pki1 ∈ V
Ret (K, RSignski (V, M ))b
A outputs b0
Ret b0 = b
Figure 15: Ring signature full-key exposure anonymity experiment.
On the other hand, it is straightforward to see that security in the ranon-ind sense implies
security in the ranon-fke sense. Briefly, assume we have an adversary A against the anonymity ofa ring signature scheme in the full key exposure experiment. We can build an adversary B thatuses A to distinguish in the ranon-ind game. The adversary B picks η key pairs pki , ski and givethem to A. Then, it simulates, using these secret keys, adversary A’s signing and corruption oraclesin the natural way. Finally A outputs a pair of indices i0 , i1 , a message M , and a target group
V. In turn, B queries its left-or-right oracle on (ski0 , ski1 , V, M ) and forwards the response to A.
When A outputs a bit, the adversary B returns it.

36