Count Me In! Extendability for Threshold Ring Signatures

Diego Aranha¹, Mathias Hall-Andersen¹, Anca Nitulescu³, ??? Elena Pagnin², and Sophia Yakoubov¹

¹ Aarhus University, Aarhus, Denmark; {dfaranha, ma, sophia.yakoubov}@cs.au.dk ² Lund University, Lund, Sweden; elena.pagnin@eit.lth.se ³ 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 sk_A). (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 a<b, we denote the list of integer numbers between a and b as [a, . . . , b]. For compactness, when a = 1, we simply write [b] for [1,...,b]. We denote empty strings as ✏. Unless otherwise specified, all the algorithms defined throughout this work are assumed to be probabilistic Turing machines that run in polynomial time (abbreviated as PPT). When sampling the value a uniformly at random from a set X,weemploy

the notation a_RX. 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(µ, {pk_j}_j2R,sk_i)! : 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 sk_iof the signer i 2R(i.e., the signer’s public key must appear in the set {pk_j}_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(µ, {pk_i}_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(µ, {pk_j}_j2R,sk,)! : Takes a message µ, a set of public keys {pk_j}_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}j2R0)! : 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 a^ll sets of signer identifiers. In addition, we make use of an algorithm Process(*µ,L_keys,*lad), that we describe in Figure 1. As the name suggests, this algorithm processes a ladder lad on a given message µ using keys from L_keys (1) (the list of generated keys). Process signs µ using sk_iunder the ring R, and extends the signature to all the subsequent rings (using keys stored in the list L_keys). 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 fina^l 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) ⁽¹⁾ (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} $$

⁴ 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 Exp_A,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 {OSign,OKeyGen,OCorrupt}* ⇤ ⇤ ⇤ O 4 :( µ, R,) A (pp) // rule out trivial wins due to ring expansion ⇤ 5 : if 9 (µ, R, ·) 2 Lsigns.t. {pk_j}j2R ✓{pk_j}j2R⇤ 6 : return lose // rule out trivial wins due to key duplication 7 : if {pk_j}j2R⇤ {pk_j}j2Lcorr6= ? 8 : return lose

OKeyGen(i, pk) // standard key generation for a new identifier i 1 : if pk =? 2 :( pk_i,ski) ERS*.KeyGen() 3 : LkeysLkeys[{(i, pki,ski*)} 4 : else // A over-writes an identifier with malicious keys 5 : Lcorr Lcorr [{i} 6 : pk_ipk 7 : LkeysLkeys*[{(i, pki, ?)}* 8 : return pk_i OSign(µ, R,i)

⇤ ⇤ 9 : if Verify(µ, {pk_j}j2R⇤,)=reject 1 : if (i 2 L _ i/ 2R): return*?*

10 : return lose 11 : return win OCorrupt(i) 1 : if (i, pk_i,ski) 2 Lkeysand ski 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(µ, {pk_j}j2R,ski) 6 : LsignLsign[{(µ, R,i)}*

3 : return (pki*,*ski) 7 : return 4 : return? // if i has not been initialized.

$$ \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 (lad⁰*,*lad¹in line 5 of ANEXT Exp_A,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 Chal_b). 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 lad₀=(i₀, R),lad₁=(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)

⇤ ⇤ ^⇤ Chalb(µ,lad0,lad1) ^⇤ (1) (0l0) 1 : parse lad₀=(i₀, R₀,...,R⁾ ⇤ (1) (1l1) 2 : parse lad₁=(i₁, R₁,...,R⁾ // cha^llenge signing keys should not be corrupted

// handle of oracles, for compact notation3 : if i₀,i₁ 2 Lcorr return*?* 4 : O {OSign*,OKeyGen,OCorrupt}* // sign and extend following the instructions

⇤ ⇤ ⇤ O 5 :( µ,lad₀,lad₁) A (pp) ⇤ ⇤ ⇤ 6 :¯ Chalb(*µ,lad0,*lad1) ^⇤ O 7 : b A (¯)

// in both ladders ⇤ 4 : 0 Process(*µ,Lkeys,*lad₀) ^⇤ 5 : 1 Process(*µ,Lkeys,*lad₁)

// 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 OSign, OKeyGen and OCorrupt are defined in Figure 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_RG 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 td_RZ_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 sk_ias 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 = {(hi*,pkⁱ,⇡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 {pk_j}j2R 6= {pk_i}_i2R0:

ERS*.KeyGen() 7! (pk,sk) 1 : sk Zp* sk 2 : pk := g 3 : return (sk*,pk) ERS.Sign(µ, sk) 7! 1 : td R Zp* 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,pk_i) if SoK.Verify((nonce,µ), R,i,⇡i)=reject : return reject 5 : return accept 0 ERS.Extend(µ, {pkj}j2R,,pk) 7! 1 : if pk 2{pk_j}j2R : return*?* 2 : parse =(nonce*,td,P* = {(hi,pk_i,⇡i)}_i2R0) 3 : td⁰ R Zp // pick a trapdoor 4 : td td td⁰ (mod p) td0 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*,⇡)toP* // 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 RG = {(, w)=(h, pk*,x*) 2 G ⇥ G ⇥ Zp : 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 2Rsuch 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, if 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_istimesg (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 pk_i^⇤ := 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,whereq_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ⁱ, B computes the discrete log of H as the sum of these witnesses (as well as the discrete logs of the hⁱ’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 pk_i= 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, unlinkable (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(µ,(₀, {pk_j}_j2R0), (₁, {pk_j}_j2R1))!{linked,unlinked}: An algorithm that takes a message µ, two signatures (₀,₁) and two sets of public keys belonging to members of the rings R₀, R₁. It outputs linked if ₀and ₁were 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 (t1) 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 (Exp_A,SMLERS() omlink depicted in Figure 5),itholdsthat: Pr[Exp_A,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 (Exp_A,SMLERS() depicted in Figure 6), it holds that the success probability of A is negligibly close to random guessing, i.e.,: cmunlink 1 Pr[Exp_A,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 {OSign*,OKeyGen,OCorrupt}* ⇤ ⇤ ⇤ 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 Lsigns.t. R✓Rkfor 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 |(R1*[···[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(µ, {pk_j}_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, {p_kj}_j2R⇤), (_l⇤, {pk_j}_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 {OSign*,OKeyGen,OCorrupt}*

Chalb({µ₀, 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) Chalb({µ₀, 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₀,pk_i,ski₀) 2 Lkeysreturn*?* 0 6 : if @ (i₁,pk_i,ski₁) 2 Lkeysreturn*?* 1 // generate a signature 7 :¯ 0 LRS*.S_ign(µ₀, {pki}i2R₀,ski*₀) // 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₁ib 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 ₀and ₁that 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 thresholdt, 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(µ, {pk_i}_i2R,sk)! : Returns a signature with threshold t =1usingthesecretkeysk corresponding to a public key pk_iwith 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, µ, {pk_i}_i2R,)! accept*/*reject: Verifies a signature for the message µ against the public keys {pk_i}_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(µ, ₀,₁, {pk_i}^i2R) 7! : Combines two signatures ⁰, ¹for the same ring R into a 0 signature with threshold t = |S₀ [ S₁| where S₀,S₁ is the set of (hidden) signers for ₀and 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}ⁱ2R*, {pk}*_i2R⁰) 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(µ,L_keys,lad), which processes all of the operations in lad on the message µ (using keys stored in the list L_keys) 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 ski* =? 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⁽µ, {pkj}_(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) (l0) (l) (l1) (l2) 13 : S = S [S // generate the signers’ set 0 (l0) (l0) (l) (l1) (l2⁾ 14 : Combine⁽µ, ,, {pkj}(l0)) _{j2R (l0)} (l0) (l0) (l0) 15 : if action = Extend parse input as ⁽l₁, R) ^(l0) (l0) (l0) l1l1l1 16 : retrieve ⁽R, S,) ⁽l0^{) 1}7 : for all j 2R if (j, pkj*, ·) 62 Lkeysreturn?* // public keys are initialized (l0) 0 l1(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 2⁰ : Extend⁽µ, , {pkj}⁽l0⁾, {pk_j}₍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 ExpA,ETRS() 1 : Lkeys, Lcorr*,* Lsign?

2 : pp Setup(1) 3 : O {OSign*,OKeyGen,OCorrupt}* ⇤ ⇤ ⇤ ⇤ O 4 :( t,µ, R,) A (pp) ⇤ ⇤ 5 : q |{(µ, R, ·) 2 Lsigns.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, µ, {pk_j}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 ExpA,_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 Exp_A,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*,...,2t* 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 Exp_A,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)

⇤ ⇤ ^⇤ Chalb(µ,lad0,lad1) ^⇤ ⇤ 1 : if lad₀or lad₁is not well-formed 2 : return*?* ⇤ 3 : if 9i 2 lad0*.*signers s.t. i 2 Lcorr

4 : O {OSign*,OKeyGen,OCorrupt}* 4 : return*?*

⇤ ⇤ ⇤ O 5 :( µ,lad₀,lad₁) A (pp) ⇤ ⇤ ⇤ 6 :¯ Chalb(*µ,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(µ, , {pk_i}i2R₀, {pk_i}i2R₁,) 7! return {SMLERS.Extend({pk_i}i2R₁, {pk_j}j2R₂,i)}i 2 0 Combine(µ, 0*,1, {pk_i}i2R*) 7! ⁰ 1 : ⁰{s₀ 2 0 8s₁ 2 1 : L_ink(µ,(s₀, {pki}i2R), (s₁, {pk_i}i2R)) = unlinked*}* 0 2 : return ⁰[ 1 Verify(t, µ, {pki}i2R,) 7! accept*/reject 1 : Parse = {s₀,...,s`} as a set of signatures // removing duplicates 2 : if || <t return reject 3 : if 9 si 2 : Ver_ify(µ, {pki}i2R,si)=reject return reject 4 : if 9 (si,sj) 2 ⇥ : si 6= sj ^ Link(µ,(si, {pk_i}i2R),* (sj, {pk_i}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., lad⁰.signers * lad¹.signers = ?). The intermedi- ⇤ ate hybrids progressively change the signer set of the challenge signature from lad₀.signers to _⇤ lad₁.signers. In detail, for j =1,...,t,inhybridH*_jthe challenger returns a signature ¯ ob- ⇤ tained combining the signatures of the first j signer identities from lad₁.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 ANEXT 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 [E_j]|t ·|Pr Exp_A,ERS()=win |,wheret is j=1 Anon 2 the threshold. The last inequality follows from the triangular inequality and the following reduction. For every j,defineB to forward all of A’s queries to i_ts ANEXT-ERS challenger. Upon receiving ⇤ ⇤ ^⇤ (µ,lad⁰,lad₁) 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 ⇤ _⇤ lad¹.signers and the last t j identities in lad₀.signers. Let ⁱdenote the obtained responses. ⇤ (0) ⇤ Third, B submits to its ANEXT-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 lad^b. 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 SMLERS. 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,withtwopublicelementsg, 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,td_i) 2 Z_p⇥ G. These pairs of values define a unique polynomial f (x) of degree n⁰ such that f(0) = dlog_g(H) and f (x_i)=td_ifor every i 2 [n⁰]. Of course, since dlog_g(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^{) f}or 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 {xi*}i2[n0*]. 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*,td_i), and generate a proof for R_G by satisfying the first clause (proving knowledge of td_i), to include any pk in the ring. The pair (x_i,*td_i) is then removed from the list of trapdoors. (In case the owner of pk later wants to join the signature, the Extend algorithm encrypts td_ito pk; later, the owner of pk can recover td_iand 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 ˆxand 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 L^keys; 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 a_ll 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(µ, {pk_j}⁽l0⁾,sk_i,). 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,_sks*) ERS*.KeyGen() 2 :( pk_e,ske*) PKE*.*KeyGen()

0 Extend(µ, {pkj}j2R,,pk) 7! 1 : if pk 2{pk_j}j2R : return*?* 2 :(ˆ x, tdˆ )R T // Pick eval-point and trapdoor

3 : return (pk =(pks*,pke),sk =(_sks,ske*)) 3 : c⁰ Enc(pk*,*tdˆ ) // enable future endorsing e

Sign(µ, sk) 7!

// interpolate 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⁰,pk^s,⇡,c⁰)} 4 : td _R Zp // generate trapdoors for poly. values 7 : Randomly permute P 5 : T T [{(x, td)} // populate trapdoor set ⁰ 8 : return :=(T,P) 6 : c Enc(pke, ?) // no info to pass on ⇤ 7 :ˆ x R Z_p\ X // pick a new evaluation point Verify(t, µ, {pk_j}j2R,) 7! accept/reject 8 :( y, ⇡) PolySign(P, T, x, w ˆ := sk*,pk,µ*) 1 : if {pk_j}j2R 6= {pk_i}_{(·,·,pk,·,·)2P}: i

9 : P := {(ˆx, y, pk_s,⇡,c)} 10 : return :=(T,P) 0 Join(µ, {pkj}j2R,sk,) 7! // check if current signer’s pksis in P 1 : if 9 (x, y, pk*,⇡,c*) *2 Ps.t.*pk = pk_s

2 : return reject // check y’s are consistent 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 simulated proof for the signer who wants to join

2 : P P {(x, y, pk_s,⇡,c)} // retrieve trapdoor value 3 : td Dec(ske,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 the set of available trapdoors 10 :ˆ µ :=(µ, {Vi}_i2[n0_]) 4 : T T [{(x, td)}

c⁰ Enc(pk*, ?*)

11 : for (x, y, pks,⇡,c) 2 P // check proofs individually

5 :e// no info to pass on ⇤ 12 : :=(y,pks) 6 :ˆ x R Zp\ X // pick a new evaluation point 13 : if SoK*.Verify(ˆµ, RG,,⇡)=reject // interpolate a unique representation of the polynomial ⁰ 14 : return reject₀ 7 :( y⁰,⇡) PolySign(P, T, x, w ˆ := sk,pk,µ*) 15 : if |T | + |P |t + n return accept

0 8 : P P [{(ˆx, y⁰,pk_s,⇡,c⁰)} 9 : Randomly permute P 10 : return :=(T,P)

16 : else return 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 RG = x x {(, w)=(h, pk*,x*) 2 G ⇥ G ⇥ Zp : 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 (_sks,ske*)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?* ⁰ 4 : Join(µ, {pk_j}j2R,ski,) 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 OJoin (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 L_joinof 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 OJoin 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 L_join}| where L_joindenotes 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 pk^i⇤ := 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.

⁵ 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