# Count Me In! Extendability for Threshold Ring Signatures
Diego Aranha¹, Mathias Hall-Andersen¹, Anca Nitulescu³,
???
Elena Pagnin², and Sophia Yakoubov¹
1
Aarhus University, Aarhus, Denmark; *{*dfaranha, ma, sophia.yakoubov*}*@cs.au.dk
2
Lund University, Lund, Sweden; elena.pagnin@eit.lth.se
3
Protocol Labs
Abstract. Ring signatures enable a signer to sign a message on behalf of a group *anonymously*,without
revealing her identity. Similarly, threshold ring signatures allow several signers to sign the same message
on behalf of a group; while the combined signature reveals that some threshold *t* of the group members
signed the message, it does not leak anything else about the signers’ identities. Anonymity is a central
feature in threshold ring signature applications, such as whistleblowing, e-voting and privacy-preserving
cryptocurrencies: it is often crucial for signers to remain anonymous even from their fellow signers. When
the generation of a signature requires interaction, this is dicult to achieve. There exist threshold ring
signatures with non-interactive signing — where signers locally produce *partial* signatures which can
then be aggregated — but a limitation of existing threshold ring signature constructions is that all
of the signers must agree on the group on whose behalf they are signing, which implicitly assumes
some coordination amongst them. The need to agree on a group before generating a signature also
prevents others — from outside that group — from endorsing a message by adding their signature to
the statement post-factum.
We overcome this limitation by introducing *extendability* for ring signatures, same-message linkable
ring signatures, and threshold ring signatures. Extendability allows an untrusted third party to take
a signature, and *extend* it by enlarging the anonymity set to a larger set. In the extendable threshold
ring signature, two signatures on the same message which have been extended to the same anonymity
set can then be combined into one signature with a higher threshold. This enhances signers’ anonymity,
and enables new signers to anonymously support a statement already made by others.
For each of those primitives, we formalize the syntax and provide a meaningful security model which
includes di↵erent flavors of anonymous extendability. In addition, we present concrete realizations of
each primitive and formally prove their security relying on signatures of knowledge and the hardness
of the discrete logarithm problem. We also describe a generic transformation to obtain extendable
threshold ring signatures from same-message-linkable extendable ring signatures. Finally, we implement
and benchmark our constructions.
Keywords: Ring Signatures, Threshold Ring Signatures, Anonymity, Flexibility, Extendability
## 1 Introduction
Anonymity has become a requirement in many real-world implementations of cryptographic systems and privacy-enhancing technologies, including electronic voting [26], direct anonymous attestation [9], and private cryptocurrencies [29]. Another compelling scenario is whistleblowing of
organizational wrongdoing. In this case, an insider publishes a *secret* in a manner that convinces the
public of its authenticity, while having his/her identity protected [27]. In all of these applications,
a large *anonymity set*, i.e., set of users who may have performed a certain action, is crucial in order
to not reveal who exactly is behind it.
?
Funded in part by ELLIIT and the Swedish Foundation for Strategic Research grant RIT17-0035.
??
Funded in part by the European Research Council (ERC) under the European Unions’s Horizon 2020 research and
innovation programme under grant agreement No 803096 (SPEC).
---
Group signatures enable any member of a given group to sign a message, without revealing
which member signed. However, group signatures su↵er from the drawback that they require trusted
setup for every group. Ring signatures are a manager-free variant of group signatures. They enable
individual users to sign messages anonymously on behalf of a dynamically chosen group of users,
while hiding the exact identity of the signer(s) [27]. Traditionally, this is enabled by including a
“ring” *R* of public keys (belonging to all possible signers, including the actual signer) as an input
to the signing algorithm; a ring signature does not reveal which of the corresponding secret keys
was used to produce it. There are many ways to construct ring signatures using di↵erent building
blocks: classic RSA [13], bilinear pairings [32,5,12], composite-order groups [28,7], non-interactive
zero knowledge [6,21], and, most recently, quantum-safe isogenies and lattices [14,20,19,4].
*Threshold* ring signatures are a threshold variant of this primitive [8], which allow some *t* signers
to sign a message on behalf of a ring *R* of size larger than *t*. The signature reveals that *t* members of
the ring signed the message, but not the identities of those members. Some threshold ring signature
schemes are *flexible* [24], meaning that even after the threshold ring signature has been produced for
a given ring *R*, another signer from that ring can participate, resulting in a threshold ring signature
for the same ring *R* but with a threshold of *t*+ 1. However, if a signer from *outside* the ring wants
to participate, existing constructions do not support this. All existing constructions of ring and
threshold ring signatures have a common limitation: the ring of potential signers is fixed at the
time of signature generation. In particular, it is not possible to have the added flexibility of publicly
“adjusting” the ring, i.e., to extend the initial ring to a larger one, increasing the anonymity set.
Increasing the size of the set of potential signers not only increases the anonymity provided by the
signature, but also makes threshold systems easier to realize in practice.
To work in practice, standard threshold ring signatures need all of the signers to independently
sign the same message *µ* with the same ring *R*, which must include the public keys of all *t* signers.
We are interested in relaxing this implicit synchronization requirement.
$$
\mu
$$
## 1.1 Our Contributions
In this paper, we introduce a new property of (threshold) ring signatures which we call *extendability*.
A (threshold) ring signature scheme is *extendable* if it allows anyone to enlarge the set of potential
signers of a given signature. Extendable threshold ring signatures are fundamental for whistleblowing, where one party may want to “join the cause” after it becomes public. Extendability, together
with flexibility, enables a signer *A* to join a threshold ring signature which was produced using
an anonymity ring *R* that does not contain *A*. This can be done by first extending the existing
signature to a new ring *R⁰ ◆R[{A}* which contains both the ring used by previous signers as
well as the new signer. Then, thanks to flexibility, the new signer can add their own signature with
respect to the new ring *R⁰* (using skA). (Of course, an observer who has seen signatures under the
old ring *R* and under the new ring *R⁰* will be able to determine *R⁰\R*; this is inherent — since an
observer can always tell which ring a signature is meant for by attempting verification — and can
help that observer narrow down possibilities for the identity of *A*. However, an observer who has
*not* seen a signature under the old ring *R* will learn nothing additional about the identity of *A*.)
$$
\mathcal{R}^{\prime}\supseteq\mathcal{R}\cup\{A\}
$$
$$
\mathcal{R}^{\prime}\backslash\mathcal{R}
$$
$$
\mathcal{R}^{\prime}\ \ \\ {\mathrm{(u s i n g~s k_{A})}}
$$
In addition to drawing formal models, we give the first constructions of *extendable ring signa-*
*tures*, *same-message linkable* extendable ring signatures and extendable *threshold* ring signatures.
We provide a proof of concept implementation of our construction, benchmark the signing and
verification running times as well as the signature size.
---
Constructions from Signatures of Knowledge and Discrete Log We build extendable ring
signatures and same-message linkable extendable ring signatures using signatures of knowledge.
Each signature will include several elements of a group, with the property that all of their discrete
logs cannot be known. (This is because the product of the elements gives a discrete log challenge
which is part of the public parameters.) A signer signs the message with a *signature of knowledge*
that proves that she knows either her own secret key, or the discrete log of one of the elements.
The signer uses her secret key for this (and so can use the element for which the discrete log is
unknown), but for each of the other signers’ public keys in the ring, she includes a signature of
knowledge using the discrete log of one of the elements. Because all of the element discrete logs
cannot be known, a verifier is convinced that at least one signature of knowledge is produced using
a secret key, and that therefore the overall signature was produced by one of the members of the
ring.
We build extendable threshold ring signatures similarly, but by choosing the elements in such
a way that at least *t* of their discrete logs cannot be known without revealing the discrete log of a
challenge element in the public parameters. We enforce this by placing the elements on a polynomial
of appropriate degree.
A Generic Transformation One might hope to build extendable threshold ring signatures by
concatenating *t* extendable ring signatures; however, we would need to additionally prove to the
verifier that the *t* signatures were produced by *t* di↵erent signers. Building such a proof would require
interaction between the signers, and it would be challenging to maintain the proof as the ring is
expanded. Instead, we solve this problem using a primitive which we call a *same-message linkable*
*extendable ring signatures*, where, given two signatures on the same message, it is immediately
clear whether they were produced by the same signer. Our realizations of this primitive provide
linkability without revealing the signer’s identity or resorting to additional zero knowledge proofs
and can be used to construct extendable threshold ring signatures in a generic way.
Implementation We provide an implementation that demonstrates the concrete eciency of
our schemes. The benchmarks place our constructions firmly within the realm of practicality: an
extendable ring signature for a ring with 2048 members can be created in 0.24s.
## 1.2 Related Work
Ring signatures were first introduced by Rivest, Shamir, and Tauman in [27] as a mechanism
to leak secrets anonymously. This initial construction was based on trapdoor permutations, but
other schemes quickly followed. A threshold version of their scheme was proposed the following
year by Bresson *et al.* [8], together with a revised security analysis for the original scheme. By
using RSA accumulators and the Fiat-Shamir transform, a ring signature scheme with signature
sizes independent of the ring size was later constructed by Dodis *et al.* [13]. (A similar scheme in
the threshold setting was described by Munch-Hansen *et al.* [23].) In addition to the hardness of
integer factorization, pairing groups were used in early constructions to obtain ring signatures in
the conventional [5] and identity-based [32] settings.
The first ring signature constructions were all based on the random oracle model, but alternatives proven secure in the common reference string model were later proposed [12,28], including
constructions with sublinear [10] and constant signature size [7]. In the standard model, early constructions were based on 2-round public coin witness-indistinguishable protocols [1], but more recent constructions rely on non-interactive zero-knowledge proofs [6,21]. The transition to post-quantum
cryptography has also motivated revisiting many cryptographic primitives, and ring signatures are
no di↵erent. As with other post-quantum signature schemes, the most popular underlying assumption is hard problems on lattices [14,20,19,4].
Threshold ring signature schemes come in many flavors, with many constructions based on
RSA and bilinear maps and security based on number-theoretic assumptions [18,30,31]; and postquantum schemes based both on lattices [3] and coding theory [22]. The post-quantum schemes
have traditionally relied on the Fiat-Shamir transform, the quantum security of which is not fully
determined. Recent work in threshold ring signatures has provided both improved security definitions [23] and constructions based on the quantum-safe Unruh’s transform [16].
## 2 Background and Preliminaries
## 2.1 Notation
We denote the set of natural numbers by **N** and let the computational security parameter of our
schemes to be *2* **N**. We say that a function is *negligible* (in ), and we denote it by negl,if
c
negl()=*⌦*() for any fixed constant *c>*1. We also say that a probability is *overwhelming*
(in ) if it is greater than or equal to 1 negl. Given two values aR*X*. In our constructions, we denote by GroupGen(1) the algorithm that, given
in input the security parameter, outputs the tuple (*p, g,***G**), where *p* is a 2-bit prime; *g* is a group
generator and **G** is a description of a group of order *p*, **G** = *hgi*. Through out the paper, we assume
solving the Discrete Logarithm Problem in **G** is computationally hard.
$$
\lambda\in\mathbb{N}
$$
$$
\lambda)
$$
$$
c>1
$$
$$
{\tt n e g l}(\lambda)=\varOmega(\lambda^{-c})
$$
$$
(\ln{\boldsymbol{\lambda}})
$$
$$
a\,<\,b
$$
$$
\ \mathrm{1-e g l}
$$
$$
a
$$
$$
b
$$
$$
[a,\ldots,b]
$$
$$
a=1
$$
$$
[1,\ldots,b]
$$
$$
a
$$
$$
X,
$$
$$
a\leftarrow_{R}X
$$
$$
\ 1^{\lambda})
$$
$$
(p,g,\mathbb{O})
$$
$$
p
$$
$$
g
$$
$$
\mathbb{O}
$$
$$
p,\mathbb{G}=\langle g\rangle
$$
## 2.2 Ring Signatures
Ring signatures come as a natural extension of group signature schemes. Group signatures have
the drawback of requiring a trusted authority to act as a group manager. This group manager is
responsible for defining the group of signers and distributing keys to them. (The group manager
can then add and revoke signers over time.) The signers’ keys can be used to anonymously sign
messages on behalf of the entire group. Ring signatures improve on group signatures by not requiring
a trusted group manager. Instead, they allow signers to generate their own key pairs, and to form
groups in an ad-hoc way.
Syntax A ring signature scheme is defined as a tuple of four probabilistic polynomial time algorithms RS =(Setup*,*KeyGen*,*Sign*,*Verify), where the public parameters pp produced by Setup are
implicitly available to KeyGen, Sign and Verify:
Setup(1)*!* pp: Takes a security parameter and outputs a set of public parameters pp.The
public parameters are implicitly input to all subsequent algorithms.
$$
\lambda
$$
KeyGen()*!* (pk*,*sk): Produces a key pair (pk*,*sk).
$$
{\sf K e y G e n}()\to({\tt p k},{\tt s k})
$$
---
⇤
Sign(*µ, {*pkj*}*j2R*,*ski)*!* : Takes a message *µ 2{*0*,*1*}* to be signed, the set of public keys of the
users within the ring of identifiers *R*, and the secret key skiof the signer *i 2R*(i.e., the signer’s
public key must appear in the set *{*pkj*}*j2R). Outputs a signature .
$$
\mu\in\{0,1\}^{*}
$$
$$
\mathsf{S i g n}(\mu,\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}},\mathtt{s k}_{i})\to\sigma;
$$
$$
\mathcal{R}
$$
$$
\mathbf{s}\mathbf{k}_{i}
$$
$$
i\in\mathcal{R}
$$
Verify(*µ, {*pki*}*i2R*,*)*!* accept*/*reject: Takes a message, a set of public keys of the users within
a ring, and a signature .Outputsaccept or reject, reflecting the validity of the signature
on the message *µ* with respect to the ring *R*.
$$
\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}})
$$
$$
\left(\mu,\{\mathtt{p k}_{i}\}_{i\in\mathcal{R}},\sigma\right)\rightarrow
$$
$$
\sigma
$$
$$
\sigma
$$
$$
\sigma
$$
$$
\mathcal{R}
$$
$$
\mu
$$
Naturally, a ring signature scheme should satisfy correctness, meaning that any signature generated by Sign should verify (against the signed message and the original ring). A *secure* ring signature
scheme RS must additionally satisfy (a) unforgeability, meaning that no adversary should be able
to produce a verifying signature without knowledge of at least one signing key corresponding to a
public verification key in the ring, and (b) anonymity, meaning that no adversary should be able
to tell from a signature which ring member produced it. We refer to prior work for the formal
definitions of a ring signature scheme [8,13,17].
## 2.3 Threshold Ring Signatures
Threshold ring signatures are similar to ring signatures, but instead of allowing any one signer
to anonymize themselves among a ring of signers, a threshold ring signature scheme allows any *t*
signers to anonymize themselves among a ring of signers *R* where *t |R|*. A verifier can then check
that at least *t* signers in the ring *R* signed the same message. Note that a ring signature scheme
can be viewed as a threshold ring signature scheme with *t* = 1.
$$
\mathcal{R}
$$
$$
t\leq|\mathcal{R}|
$$
$$
\mathcal{R}
$$
$$
t=1
$$
Syntax There are many di↵erent ways to formalize the threshold ring signature syntax, which
force varying degrees of interaction between the *t* signers. A non-interactive threshold ring signature
scheme is defined as a tuple of five probabilistic polynomial time algorithms (Setup*,*KeyGen*,*Sign*,*
Combisign*,*Verify). The algorithms Setup*,*KeyGen*,*Sign and Verify are syntactically the same as in
a ring signature scheme, with the exceptions that (1) Sign now outputs a *partial* signature ifor
signer *i*, and (2) Verify now additionally takes the threshold *t* as input. The algorithm Combisign,
described below, combines *t* partial signatures into a single threshold signature. It may be run by
any third party, as it does not require any signers’ secrets.
$$
\sigma_{i}
$$
$$
{boldsymbol i},\,{,\,}
$$
Combisign(*{*i*}*i2S✓R)*!* : Takes partial signatures *{*i*}*i2Sfrom *|S|* = *t* signers, and outputs a
combined signature .
$$
\big(\{\sigma_{i}\}_{i\in\mathcal{S}\subseteq\mathcal{R}}\big)\to\sigma\colon
$$
$$
\{\sigma_{i}\}_{i\in\mathcal{S}}
$$
$$
|\mathcal{S}|=t
$$
$$
\sigma
$$
There are also interactive threshold ring signature schemes. In this case Sign (which in this
case also subsumes Combisign) is an interactive protocol run between the signers, which implicitly
requires the signers to be aware of one another’s identities.
Finally, there is a solution in between, where one signer produces the initial signature, and then
the remaining signers pass the signature around, and each “joins” the signature before passing it
on. In such a syntax, each signer must only receive (at most) one message from one other signer,
and send (at most) one message to one other signer. Instead of Combisign, in such a syntax we have
a Join algorithm, described below.
0
Join(*µ, {*pkj*}*j2R*,*sk*,*)*!* : Takes a message *µ*, a set of public keys *{*pkj*}*j2R,whichincludes
the public key of the new signer, the new signer’s secret key sk, and a signature produced
0
by a subset of *R* (with threshold level *t⁰*). Outputs a modified threshold ring signature with
threshold *t⁰* + 1.
$$
\left(\mu,\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}},\mathtt{s k},\sigma\right)\to\sigma^{\prime};
$$
$$
\mu,
$$
$$
\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}}
$$
$$
\mathcal{R}
$$
$$
\sigma
$$
$$
t^{\prime}\big)
$$
$$
\sigma^{\prime}
$$
$$
t^{\prime}+1
$$
---
## 2.4 Signatures of Knowledge
Signatures of Knowledge (SoKs) [11] generalise digital signatures by replacing the public key with an
*instance*, or *statement*, in a NP language. The notion of SoKs mimics digital signatures with strong
existential unforgeability: even if the adversary has seen many signatures on arbitrary messages
under arbitrary statements, she cannot create a new signature (not seen before) without knowing
the witness for the statement in question. Signatures of knowledge are closely related to simulationextractable SNARKs.
We use the definitions of Signatures of Knowledge from a recent work [15] that implicitly
considers only compact signatures. In the following, we will consider an eciently decidable binary
relation *R*. For pairs (*, w*) *2 R* we call the instance/statement and *w* the witness. Let *L*R
be the language consisting of statements for which there exist matching witnesses *w* such that
(*, w*) *2 R*.
$$
\mathcal{R}.
$$
$$
\phi
$$
$$
(\phi,w)\,\in\,{\mathcal{R}}
$$
$$
L\mathcal{A}
$$
$$
\phi
$$
$$
(\phi,w)\in\mathcal{R}
$$
Syntax A SoK for an eciently decidable binary relation *R* is defined as a tuple of PPT algorithms
SoK =(Setup*,*Sign*,*Verify*,*SimSetup*,*SimSign):
$$
\mathcal{R}
$$
Setup(1*, R*)*!* pp: Takes a security parameter and a binary relation *R* and returns public
parameters pp.Theinputpp is implicit to al subsequent algorithms.
$$
{\mathsf{S e t u p}}(1^{\lambda},{\mathcal{B}})\to{\mathsf{p p}}
$$
$$
\lambda
$$
$$
\mathcal{B}
$$
⇤
Sign(*µ, , w*)*!* : Takes as input a message *µ 2{*0*,*1*}*, a statement , and a witness *w*.Outputs
a signature .
$$
{\mathsf{S i g n}}(\mu,\phi,w)\to\sigma\colon\\
$$
$$
\mu\in\{0,1\}^{}
$$
$$
\phi,
$$
$$
w
$$
$$
\sigma
$$
Verify(*µ, ,* )*!* accept*/*reject: Takes as input a message *µ*, a statement , and a signature .
Outputs accept if the the signature is valid, reject otherwise.
$$
\left(\mu,\phi,\sigma\right)
$$
$$
\mu,
$$
$$
\phi,
$$
$$
\sigma
$$
SimSetup(1*, R*)*!* (pp*,*td): A simulated setup which takes as input a relation *R* and returns
public parameters pp and a trapdoor td.
$$
{\mathfrak{t u p}}(1^{\lambda},{\mathcal{R}})\to({\mathfrak{p p}},{\mathfrak{t d}})
$$
$$
\mathcal{R}
$$
0
SimSign(td*,µ,*)*!* : A simulated signing algorithm that takes as input a trapdoor td, a message
0
*µ* and a statement and returns a simulated signature .
$$
(\mathtt{t d},\mu,\phi)\to\sigma^{\prime}.
$$
$$
\mu
$$
$$
\sigma^{\prime}
$$
$$
\phi
$$
Security Model We require a scheme SoK =(Setup*,*Sign*,*Verify*,*SimSetup*,*SimSign)tohavethree
properties: *correctness*, *simulatability* and *simulation extractability*. Below we give an intuition of
what these properties o↵er. We refer the reader to Groth and Maller [15] for formal definitions.
$$
\ mathrm S S o K=({\sf S e t u p},{\sf S i g n}
$$
Correctness: Informally, this implies that a signer holding a valid witness can always produce a
signature that will convince the verifier.
Simulatability: This property essentially states that the verifier should not learn anything about
the witness from the signature. The secrecy of the witness is modeled by the ability to simulate
signatures without the witness. More precisely, we say a signature of knowledge is simulatable
if an an adversary is unable to distinguish real public parameters and signatures from the
ones generated by a simulator (that generates public parameters together with an associated
trapdoor, and produces signatures using the trapdoor but without a witness).
Simulation Extractability: This notion guarantees that an adversary is not able to issue a new
signature unless it knows a witness. This should hold even if the adversary gets to see signatures
on arbitrary messages under arbitrary statements, which may include false statements. Even
under this strong attack model, we require that whenever the adversary outputs a valid signature
not queried before, it is possible to extract a witness for the signature.
---
## 3 Extendable Ring Signatures
Ring signatures enable a signer to generate a signature while hiding her identity within a ring of
potential signers. Even though the ring of potential signers *R* can be arbitrary⁴ — realizing ad-hoc
anonymity sets — existing constructions do not let a third party increase the size of *R* after the
signature is produced. Once a signature is generated, it is not possible to “extend” it to a larger
anonymity set; in other words, ring signatures do not allow one to modify a signature and obtain
a new signature for the same message but with a wider set of potential signers. Our notion of
extendability aims to allow exactly this, while preserving signer anonymity.
We introduce the notion of extendability for ring signature schemes (3.1), a security model for
anonymous extendability (Section 3.2) and present a realization based on standard assumptions
(Section 3.3).
## 3.1 Syntax
An extendable ring signature scheme (ERS) is a ring signature scheme that has an additional
algorithm, Extend, that allows any third party to enlarge the ring of potential signers of a given
signature:
0
Extend(*µ, {*pk*}*i2R*,,{*pk*}*j2R*0*)*!* : Takes a message, a set of public keys (indexed by the ring
i j
*R*), a signature , and a second ring of public keys (indexed by *R⁰*). It outputs a modified
0
signature which verifies under *R[R⁰*.
$$
\left(\mu,\{\mathtt{p k}_{i}\}_{i\in\mathcal{R}},\sigma,\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}^{\prime}}\right)\to\sigma^{\prime}
$$
$$
\mathcal{R}\cup\mathcal{R}^{\prime}
$$
$$
\sigma^{\prime}
$$
*Remark 1.* Consider an ERS scheme where Extend can be repeatedly applied to extend a signature a
polynomial number of times. In this case, we can have a very simple instantiation where Sign always
produces a signature for the singleton ring *{*pk*}* containing only the signer’s public key pk, and
Extend is called only on singleton extension rings, i.e., *|R⁰|* = 1. A signature for the singleton ring
can be extended to any ring by having the signer iteratively apply Extend with a single additional
public key.
$$
|\mathcal{R}^{\prime}|=1
$$
(1) (2) (l)
For the following definitions, we use ladders of rings, i.e., tuples lad =(*i, R, R,...,R*),
(1) (2) (l)
where *i* is a signer identity, and the rings *R, R,...,R* are all sets of signer identifiers. In
addition, we make use of an algorithm Process(*µ,*Lkeys*,*lad), that we describe in Figure 1. As the
name suggests, this algorithm processes a ladder lad on a given message *µ* using keys from Lkeys
(1)
(the list of generated keys). Process signs *µ* using skiunder the ring *R*, and extends the signature
to all the subsequent rings (using keys stored in the list Lkeys). Process returns an extendable ring
signature , which is the output of the last operation.
$$
=,i mathcal R{}^{(1)},\mathcal{R}{}^{(2)},\ldots,\mathcal{R}{}^{(l)})
$$
$$
\mathcal{R}^{(1)},\mathcal{R}^{(2)},\dots,\mathcal{R}^{(l)}
$$
$$
(\mu,\mathsf{L}_{\mathsf{k e y s}},\mathsf{l a d})
$$
$$
\ _{\ y e y s}
$$
$$
\mathbf{s k}_{i}
$$
$$
\mathcal{R}^{(1)}
$$
$$
L_{\mathrm{k e y s}})
$$
For correctness, we require that any — possibly extended — signature output by Process verifies
(l)
for the given message, under the final ring *R*.
$$
\mathcal{R}^{(l)}
$$
Definition 1 (Correctness for ERS). *An extendable ring signature scheme ERS is said to be*
⇤
*correct if, for all security parameters 2* **N***, for any message µ 2{*0*,*1*}, for any ladder* lad =
(1) (2) (l) (1)
(*i, R, R, ···, R*) *where i 2R and l>*0*,itmustholdthat:*
2 3
$$
i!f,
$$
$$
\lambda\in\mathbb{N}
$$
$$
\mu \in \{0, 1 \} ^ {*}
$$
$$
(i,\mathcal{R}^{(1)},\mathcal{R}^{(2)},\cdots,\mathcal{R}^{(l)})
$$
$$
i\in\mathcal{R}^{(1)}
$$
$$
l>0
$$
$$
\begin{array}{c}\end{array}
$$
4
The ring *R* should of course contain the signer’s identity.
$$
\mathcal{R}
$$
---
Fig. 1: The Process algorithm for extendable ring signatures.
## 3.2 Security Model
Definition 2 (ERS). *An extendable ring signature scheme is secure if it satisfies correctness (Def-*
*inition 1), unforgeability (Definition 3), anonymity (Definition 4), and some notion of anonymous*
*extendability (described below).*
Unforgeability Extendable ring signatures inherit their unforgeability requirement from regular
ring signatures: no adversary should be able to produce a signature unless they know at least one
secret key belonging to a party in the ring. Notably, the unforgeability experiment for ERS (cmEUF,
detailed in Figure 2) needs to take into account that the adversary can arbitrarily expand the ring
associated to a signature. To rule out trivial attacks derived with this strategy, the adversary does
not break unforgeability if the candidate forgery could be generated by extending the outcome of
cmEUF
a signing query (line 5 in ExpA,ERS()). Additionally, to account for the key duplication attack
(where an adversary registers an existing public key to a new identity), instead of simply checking if
the identities in the output ring are among the corrupted ones, the experiment checks if the *public*
*keys* belonging to the parties involved in the adversary’s output ring are among the corrupted ones
(line 7, Figure 2).
Definition 3 (Unforgeability for ERS). *An extendable ring signature scheme ERS is said to*
*be unforgeable if for all PPT adversaries A taking part in the unforgeability experiment (* cmEUF
*in Figure 2), the success probability is negligible, i.e.:*
$$
\operatorname*{P r}\left[\sf E x p_{\mathcal{A},E R S}^{c m c U F}(\lambda)=w i n\right]\leq n e g l.
$$
Anonymous Extendability For extendability, we consider security notions related to anonymity
(thus the name anonymous extendability). We define an experiment that is general enough to
support three di↵erent flavors of anonymous extendability: the standard *anonymity* notion, where
no extension happens; *weak extendability*, where it is not possible to identify the original subring cmEUF
ExpA,ERS()
1 : Lkeys*,* Lcorr*,* Lsign?
2 : pp ERS*.*Setup(1)
3 : *O {O*Sign*,O*KeyGen*,O*Corrupt*}*
⇤ ⇤ ⇤ O
4 :( *µ, R,*) *A* (pp)
// rule out trivial wins due to ring expansion
⇤
5 : if *9* (*µ, R, ·*) *2* Lsign*s.t.*
*{*pkj*}j2R ✓{*pkj*}j2R⇤*
6 : return lose
// rule out trivial wins due to key duplication
7 : if *{*pkj*}j2R⇤ \{*pkj*}j2*Lcorr6= ?
8 : return lose
OKeyGen(i, pk)
// standard key generation for a new identifier *i*
1 : if pk =*?*
2 :( pki*,*sk*i*) ERS*.*KeyGen()
3 : LkeysLkeys*[{*(*i,* pki*,*sk*i*)*}*
4 : else
// *A* over-writes an identifier with malicious keys
5 : Lcorr Lcorr *[{i}*
6 : pkipk
7 : LkeysLkeys*[{*(*i,* pki*, ?*)*}*
8 : return pki
OSign(µ, R,i)
⇤ ⇤
9 : if Verify(*µ, {*pkj*}j2R⇤,*)=reject
1 : if (*i 2* L *_ i/ 2R*): return*?*
10 : return lose
11 : return win
OCorrupt(i)
1 : if (*i,* pki*,*sk*i*) *2* Lkeysand sk*i* 6=*?*
2 : Lcorr Lcorr *[{i}*
corr
// check that all keys in the query are initialized
2 : for all *j 2R*
3 : if (*j,* pkj*, ·*) *2/* Lkeys
4 : return*?*
5 : ERS*.*Sign(*µ, {*pkj*}j2R,*sk*i*)
6 : LsignLsign*[{*(*µ, R,i*)*}*
3 : return (pki*,*ski)
7 : return
4 : return? // *i*f *i* has not been *i*nitialized.
$$
\mathsf{L}_{\mathsf{k e y s}},\mathsf{L}_{\mathsf{c o r r}},\mathsf{L}_{\mathsf{s i g n}}\leftarrow\varnothing
$$
$$
{\mathtt{p k}}=\bot
$$
$$
\mathtt{p p\ \leftarrow E R S.S e t u p(1^{\lambda})}
$$
$$
(\mathtt{p k}_{i},\mathtt{s k}_{i})\leftarrow\mathtt{E R S.K e y G e n}(
$$
$$
(\boldsymbol{\mu}^{*},\mathcal{R}^{*},\boldsymbol{\sigma}^{*})\gets\mathcal{A}^{O}(\mathtt{p p})
$$
$$
\mathsf{L}_{\mathsf{k e y s}}\leftarrow\mathsf{L}_{\mathsf{k e y s}}\cup\left\{\left(i,\mathtt{p k}_{i},\mathtt{s k}_{i}\right)\right\}
$$
$$
O \leftarrow \{O \mathrm {S i g n}, O \mathrm {K e y G e n}, O C o r r u p t \}
$$
$$
\mathbf{i f}\ \exists\ (\mu^{*},\mathcal{R},\cdot)\in\mathsf{L}_{\mathsf{s i g n}}\ {}\ s.t.
$$
$$
\mathsf{L_{c o r r}}\leftarrow\mathsf{L_{c o r r}}\cup\{i\}
$$
$$
\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}}\subseteq\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}^{*}}
$$
$$
\mathrm {p k} _ {i} \leftarrow \mathrm {p k}
$$
$$
\mathsf{L}_{\mathsf{k e y s}}\leftarrow\mathsf{L}_{\mathsf{k e y s}}\cup\left\{\left(i,\mathtt{p k}_{i},\bot\right)\right\}
$$
$$
\mathbf{p}\mathbf{k}_{i}
$$
$$
\big\{\mathtt{p k}_{j}\big\}_{j\in\mathcal{R}^{*}}\cap\big\{\mathtt{p k}_{j}\big\}_{j\in\mathsf{L}_{\mathsf{c o r r}}}\neq\varnothing
$$
$$
(i\in\mathsf{L_{c o r r}}\vee i\notin\mathcal{R})
$$
$$
\mathsf{i f}\ \mathsf{V e r i f y}\ \bigl(\mu^{*},\{\mathfrak{p k}_{j}\}_{j\in\mathcal{R}^{*}},\sigma^{*}\bigr)=\mathtt{r e j e c t}
$$
$$
j\in\mathcal{R}
$$
$$
(j,\mathtt{p k}_{j},\cdot)\notin
$$
$$
(i,\mathtt{p k}_{i},\mathtt{s k}_{i})\in\mathsf{L}_{\mathsf{k e y s}}
$$
$$
\neq\bot
$$
$$
\mathsf{L}_{\mathsf{c o r r}}\leftarrow\mathsf{L}_{\mathsf{c o r r}}\cup\{i\}
$$
$$
\sigma\leftarrow\mathtt{E R S.S i g n}(\mu,\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}},\mathtt{s k}_{i})
$$
$$
\mathsf{L}_{\mathsf{s i g n}}\leftarrow\mathsf{L}_{\mathsf{s i g n}}\cup\{(\mu,\mathcal{R},i)\}
$$
$$
(\mathtt{p k}_{i},\mathtt{s k}_{i})
$$
Fig. 2: Existential Unforgeability under Chosen Message Attack for (Extendable) Ring Signatures (security experiment and oracles). Our key generation oracle allows *A* to register signers with arbitrary public keys (i.e., it also acts
as a registration oracle).
of an extended signature; and *strong extendability*, where it is not possible to tell what sequence of
extensions a signature has undergone.
⇤ ⇤
For standard anonymity we consider adversaries that output ladders (lad0*,*lad1in line 5 of
ANEXT
ExpA,ERSin Figure 3) each containing only one ring. To avoid making the game trivial to win,
the two rings need to be identical (line 7 of Chalb). Moreover since the extension algorithm is never
called (*l₀* = *l₁* = 1 in this case), it is clear that — with this restriction on the adversary’s input to
the challenger — our ANEXT experiment is the same as the standard anonymity one.
$$
\mathsf{E x p}_{\mathcal{A},\mathsf{E R S}}^{\mathrm{A N E T}}
$$
$$
\mathrm{(1a d_{0}^{*},1a d_{1}^{*}}
$$
$$
\boxed{5}
$$
$$
(l_{0}=l_{1}=1
$$
Definition 4 (Anonymity for ERS). *An extendable ring signature scheme is said to be anony-*
*mous if for all PPT adversaries A taking part in the anonymous extendability experiment (* ANEXT
⇤ ⇤
*in Figure 3) and submitting to the challenger ladders of the type* lad0=(*i₀, R*)*,*lad1=(*i₁, R*)*, it*
*holds that the success probability of A is negligibly close to random guessing. i.e.,:*
$$
\ {tt l l a}_{0}^{*}=(i_{0},\mathcal{R}),{\tt l a d}_{1}^{*}=(i_{1},\mathcal{R})
$$
$$
\textstyle\operatorname*{P r}\left[\sf{E x p}_{\mathcal{A},E R S}^{A N E X T}(\lambda)=w i n\right]\leq\frac{1}{2}+n e g l.
$$
For weak anonymous extendability we require the adversary to submit ladders of rings to the
challenger such that each ladder only contains two rings. In other words, the adversary chooses two
(1) (2) (1) (2) (1) (2) (1)
(possibly distinct) two-ring ladders (*i₀, R₀, R₀*) and (*i₁, R₁, R₁*) such that *R₀ [R₀* = *R₁ [*
$$
(i_{0},\mathcal{R}_{0}^{(1)},\mathcal{R}_{0}^{(2)})
$$
$$
(i_{1},\mathcal{R}_{1}^{(1)},\mathcal{R}_{1}^{(2)},
$$
$$
\mathcal{R}_{0}^{(1)}{\cup}\mathcal{R}_{0}^{(2)}=\mathcal{R}_{1}^{(1)}{}
$$
---
ANEXT
ExpA,ERS()
1 : *b R {*0*,*1*}*
2 : Lkeys*,* Lcorr*,* Lsign?
3 : pp ERS*.*Setup(1)
⇤ ⇤ ⇤
Chal*b*(µ,lad0,lad1)
⇤ (1) (0l0)
1 : parse lad0=(*i₀, R*0*,...,R*)
⇤ (1) (1l1)
2 : parse lad1=(*i₁, R*1*,...,R*)
// challenge signing keys should not be corrupted
// handle of oracles, for compact notation3 : if *i₀,i₁ 2* Lcorr return*?*
4 : *O {O*Sign*,O*KeyGen*,O*Corrupt*}* // sign and extend following the instructions
⇤ ⇤ ⇤ O
5 :( *µ,*lad0*,*lad1) *A* (pp)
⇤ ⇤ ⇤
6 :¯ Chal*b*(*µ,*lad0*,*lad1)
⇤ O
7 : *b A* (¯)
// in both ladders
⇤
4 : 0 Process(*µ,*Lkeys*,*lad0)
⇤
5 : 1 Process(*µ,*Lkeys*,*lad1)
// make sure *A* did not corrupt the challenge6 : if 0 =*?* or 1 =*?* return*?*
// keys during the second query phase// check that ladders end with the same ring
8 : if *i₀ 2* Lcorr *_ i₁ 2* Lcorr
9 : return lose
⇤
10 : if *b* 6= *b*
11 : return lose
12 : return win
(1) (0l0) (1) (1l1)
7 : if R0[···[R 6= R1[···[R
8 : return?
// set the challenge signature according to *b*
9 :¯ b
10 : return ¯
$$
{\tt l a d}_{0}^{*}=(i_{0},\mathcal{R}_{0}^{(1)},\ldots,\mathcal{R}_{0}^{(l_{0})})
$$
$$
\mathsf{L}_{\mathsf{k e y s}},\mathsf{L}_{\mathsf{c o r r}},\mathsf{L}_{\mathsf{s i g n}}\leftarrow\varnothing
$$
$$
{\tt l a d}_{1}^{*}=(i_{1},\mathcal{R}_{1}^{(1)},\ldots,\mathcal{R}_{1}^{(l_{1})})
$$
$$
\mathtt{p p\ \leftarrow E R S.S e t u p(1^{\lambda})}
$$
$$
O\leftarrow\{O\mathsf{S i g n},O\mathsf{K e y G e n}.
$$
$$
i_{0},i_{1}\in\mathsf{L}_{\mathsf{c o r r}}
$$
$$
\left(\mu^{*},\mathtt{l a d}_{0}^{*},\mathtt{l a d}_{1}^{*}\right)\leftarrow\mathcal{A}^{O}(\mathtt{p p})
$$
$$
\sigma_{0}\leftarrow\sf{P r o c e s s}(\mu,L_{k e y s},l a d_{0}^{*})
$$
$$
\bar{\sigma}\leftarrow\mathsf{C h a l}_{b}(\mu^{*},\mathtt{l a d}_{0}^{*},\mathtt{l a d}_{1}^{*})
$$
$$
\boldsymbol{b}^{*}\leftarrow\boldsymbol{\mathcal{A}}^{O}(\bar{\boldsymbol{\sigma}})
$$
$$
\sigma_{0}=\bot
$$
$$
\sigma_{1}=\bot
$$
$$
i_{0}\in\mathsf{L_{c o r r}}\vee i_{1}\in\mathsf{L_{c o r}}
$$
$$
\mathcal{R}_{0}^{(1)}\cup\dots\cup\mathcal{R}_{0}^{(l_{0})}\neq\mathcal{R}_{1}^{(1)}\cup\dots\cup\mathcal{R}_{1}^{(l_{1})}
$$
$$
b^{*}\neq b
$$
Fig. 3: Anonymity and Anonymous Extendability for Extendable Ring Signatures. The oracles *O*Sign, *O*KeyGen and
*O*Corrupt are defined in Figure 2.
(2)
*R₁* = *R*. The adversary breaks weak anonymous extendability if, given an extended signature for
the super-ring *R*, it is able to identify (with better accuracy than random guessing) which ladder
was used.
$$
\mathcal{R}_{1}^{(2)}=\mathcal{R}
$$
Definition 5 (Weak Anonymous Extendability for ERS). *An extendable ring signature*
*scheme ERS is said to be weakly anonymous extendable if for all PPT adversaries A taking part*
*in the anonymous extendability experiment (* ANEXT *in Figure 3) and submitting to the challenger*
⇤ (1) (2) ⇤ (1) (2)
*ladders of the type* lad₀ =(*i₀, R₀, R₀*)*,*lad₁ =(*i₁, R₁, R₁*)*, it holds that the success probabil-*
*ity of A is negligibly close to random guessing, i.e.:*
$$
F i g u r e[\mathfrak{g}]
$$
$$
\mathtt{a d}_{0}^{*}=(i_{0},\mathcal{R}_{0}^{(1)},\mathcal{R}_{0}^{(2)}),\mathtt{l a d}_{1}^{*}=(i_{1},\mathcal{R}_{1}^{(1)},\mathcal{R}_{1}^{(2)})
$$
$$
\textstyle\operatorname*{P r}\left[\sf x p p_{{\mathcal{A}},\ \mathrm E R S}^{\sf A N E X T}(\lambda)=\ w i n\right]\leq\ \frac{1}{2}+\tt n e g l.
$$
*Remark 2.* Weak anonymous extendability requires that an adversary not be able to distinguish
between two extended signatures, as long as (a) they were extended to the same ring, and (b) they
were both only extended once. One might also consider a form of weak extendability where, instead
of limiting the signatures to a single extension, we let them be extended any number of times, as
long as their numbers of extensions are the same.
Finally, for strong anonymous extendability we consider adversaries that output any other type
of ladders that culminate in the same ring. In particular, we could have *l₀* 6= *l₁*. Notice that strong
anonymous extendability implies both weak anonymous extendability and anonymity.
$$
l_{0}\neq l_{1}
$$
Definition 6 (Strong Anonymous Extendability for ERS). *An extendable ring signature*
*scheme is said to be strongly anonymous extendable if for all PPT adversaries A taking part in the*
*anonymous extendability experiment (Figure 3), it holds that:*
$$
(F i g u r e{\mathbb{}}{\mathbb{B}})
$$
---
$$
\Pr \left[ \operatorname {E x p} _ {\mathcal {A}, \mathbf {E R S}} ^ {\mathrm {A N E X T}} (\lambda) = \mathrm {w i n} \right] \leq \frac {1}{2} + \mathrm {n e g l}.
$$
We remark that strong extendability implies that the act of extending a ring signature is seamless, i.e., an adversary is not able to distinguish between a fresh ring signature (returned by Sign),
and an extension of it (returned by Extend). This is covered in the strong extendability game for
*l₀* = 1 and *l₁ >* 1.
$$
l_{0}=1
$$
$$
l_{1}>1
$$
## 3.3 ERS from Signatures of Knowledge and Discrete Log
In what follows, we exhibit an ecient realization of extendable ring signature scheme from prime
order groups and signatures of knowledge.
Our Construction in a Nutshell The setup generates a prime-order group **G** = *hgi*, a random
group element *H*R**G** and public parameters for a SoK scheme for the relation
$$
\mathbb{G}=\langle g\rangle
$$
$$
H\leftarrow_{R}\mathbb{G}
$$
$$
\mathcal {R} _ {\mathbb {G}} \left(\phi = (h, \mathrm {p k}) , w = x\right) = \left\{g ^ {x} = h \vee g ^ {x} = \mathrm {p k} \right\}.
$$
Intuitively, *R*Grequires that the witness be either the discrete log of pk (which is the corresponding
secret key), or the element *h*. The signing procedure simply samples a random value tdR**Z**p,
td td
creates an element *h* := *H · g* (which implies that *h · g* = *H*), and computes a signature
of knowledge *⇡* for (*h,* pk)usinghersecretkeysk. The signature contains td, and a set *P* =
*{*(*h,* pk*,⇡*)*}*. Extending works essentially like signing, except that the extender uses the other kind
0 0 td0
of witness. Concretely, the extender samples a new td, computes *h* = *g* and a signature of
0 0
knowledge *⇡* for the pk⁰ she wishes to add to the ring, using td⁰ as the witness. The tuple (h⁰,pk⁰,⇡)
Q
0 td
is added to *P,* and td is replaced by td td. The verification checks that *H* = *g · h*ifor all
*h*ipresent in *P*, and that all *⇡*iverify. This ensures that at least one of the *⇡*iwas produced using
skias a witness (otherwise we would be able to extract *dlog*(*H*)). A formal description of this
construction is given in Figure 4.
$$
\mathcal{R}_{\mathbb{G}}
$$
$$
\leftarrow_{R}\mathbb{Z}_{p},
$$
$$
h\,:=\,H\cdot g^{-\mathsf{t d}}
$$
$$
h\cdot g^{\mathsf{t d}}\,=\,H)
$$
$$
\pi
$$
$$
P\,=
$$
$$
\{(h, \mathrm {p k}, \pi) \}
$$
$$
\mathsf{t d^{\prime}},
$$
$$
h^{\prime}=g^{\mathsf{t d}^{\prime}}
$$
$$
\pi^{\prime}
$$
$$
\mathbf{p k}^{\prime}
$$
$$
(h^{\prime},\mathtt{p k}^{\prime},\pi^{\prime})
$$
$$
\mathsf{t d}^{\prime}
$$
$$
\tt{t d-t d}^tt{prime}..
$$
$$
\ =g^{\tt{t d}}\cdot\prod h\_\,{}
$$
$$
h_{i}
$$
$$
\pi_{i}
$$
$$
\pi_{i}
$$
$$
\mathbf{s k}_{i}
$$
$$
d l o g(H)
$$
Theorem 1. *Assuming that* SoK *is a secure signature of knowledge scheme, and that the discrete*
*log problem is hard in the group* **G***, then the scheme* ERS =(Setup*,*KeyGen*,*Sign*,*Verify*,*Extend)
*described in Figure 4 is an extendable ring signature scheme that satisfies* correctness *(Definition 1),*
unforgeability *(Definition 3), and* strong anonymous extendability *(Definition 6).*
$$
(D\bar{e e n n i t i o n}\underline{{\mathcal{B}}})
$$
*Proof.* The correctness of the construction follows by inspection.
Unforgeability To prove unforgeability, we present a sequence of hybrid games at the end of which
the reduction is able to extract a solution to a discrete logarithm challenge from *A*’s forgery with
high-enough probability. Essentially this involves: embedding a discrete logarithm into *H*;moving
to the simulatable setup for the SoK; replacing all signatures of knowledge with simulated ones;
⇤
and using the witness extracted from *⇡* to learn *dlog*(*H*).
$$
H;
$$
$$
\pi^{*}
$$
In more detail, following the statement of Definition 3, we want to prove that an adversary *A*
can successfully forge a signature only with negligible probability. For the sake of contradiction,
assume that *A* wins the unforgeability game with non-negligible probability. We want to exhibit
a reduction *B* that interacts with *A* — playing the role of the unforgeability challenger — and
extracts from *A*’s forgery a solution to a discrete log challenge. We describe a sequence of hybrids
in each of which the behavior of *B* changes in ways that *A* should not be able to detect. In the final
hybrid, *B* can use *A* to solve a discrete log challenge.
$$
\ ^{\ {}\ }\mathrm{}\mathrm{{S}}
$$
---
ERS*.*Setup(1) *7!* pp
ERS.Verify(µ, {pkj}*j2R*,) 7! accept/reject
1 :( *p, g,***G**) GroupGen(1) 1 : parse =(nonce*,*td*,P* = *{*(*h*i*,*pki*,⇡i*)*}*i2R0)
Y
td
2 : SoK*.*pp SoK*.*Setup(1*, R***G**) 2 : if *H 6*= *g · h*i : return reject
3 : *H* R **G**
*i2R0*
4 : return pp := (SoK*.*pp*,g,H*) 3 : if *{*pkj*}j2R* 6= *{*pki*}*i2R0:
ERS*.*KeyGen() *7!* (pk*,*sk)
1 : sk **Z***p*
sk
2 : pk := *g*
3 : return (sk*,*pk)
ERS*.*Sign(*µ,* sk) *7!*
1 : td *R* **Z***p*
td
2 : *h* := *H · g*
// signer does not know *dlog*(*h*)
// compute the signature
3 : nonce *R {*0*,*1*}*
4 : := (*h,* pk)
5 : *w* := sk
return reject
4 : for *i 2R⁰* :
*i* := (*hi,*pki)
if SoK*.*Verify((nonce*,µ*)*, R,i,⇡i*)=reject :
return reject
5 : return accept
0
ERS.Extend(µ, {pkj}*j2R*,,pk) 7!
1 : if pk *2{*pkj*}j2R* : return*?*
2 : parse =(nonce*,*td*,P* = *{*(*hi,*pki*,⇡i*)*}*i2R0)
3 : td⁰ *R* **Z***p* // pick a trapdoor
4 : td td td⁰ (mod *p*)
td*0*
5 : *h* := *g* // to simulate using the trapdoor
6 : := (*h,* pk)*,w*:= td⁰
6 : ⇡ SoK.Sign((nonce,µ), R,*,w*) 7 : *⇡* SoK*.*Sign((nonce*,µ*)*, R,,w*)
7 : *P* := *{*(*h,* pk*,⇡*)*}*
8 : return := (nonce*,*td*,P*)
8 :add( *h,* pk*,⇡*)to*P* // update the signature
0
9 : return := (nonce*,*td*,P*)
$$
H\neq g^{\tt t d}\cdot\prod_{i\in{\cal R}^{\prime}}h_{i}
$$
$$
\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}}\neq\{\mathtt{p k}_{i}\}_{i\in\mathcal{R}^{\prime}}
$$
$$
H\leftarrow_{R}\mathbb{G}
$$
$$
i\in\mathcal{R}^{\prime}:
$$
$$
\mathtt{s k}\leftarrow\mathbb{Z}_{p}
$$
$$
\mathfrak{j}_{i}:=(h_{i},\mathtt{p k}_{i})
$$
$$
{mathtt{p k}}:=g^{\mathtt{s k}}
$$
$$
\mathsf{I}\big(\mu,\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}},\sigma,\mathtt{p k}\big)\mapsto\sigma^{\prime}
$$
$$
\mathsf{t d}\leftarrow_{R}\mathbb{Z}_{p}
$$
$$
h:=H\cdot g^{-\mathtt{t d}}
$$
$$
\mathbf{p a r s e}\ \sigma=\ (\mathbf{n o n c e},\mathbf{t d},P=\{(h_{i},\mathbf{p k}_{i},\pi_{i})\}_{i\in\mathcal{R}^{\prime}})
$$
$$
h:=g^{\mathtt{t d}^{\prime}}\ //
$$
$$
\phi:=(h,\ {mathtt p p k}),w:={\mathtt{t d}}^{\prime}
$$
$$
\pi\leftarrow\mathtt{S o K.S i g n}((\mathtt{n o n c e},\mu),\mathscr{B},\phi,w)
$$
$$
(h,\mathtt{p k},\pi)
$$
Fig. 4: Extendable Ring Signatures from Signature of Knowledge and Discrete Log. The relation used by the SoK
x x
scheme is *R***G** = *{*(*, w*)=(*h,* pk*,x*) *2* **G** *⇥* **G** *⇥* **Z***p* : *g* = *h _ g* = pk*}.*
$$
\mathcal{K}_{\mathbb{G}}=\{(\phi,w)=(h,\mathtt{p k},x)\in\mathbb{G}\times\mathbb{G}\times\mathbb{Z}_{p}:g^{x}=h\vee g^{x}=\mathtt{p k}\}
$$
*G₀*: This is precisely the unforgeability game described in Figure 2.
$$
{\mathcal{G}}_{0}.
$$
*G₁*: This is the same as *G₀* except that *H* is set to be the challenge *B* receives from its dlog
challenger. *A* cannot distinguish this hybrid from the previous one, since its views in the two
games are identically distributed.
$$
\mathcal{G}_{1}
$$
$$
\mathcal{G}_{0}
$$
*G₂*: This is the same as *G₁* except that the real setup for the signature of knowledge, *⌃.*Setup,is
replaced by the simulated setup. Notably, the simulated setup gives *B* a trapdoor that allows
it to (a) simulate signatures without knowledge of a witness, and (b) extract a witness from
any signature produced by the adversary. In this game, *B* additionally replaces all signatures of
knowledge with simulated signatures. In particular, this means that none of the signatures of
knowledge depend on any honest party secret keys.
$$
\mathcal{G}_{2},
$$
$$
{\mathcal{G}}_{1}
$$
If *A* can distinguish this game from the previous one, *B* can use *A* to break the simulatability
property of the signature of knowledge.
*G₃*: This is the same as *G₂* except that, when receiving a signing oracle query (*µ, i, R*), *B* randomly
picks the index *j 2R*such that it doesn’t know the discrete log of *h*j(instead of using *i*
as instructed by *A* in the signing oracle query). Since all signatures of knowledge are already
simulated (and thus no witnesses — in the form of either discrete logs or secret keys — are
$$
\mathcal{G}_{2}
$$
$$
\mathcal{G}_{3}
$$
$$
j\in\mathcal{R}
$$
$$
h_{j}
$$ used), *A* cannot distinguish this hybrid from the previous one since its views in the two games
are identically distributed.
*G₄*: This is the same as *G₃* except that, if the candidate forgery returned by the adversary contains
any signatures of knowledge on statements already contained in simulated signatures (returned
in response to signing oracle queries) *where B does not know the discrete log of h*i, *B* aborts.
$$
{\mathcal{G}}_{3}
$$
$$
{\mathcal{G}}_{4}.
$$
With polynomial probability, *B* does not abort in this game. This is true since, for any signing
oracle query (*µ, i, R*), the candidate forgery cannot be on (a) the same message and (b) on a
superset of *R*; so, from any simulated signature, only a subset of statements can be included.
Since every simulated signature will be on a di↵erent nonce with overwhelming probability, only
statements from a single simulated signature will be included. Exactly one random *h*iin a given
1
simulated signature has a discrete log not known to *B*, and with probability at least, that
|R|
one is not included in the candidate forgery.
$$
h_{i}
$$
$$
(\mu,i,\mathcal{R})
$$
$$
{\cal R};
$$
$$
h_{i}
$$
$$
\frac{1}{|\mathcal{R}|}
$$
*G₅*: This is the same as *G₄* except that, *i*f the candidate forgery returned by the adversary contains
only signatures of knowledge on statements already contained in simulated signatures, *B* aborts.
If *B* aborts in this game but not in the previous one, *A* can be used to solve the discrete log
problem. Since *B* knows the discrete log of each *h*iused in the candidate forgery, if the product
td
of the *h*istimes*g* (for a known td) gives *H*, *B* has learned the discrete log of *H*.
$$
{mathcal G_{{}55}};
$$
$$
{\mathcal{G}}_{4}
$$
$$
\mathcal{A}
$$
$$
g^{\mathrm{t d}}
$$
$$
h_{i}\mathbf{s}
$$
$$
h_{i}
$$
$$
H
$$
⇤
*G₆*: This is the same as *G₅* except that, for a randomly-chosen *i*, when prompted to generate a
⇤ e
key pair for *i*, *B* returns pki⇤ := *H* for a random exponent *e* **Z**p(no matching secret key is
⇤
generated). If *A* submits a corruption query for *i*, *B* aborts. When *A* outputs a valid forgery
⇤ ⇤ ⇤ ⇤
(*µ, R,*), *B* checks that *i 2R*; otherwise it aborts.
$$
\mathcal{G}_{5}
$$
$$
\mathcal {G} _ {6}
$$
$$
i^{*}
$$
$$
i^{*}
$$
$$
\mathtt{p k}_{i^{*}}:=H^{e}
$$
$$
e\gets\mathbb{Z}_{p}
$$
$$
i^{*}
$$
$$
(\mu^{*},\mathcal{R}^{*},\sigma^{*})
$$
$$
i^{*}\in\mathcal{R}
$$
⇤
In order for *A* to win, there must exist at least one uncorrupted party in *R*; so, *B* does not
abort in this game with probability at least 1*/q*KG,where*q*KGis the number of *A*’s queries to
the key generation oracle.
$$
\mathcal{R}^{*}
$$
$$
1/q_{\mathsf K G}
$$
*G₇*: This is the same as *G₅* except that *B* calls the extractor *"*Afor SoK to extract witnesses *w*i
⇤
from each signature of knowledge *⇡*iin (which are not simulated signatures).
$$
{\mathcal{G}}_{7}
$$
$$
\mathcal{G}_{5}
$$
$$
\varepsilon_mathcal{A}
$$
$$
\pi_{i}
$$
$$
\sigma^{*}
$$
If extraction fails from any non-simulated signature, *B* aborts. If *B* aborts with non-negligible
probability here, *A* can be used to break the simulation extractability of the signature of knowledge scheme.
|R|1
If *⇡*i⇤ is simulated, *B* aborts. B aborts here with probability at most, since — after *G₄* —
R
we are guaranteed that one of the signatures will not be simulated.
$$
\pi_{i^{*}}
$$
$$
\frac{|\mathcal{R}|-1}{\mathcal{R}}
$$
$$
\mathcal{G}-
$$
wi
If all the extracted witnesses *w*iare such that *g* = *h*i, *B* computes the discrete log of *H* as
the sum of these witnesses (as well as the discrete logs of the *h*i’s from simulated signatures).
wi⇤wi⇤
Otherwise, if the witness *w*i⇤ is such that pk ⇤ = *g*, *B* computes the discrete log of *H* as
i e
⇤
mod *p* (*e* is the random exponent generated for *i*).
$$
w_{i}
$$
$$
g^{w_{i}}=h_{i}
$$
$$
h_{i}
$$
$$
w_{i^{*}}
$$
$$
\mathtt{p k}_{i^{*}}=g^{w_{i^{*}}}
$$
$$
\frac{w_{i^{*}}}{e}
$$
$$
i^{*})
$$
|R|1
Otherwise, *B* aborts. *B* aborts here with probability at most, since at least one of the
R
wi
witnesses *w*iis such that pki= *g* (if not all of them are of the other form).
$$
\frac{|\mathcal{R}|-1}{\mathcal{R}}
$$
$$
w_{i}
$$
$$
{mathtt{p k}}_{i}=mathfrak g{\mathfrak{g}}^{w_{i}}
$$
Anonymous Extendability To prove the strong anonymous extendability of our construction
it suces to show that if an adversary *A* can successfully break anonymous extendability, we can
build a reduction *B* that breaks the security of the signature of knowledge. Imagine that *B*,playing
the role of the challenger, runs the simulated setup for the signature of knowledge, instead of the
real setup. This gives *B* a trapdoor that allows it to simulate signatures without knowledge of a
witness. *B* uses this trapdoor to simulate all signatures of knowledge in response to signing queries
from *A*. *B* generates the challenge signature with no reference to the ladders. It simply chooses td
---
Q
td
at random, generates the *h*i’s as random values such that *g · h*i= *H*, and uses the trapdoor
to simulate all signatures of knowledge. If *A* can distinguish *B* from an honest challenger, *B* can
use *A* to break the simulatability property of the signature of knowledge. If *A* cannot distinguish
*B* from an honest challenger, since *B*’s behavior does not depend on choice of *b*, *A* cannot possibly
win the anonymous extendability game with probability non-negligibly more than half. *ut*
$$
g^{\mathsf{t d}}\cdot\prod h_{i}=H
$$
$$
{h_i{^\ }S}
$$
$$
\mathcal{B}
$$
$$
\mathcal{A}
$$
$$
B^{\ }
$$
$$
^,
$$
## 4 Same-Message Linkable Extendable Ring Signatures
A same-message linkable ring signature scheme (SMLRS) is a ring signature scheme that additionally allows any third party to publicly identify (link) whether two signatures were generated by the
same signer for the same message. This means that if the same party signs the same message twice,
even for di↵erent rings, the two signatures can be linked by any third party.
The main motivation for same-message linkable ring signatures is that they leads to a very
intuitive and natural construction of *threshold* ring signatures: a threshold ring signature can be
built as a simple concatenation of *t* same-message linkable ring signatures. Furthermore, SMLRS
can be used to build other schemes with varying degrees of linkability, in generic ways. For example, *un*linkable (ring) signatures can be realized from a SMLRS scheme simply by requiring each
signer to include a random nonce in their message. Standard *linkable* (ring) signatures — where
two signatures from the same signer are linkable no matter which message they sign — can be
instantiated from a SMLRS scheme by requiring the signer to always sign a fixed value (e.g.*?*)in
addition to the message *µ*.
$$
\mu.
$$
$$
(\mathrm{e.g.}\perp)
$$
In what follows, we introduce the notion of *extendable* same-message linkable ring signatures
(SMLERS). We give a security model for this new primitive, and describe an instantiation that
builds on our ERS construction from Section 3.3.
## 4.1 Syntax
A same-message linkable extendable ring signature scheme is a tuple of six algorithms SMLERS =
(Setup*,*KeyGen*,*Sign*,*Verify*,*Extend*,*Link). The first five algorithms are inherited from extendable
ring signatures. The Link algorithm (described below) allows any verifier to determine whether two
signatures on a particular message were produced by the same signer.
Link(*µ,*(0*, {*pkj*}*j2R0)*,* (1*, {*pkj*}*j2R1))*!{*linked*,*unlinked*}*: An algorithm that takes a message *µ*, two signatures (0*,*1) and two sets of public keys belonging to members of the rings
*R₀, R₁*. It outputs linked if 0and 1were produced by the same signer, and unlinked otherwise.
$$
\mathsf{L i n k}(\mu,\ \mathtt{(}\sigma_{0},\:\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}_{0}}),\:(mathtt{}\sigma_{1},\:\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}_{1}}))\;\to
$$
$$
\mu.
$$
$$
\left\langle\sigma_{0},\sigma_{1}\right\rangle
$$
$$
\mathcal{R}_{0},\mathcal{R}_{1}
$$
$$
\sigma_{0}
$$
$$
\sigma_{1}
$$
We remark that Link does not necessarily reveal the identity of the common signer if signatures are
linked. Next we discuss correctness for extendable same-message linkable ring signature schemes,
which encompasses two statements: *extended signatures verify*, which is inherited from correctness
for extendable ring signatures (Definition 1); and *extended signatures from di↵erent signers are*
*unlinked*, which we formalize in the following definition.
Definition 7 (Cross-Signer Correctness for SMLERS). *For all security parameters 2* **N***,*
⇤ (1) (l0) (1) (l0)
*for any message µ 2{*0*,*1*}, for any two ladders* lad₀ =(*i₀, R₀,...,R₀*)*,* lad₁ =(*i₁, R₁,...,R₁*)
$$
\lambda\in\mathbb{N}.
$$
$$
\mu\in\{0,1\}^{*}
$$
$$
\ .\mathtt{a d}_{0}=(i_{0},\mathcal{R}_{0}^{(1)},\dots,\mathcal{R}_{0}^{(l_{0})}),\mathtt{l a d}_{1}=(i_{1},\mathcal{R}_{1}^{(1)},\dots,\mathcal{R}_{1}^{(l_{0})})
$$
---
(1) (1)
*where i₀ 2R₀, i₁ 2R₁, l₀ >* 0*, l₁ >* 0 *and i₀* 6= *i₁,itmustholdthat:*
2 3
$$
i_{0}\in\mathcal{R}_{0}^{(1)},\,i_{1}\in\mathcal{R}_{1}^{(1)},\,l_{0}>0,\,l_{1}>0
$$
$$
\neq i_{1}
$$
$$
\mathbf{P}\left[\begin{array}{l|c}c{\mathsf{R i n k}(\mu,(\sigma_{0},\{\mathsf{p k}_{j}\}_{j\in\mathcal{R}_{0}}),}&{\mathcal{R}_{0}=\mathcal{R}_{1}^{(1)}\cup\cdots\cup\mathcal{R}_{1}^{(0)})}\\ {\mathsf{R}_{1}=\mathcal{R}_{1}^{(1)}\cup\cdots\cup\mathcal{R}_{1}^{(0)}}\\ {(\sigma_{1},\{\mathsf{p k}_{j}\}_{j\in\mathcal{R}_{1}})\to\mathtt{n n l i n d e d}}&{\mathcal{R}_{1}=\mathtt{n e l}}}\\{{((\sigmasigma_{{1}},\{\mathsf{p k}_{j}\}_{j\in\mathcal{R}_{1}}))\to\mathtt{n n l n e d4}}&{\mathcal{R}_{1}=\mathtt{n e l1}}\\ {\mathsf{}}\\ {\mathsf_{0}\ \mathsf{p e r}}&{\mathsf{P r r}\\ \ mathsf P r c\ \mathsf(\mu,\ _{\\mathsf{{k}}_{o b o}},\mathtt\{_{1b}})}\\ {\mathsf{\sigma_{1}}\gets\mathsf{P r o c}\ \ \mathsf{8p e}(\mu,\mathsf{\ {iota k}}{\ ,_{b a b}}_{1})\quad}\\ \end{array}\right]\ {{1-\mathtt n e g1}}
$$
*where* Process *is the algorithm described in Figure 1 except that the ERS algorithms are replaced*
*with the corresponding SMLERS ones.*
*Remark 3.* To build some intuition that may come in handy for understanding the security model,
the reader might consider the following natural strategy for constructing an extendable samemessage linkable ring signature scheme: ensuring that (part of) the signature is unique for every
public key and message pair. In other words, the signer’s public key and the signed message uniquely
determine a part of the ring signature; we will refer to this part as the *linkability tag*. This tag is
not modified by ring extensions and can be used to identify if two ring signatures, on the same
message, were produced by the same signer simply by checking whether they share the same tag.
## 4.2 Security Model
Informally, a same-message linkable extendable ring signature scheme is an extendable ring signature that additionally satisfies the following properties:
Same-Message One-More Linkability: no set of (*t*1) corrupt signers can produce *t* signatures
for the same message which appear pairwise unlinked. (We present this property in Definition 9).
Cross-Message Unlinkability: no adversary can determine whether two signatures for di↵erent
messages were produced by the same signer. (We present this property in Definition 10).
Unframeability (optional): no adversary can produce a signature that appears linked to an
honest signer’s signature. (We do not require unframeability for our extendable threshold ring
signature scheme, so we do not define it formally or prove that our construction meets it.)
This property can be thought of as a strengthening of cross-signer correctness to account for
malicious signers.
Definition 8 (Secure SMLERS). *A same-message linkable extendable ring signature scheme*
*(SMLERS) is* secure *if it satisfies correctness, same-message one-more linkability (Definition 9,*
*which implies unforgeability), and cross-message unlinkability (Definition 10).*
Definition 9 (Same-Message One-more Linkability for SMLERS). *A same-message link-*
*able extendable ring signature scheme SMLERS is said to be one-more linkable if for all PPT*
omlink
*adversaries A taking part in the same-message one-more linkability experiment* (ExpA,SMLERS()
omlink
*depicted in Figure 5*)*,itholdsthat:* Pr[ExpA,SMLERS()=win] ** negl*.*
$$
(\mathsf{E x p}_{\mathcal{A},\mathsf{S M L E R S}}^{\mathsf{o m l i n k}}(\lambda)
$$
$$
\operatorname{P r}[\sf{E x p}_{A,S M L E R S}^{o m l i n k}(\lambda)=w i n]\leq n e g L
$$
Definition 10 (Cross-Message Unlinkability for SMLERS). *A same-message linkable ex-*
*tendable ring signature scheme SMLERS is said to be cross-message unlinkable if for all PPT*
cmunlink
*adversaries A taking part in the cross-message unlinkability experiment* (ExpA,SMLERS() *depicted*
*in Figure 6*)*, it holds that the success probability of A is negligibly close to random guessing, i.e.,:*
cmunlink 1
Pr[ExpA,SMLERS()=win] ** + negl*.*
2
$$
(\mathsf{E x p}_{\mathcal{A},\mathtt{S M L E E S}}^{\operatorname{c m u n l i n k}}(\lambda)
$$
$$
\textstyle\operatorname*{P r}[\sf{E x p}_{\mathcal{A},S M L E R S}^{\ c{m{m\ m k n k}}}(\lambda)=w i n]\leq\frac{1}{2}+n e g l
$$ omlink
Exp*A,*SMLERS()
1 : pp Setup(1)
2 : Lkeys*,* Lcorr*,* Lsign?
3 : *O {O*Sign*,O*KeyGen*,O*Corrupt*}*
⇤ ⇤ ⇤ O
4 :( *µ, {*(k*, R*k)*}*k2[1...,t]) *A* (pp)
// *A* has never seen a signature for the message and a subring of the forgery rings
⇤ ⇤
5 : if *9* (*µ, R, ·*) *2* Lsign*s.t. R✓R*kfor some *k 2* [1*,...,t*] return lose
// *A* holds at most *t* 1 secret keys, among the keys identified by the forgery rings
⇤ ⇤
6 : if *|*(*R*1*[···[R*t) *\* Lcorr*|t* return lose
// all the signatures in the forgery verify (for the same message)
⇤ ⇤
7 : if *9 k 2* [1*...,t*]s.t.Verify(*µ, {*pkj*}*j2R⇤*,*k)=reject return lose
k
// all signatures in the forgery are unlinked (here *k, l 2* [1*,...,t*])
⇤ ⇤
8 : if *9 k 6*= *l* s.t. Link(*µ,* (k*, {*pkj*}*j2R⇤)*,* (l⇤*, {*pkj*}*j2R⇤)) = linked
k l
9 : return lose
10 : return win
$$
(\mu{}^{*},\{(\sigma_{k}^{*},\mathcal{R}_{k}^{*})\}_{k\in[1\ldots,t]})\leftarrow\mathcal{A}^{\it{O}}(\mathfrak{p p})
$$
$$
\exists \left(\mu^ {*}, \mathcal {R}, \cdot\right) \in \mathrm {L} _ {\mathrm {s i g n}} s. t. \mathcal {R} \subseteq \mathcal {R} _ {k} ^ {*}
$$
$$
k\in[1,\ldots,t]
$$
$$
\left|\left(\mathcal{R}_{1}^{*}\cup\cdots\cup\mathcal{R}_{t}^{*}\right)\cap\mathsf{L}_{\mathsf{c o r r}}\right|\geq t
$$
$$
\exists\ k\in[1\ldots,t]
$$
Fig. 5: Security experiment for same-message one-more linkability. The signing, key generation and corruption oracles
are as defined in Figure 2, except that the algorithms for ERS are replaced with the corresponding algorithms for
SMLERS. We recall that the list Lsignof sign-queries contains elements of the form (*µ, R,i*).
$$
\ {\mathfrak{L}}_{\mathsf{s i g n}}
$$
$$
(\mu,\mathcal{R},i)
$$
## 4.3 SMLERS from Signatures of Knowledge and Discrete Log
Our SMLERS construction builds on the ERS construction in Figure 4. Since the nuance is limited,
we only briefly describe the tweaks needed to transform our ERS into an SMLERS.
First, we adopt a slightly di↵erent relation *R*SMLERS:
$$
\mathcal{R}_{\mathbf{S M L E R S}}
$$
$$
\mathcal {R} _ {\mathrm {S M L E R S}} \left(\phi = (h, \mathrm {p k}, g ^ {\prime}, \tau), w = x\right) = \left\{g ^ {x} = h \vee \left(g ^ {x} = \mathrm {p k} \wedge \left(g ^ {\prime}\right) ^ {x} = \tau\right) \right\}
$$
Notably, the last *AND* not only requires a signer to prove knowledge of the secret key, but it
also enforces that the same secret key is used to generate the linkability tag *⌧*. The signatures of
knowledge for SMLERS are with respect to the new relation *R*SML.
$$
\mathcal{R}_{\mathsf{S M L}}
$$
Second, we modify the Sign algorithm of our ERS in Figure 4 so that it additionally computes
sk
*g⁰* := H(*µ*) and *⌧* := (*g⁰*) for some hash function H, and it includes the linkability tag *⌧* as part of
the signature. Finally, the algorithm Link simply compares the linkability tags in the two signatures.
It returns linked if they are equal, and unlinked otherwise.
$$
\ !\!{\mathfrak{g}}^{\prime}:={\mathsf{H}}(\mu)
$$
$$
\tau:=(g^{\prime})^{\mathtt{s k}}
$$
This scheme can be shown to be same-message one-more linkable (resp. cross-message unlinkable) with only minor modifications to the proof of unforgeability (resp. anonymous extendability)
of the extendable ring signature scheme.
## 5 Extendable Threshold Ring Signatures
Like a traditional threshold ring signature scheme, an *extendable* threshold ring signature scheme
enables parties to produce a signature on a message *µ* for a ring *R* showing that at least *t* of the
*|R|* potential signers in the ring participated, without revealing which. An extendable threshold
ring signature scheme additionally has the following properties:
$$
\mu
$$ cmunlink
ExpA,LRS()
1 : *b R {*0*,*1*},*Lkeys*,* Lcorr*,* Lsign?
2 : pp Setup(1)
3 : *O {O*Sign*,O*KeyGen*,O*Corrupt*}*
Chal*b*({µ₀, R₀,i₀}, {µ₁, R₁,i₁})
// the challenge identities must be uncorrupted
1 : if *i₀ 2* Lcorr *_ i₁ 2* Lcorr
2 : return*?*
O
4 :( *{µ₀, R₀,i₀}, {µ₁, R₁,i₁}*) *A* (pp) // one identity needs to be in both rings
5 :(¯ 0*,* ¯1) Chal*b*(*{µ₀, R₀,i₀}, {µ₁, R₁,i₁}*) 3 : if *i₀ 2/ R₀ \R₁ _ i₁ 2/ R₁*
⇤ O
6 : *b A* (¯0*,* ¯1)
// Rule out corruption of challenge identities
7 : if *i₀ 2* Lcorr *_ i₁ 2* Lcorr return lose
// Rule out trivial attacks using Link
8 : if *µ₀* = *µ₁* return lose
// Rule out trivial attacks using Link
9 : if (*µ₀, ·,i₀*) *2* L *_* (*µ₀, ·,i₁*) *2* L
4 : return*?*
// signing keys must exist
5 : if @ (*i₀,*pki*,*sk*i*0) *2* Lkeysreturn*?*
0
6 : if @ (*i₁,*pki*,*sk*i*1) *2* Lkeysreturn*?*
1
// generate a signature
7 :¯ 0 LRS*.*Sign(*µ₀, {*pki*}i2R*0*,*sk*i*0)
// generate the second signature according to
sign sign
_ (µ₁*, ·,i₀*) *2* Lsign*_* (*µ₁, ·,i₁*) *2* Lsign// the experiment’s bit *b*
10 : return lose 8 :¯ LRS*.*Sign(*µ₁, {*pk*},*sk)
⇤
11 : if *b* 6= *b* return lose
12 : return win
1 i *i2R*1ib
9 : return (¯0*,* ¯1)
$$
\left(\{\mu_{0},\mathcal{R}_{0},i_{0}\},\{\mu_{1},\mathcal{R}_{1},i_{1}\}\right)
$$
$$
b\leftarrow_{R}\{0,1\},mathsf L_{{\mathsf k e y s}},\mathsf L_{{\mathsf c o r r}},\mathsf L_{{\mathsf s i g n}}\leftarrow\varnothing
$$
$$
i_{0}\in\mathsf{L_{c o r r}}\vee i_{1}\in\mathsf{L_{c o r r}}
$$
$$
{\mathtt{p p}}\leftarrow{\mathsf{S e t u p}}(1^{\lambda})
$$
$$
O\leftarrow{O S i g n,O K e g G e n,O C o r r u p t}\}
$$
$$
(\{\mu_{0},\mathcal{R}_{0},i_{0}\},\{\mu_{1},\mathcal{R}_{1},i_{1}\})\leftarrow\mathcal{A}^{\it{}}({\mathfrak{p p}})
$$
$$
(\bar{\sigma}_{0},\bar{\sigma}_{1})\xleftarrow{}\mathsf{C h a l}_{b}(\{\mu_{0},\mathcal{R}_{0},i_{0}\},\{\mu_{1},\mathcal{R}_{1},\mathit{i}_{1}\})
$$
$$
\notin \mathcal {R} _ {0} \cap \mathcal {R} _ {1} \vee i _ {1} \notin \mathcal {R} _ {1}
$$
$$
b^{*}\leftarrow\mathcal{A}^{O}(\bar{\sigma}_{0},\bar{\sigma}_{1})
$$
$$
\nexists\;(i_{0},\mathtt{p k}_{i_{0}},\mathtt{s k}_{i_{0}})\in\mathsf{L}_{\mathsf{k e y s}}
$$
$$
i_{0}\in\mathsf{L_{c o r r}}\vee i_{1}\in\mathsf{L_{c o r r}}
$$
$$
\mathbf {f} \neq \left(i _ {1}, \mathrm {p k} _ {i _ {1}}, \mathrm {s k} _ {i _ {1}}\right) \in \mathrm {L} _ {\mathrm {k e y s}} \text {r e t u r n} \perp
$$
$$
\mu_{0}=\mu_{1}
$$
$$
\bar{\sigma}_{0}\leftarrow\mathtt{L R S.S i g n}(\mu_{0},\{\mathtt{p k}_{i}\}_{i\in\mathcal{R}_{0}},\mathtt{s k}_{i_{0}})
$$
$$
\big(\mu_{0},\cdot,i_{0}\big)\in\mathsf{L}_{\mathsf{s i g n}}\vee\big(\mu_{0},\cdot,i_{1}\big)\in\mathsf{L}_{\mathsf{s i g n}}
$$
$$
\vee\big(\mu_{1},\cdot,i_{0}\big)\in\mathsf{L}_{\mathsf{s i g n}}\vee\big(\mu_{1},\cdot,i_{1}\big)\in\mathsf{L}_{\mathsf{s i g n}}
$$
$$
\bar{\sigma}_{1}\leftarrow\mathtt{L R S.S i g n}(\mu_{1},\{\mathtt{p k}_{i}\}_{i\in\mathcal{R}_{1}},\mathtt{s k}_{i_{b}})
$$
$$
b^{*}\neq b
$$
$$
\left\langle\bar{\sigma}_{0},\bar{\sigma}_{1}\right\rangle
$$
Fig. 6: Cross-message unlinkability. The signing, key generation and corruption oracles are as defined in Figure 2,
except that the ERS algorithms are substituted with the respective SMLERS variants.
Flexibility: Given any two threshold signatures 0and 1that verify for the same message *µ* and
for the same ring *R*, anyone can *non-interactively* combine the signatures to obtain .Thenew
signature is also a threshold ring signature and its threshold is equal to the total number
of unique signers who contributed to at least one of the two signatures. This functionality is
provided by the Combine algorithm (below).
$$
\sigma_{0}
$$
$$
\mu
$$
$$
\sigma_{1}
$$
$$
{sigma\,,}
$$
$$
\sigma
$$
Extendability: Given a signature on a message *µ* for the ring *R* with threshold *t*, anyone
0
can *non-interactively* transform into a signature on the same message *µ* with the same
threshold*t*, but for a larger ring *R⁰ ◆R*. This functionality is provided by the Extend algorithm
(below).
$$
t,
$$
$$
\mathcal{R}
$$
$$
\mu
$$
$$
\sigma
$$
$$
\sigma^{\prime}
$$
$$
\mu
$$
$$
\mathcal{R}^{\prime}\supseteq\mathcal{R}
$$
## 5.1 Syntax
A non-interactive extendable threshold ring signature scheme (ETRS) is defined as a tuple of six
PPT algorithms ETRS =(Setup*,*KeyGen*,*Sign*,*Verify*,*Combine*,*Extend), where the public parameters pp produced by Setup are implicitly available to all other algorithms:
Setup(1)*!* pp: Takes a security parameter and outputs a set of public parameters pp.
$$
{\mathsf{S e t u p}}(1^{\lambda})\to{\mathtt{p p}}{\mathrm{:}}
$$
$$
\lambda
$$
KeyGen()*!* (pk*,*sk): Generates a new public and secret key pair.
$$
{\sf K e y G e n}()\to({\tt p k},{\tt s k})
$$
Sign(*µ, {*pki*}*i2R*,*sk)*!* : Returns a signature with threshold *t* =1usingthesecretkeysk corresponding to a public key pkiwith *i 2R*.
$$
\operatorname {S i g n} \left(\mu , \left\{\mathrm {p k} _ {i} \right\} _ {i \in \mathcal {R}}, \mathrm {s k}\right)\rightarrow \sigma :
$$
$$
t=1
$$
$$
\ mathrm p p k_{i}
$$
$$
i\in\mathcal{R}
$$
Verify(*t, µ, {*pki*}*i2R*,*)*!* accept*/*reject: Verifies a signature for the message *µ* against the
public keys *{*pki*}*i2Rwith threshold *t*.
$$
,\mu,\{\mathtt{p k}_{i}\}_{i\in\mathcal{R}},\sigma\big)\rightarrow
$$
$$
\sigma
$$
$$
\mu
$$
$$
\{\mathtt{p k}_{i}\}_{i\in\mathcal{R}}
$$
---
0
Combine(*µ,* 0*,*1*, {*pki*}*i2R) *7!* : Combines two signatures 0, 1for the same ring *R* into a
0
signature with threshold *t* = *|S₀ [ S₁|* where *S₀,S₁* is the set of (hidden) signers for 0and
1respectively.
$$
\left(\mu,\sigma_{0},\sigma_{1},\{\mathtt{p k}_{i}\}_{i\in\mathcal{R}}\right)\mapsto\sigma^{\prime};
$$
$$
\sigma_{0},\ \sigma_{1}
$$
$$
\mathcal{R}
$$
$$
t=|S_{0}\;\cup\;S_{1}|
$$
$$
\sigma^{\prime}
$$
$$
S_{0},S_{1}
$$
$$
\sigma_{0}
$$
$$
\sigma_{1}
$$
0
Extend(*µ, , {*pk*}*i2R*, {*pk*}*i2R0) *7!* : Extends the signature with threshold *t* for the ring *R*
i i
0
into a new signature with threshold *t* for the larger ring *R[R⁰*.
$$
\left(\mu , \sigma , \left\{\mathrm {p k} _ {i} \right\} _ {i \in \mathcal {R}}, \left\{\mathrm {p k} _ {i} \right\} _ {i \in \mathcal {R} ^ {\prime}}\right) \mapsto \sigma^ {\prime}
$$
$$
\sigma^{\prime}
$$
$$
\mathcal{R}\cup\mathcal{R}^{\prime}
$$
For a somewhat more interactive syntax, we can replace ‘Sign&Combine’ executions with a Join
operation (described in Section 2.3). For the sake of formalism, we present our security model only
for schemes with Combine and defer the discussion on how to handle Join operations to the Section 5.4, where we present a construction that uses the Join operation from signatures of knowledge
and the discrete log problem.
For the following definitions, we use ladders lad in a slightly di↵erent way than we did in the
context of extendable ring signatures (Section 3). Previously, lad contained a sequence of rings,
which were used in repeated invocations of Extend. Now, we generalize lad to support arbitrary
sequences of actions that could lead to a valid threshold ring signature (on some fixed message).
lad will contain a sequence of tuples of the form (action*,*input). The first component, action,
can take on the values Sign*,*Combine, or Extend.Ifaction = Sign,weexpectinput =(*R,i*),
where *R* and *i* are the ring and signer identity with which the signature should be produced. If
action = Combine,weexpectinput =(*l₁,l₂, R*), where *l₁* and *l₂* are indices of two signatures
under the same ring *R*.Ifaction = Extend,weexpectinput =(*l⁰, R*), where *l⁰* is the index of an
existing signature which we will extended to *R*.
$$
{\bf{\nabla}}=(\mathcal{R},i)
$$
$$
\mathcal{R}
$$
$$
\ \ =\ (l_{1},l_{2},\mathcal{R})
$$
$$
l_{1}
$$
$$
l_{2}
$$
$$
\mathcal {R}
$$
For use in our definitions, we define an algorithm Process(*µ,*Lkeys*,*lad), which processes all of
the operations in lad on the message *µ* (using keys stored in the list Lkeys) and returns (*, t, R*):
the signature returned by the last operation of lad, the corresponding threshold, and the ring that
verifies under. We define lad*.*sr to be the union of all identities and rings in lad.(sr stands for
super-ring.)
$$
(\mu,\mathsf{L}_{\mathsf{k e v s}},\mathsf{l a d})
$$
$$
\mu
$$
$$
(\sigma,t,\mathcal{R})
$$
$$
\ _\mathrm{k e y s})
$$
Definition 11 (Correctness for ETRS). *For correctness, we require that for all ladders* lad*,*
*the signature returned by* Process(lad) *verifies. Formally: for all security parameters 2* **N***,for*
⇤
*any message µ 2{*0*,*1*}, for any ladder* lad *of polynomial size identifying a ring R* := lad*.*sr *of*
*public-key identifiers, for any chosen threshold value* 1 * t |R|,itholds:*
$$
\lambda\in\mathbb{N}
$$
$$
\mu \in \{0, 1 \} ^ {*}
$$
$$
1\leq t\leq|\mathcal{R}|
$$
$$
\Pr \left[ \begin{array}{c c} \operatorname {V e r i f y} (t, \mu , \{\mathrm {p k} _ {i} \}_{i \in \mathcal {R}}, \sigma) \\ = \mathrm {a c c e p t} O R \sigma = \bot \\ \end{array} \right| \begin{array}{l l} \mathrm {p p} \leftarrow \operatorname {S u t e p} \left(1 ^ {\lambda}\right) \\ \mathrm {L} _ {\mathrm {k e y s}} \leftarrow \{\mathrm {K e y G e n ()} \}_{j \in \mathrm {l a d . s r}} \\ (\sigma , t, \mathcal {R}) \leftarrow \operatorname {P r o c e s s} \left(\mu , \mathrm {L} _ {\mathrm {k e y s}}, \mathrm {l a d}\right) \end{array} ] = 1.
$$
## 5.2 Security Model
Our security definitions are loosely based on the ones given for threshold ring signatures by Munch-
Hansen *et al.* [23].
Definition 12 (Secure ETRS). *An extendable threshold ring signature scheme is secure if it*
*satisfies correctness (Definition 11), unforgeability (Definition 13), anonymity (Definition 14), and*
*some notion of anonymous extendability.*
---
ETRS*.*Process(*µ,*Lkeys*,*lad)
(1) (1) (l) (l)
1 : Parse lad as ((action*,*input)*,...,*(action*,*input))
2 : for *l⁰ 2* [1*,...,l*]
(l0) (l0) (l0) (l0)
3 : if action = Sign parse input as (*R,i*)
(*l0*)
4 : for all *j 2R* if (*j,* pkj*, ·*) *62* Lkeysreturn? // public keys are initialized
5 : if sk*i* =*?* return*?* // signer’s secret key was generated honestly
(*l0*)
6 : if *i/ 2R* return*?* // signer is in the ring
(*l0*) (*l0*)
7 : *S* = *{i}* // generate the signer set
(l0)
8 : Sign(*µ, {*pk*j}*(l0)*,*sk(l0))
j2R i
(l0) (l0) (l0) (l0) (l0)
9 : if action = Combine parse input as (*l₁,l₂, R*)
(l0) (l0) (l0) (l0) (l0) (l0)
(l1) (l1) (l1) (l2) (l2) (l2)
10 : retrieve (*R*, S,)and(*R*, S,)
(1l0)
11 : for all *j 2R* if (*j,* pkj*, ·*) *62* Lkeysreturn*?* // public keys are initialized
(l0) 0 (l0) 0
(l1) (l) (l1) (l)
12 : if *R* 6= R or R 6= R return? // comb. signatures use same ring
0 (*l0*) (*l*0)
(l) (l1) (l2)
13 : *S* = *S [S* // generate the signers’ set
0 (*l0*) (l0)
(l) (l1) (*l*2)
14 : Combine(*µ, ,, {*pk*j}*(*l0*))
j2R
(l0) (l0) (l0) (l0)
15 : if action = Extend parse input as (*l₁, R*)
(l0) (l0) (l0)
l1l1l1
16 : retrieve (*R, S,*)
(*l0*)
17 : for all *j 2R* if (*j,* pkj*, ·*) *62* Lkeysreturn*?* // public keys are initialized
(*l*0) 0
*l*1(l)
18 : if *R 6⇢ R* return*?* // the extended ring is a superset
*0* (*l0*)
(*l*) l1
19 : *S* = *S* // generate the signers’ set
0 (*l0*)
(*l*) l1
20 : Extend(*µ, , {*pk*j}*(*l0*)*, {*pkj*}*(*l0*))
*l*j2R
j2R 1
$$
\mathrm {a d} \text {a s} ((\mathrm {a c t i o n} ^ {(1)}, \mathrm {i n p u t} ^ {(1)}), \dots , (\mathrm {a c t i o n} ^ {(l)}, \mathrm {i n p u t} ^ {(l)}))
$$
$$
l^{\prime}\in[1,\ldots,l]
$$
$$
.l{^{\prime\prime}})
$$
$$
{\mathtt{a c t i o n}}^{(l^{\prime})}={\mathtt{S i g n}}
$$
$$
(\mathcal{R}^{(l^{\prime})},i^{(l^{\prime})})
$$
$$
j \in \mathcal {R} ^ {\left(l ^ {\prime}\right)} \mathrm {i f} (j, \mathrm {p k} _ {j}, \cdot) \notin \mathrm {L} _ {\mathrm {k e y s}}
$$
$$
\mathtt{s k}_{i}=\bot
$$
$$
1/1
$$
$$
i\notin\mathcal{R}^{(l^{\prime})}
$$
$$
\mathcal{S}^{(l^{\prime})}=\big\{i^{(l^{\prime})}\big\}
$$
$$
\ //
$$
$$
\sigma^{(l^{\prime})}\leftarrow\mathsf{S i g n}(\mu,\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}^{(l^{\prime})}},\mathtt{s k}_{i(l^{\prime})})
$$
$$
(l_{1}^{(l^{\prime})},l_{2}^{(l^{\prime})},\mathcal{R}^{(l^{\prime})})
$$
$$
\mathtt{a c t i o n}^{(l^{\prime})}=
$$
$$
(\mathcal{R}^{(l_{1}^{(l^{\prime})})},\mathcal{S}^{(l_{1}^{(l^{\prime})})},\sigma^{(l_{1}^{(l^{\prime})})})
$$
$$
(\mathcal{R}^{(l_{2}^{(l^{\prime})})},\mathcal{S}^{(l_{2}^{(l^{\prime})})},\sigma^{(l_{2}^{(l^{\prime})})})
$$
$$
(j,\mathtt{p k}_{j},\cdot)
$$
$$
j\in\mathcal{R}_{1}^{(l^{\prime})}
$$
$$
\ //
$$
$$
\mathcal{R}^{(l_{1}^{(l^{\prime})})}\neq\mathcal{R}^{(l^{\prime})}
$$
$$
\ //
$$
$$
\mathcal{S}^{(l^{\prime})}=\mathcal{S}^{(l_{1}^{(l^{\prime})})}\cup\mathcal{S}^{(l_{2}^{(l^{\prime})})}
$$
$$
\sigma^{(l^{\prime})}\leftarrow\mathsf{C o m b i n e}(\mu,\sigma^{(l_{1}^{(l^{\prime})})},\sigma^{(l_{2}^{(l^{\prime})})},\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}^{(l^{\prime})}})
$$
$$
.cdot^{(l^{\prime})}
$$
$$
(l_{1}^{(l^{\prime})},\mathcal{R}^{(l^{\prime})})
$$
$$
(\mathcal{R}^{l_{1}^{(l^{\prime})}},\mathcal{S}^{l_{1}^{(l^{\prime})}},\sigma^{l_{1}^{(l^{\prime})}})
$$
$$
j\in\mathcal{R}^{(l^{\prime})}
$$
$$
(j,\mathtt{p k}_{j},\cdot)\not\in\mathsf{L}_{\mathsf{k e y s}}
$$
$$
1/1
$$
$$
\mathcal{R}^{l_{1}^{(l^{\prime})}}\not\subset\mathcal{R}^{(l^{\prime})}
$$
$$
\mathcal{S}^{(l^{\prime})}=\mathcal{S}^{l_{1}^{(l^{\prime})}}
$$
$$
\bot\ //
$$
$$
\sigma^{(l^{\prime})}\leftarrow\mathsf{E x t e n d}(\mu,\sigma^{l_{1}^{(l^{\prime})}},\{\mathtt{p k}_{j}\}_{{:}\in\mathcal{R}^{l}{}_{{}^{(l^{\prime})}}},\{\mathtt{p k}_{j}\}_{{}{{}^{}}}\ {{}_{j}\in\mathcal{R}^{(l^{\prime})}})
$$
Fig. 7: The Process algorithm for extendable threshold ring signatures.
---
cmEUF
Exp*A,*ETRS()
1 : Lkeys*,* Lcorr*,* Lsign?
2 : pp Setup(1)
3 : *O {O*Sign*,O*KeyGen*,O*Corrupt*}*
⇤ ⇤ ⇤ ⇤ O
4 :( *t,µ, R,*) *A* (pp)
⇤ ⇤
5 : *q |{*(*µ, R, ·*) *2* Lsign*s.t. R✓R*)*}|*
// rule out attacks if *A* knows too many sk:s or honestly generated signatures for *µ⇤*
⇤
6 : if *|R \* Lcorr*|* + *q t* return lose
// rule out outputs that do not verify
⇤ ⇤
7 : if Verify(*t, µ, {*pkj*}j2R⇤,*)=reject return lose
8 : return win
$$
\mathsf{L}_{\mathsf{k e y s}},\mathsf{L}_{\mathsf{c o r r}},\mathsf{L}_{\mathsf{s i g n}}\leftarrow\varnothing
$$
$$
{\tt p p}\leftarrow{\sf S e t u p}(1^{\lambda})
$$
$$
O\leftarrow{O O S i,O K e y G e n,O C o r n u p t\}}
$$
$$
q \leftarrow | \left\{\left(\mu^ {*}, \mathcal {R}, \cdot\right) \in L _ {\mathrm {s i g n}} s. t. \mathcal {R} \subseteq \mathcal {R} ^ {*} \right\}) |
$$
$$
|\mathcal{R}^{*}\cap\mathsf{L}_{\mathsf{c o r r}}|+q\geq t
$$
$$
(t^{*},\mu^{*},\mathcal{R}^{*},\sigma^{*})\leftarrow\mathcal{A}^{O}(\mathtt{p p})
$$
Fig. 8: Existential Unforgeability under Chosen Message Attack for (Extendable) Threshold Ring Signatures . The
key generation, corruption and signing oracles are as in Figure 2, with the di↵erence that the ERS algorithms are
substituted with the ETRS variants, and the signing oracle now returns partial signatures.
Definition 13 (Unforgeability for ETRS). *An extendable threshold ring signature scheme*
ETRS *is said to be unforgeable if for all thresholds* t, for all PPT *adversaries* A the *success*
⇥ ⇤
cmEUF
*probability in the* cmEUF *experiment in Figure 8 is* Pr Exp*A*,ETRS()=win ** negl*.*
$$
{\sf{r}}\left[\sf{E x p}_{A,E T R S}^{c m E U F}(\lambda)=w i n\right]\leq n e g L
$$
Just like for extendable ring signatures, the notion of anonymity for extendable threshold ring
signatures captures scenarios where the adversary distinguishes fresh (not-extended) signatures,
i.e., the challenge will be a threshold ring signature which has not be extended.
Definition 14 (Anonymity for ETRS). *An extendable threshold ring signature scheme is said*
*to be anonymous if for all PPT adversaries A taking part in the anonymous extendability ex-*
*periment (* ANEXT *in Figure 9) and submitting to the challenger two ladders with the structure*
*explained below, it holds that the success probability of A is negligibly close to random guessing,*
⇥ ⇤
ANEXT 1
*i.e.:* Pr ExpA,ETRS()=win ** + negl*.*
2
$$
i.e.:\operatorname{P r}\left[\sf x p_{A,E T R S}^{A N E X T}(\lambda)=w i n\right]\leq\ {\frac{1}{2}}+n e g l
$$
*For anonymity, the ladders submitted by the adversary to the challenger have the following struc-*
*ture (here t denotes the threshold of the scheme): the first t instructions are of the type* (Sign*,* (*R,i*))*,*
*where R is the same for all instructions in both ladders, and the signer indexes i are all distinct*
*within the same ladder; the last* (*t* 1) *instructions are of the type* (Combine*,* (*l₁,l₂, R*))*, where R*
*is the same for all instructions in both ladders, l₁* =1*,*2*,...,t* 1*,andl₂* = *t, t* +1*,...,*2*t* 2*.*
$$
(\mathsf{S i g n},(\mathcal{R},i))
$$
$$
(l_{1},l_{2},\mathcal{R}))
$$
$$
l_{1}=1,2,\ldots,t-1
$$
$$
l_{2}=t,t+1,\ldots,2t-2
$$
The notion of anonymous extendability is modelled by the following two definitions (which
are essentially adaptations of the ones given in Section 3.2 for extendable ring signatures, to the
threshold setting).
Definition 15 (Weak Anonymous Extendability for ETRS). *An extendable threshold ring*
*signature scheme ETRS is said to be weakly anonymous extendable if for all PPT adversaries A*
*taking part in the anonymous extendability experiment (* ANEXT *in Figure Figure 9) and submitting*
*to the challenger ladders with the structure specified below, it holds that the success probability of*
⇥ ⇤
ANEXT 1
*A is negligibly close to random guessing, i.e.:* Pr ExpA,ERS()=win ** + negl*.*
2
$$
\textstyle\ \ [tt E\ \ p_{A,E R S}^{A N E X T}(\lambda)=\tt w i n]\,\le\,\,\frac{1}{2}+\tt{n e g1}
$$
*For weak anonymous extendability the adversary submits ladders with the following structure:*
*the first t instructions are of the type* (Sign*,* (*i, R*))*, where the signer identities are pairwise distinct*
---
ANEXT
ExpA,ETRS()
1 : *b R {*0*,*1*}*
2 : Lkeys*,* Lcorr*,* Lsign?
3 : pp ETRS*.*Setup(1)
⇤ ⇤ ⇤
Chal*b*(µ,lad0,lad1)
⇤ ⇤
1 : if lad0or lad1is not well-formed
2 : return*?*
⇤
3 : if *9i 2* lad0*.*signers *s.t. i 2* Lcorr
4 : *O {O*Sign*,O*KeyGen*,O*Corrupt*}* 4 : return*?*
⇤ ⇤ ⇤ O
5 :( *µ,*lad₀*,*lad₁) *A* (pp)
⇤ ⇤ ⇤
6 :¯ Chal*b*(*µ,*lad0*,*lad1)
⇤ O
7 : *b A* (¯)
⇤
⇤
5 : if *9i 2* lad1*.*signers *s.t. i 2* Lcorr
6 : return*?*
// make sure the public keys are known / initialized
⇤
7 : if *9i 2* lad₀*.*sr *s.t.* (pki*, ·*) *2/* Lkeys
8 : if *9i 2* lad₀*.*signers *s.t.* i *2* Lcorr
8 : return*?*
9 : return lose
⇤
⇤
9 : if *9i 2* lad₁*.*sr *s.t.* (pk*, ·*) *2/* L
i keys
10 : if *9i 2* lad₁*.*signers *s.t.* i *2* Lcorr
10 : return*?*
11 : return lose
⇤
11 :( *,t , R*) Process(µ ,L,lad )
⇤ ⇤ 0 0 0 keys 0
12 : if *9*(*µ, ·,i*) *2* Lsignfor i 2 lad₀*.*signers
⇤
13 : return lose
12 :( *,t , R* 1 1 1) Process(*µ ,*Lkeys*,*lad )1
⇤ ⇤ // rule out trivial attacks
14 : if *9*(*µ, ·,i*) *2* Lsignfor *i 2* lad₁*.*signers
15 : return lose
⇤
16 : if *b* 6= *b*
17 : return lose
18 : return win
13 : if *R₀* 6= *R₁* or *t₀* 6= *t₁*
14 : return*?*
15 :¯ b
16 : return ¯
$$
\mathsf{L}_{\mathsf{k e y s}},\mathsf{L}_{\mathsf{c o r r}},\mathsf{L}_{\mathsf{s i g n}}\leftarrow\varnothing
$$
$$
\mathtt{p p\leftarrow E T R S.S e t u p((1^{\lambda})}
$$
$$
O\leftarrow\{O\mathsf{S i g n},O\mathsf{K e y G e n},
$$
$$
(\mu^{*},\mathtt{l a d}_{0}^{*},\mathtt{l a d}_{1}^{*})\leftarrow\mathcal{A}^{O}(\mathtt{p p})
$$
$$
b{}^{*}\leftarrow\mathcal{A}^{O}(\bar{\sigma})
$$
$$
s.t.\ i\in\mathsf{L}_{omathsf r r}
$$
$$
\bar{\sigma}\leftarrow\mathsf{C h a l}_{b}(\mu^{*},\mathtt{l a d}_{0}^{*},\mathtt{l a d}_{1}^{*})
$$
$$
\exists{i}\in\mathtt{1a d}_{1}^{*}
$$
$$
s.t.\;i\in\mathsf{L}_{o r r}
$$
$$
\exists(\mu^{*},\cdot,i)\in\mathsf{L}_{\mathsf{s i g n}}
$$
$$
(\sigma_{0},t_{0},\mathcal{R}_{0})\leftarrow\sf{P r o c e s s}(\mu^{*},L\_{k e y s},l a d_{0})
$$
$$
(\sigma_{1},t_{1},\mathcal{R}_{1})\leftarrow\sf{P r o c e s s}(\mu^{*},\_{L e g s},l a d_{1})
$$
$$
\exists(\mu^{*},\cdot,i)\in\mathsf{L}_{\mathsf{s i g n}}
$$
$$
i\in\mathtt{I a a}_{1}^{*}
$$
$$
\mathcal{R}_{0}\neq\mathcal{R}_{1}
$$
$$
b^{*}\neq b
$$
$$
t_{0}\neq t_{1}
$$
$$
\bar{\sigma}\gets\sigma_{b}
$$
Fig. 9: Anonymity and Anonymous Extendability for Extendable Threshold Ring Signatures. The key generation,
corruption and signing oracles are exactly as described in the unforgeability experiment (Figure 8).
*within a ladder, and the ring R is the same within the ladder (but possibly di↵erent for each*
*ladder); the subsequent t* 1 *instructions are of the form* (Combine*,* (*l₁,l₂, R*)) *where the indexes*
*l₁,l₂ progressively combine (threshold) signatures on the same ring R; the final ladder instruction*
*is* (Extend*,* (*l⁰, R⁰*)) *and extends the latest threshold ring signature to a wider ring, R⁰ ◆R.*
$$
(l_{1},l_{2},\mathcal{R}))
$$
$$
l_{1}
$$
$$
\mathcal{R}^{\prime}\supseteq\mathcal{R}
$$
Definition 16 (Strong Anonymous Extendability for ETRS). *An extendable threshold ring*
*signature scheme ETRS is said to be strongly anonymous extendable if for all PPT adversaries A*
*taking part in the anonymous extendability experiment (* ANEXT *in Figure 9) and submitting to*
*the challenger ladders with the structure specified below, it holds that the success probability of A is*
*negligibly close to random guessing, i.e.:*
$$
\textstyle\operatorname*{P r}\left[\sf x p_{\mathcal{A}_{\mathrm{s A n o n}},\mathrm{}{E R S}}^{\mathrm{}{A N E X T}}(\lambda)=\ w i n\right]\leq\ \textstyle{frac11}2+g l.
$$
*For strong anonymous extendability the adversary submits ladders that have the same structure as*
*for weak anonymous extendability, except for the final* Extend *instruction. While in weak anonymous*
*extendability we allow a single extension (to the same ring R⁰), in strong anonymous extendability*
*each ladder may contain an arbitrary (polynomial, and possibly di↵erent for each ladder) number*
*of subsequent* Extend *instructions, so long the final one of each ladder culminates in the same ring.*
---
## 5.3 A Generic Compiler for ETRS from SMLERS
In what follows, we formalize the intuition given in Remark 3 (Section 4.1) on how to generically derive an extendable threshold ring signature scheme from any given same-message linkable
extendable ring signature scheme. The compiler is detailed in Figure 10.
Setup(1) 7! pp KeyGen() 7! (pk,sk)
return SMLERS*.*Setup(1) return SMLERS*.*KeyGen()
Sign(*µ,* sk*, {*pki*}i2R*) *7!*
return SMLERS*.*Sign(*µ,* sk*, {*pki*}i2R*)
0
Extend(*µ, , {*pki*}i2R*0*, {*pki*}i2R*1*,*) *7!*
return *{*SMLERS*.*Extend(*{*pki*}i2R*1*, {*pkj*}j2R*2*,i*)*}i 2*
0
Combine(*µ,* 0*,*1*, {*pki*}i2R*) *7!*
0
1 : 0*{s₀ 2* 0 *8s₁ 2* 1 : Link(*µ,*(*s₀, {*pki*}i2R*)*,* (*s₁, {*pki*}i2R*)) = unlinked*}*
0
2 : return 0*[* 1
Verify(*t, µ, {*pki*}i2R,*) *7!* accept*/*reject
1 : Parse = *{s₀,...,s`}* as a set of signatures // removing duplicates
2 : if || ify(*µ, {*pki*}i2R,si*)=reject return reject
4 : if *9* (*si,sj*) *2 ⇥* : *si* 6= *sj ^*
Link(*µ,*(*si, {*pki*}i2R*)*,* (*sj, {*pki*}i2R*)) = linked return reject
5 : return accept
$$
\sigma=\{s_{0},\ldots,s_{\ell}\}
$$
Fig. 10: Generic Compiler for Extendable Threshold Ring Signatures from Extendable Same-Message Linkable Ring
Signatures.
Theorem 2. *Assuming that* SMLERS *is a secure same-message linkable extendable ring signa-*
*ture scheme, then the scheme* ETRS =(Setup*,*KeyGen*,*Sign*,*Verify*,*Extend*,*Combine) *described in*
*Figure 10 is an extendable threshold ring signature scheme that satisfies* correctness *(Definition 11),*
unforgeability *(Definition 13), and* anonymity *(Definition 14).*
*Proof.* The correctness of the construction follows by inspection.
Unforgeability The unforgeability of the ETRS scheme reduces directly to the one-more linkability of the underlying SMLERS scheme. The reduction is straightforward and tight, because a
forgery for the ETRS scheme corresponds to *t* unlinked SMLERS signatures.
Anonymity The anonymity of the ETRS construction reduces to the anonymity of the underlying SMLERS. The proof goes though a sequence of hybrid games. In *H₀*, the challenger always
$$
\ \mathcal{H}_{0}.
$$ picks the anonymity bit *b* = 0 (deterministically). In the final hybrid *H*t, the challenger always
picks the anonymity bit *b* = 1. For simplicity, assume that the two sets of signers selected by the
⇤ ⇤
adversary for the challenge are distinct (i.e., lad0*.*signers *\* lad1*.*signers = ?). The intermedi-
⇤
ate hybrids progressively change the signer set of the challenge signature from lad0*.*signers to
⇤
lad1*.*signers. In detail, for *j* =1*,...,t*,inhybrid*H*jthe challenger returns a signature ¯ ob-
⇤
tained combining the signatures of the first *j* signer identities from lad1*.*signers, and the last *t j*
⇤ ⇤
identities from lad0.signers. Let EjA guesses *b* = 1 at the end of *H*j.
⇥ ⇤denote the event where
*A*NEXT 1
Clearly, *|*Pr ExpA,ETRS()=win *|* = *|*Pr [*E₀*]Pr [*E*t] *|*. We can bound this probability by:
Anon 2⇥ ⇤
P
t ANEXT 1
|Pr [E₀] Pr [Et] | = | Pr [Ej1] Pr [Ej]*|t ·|*Pr ExpA,ERS()=win |,where*t* is
j=1 Anon 2
the threshold. The last inequality follows from the triangular inequality and the following reduction.
For every *j*,define*B* to forward all of *A*’s queries to its AN*E*XT-ERS challenger. Upon receiving
⇤ ⇤ ⇤
(*µ,*lad0*,*lad1) from *A* (line 6 in the ANEXT-ETRS experiment of Figure 9), the reduction sub-
⇤ ⇤
mits signing queries of the form (*µ, R,i*), where *i* ranges over all of the first (*j* 1) identities in
⇤ ⇤
lad1*.*signers and the last *t j* identities in lad0*.*signers. Let idenote the obtained responses.
⇤ (0) ⇤
Third, *B* submits to its AN*E*XT-ERS challenger the tuple (*µ,*lad₀*,*lad₁)wherelad₀ =(*i, R*)
j
(1) ⇤ (b)
and lad₁ =(*i, R*). Here, *i* denotes the identity of the *j*-th signer in ladder ladb. Let ¯ be the
j j
signature returned by the challenger. The reduction combines the *t* same-message-linkable extend-
⇤
able ring signatures *{*i*}*i2[1,...,j1,j+1,...,n]*[{*¯*}* to create ¯, the challenge extendable threshold
ring signature for *A*. Clearly, the reduction is simulating *H*jwhen *b* = 0, and *H*j+1when *b* = 1.
Thus *B* can exploit an adversary that can distinguish between a pair of consecutive hybrids to
break the anonymity of the underlying SML*E*RS.
*ut*
$$
\mathcal{H}_{t}.
$$
$$
\cap \mathrm {l a d} _ {1} ^ {*}
$$
$$
{\tt{a a}}{\tt{d}}_{0}^{*}.
$$
$$
j\,=\,1,\ldots,t
$$
$$
\bar{\sigma}
$$
$$
\mathcal{H}_{j}
$$
$$
t-j
$$
$$
E_{i}
$$
$$
\mathtt{I a d}_{\Omega}^{*}
$$
$$
b^{*}=1
$$
$$
\Pr \left[ \operatorname {E x p} _ {\mathcal {A} _ {\mathrm {A p o n}} \cdot \mathbf {E T R S}} ^ {\mathrm {A N E X T}} (\lambda) = \mathrm {w i n} \right] - \frac {1}{2} | = | \Pr [ E _ {0} ] - \Pr [ E _ {t} ] |
$$
$$
\mathcal{H}_{j}
$$
$$
\operatorname*{P r}\left[E_{0}\right]-\operatorname*{P r}\left[E_{t}\right]\big|=\big|\sum_{i=1}^{t}\operatorname*{P r}\left[E_{j-1}\right]-\operatorname*{P r}\left[E_{j}\right]\big|\leq t\cdot\big|\operatorname*{P r}\left[\mathsf{E r p}_{\mathfrak{A}_{\mathrm{s s e m}},\mathtt{E R S}}^{\mathrm{N N N T T}}(\lambda)=\mathtt{w i n}\right]-\frac{1}{2}\big|
$$
$$
(\mu^{*},\mathtt{l a d}_{0}^{*},\mathtt{l a d}_{1}^{*})
$$
$$
(\mu^{*},\mathcal{R}^{*},i)
$$
$$
\sigma_{i}
$$
$$
\mathtt{I a d}_{0}^{*}
$$
$$
t-j
$$
$$
\left(\mu^ {*}, \mathrm {l a d} _ {0}, \mathrm {l a d} _ {1}\right)
$$
$$
\mathtt{l a d}_{0}=(i_{j}^{(0)},\mathcal{R}^{*})
$$
$$
\mathtt{l1a d}_{1}=(i_{i}^{(1)},\mathcal{R}^{*})
$$
$$
\mathtt{I a d}_{b}
$$
$$
i_{j}^{(b)}
$$
$$
\bar{\sigma}^{*}
$$
$$
\big\{\sigma_{i}\big\}_{i\in[1,\ldots.,j-1,j+1,\ldots,n]}\cup\big\{{bar{\sigma}}\big\}
$$
$$
\mathcal{H}_{j}
$$
$$
b=0
$$
$$
b=1
$$
$$
\mathcal{H}_{j+1}
$$
## 5.4 ETRS from Signatures of Knowledge and Discrete Log
In what follows we present a somewhat more interactive Extendable Threshold Ring Signature
Scheme that supports Join operations and enjoys more compact signatures. Concretely, the size of
extended threshold signatures is independent of the threshold *t*, instead it grows linearly with *n⁰*
(an upper bound on the ring size). This is an improvement compared to the compiler presented
in Figure 10, which if instantiated using our SMLERS from Signatures of Knowledge and Discrete
Log of Section 4.3, returns signatures of size linear in *t ·|R|*.
$$
n^{\prime}
$$
$$
t\cdot|\mathcal{R}|
$$
Our Construction in a Nutshell Similarly to the ERS construction of Figure 4, we work with a
prime order group **G**,withtwopublicelements*g, H 2* **G** and a signature of knowledge for a relation
*R*Gfor knowledge of the discrete logarithm either of a given value *h* or of a pk.
$$
g,H\in\mathbb{G}
$$
$$
\mathcal{R}_{\mathbb{O}}
$$
Let *n⁰ 2* **N** be an upper bound on the ring size. We achieve the threshold functionality by
leveraging features of polynomials in a similar way to Shamir secret sharing. Intuitively, the signer
samples *n⁰ >* 0 pairs of values (*x*i*,*tdi) *2* **Z**p*⇥* **G**. These pairs of values define a unique polynomial
*f* (*x*) of degree *n⁰* such that *f*(0) = dlogg(*H*) and *f* (*x*i)=tdifor every *i 2* [*n⁰*]. Of course, since
dlogg(*H*) is unknown, our signers don’t know the coecients of this polynomial. However, since
polynomial interpolation involves only linear operations (when the *x*-coordinates are fixed and
known), the signers can interpolate this polynomial *in the exponent* to learn additional points
f(ˆx)
(ˆ*x, y* = *g*) for any given ˆ*x*. In order to sign, and later to endorse a statement (Join a signature),
f(ˆx)
the signer is required to produce a signature of knowledge for *R*Gfor a random point (ˆ*x, y* = *g*)
on the polynomial such that ˆ*x 62 {x*i*}*i2[n*0*]. Crucially, the signer does not know the discrete log of *y*
$$
n^{\prime}\;\in\;\mathbb{N}
$$
$$
\ x_{i},\mathtt{t d}_{i})\in\mathbb{Z}_{p}\times\mathbb{G}
$$
$$
n^{\prime}>0
$$
$$
f(0)={\mathrm{d l o g}}_{g}(H)
$$
$$
f(x_{i})=\mathsf{t d}_{i}
$$
$$
i\in[n^{\prime}]
$$
$$
n^{\prime}
$$
$$
f(x)
$$
$$
\mathrm {d} \log_ {g} (H)
$$
$$
(\hat{x},y=g^{f(\hat{x})})
$$
$$
(\hat{x},y=g^{f(\hat{x})})
$$
$$
\mathcal{R}_{\mathbb{G}}
$$
$$
\hat{x}\not\in\{x_{i}\}_{i\in[n^{\prime}]}
$$
---
Fig. 11: Subroutine used in our ETRS construction depicted in Figure 12.
tdi
(i.e., (ˆ*x, y*) is not among the ‘trapdoored’ values (*x*i*,g*)), and thus must satisfy the second clause
of the relation (proving knowledge of their secret key). On the other hand, to extend a signature,
anyone can pick one of the (remaining) ‘trapdoored’ points (*x*i*,*tdi), and generate a proof for *R*G
by satisfying the first clause (proving knowledge of tdi), to include any pk in the ring. The pair
(*x*i*,*tdi) is then removed from the list of trapdoors. (In case the owner of pk later wants to join
the signature, the Extend algorithm encrypts tdito pk; later, the owner of pk can recover tdiand
return it to the list of trapdoors before producing a fresh signature of knowledge using her secret
key.)
$$
(\mathrm{i.e.},(\hat{x},\mathcal{y})
$$
$$
(x_{i},g^{\mathsf{t d}_{i}}))
$$
$$
\mathcal{R}_{\mathbb{G}}
$$
$$
(x_{i},\mathtt{t d}_{i})
$$
$$
\mathsf{t d}_{i})
$$
$$
(x_{i},\mathtt{t d}_{i})
$$
$$
\dagger\mathrm{d}_{i}
$$
$$
\dagger\mathrm{d}_{i}
$$
The key idea of our construction is detailed in Figure 11 (the PolySign subroutine employed in
Signand Join–where this is called using the signer’s secret key as *w* and on a random value ˆ*x*– and in
Extend–where an evaluation point and its corresponding trapdoor are used as ˆ*x*and *w* respectively).
For any field F (often implicit) and *X✓***F**, *j 2X*, define the degree *|X |*1 Lagrange polynomial
Q
Xmm
*L*(*X*,j)(X) := *2* **F**[*X*].
m2X \{j} j
$$
\mathcal{X}\subseteq\mathbb{F},j\in\mathcal{X}
$$
$$
L_{(\mathcal{X},j)}(X)\mathrel{\mathop:}=\prod_{m\in\mathcal{X}\setminus\{j\}}\xrightarrow{j-m}\mathbb{F}\big[X\big]
$$
$$
|\mathcal{X}|-1
$$
Remarks on Modeling Join Operations Intuitively, our construction replaces Combine with
Join,whereJoin essentially performs Sign& Combine in a more ecient manner. To formally support
Join, we need to make a few tweaks to the security definitions introduced in Section 5.2.
First, we define how to process join actions in a ladder. If action = Join,weexpectinput =
(*l⁰, R,i*), where *l⁰* is the index of an existing signature in the ladder which is to be joined by
(l0) (l0) (l0)
signer *i*. Concretely, ETRS.Process retrieves (*R, S,*); checks that all of the keys in *R*
(l0)
have been initialized, i.e., appear in Lkeys; checks that *R [{i}* = *R*, and checks that the index
(l0)
of the new signer appears in *R* but not among the singers set *S*. If all these checks pass, the
(l0)
signer is added to *S*; that is, we set *S* := *S [{i}*. We then process the join action as
(l0)
Join(*µ, {*pkj*}*(*l0*)*,*ski*,*). Finally, we store (*R, S,*) and return (*R,t*= *|S|,*).
j2R
$$
(l^{\prime},\mathcal{R},i)
$$
$$
(\mathcal{R}^{\vec{l(l^{\prime})}},\mathcal{S}^{(l^{\prime})},\sigma^{(l^{\prime})})
$$
$$
\mathcal{R}^{(l^{\prime})}\cup\{i\}=\mathcal{R}.
$$
$$
L_{\mathrm{k e y s}},
$$
$$
\ {dot S^{{(l^{\prime})}}}
$$
$$
\ ;
$$
$$
{\mathcal{S}}\,:=\,{\mathcal{S}}^{(l^{\prime})}\cup\{i\}
$$
$$
\sigma\leftarrow
$$
$$
\mathsf{J o i n}(\mu,\{\mathtt{p k}_{j}\}_{i\in\mathcal{R}^{(l^{\prime})}},\mathtt{s k}_{i},\sigma^{(l^{\prime})})
$$
$$
(\mathcal{R},\mathcal{S},\sigma)
$$
$$
(\mathcal{R},t=|\mathcal{S}|,\sigma)
$$
---
KeyGen() *7!* (pk*,*sk)
1 :( pks*,*sk*s*) ERS*.*KeyGen()
2 :( pke*,*sk*e*) PKE*.*KeyGen()
0
Extend(µ, {pkj}*j2R*,,pk) 7!
1 : if pk *2{*pkj*}j2R* : return*?*
2 :(ˆ *x,* tdˆ )*R T* // Pick eval-point and trapdoor
3 : return (pk =(pks*,*pke)*,*sk =(sk*s,*sk*e*)) 3 : *c⁰* Enc(pk*,*tdˆ ) // enable future endorsing
e
Sign(*µ,* sk) *7!*
// int*e*rpolate a unique representation of the polynomial
0 0
4 :( *y ,⇡*) PolySign(*P, T, x, w* ˆ :=ˆ*x,* pk*,µ*)
Z⇤
1 : X R // pick *n0* distinct evaluation pointsˆ )
5 : *T T \{*(ˆ*x,* td*}* //
*np0*
2 : *T* := ?; *P* := ?
3 : for *x 2 X*
erase used trapdoor
// Add simulated signature to the set of proofs
0
6 : P *P [{*(ˆ*x, y⁰,*pks*,⇡,c⁰*)*}*
4 : td R **Z***p* // generate trapdoors for poly. values
7 : Randomly permute *P*
5 : *T T [{*(*x,* td)*}* // populate trapdoor set 0
8 : return :=(*T,P*)
6 : *c* Enc(pk*e, ?*) // no info to pass on
⇤
7 :ˆ *x R* **Z**p*\ X* // pick a new evaluation point Verify(t, µ, {pkj}*j2R*,) 7! accept/reject
8 :( *y, ⇡*) *P*olySign(*P, T, x, w* ˆ := sk*,*pk*,µ*)
1 : if *{*pkj*}j2R* 6= *{*pki*}*(·,·,pk,·,·)2P:
i
9 : *P* := *{*(ˆ*x, y,* pks*,⇡,c*)*}*
10 : return :=(*T,P*)
0
Join(*µ, {*pkj*}j2R,*sk*,*) *7!*
// check if current signer’s pk*s*is in *P*
1 : if *9* (*x, y,* pk*,⇡,c*) *2 Ps.t.*pk = pks
2 : return reject
// check *y*’s are cons*i*stent with a degree *n0* polynomial
td
3 : *Z* := *{*(0*,H*)*}[{*(*x, g*)*}*(x,td)2T
4 : *Z Z[{*(*x, y*)*}*(*x,y,*pk*,c,⇡*)*2P*
ˆ ˆ0
5 :Pick *Z✓Zs.t. |Z|* = n +1
X := {x}; Xˆ := *{x}*
6 :(x,y)2Z (x,y)2Zˆ
// remove *s*imulated proof for the signer who wants to join
2 : *P P \{*(*x, y,* pks*,⇡,c*)*}*
// retrieve trapdoor value
3 : td Dec(sk*e,c*)
7 : for (*x, y*) *2Z*:
QL (x)
(X,x ˆ ˆ)
8 : if *y 6*=(ˆx,*y*ˆ)2Zˆyˆ : return reject
// Interpolation over the standard set *{*1,. . . ,*n0}*
Q
0 L(X,x)(i)
9 : for i 2 [n]: Vi (x,y)2Zy
// add eval. point and td to th*e* set of available trapdoors
10 :ˆ *µ* :=(*µ, {Vi}*i2[n*0*])
4 : *T T [{*(*x,* td)*}*
c⁰ Enc(pk*, ?*)
11 : for (*x, y,* pk*s,⇡,c*) *2 P* // check proofs individually
5 :*e*// no info to pass on
⇤ 12 : :=(*y,*pk*s*)
6 :ˆ *x R* **Z***p\ X* // pick a new evaluation point
13 : if SoK*.*Verify(ˆ*µ, R*G,,⇡)=reject
// interpolate a unique representation of the polynomial
0 14 : return reject₀
7 :( *y⁰,⇡*) *P*olySign(*P, T, x, w* ˆ := sk*,*pk*,µ*)
15 : if *|T |* + *|P |t* + *n* return accept
0
8 : *P P [{*(ˆ*x, y⁰,*pks*,⇡,c⁰*)*}*
9 : Randomly permute *P*
10 : return :=(*T,P*)
16 : else retur*n* reject
$$
\mathsf{K e y G e n}()tt\ \mapsto\ (p k,s k)
$$
$$
(\mathtt{p k}_{s},\mathtt{s k}_{s})\leftarrow\mathtt{E R S.K e y G e n}(
$$
$$
\left(\mu,\{{mathtt{p k}}_{j}\}_{j\in\mathcal{R}},\sigma,{\mathtt{p k}}\right)\mapsto\sigma^{\prime}
$$
$$
\mathtt{i f}\ \mathtt{p k}\in\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}}:
$$
$$
(\mathtt{p k}_{e},\mathtt{s k}_{e})\gets\mathtt{P K E.K e y G e n}(
$$
$$
(\hat{x},\hat{\mathtt t d})\leftarrow_{R}T\ //
$$
$$
\mathbf{r e t u r n}\ (\mathbf{p k}=(\mathbf{p k}_{s},\mathbf{p k}_{e}),\mathbf{s k}=(\mathbf{s k}_{s},\mathbf{s k}_{e}))
$$
$$
c^{\prime}\leftarrow\mathsf{E n c}(\mathfrak{p k}_{e},\hat{\mathsf{t d}})\ //
$$
$$
\mathsf{S i g n}(\mu,\mathtt{s k})\mapsto\sigma
$$
$$
X\leftarrow_{R}{binom\mathbb{Z}_{p}^{*}}n
$$
$$
(y^{\prime},\pi^{\prime})\leftarrow\mathsf{P o l y S i g n}(P,T,\hat{x},w:=\hat{x},\mathtt{p k},\mu)
$$
$$
\mathbf{f o r}\ x\in X
$$
$$
T\leftarrow T\setminus\{(\hat{x},\hat{\mathtt{t d}})\}
$$
$$
T:=\varnothing;\quad P:=\varnothing
$$
$$
\mathtt{t d}\leftarrow_{R}\mathbb{Z}_{p}\ //
$$
$$
P\leftarrow P\cup\left\{(\hat{x},y^{\prime},\mathfrak{p k}_{s},\pi^{\prime},c^{\prime})\right\}
$$
$$
T\leftarrow T\cup\left\{(x,\mathtt{t d})\right\}\ /{/}
$$
$$
\mathbf{r e t u r n}\ \sigma^{\prime}:=(T,P)
$$
$$
c\leftarrow\mathsf{E n c}(\mathtt{p k}_{e},\bot)\ //
$$
$$
\hat{x}\leftarrow_{R}\mathbb{Z}_{p}^{*}\setminus X\;\;//;
$$
$$
\operatorname {v e r i f y} \left(t, \mu , \left\{\mathrm {p k} _ {j} \right\} _ {j \in \mathcal {R}}, \sigma\right) \mapsto \mathrm {a c c e p t / r e j e c t}
$$
$$
(y,\pi)\leftarrow\mathsf{P o l y S i g n}(P,T,\hat{x},w:=\mathtt{s k,p k},\mu)
$$
$$
P:=\{({\hat{x}},y,{\mathtt{p k}}_{s},\pi,c)\}
$$
$$
\ {mathfrak f f f}\ \{{\mathfrak{p k}}_{j}\}_{j\in\ {{\mathfrak{p k}}}_{i}\}_{(\cdot,\cdot,{\mathfrak{p k}}_{i},\cdot,\cdot)\in P}:}
$$
$$
{\mathrm{r\ t u t u r n\ }}\sigma:=(T,P)
$$
$$
\mathsf{J o i n}(\mu,\{\mathtt{p k}_{j}\}_{j\in\mathcal{R}},\mathtt{s k},\sigma)\mapsto\sigma^{\prime}
$$
$$
{\mathrm{i f~}}\exists\left(x,y,{\mathfrak{p k}},\pi,c\right)\in P\;{\mathrm{s.t.~}}{\mathfrak{p k}}={\mathfrak{p k}}_{s}
$$
$$
n^{\prime}
$$
$$
\mathcal{Z}:=\{\big(0,H\big)\}\cup\{\big(x,g^{\tt t d})\}_{(x,{\tt t d})\in T}
$$
$$
\mathcal{Z}\leftarrow\mathcal{Z}\cup\{(x,y)\}_{(x,y,\ {mathfrak p k k},c,\pi)\in P}
$$
$$
\operatorname{P i c k}\ \hat{\mathcal{Z}}\subseteq\mathcal{Z}\ s.t.\ \big|\hat{\mathcal{Z}}\big|=n^{\prime}+1
$$
$$
P\leftarrow P\setminus\{(x,y,{\mathfrak{p k}}_{s},\pi,c)\}
$$
$$
\mathcal{X}:=\big\{x\big\}_{(x,y)\in\mathcal{Z}};\hat{\mathcal{X}}:=\big\{x\big\}_{(x,y)\in\hat{\mathcal{Z}}}
$$
$$
(x,y)\in\mathcal{Z}
$$
$$
\ {tt t}\mathtt{d}\leftarrow\ \ \mathsf{D e c}(\mathtt{s k}_{e},c)
$$
$$
\textstyle\ !y neq prod{}_{(\hat{x},\hat{y})\in\hat{\mathcal{Z}}}\hat{y}^{L_{(\hat{\mathcal{X}},\hat{x})}}{}^{(x)}
$$
$$
\{1,\ldots,n^{\prime}\ \}
$$
$$
\begin{array}{l l}{i\in[n^{\prime}]:}&{V_{i}\leftarrow\prod_{(x,y)\in\mathcal{Z}}y^{L_{(\mathcal{X},x)}(i)}}\\ \end{array}
$$
$$
T\leftarrow T\cup\{(x,\mathtt{t d})\}
$$
$$
\hat{\mu}:=(\mu,\{V_{i}\}_{i\in[n^{\prime}]})
$$
$$
c^{\prime}\leftarrow\mathsf{E n c}(\mathtt{p k}_{e},\bot)\ //
$$
$$
(x, y, \mathrm {p k} _ {s}, \pi , c) \in P /
$$
$$
\hat{x}\leftarrow_{R}\mathbb{Z}_{p}^{*}\setminus X\;\;//
$$
$$
\phi:=(y,\mathtt{p k}_{s})
$$
$$
(y^{\prime},\pi^{\prime})\leftarrow\sf P o P y S i g n(P,T,\hat{x},w:=\tt s k,\tt p k,\mu)
$$
$$
P\leftarrow P\cup\left\{\left(\hat{x},y^{\prime},\mathfrak{p k}_{s},\pi^{\prime},c^{\prime}\right)\right\}
$$
$$
{\bf{i f}}\ |T|+|P|\geq t+n^{\prime}
$$
$$
\sigma:=(T,P)
$$
Fig. 12: Extendable Threshold Ring Signatures from Signature of Knowledge and Hardness of Discrete Log. The Setup algorithm is the same as in the ERS construction of Figure 4 (with *R***G** =
x x
*{*(*, w*)=(*h,* pk*,x*) *2* **G** *⇥* **G** *⇥* **Z***p* : *g* = *h _ g* = pk*}*). In the description, *n⁰ >* 0denotesthemaximumamountof
times a signature can be extended (it can be set in pp,orchosenuponsigning).Wealwaysletpk denote the public
key corresponding to sk; any algorithm that is given sk as input implicitly has access to pk. The parsing of pk into
(pks*,*pke)(orofpkiinto (pks*,*i,pke,i)), of sk into (sk*s,*sk*e*)andof into (*T,P*)isdoneimplicitly.
$$
\{(\phi,w)=(h,\mathtt{p k},x)\in\mathbb{G}\times\mathbb{G}\times\mathbb{Z}_{p}:g^{x}=h\vee g^{x}=\mathtt{p k}\}
$$
$$
\begin{array}{r l}{\mathcal{R}_{\mathbb{G}}}&{{}=}&{}\end{array}
$$
$$
n^{\prime}>0
$$
$$
(\mathtt{p k}_{s},\mathtt{p k}_{e})
$$
$$
(\mathtt{p k}_{s,i},\mathtt{p k}_{e,i}))
$$
$$
\mathbf{p k}_{i}
$$
$$
\left(\mathtt{s k}_{s},\mathtt{s k}_{e}\right)
$$
$$
\sigma
$$
$$
(T,P)
$$
---
OJoin(µ, R,i,)
1 : if *i 2* Lcorr return*?*
2 : for all *j 2R*
3 : if (*j,* pkj*, ·*) *2/* Lkeysreturn*?*
0
4 : Join(*µ, {*pkj*}j2R,*sk*i,*)
5 : LjoinLjoin*[{*(*µ, i,* )*}*
0
6 : return
$$
\mathsf{I}(\mu,\mathcal{R},i,\sigma)
$$
$$
i\in\mathsf{L}_{\mathsf{c o r r}}
$$
$$
j\in\mathcal{R}
$$
$$
\cdot\:(j,\mathtt{p k}_{j},\cdot)\notin\mathsf{L}_{\mathsf{k e y s}}
$$
$$
\sigma^{\prime}\leftarrow\mathsf{J o i n}(\mu,\{\mathfrak{p k}_{j}\}_{j\in\mathcal{R}},\mathfrak{s k}_{i},\sigma)
$$
Second, for unforgeability we add *O*Join (described to the left) to the oracle handle *O*
available to the adversary (ln 3 in Figure 8).
The join oracle also manages a list Ljoinof join
queries, initialized as empty at the beginning
of the experiment.
$$
\mathsf{L_{j o i n}}\leftarrow\mathsf{L_{j o i n}}\cup\{(\mu,i,\sigma)\}
$$
$$
\boxed {8})
$$
$$
\downarrow_{\ i o i n}
$$
$$
\sigma^{\prime}
$$
In addition, we need to keep track of signatures *A* obtains through *O*Join among the list of signatures
that trivially lead to a forgery. To do so, we add to the count on line 5 of Figure 8 the number
⇤ ⇤
of relevant join operations *|{*(*µ,i,·*) *2* Ljoin*}|* where Ljoindenotes the list of join queries, *µ* is the
⇤
message specified in the forgery and *i 2R* is among the signer identities specified in the forgery
ring.
$$
\triangle
$$
$$
|\{(\mu^{*},i,\cdot)\in\mathsf{L_{j o i n}}\}|
$$
$$
\mathsf{L}_{\mathrm{j o i n}}
$$
$$
\mu^{*}
$$
$$
i\in\mathcal{R}^{*}
$$
Theorem 3. *Assuming that* SoK *is a secure signature of knowledge scheme, and that the dis-*
*crete log problem is hard in the group* **G***, then the scheme* ETRS =(Setup*,*KeyGen*,*Sign*,*Verify*,*
Extend*,*Join) *described in Figure 12 is an extendable threshold ring signature scheme that satisfies*
correctness *(Definition 11),* unforgeability *(Definition 13), and* strong anonymous extendability
*(Definition 14).*
*Proof.* Correctness follows by inspection. The proof for anonymous extendability is almost identical
to that in the proof of Theorem 1.
Unforgeability The proof of unforgeability closely follows the proof of unforgeability of the ERS
scheme described in Figure 4 (Theorem 1), but is a bit more involved. Here, we describe how each
hybrid is di↵erent.
*G₀*: Same as in the proof of Theorem 1. This is the unforgeability game.
$$
\mathcal{G}_{0}^{\ast}
$$
$$
{\mathcal{G}}_{1}.
$$
*G₁*: Same as in the proof of Theorem 1. *H* is set to be the challenge *B* receives from its dlog
challenger.
*G₂*: Same as in the proof of Theorem 1. All signatures of knowledge are now simulated.
$$
{\mathcal{G}}_{2},
$$
*G₂*a: This is the same as *G₀*, except that now, in response to sign queries, all encryptions to honest parties are encryptions of*?*. The reduction remembers which trapdoor should have been
encrypted, for future use.
$$
\ mathcal\ G{_{2a}}
$$
This is indistinguishable from the previous game by CCA security of the encryption scheme.
*G₃*: Same as in the proof of Theorem 1. In response to a sign query, the reduction randomizes
which *h*iit does not know the discrete log of. (Note that we needed *G₂*abefore this game, since
otherwise, this change would a↵ect the distribution of the generated signatures.)
$$
{mathcal G_{{}33}}
$$
$$
\mathcal{G}_{2a}
$$
$$
h_{i}
$$
*G₄*a: This is the same as *G₃*, except now, if the candidate forgery contains *a subset* of a response to
a sign query and this subset contains any signatures of knowledge on statements *where B does*
*not know the discrete log of h*i, *B* aborts.
$$
\mathcal{G}_{4a},
$$
$$
\mathcal{G}_{3}
$$
$$
h_{i}
$$
With polynomial probability, *B* does not abort in this game, by the same reasons given in *G₄*
in the proof of Theorem 1.
$$
\mathcal{G}_{4}
$$
*G₅*: Same as in the proof of Theorem 1. *B* now aborts if the candidate forgery contains only
simulated signatures of knowledge (returned by either the sign or join oracles). In order to be a
good candidate forgery, a signature cannot consist of a response to a sign query together with
$$
\mathcal{G}_{5}
$$ responses to join queries; so, it must contain only a subset of the simulated signatures returned
in response to the relevant sign query. *B* can now obtain the discrete log of *H* via interpolation
instead of via addition.
⇤
*G₆*: Same as in the proof of Theorem 1. When prompted to generate a key pair for *i*, *B* returns
e
pki⇤ := *H* for a random exponent *e* **Z**p(no matching secret key is generated). If *A* submits
⇤ ⇤ ⇤ ⇤
a corruption query for *i*, *B* aborts. When *A* outputs a valid forgery (*µ, R,*), *B* checks that
⇤
*i 2R*; otherwise it aborts.
$$
i^{*}
$$
$$
\mathtt{p k}_{i^{*}}:=H^{e}
$$
$$
e\gets\mathbb{Z}_{p}
$$
$$
i^{*}
$$
$$
(\mu^{*},\mathcal{R}^{*},\sigma^{*})
$$
$$
i^{*}\in\mathcal{R}
$$
*G₇*: Same as in the proof of Theorem 1.
$$
{mathcal G_{{}77}}
$$
⇤
Note that at this point, honest party *i* is in the challenge ring. Note also that either
$$
i^{*}
$$
(a) the polynomial was generated by *B* in response to a sign query — in which case *B* already
knows *n⁰* points on the polynomial, and simulated signatures might be a part of the candidate
forgery — or
$$
n^{\prime}
$$
(b) the polynomial was generated by the adversary — in which case at least *t q* signatures are
not simulated, where *q* is the number of join queries the adversary asked with the challenge
message and polynomial on behalf of honest parties in the challenge ring.
$$
t\!-\!q
$$
*B* now calls the extractor *"*Afor SoK to extract witnesses *w*ifrom each signature of knowledge
⇤
*⇡*iin (which are not simulated signatures).
$$
\varepsilon\mathcal{A}
$$
$$
w_{i}
$$
$$
\pi_{i}
$$
$$
\sigma^{*}
$$
Like in the proof of Theorem 1, if extraction fails from any non-simulated signature, *B* aborts.
If *⇡*i*⇤* is simulated, *B* aborts.
$$
\pi_{i\ast{}}
$$
If any of the witnesses are secret keys, and if *w*i*⇤* is not a secret key, *B* aborts. (This happens
⇤
with at most polynomial probability.) If *w*i*⇤* is the secret key of party *i*, *B* can find the discrete
log of *H* from this (by dividing the secret key by *e*).
$$
w_{i^{*}}
$$
$$
w_{i^{*}}
$$
$$
i^{*}
$$
$$
e e)
$$
Otherwise, if all the extracted witnesses are points on the polynomial, *B* then extracts at least
*n q* points on the polynomial; an additional *n⁰* (*n t*) are available as trapdoors. If *q t*
the candidate forgery is invalid; so, *n q>n t*, and *B* ends up knowing at least *n⁰* + 1 points
on the polynomial. *B* can now find the discrete log of *H* by interpolating the polynomial.
*ut*
$$
n-q
$$
$$
n^{\prime}-(n-t)
$$
$$
q\geq t
$$
$$
n-q>n-t.
$$
$$
n^{\prime}+1
$$
*Remark 4.* Note that a malicious extender can prevent the newly added members of the ring from
later joining a signature, simply by not encrypting the correct trapdoor under that new member’s
public key. This is not captured by our security definitions, but precluding such attacks would be
an interesting and valuable extension. We can modify our construction to disallow this by adding
a zero knowledge proof that the encrypted value is in fact the discrete log of the *h* in question.
## 6 Implementation Results
We have implemented the ERS and ETRS constructions from Section 3 and 5 with two di↵erent
5
choices of groups at the 128-bit security level within the RELIC library. The first parameter choice
is the conservative edwards25519 curve used in the Ed25519 signature scheme [2], and the second
is the record-setting GLS254 binary curve [25]. The latter provides an ecient endomorphism that
accelerates scalar multiplication by breaking scalars into smaller subscalars that can be handled in
an interleaved manner. In the ERS construction, the performance depends on the ring size only, so
the number of extensions is always the number of keys. For the ETRS construction, the quadratic
cost of interpolation clearly dominates the signing, joining and verification steps. The forked library
is available at https://github.com/relic-toolkit/relic.
5
https://github.com/relic-toolkit/relic
---
Fig. 13: Clock time for Sign, Verify and signature sizes for extendable ring signatures (Figure 4). The signature size
is the same for both Ed25519 and GLS254.
Fig. 14: Clock time and signature sizes for our ETRS scheme (Figure 12), for di↵erent thresholds. The signature
generation time includes the initial signature generation and subsequent extensions. The signature size is independent
of the threshold.
11
ERS Benchmark We benchmark our ERS implementation for ring sizes of 1 to 2 on an Intel
Core i7-6700K Skylake running at 4 Ghz, with HyperThreading and TurboBoost disabled. The
signature generation time, verification times and signature sizes (without point compression) are
shown in Figures 13.
$$
2^{11}
$$
---
ETRS Benchmark We benchmark our ETRS implementation for thresholds of 1*,*2*,*4*,*8 and ring
11
sizes of 1 to 2 over edwards25519 on an Intel Core i7-6700K Skylake running at 4 Ghz, with
HyperThreading and TurboBoost disabled. For ease of exposition, we combined the wall time for
the initial signature generation and subsequent extensions in the plot (Figure 14). The verification
time is that of verifying the final extended signature. Compared to the ERS scheme, the additional
computational overhead is dominated by the polynomial interpolation. Finally, we also implemented
and benchmarked the less ecient generic ETRS from SMLERS, with the data plotted in Figure
15.
$$
1\ \{\mathrm{t o}\ 2^{11}
$$
Fig. 15: Clock time and signature sizes for our generic ETRS scheme (Figure 10) from our SMLRS, for di↵erent
thresholds. The signature generation time includes the initial signature generation and subsequent extensions. The
signature size depends linearly on the threshold.
1. Bender, A., Katz, J., Morselli, R.: Ring signatures: Stronger definitions, and constructions without random
oracles. In: TCC 2006
2. Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.Y.: High-speed high-security signatures. Journal of
Cryptographic Engineering
3. Bettaieb, S., Schrek, J.: Improved lattice-based threshold ring signature scheme. In: Post-Quantum Cryptography
- 5th International Workshop, PQCrypto 2013
4. Beullens, W., Katsumata, S., Pintore, F.: Calamari and falafl: Logarithmic (linkable) ring signatures from isogenies and lattices. Cryptology ePrint Archive, Report 2020/646
5. Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps.
In: EUROCRYPT 2003
6. Bootle, J., Cerulli, A., Chaidos, P., Ghadafi, E., Groth, J., Petit, C.: Short accountable ring signatures based on
DDH. In: ESORICS 2015, Part I
7. Bose, P., Das, D., Rangan, C.P.: Constant size ring signature without random oracle. In: ACISP 15
8. Bresson, E., Stern, J., Szydlo, M.: Threshold ring signatures and applications to ad-hoc groups. In: CRYPTO 2002
9. Brickell, E.F., Camenisch, J., Chen, L.: Direct anonymous attestation. In: ACM CCS 2004
10. Chandran, N., Groth, J., Sahai, A.: Ring signatures of sub-linear size without random oracles. In: ICALP 2007
11. Chase, M., Lysyanskaya, A.: On signatures of knowledge. In: CRYPTO 2006
## References
12. Chow, S.S.M., Wei, V.K.W., Liu, J.K., Yuen, T.H.: Ring signatures without random oracles. In: ASIACCS 06
---
13. Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: Anonymous identification in ad hoc groups. In: EUROCRYPT 2004
14. Esgin, M.F., Steinfeld, R., Sakzad, A., Liu, J.K., Liu, D.: Short lattice-based one-out-of-many proofs and applications to ring signatures. In: ACNS 19
15. Groth, J., Maller, M.: Snarky signatures: Minimal signatures of knowledge from simulation-extractable SNARKs.
In: CRYPTO 2017, Part II
16. Haque, A., Scafuro, A.: Threshold ring signatures: New definitions and post-quantum security. In: PKC 2020,
Part II
17. Liu, J.K.: Ring signature. In: Advances in Cyber Security: Principles, Techniques, and Applications
18. Liu, J.K., Wong, D.S.: On the security models of (threshold) ring signature schemes. In: ICISC 04
19. Liu, Z., Nguyen, K., Yang, G., Wang, H., Wong, D.S.: A lattice-based linkable ring signature supporting stealth
addresses. In: ESORICS 2019, Part I
20. Lu, X., Au, M.H., Zhang, Z.: Raptor: A practical lattice-based (linkable) ring signature. In: ACNS 19
21. Malavolta, G., Schr¨oder, D.: Ecient ring signatures in the standard model. In: ASIACRYPT 2017, Part II
22. Melchor, C.A., Cayrel, P.L., Gaborit, P., Laguillaumie, F.: A new ecient threshold ring signature scheme based
on coding theory. IEEE Transactions on Information Theory
23. Munch-Hansen, A., Orlandi, C., Yakoubov, S.: Stronger notions and a more ecient construction of threshold
ring signatures. Tech. rep., Cryptology ePrint Archive, Report 2020/678
24. Okamoto, T., Tso, R., Yamaguchi, M., Okamoto, E.: A *k*-out-of-*n* ring signature with flexible participation for
signers. Cryptology ePrint Archive, Report 2018/728
25. Oliveira, T., L´opez-Hern´andez, J.C., Aranha, D.F., Rodr´ıguez-Henr´ıquez, F.: Two is the fastest prime: lambda
coordinates for binary elliptic curves. Journal of Cryptographic Engineering
26. Patachi, S., Sch¨urmann, C.: Eos a universal verifiable and coercion resistant voting protocol. In: E-VOTE-ID
27. Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret. In: ASIACRYPT 2001
28. Shacham, H., Waters, B.: Ecient ring signatures without random oracles. In: PKC 2007
29. Sun, S.F., Au, M.H., Liu, J.K., Yuen, T.H.: RingCT 2.0: A compact accumulator-based (linkable ring signature)
protocol for blockchain cryptocurrency monero. In: ESORICS 2017, Part II
30. Tsang, P.P., Wei, V.K., Chan, T.K., Au, M.H., Liu, J.K., Wong, D.S.: Separable linkable threshold ring signatures.
In: INDOCRYPT 2004
31. Yuen, T.H., Liu, J.K., Au, M.H., Susilo, W., Zhou, J.: Threshold ring signature without random oracles. In:
ASIACCS 11
32. Zhang, F., Kim, K.: ID-based blind signature and ring signature from pairings. In: ASIACRYPT 2002