Ring Signatures with User-Controlled Linkability

Abstract

Anonymous authentication primitives, e.g., group or ring signatures, allow one to realize privacy-preserving data collection applications, as they strike a balance between authenticity of data being collected and privacy of data providers. At PKC 2021, Diaz and Lehmann defined group signatures with User-Controlled Linkability (UCL) and provided an instantiation based on BBS+ signatures. In a nutshell, a signer of a UCL group signature scheme can link any of her signatures: linking evidence can be produced at signature time, or after signatures have been output, by providing an explicit linking proof.

In this paper, we introduce Ring Signatures with User-Controlled Linkability (RS-UCL). Compared to group signatures with user-controlled linkability, RS-UCL require no group manager and can be instantiated in a completely decentralized manner. We also introduce a variation, User Controlled and Autonomous Linkability (RS-UCAL), which gives the user full control of the linkability of their signatures.

We provide a formal model for both RS-UCL and RS-UCAL and introduce a compiler that can upgrade any ring signature scheme to RS-UCAL. The compiler leverages a new primitive we call Anonymous Key Randomizable Signatures (AKRS)—a signature scheme where the verification key can be randomized—that can be of independent interest. We also provide different instantiations of AKRS based on Schnorr signatures and on lattices. Finally, we show that an AKRS scheme can additionally be used to construct an RS-UCL scheme.

1 Introduction

Group signatures [CvH91, BMW03, BSZ05, BCC+16] and ring signatures [RST01] allow users to sign messages, while providing anonymity of signers and unlinkability of signatures. Group signatures require a central entity that manages group membership, whereas ring signatures allow a signer to choose an arbitrary ring of public keys, and sign on behalf of that ring.

Many application scenarios do not require full anonymity/unlinkability, and may actually ask for mechanisms to identify the signer or link signatures produced by the same party. Group signatures feature an opening authority that can de-anonymize signers and thereby test if two signatures have the same signer.

Recently, researchers have proposed more flexible linkability options for group signature schemes, where even less power is entrusted to the opener. In [HLC+11, HLC+13, SSU14, KTY04] group signatures with an authority who can test whether two signatures have the same signer but cannot open signatures were introduced. In [GL19, FGL21], group signatures are originally unlinkable, but later on can be converted to linkable signatures by an oblivious “converter”. Group signatures with message-dependant opening [SEH+12, OSEH13, LJ14, LMN16] introduce an additional entity, the admitter, who can specify messages such that the corresponding signatures can be opened. Group signatures with certified limited opening [ZWC19] introduce a certifier, instead of an admitter, who can certify a particular opener to allow them to open signatures on messages within a particular context. Abe et al., [ACHO13] use “public-key anonymous tag system” to build a traceable signature scheme. In all these lines of work, linking is performed by a trusted party, and signers have no say in which of their signatures can be linked together. Another line of work [BCC04, BFG+13, CDL16b, CDL16a] considers scenarios where a so-powerful authority is undesirable, and achieves linkability by including a one-way function of the signing key and a “scope” chosen by the signer—also known as “pseudonym”—in each signature, so that two signatures with the same pseudonym can be trivially linked.

Pseudonym-based linkability, however, require signers to decide at signature time whether their signatures should be ever linked: two signatures using different scopes – hence, with different pseudonyms – would be unlinkable by definition. Recently, Diaz and Lehmann [DL21] introduced group signatures with User-Controlled Linkability (UCL) that provide pseudonym-based linkability (labelled “implicit” linkability), but also allow a signer to link any set of her signatures generated with the same linking secret, even if those had different pseudonyms (labelled “explicit” linkability). This linking model turns useful in applications where authenticated data is collected in anonymous fashion but, later on, one may be interested to link specific data items. For example, in smart-metering applications, energy consumptions may be collected in a fully anonymous way, while, at a later time, a user may want to link her measurements to, e.g., receive tailored offers from the energy providers. Similarly, connected vehicles can anonymously report their mobility traces but, at a later time, a driver may want to link her reports so to obtain discounts from insurance companies.

Our Contributions. In this paper, we continue the study of UCL but focus on ring signatures. Compared to group signatures, a ring signature scheme enables fully decentralized applications as no group manager is needed. Previous linkable ring signatures [LWW04, SALY17] solely allow anyone to link two signatures by the same signer on the same ring.

Our first contribution is the formalization of UCL in ring signatures. We introduce the first formal model for ring signatures with UCL allowing for both implicit and explicit linkability, as in [DL21]. Next, we introduce ring signatures with User Controlled Autonomous Linkability (UCAL) to give signers full control over the linkability of their signatures. Different from UCL, UCAL does not use the signing key to create pseudonyms, but instead uses a “linking secret” which can be re-used or chosen afresh. A fresh linking secret ensures that signatures cannot be linked (i.e., via implicit linkability) even if they have the same scope. Of course, a signer can use the same linking secret on multiple signatures with the same scope so to provide implicit linkability. Ultimately, a signer can prove linkability of any set of her signatures generated with the same linking secret, even if those had different pseudonyms. Further, using different linking secrets ensures that past signatures cannot be linked even if the signer is corrupted, providing a form of forward anonymity.

As a second contribution we propose constructions of UCL and UCAL ring signatures. To do so, we introduce a new cryptographic primitive that we label Anonymous Key Randomizable Signatures (AKRS) that may be of independent interest. AKRS is essentially a signature scheme where public keys can be re-randomized, while maintaining the correspondence to the same secret key, so that a randomized public key cannot be linked to the original one. However, by using the secret, the signer can prove that multiple public keys are all randomized versions of the original one. The primitive is in a similar spirit to Signatures with Flexible Public Key [BHKS18], which however is not fully suitable for our requirements. We elaborate more on the differences in Sect. 3.

We show that AKRS can be used to upgrade any ring signature scheme to UCAL. In particular, we use an AKRS public key that has been re-randomised with the scope as the pseudonym for the (ring) signature. By using a public key corresponding to the same AKRS secret key and scope, we provide implicit linkability. Otherwise, the signer may use a different AKRS secret key to make two signatures unlinkable even on the same scope. At a later time, the signer can use her AKRS secret key to link the pseudonyms of a set of ring signatures, thereby proving that all such signatures are linked. Notably, our construction does not modify the original ring signature public keys and thus can be used to upgrade to UCAL an already up-and-running system using ring signatures.

We also show how to use AKRS, along with a NIZK, to build a UCL ring signature. The linking mechanism is obtained using the AKRS in a similar way to the UCAL construction. The difference is that, for UCL the AKRS secret key is used as the ring signature secret. Therefore, to sign a message with some scope, in addition to using the AKRS secret key to compute the pseudonym, we also add a non-interactive signature of knowledge [CS97] that the secret used to derive the pseudonym corresponds to one of the public keys in the ring.

Finally, we propose two instantiations of AKRS: one based on Schnorr’s signatures in prime order groups, and one based on Lyubashevsky’s signatures [Lyu12] on lattices. Compiling our AKRS with a ring signature scheme we get UCAL ring signatures with minimal overhead: one additional Schnorr or Lyubashevsky signature, respectively. In contrast to previous works (on group signatures) [DL21], the constructions are generic and can bootstrap any arbitrary ring signature scheme to a UCAL one. For instance we can achieve UCAL without pairings.

Related Work. There is an extensive line of work studying and constructing efficient ring signatures from various settings and assumptions, with the today’s state-of-the art achieving signatures of size logarithmic in the size of the ring [GK15, BCC+15, LPQ18, LRR+19, YSL+20, YEL+21].

Park and Sealfon [PS19] proposed the related notions of (un)Claimable and (un)Repudiable Ring Signatures. Claimability states that one can always claim a signature after she signed it, while Repudiability states the opposite, that one can always repudiate a signature she did not sign. Claimability is a notion relevant to user-controlled linkability, although it is weaker: a signer can claim a signature by linking it to a signature of a dummy message on-the-fly. The inverse, achieving user-controlled linkability from claimability, does not apply.

The idea of linking anonymous signatures of a user by using a Pseudorandom Function (PRF) has been used in the past. A user can additionally sign a random value together with its PRF output, where the seed is kept by the signer. Then, a NIZK proving knowledge of the (same) seed can be used to link signatures. However, this linking mechanism provides no succinctness: the linking proof typically grows with the number of linked signatures. AKRS generalizes this linking mechanism and guarantees succinctness; we note that an AKRS may also be instantiated with a PRF and a (succinct) NIZK.

2 Ring Signatures with User-Controlled Linkability

2.1 Standard Linkability

As in [DL21], we consider two types of linkability:

• Implicit linkability: Signatures are accompanied by a pseudonym, generated by the user for a particular scope. Re-using the same scope leads to the same pseudonym, making all signatures with the same scope linkable. Signatures with different scopes cannot be linked, except via explicit link proofs.

• Explicit linkability: A user can prove that she created a set of previously generated signatures, i.e. link the signatures in the set.

Definition 1 (RS-UCL)

A ring signature scheme with user controlled linkability (RS-UCL) is a tuple of PPT algorithms $(\textsf{KGen}, \textsf{Sig}, \textsf{Vf},\textsf{Link}, \textsf{VerifyLink})$, satisfying correctness, anonymity (Definition 3), unforgeability (Definitions 4 and 6) and non-frameability (Definitions 7 and 8); and with the following syntax:

• $\textsf{KGen}(1^\lambda )$ on input a security parameter, outputs a signing key $\textsf{sk}$ and a verification key $\textsf{vk}$.

• $\textsf{Sig}(\textsf{sk},R,m,\textsf{scp})$ signs a message m w.r.t. scope $\textsf{scp}$ via secret signing key $\textsf{sk}$ for set of verification keys (called the ring) $R=\{\textsf{vk}_1, \dots , \textsf{vk}_n\}$. The output is a pseudonym $\textsf{nym}$ and a ring signature $\sigma$.

• $\textsf{Vf}(\varSigma )$ on input a signature tuple $\varSigma =(m,\textsf{scp}, R,\sigma ,\textsf{nym})$ for ring $R=\{\textsf{vk}_1, \dots , \textsf{vk}_n\}$, returns 1 if $\sigma$ and $\textsf{nym}$ are valid for message m and scope $\textsf{scp}$ w.r.t. R, and 0 otherwise.

• $\textsf{Link}(\textsf{sk}, \textsf{lm}, \mathbf {\Sigma })$ on input a set of signature tuples $\varSigma =\{\varSigma _i\}_{i\in [n]}$, a user secret key $\textsf{sk}$, and a linking message $\textsf{lm}$ (can be used to ensure freshness of the proof), outputs a proof $\pi _l$ that these signatures are linked, or the error symbol $\bot$.

• $\textsf{VerifyLink}(\textsf{lm}, \mathbf {\Sigma }, \pi _l)$ returns 1 if $\pi _l$ is a valid proof that $\mathbf {\Sigma } =\{\varSigma _i\}_{i\in [n]}$ were produced by the same signer for link message $\textsf{lm}$, and 0 otherwise.

2.2 Autonomous Linking

We also introduce the notion of ring signatures with user controlled, and autonomous linking (RS-UCAL). This variant allows users to chose the linking secret independently of the signing key. It hence gives users the liberty of choosing which of their signatures should be linkable in the future. We express this feature via an additional algorithm $\textsf{GenLinkSec}$ which outputs a linking secret $\textsf{ls}$. Now both the signing algorithm and the linking algorithm should input both the signing secret $\textsf{sk}$ and the linking secret $\textsf{ls}$.

Definition 2

A ring signature scheme with user controlled autonomous linking (RS-UCAL) is a tuple of PPT algorithms $(\textsf{KGen}, \textsf{GenLinkSec}, \textsf{Sig}, \textsf{Vf},\textsf{Link}, \textsf{VerifyLink})$, where $\textsf{KGen}, \textsf{Vf}, \textsf{VerifyLink}$ have the same syntax as an RS-UCL, and:

• $\textsf{GenLinkSec}(1^\lambda )$ takes input a security parameter, and outputs a linking secret $\textsf{ls}$.

• $\textsf{Sig}(\textsf{sk},\textsf{ls},R,m,\textsf{scp})$ as in a RS-UCL scheme, only with additional input a linking secret $\textsf{ls}$.

• $\textsf{Link}( \textsf{ls}, \textsf{lm}, \mathbf {\Sigma })$ as in an RS-UCL scheme, only with input a linking secret $\textsf{ls}$ instead of the secret key.

An RS-UCAL scheme satisfies correctness anonymity (Definition 3), unforgeability (Definitions 5 and 6) and non-frameability (Definitions 7 and 8).

Text which is only occurs for a RS-UCAL scheme. Text which is only occurs for a RS-UCL scheme.

2.3 Correctness

An RS-UC(A)L scheme should satisfy both verification correctness, which is equivalent to correctness for standard ring signatures, and linking correctness which ensures the correctness of the explicit linking algorithm $\textsf{Link}$. We give the full definitions in the full version of this paper.

2.4 Security Model

For privacy, signatures must not reveal anything about the signer’s identity beyond what was intended by her (anonymity). Security is expressed through both unforgeability, which ensures that an adversary cannot forge a signature on behalf of a ring they are not a member of or forge a link proof for signatures they did not generate, and non-frameability, which states that an honest user cannot be framed by the adversary, so that signatures of an honest user are (implicitly or explicitly) linkable to signatures that she has not generated.

Fig. 1.

Global state variables and their contents.

Oracles and State. All oracles are parametrised by a list of keys pairs $\{(\textsf{pk}_i,\textsf{sk}_i)\}_{i \in [n]}$ , where . In Fig. 1 we describe the global state variables that all oracles can access.

• Corruption oracle $\textsf{Corr}$ takes as input an index $i\in [n]$, adds i to the list of corrupted indices $I\leftarrow I\cup \{i\}$, and outputs the randomness $w_i$ used to compute key pair $(\textsf{pk}_i,\textsf{sk}_i)$.

• 

• Signing oracle $\textsf{OSign}^{\textsf {ucl-r}}$: takes as input a set R, an index $i\in [N]$, , a message m and a scope $\textsf{scp}$ computes , adds $\varSigma :=(m, \textsf{scp}, R, \sigma , \textsf{nym})$ to the list of signatures signed by user index i : , and returns $(\textsf{nym},\sigma )$.

• Linking oracle $\textsf{OLink}$: Allows the adversary to obtain link proofs for signatures of its choice. On input a linking message $\textsf{lm}$ and a set of tuples $\mathbf {\Sigma } = \{\varSigma = (m, \textsf{scp}, R, \sigma , \textsf{nym})\}$, this oracle adds $(\textsf{lm},\mathbf {\Sigma })$ to the list of link proofs produced for index i: $\textsf {LNK}[i]\leftarrow \textsf {LNK}[i]\cup \{(\textsf{lm},\mathbf {\Sigma })\}$, and returns .

• Challenge signing oracle $\mathsf {Ch-Sign}_b$: Allows $\mathcal {A}$ to get signatures for challenge user index $i_b$ . On input a ring R, a message m, and a scope $\textsf{scp}$, $\mathsf {Ch-Sign}_b$ computes , sets $\varSigma :=(m, \textsf{scp}, R, \sigma , \textsf{nym})$, adds $\varSigma$ to the list of queried challenge signatures $\textsf {CSIG}\leftarrow \textsf {CSIG}\cup \{\varSigma \}$, and returns $(\textsf{nym},\sigma )$.

• Challenge linking oracle $\mathsf {Ch-Link}_b$: Allows $\mathcal {A}$ to get link proofs for a challenge index / . Precisely, on input a linking message $\textsf{lm}$ and a set of tuples $\mathbf {\Sigma } = \{\varSigma = (m, \textsf{scp}, R, \sigma , \textsf{nym})\}$, it adds $(\textsf{lm},\mathbf {\Sigma })$ to the list of challenge link proofs $\textsf {CLNK}\leftarrow \textsf {CLNK}\cup \{(\textsf{lm},\mathbf {\Sigma })\}$, and returns .

Helper Algorithm. As in [DL21], we introduce the helper algorithm $\textsf {Identify}$. In this case we do not need to require the existence of $\textsf {Identify}$, because there is no trusted issuer in the ring signature setting. Therefore, user secret keys do not need to be extracted from join protocols as in the group signature setting. $\textsf {Identify}$ here is just defined for notational simplicity, and can be achieved from the user controlled linkability functionality.

Anonymity. Anonymity ensures that an adversary cannot figure out which of two (honest) challenge users generated a given signature. In formalizing this notion, one must be careful to exclude trivial wins leveraging user-controlled linkability (see the comments in the security experiment).

Definition 3 (Anonymity)

An RS-UC L scheme satisfies adaptive anonymity against adversarially chosen keys if, for any PPT adversary $\mathcal {A}=(\mathcal {A}_1, \mathcal {A}_2)$, and any $n =\textsf{poly}{{(\lambda )}}$, , it holds that is negligible in $\lambda$.

Unforgeability. For both RS-UCL and RS-UCAL we must ensure that only ring members can sign. However, for RS-UCL, we must also prevent signers from outputting multiple unlinkable signatures on the same scope. For RS-UCL one captures both by defining an attack as the generation of more signatures with different pseudonyms than corrupted users in the ring, using the same scope. This is meaningless for RS-UCAL where a single corrupted user can generate many linking secrets.

Definition 4 (Signature unforgeability)

An RS-UCL scheme satisfies signature unforgeability if for any PPT adversary $\mathcal {A}$, and any $n=\textsf{poly}{{(\lambda )}}$, it holds that $\Pr [\textsf{Exp}_{\textsf{UCL},\mathcal {A}}^{\textsf {sig-uf}}(1^\lambda ,n)=1]$ is negligible in $\lambda$.

As mentioned earlier, Definition 4 is too strong for RS-UCAL. Indeed, the autonomous linking property allows parties to change the linking secret as frequently as desired. Hence an adversary which wants to output many unlinkable secrets could simply keep changing the linking secret. For such schemes we adopt a similar notion of (signature) unforgeability as that of standard ring signatures, with the difference that the adversary also has access to a linking oracle. We give the full experiment in Appendix B.

Definition 5 (Signature unforgeability with autonomous linking)

An RS-UCAL scheme satisfies signature unforgeability if, for any PPT adversary $\mathcal {A}$, and any $n=\textsf{poly}{{(\lambda )}}$, $k=\textsf{poly}{{(\lambda )}}$, it holds that $\Pr [\textsf{Exp}_{\textsf{UCAL},\mathcal {A}}^{\textsf {sig-uf-al}}(1^\lambda ,n,k)=1]$ is negligible in $\lambda$.

We additionally define link unforgeability for both the RS-UCL and RS-UCAL schemes, which ensures that the linking proof is unforgeable.

Definition 6 (Link unforgeability)

An RS-UC L scheme satisfies link unforgeability if, for any PPT adversary $\mathcal {A}$, and any $n=\textsf{poly}{{(\lambda )}}$, , the following is negligible in $\lambda$: .

Non-frameability. Non-frameability guarantees that an honest user cannot be framed by the adversary, such that signatures of an honest user are linkable to signatures that she has not generated. We capture this in the implicit/explicit setting with signature/link non-frameability respectively. We give the full games in Appendix B. Roughly, signature non-frameability ensures that an adversary cannot output a valid signature that links to another signature generated by an uncorrupted user via the signing oracle. Link non-frameability ensures that an adversary cannot explicitly link two signatures that were either from different users or such that one of the two signatures is not from a user in the experiment.

Definition 7 (Signature non-frameability)

An RS-UC L scheme satisfies signature non-frameability if, for any PPT adversary $\mathcal {A}$, and any $n=\textsf{poly}{{(\lambda )}}$, , the following is negligible in $\lambda$: .

Definition 8 (Link non-frameability)

An RS-UC L scheme satisfies link non-frameability if, for any PPT adversary $\mathcal {A}$, and any $n=\textsf{poly}{{(\lambda )}}$, , the following is negligible in $\lambda$: .

3 Anonymous Key Randomisable Signatures

We will now give the syntax and security requirements for a new primitive we call Anonymous Key Randomisable Signatures (AKRS), which is closely related to Signatures with Flexible Public Key (SFPK) [BHKS18].

Intuition. An SFPK scheme is a standard signature scheme that allows for public and secret keys to be re-randomised. These re-randomised keys are considered to be in the same equivalence class as the original key pair. Such re-randomised public keys, and signatures which verify for them, should not be linkable to the original key pair of their equivalence class. This is formalised by a class hiding requirement. Furthermore, during key generation, a trapdoor can be generated allowing to efficiently decide if public keys are in the same equivalence class.

At first sight, an SFPK scheme seems to allow transforming ring signatures into ring signatures with user controlled and autonomous linking. A user’s key pair would be that of a standard ring signature, while their linking secret key would be an SFPK key pair, with the corresponding trapdoor. During signing, the user’s pseudonym could be a re-randomisation of the SFPK public key with the randomness set to be the scope, so that the resulting public key is within the same equivalence class as the original keypair in their linking key. The signature should include a standard ring signature to ensure that the signature was output by a ring member and a SFPK signature valid under the public key in the pseudonym to prevent framing attacks.

However, in the SFPK class hiding requirement, which is necessary to ensure anonymity of the ring signature, the adversary does not get to see the randomness used to re-randomise the public key. In their game, the knowledge of this randomness allows to trivially win, as an adversary can re-run the randomisation algorithm itself. For the application to ring signatures described in the previous paragraph, this will not do, since the randomness is a public value: the scope. On the other hand, in this application, the SFPK’s secret key remains hidden: it is part of the linking secret, which is unknown to the anonymity adversary. Therefore, we modify SFPK to ensure that the secret key is necessary to generate public keys in the same equivalence class, thereby avoiding the aforementioned trivial attack, while allowing for the adversary to know the randomness.

A second issue in the above construction, is that signatures can only be explicitly linked by revealing the trapdoor, which would allow all signatures under the same linking key to be linked. One way around this is to add an additional functionality, proving, in zero-knowledge, that the pseudonyms in signatures are in the same equivalence class, using the trapdoor in the linking secret key. For efficiency, however, we chose a different approach: we allow for several key pairs in the same equivalence class to be accumulated into one key pair. Then the accumulated secret key could be used to sign a signature valid under the accumulated public key. A verifier can check that this signature is valid under an accumulated public key, resulting from the pseudonyms of all signatures being linked. This means the linking proof is only the size of an SFPK signature. However, explicitly linking signatures requires keeping track of each re-randomised secret key used in the linking key. We overcome this by re-randomising only public keys, but not secret keys, i.e., the secret key remains the same for all public keys in a given equivalence class. An accumulated public key will then correspond to the same secret key as the public keys it was built from, as long as the latter lie in the same equivalence class. Finally, observe that the secret key essentially fulfils the role of the trapdoor, as it allows to link public keys in the same equivalence class. We thus remove the trapdoor from our primitive’s syntax.

We now formally define Anonymous Key Randomisable Signatures. The security properties required are given in Sect. 3.1 to 3.3.

Definition 9 (Anonymous Key Randomisable Signature (AKRS))

An anonymous key randomisable signature scheme is a tuple of PPT algorithms $(\textsf{KGen}, \textsf{ChgPK}, \textsf{Sig}, \textsf{Vf}, \textsf{Accum})$, satisfying correctness (Definition 10), class hiding (Definition 11), existential unforgeability under chosen message attacks (Definition 12) and accumulation soundness (Definition 13); and with the following syntax:

• $\textsf{KGen}(1^\lambda )$ on input a security parameter $1^\lambda$, outputs a signing key $\textsf{sk}$ and a public key $\textsf{pk}$.

• $\textsf{ChgPK}(\textsf{sk}, t)$ on input a secret key $\textsf{sk}$ and a tag t, outputs a new public key $\textsf{pk}'$ in the same equivalence class.

• $\textsf{Sig}(\textsf{sk}, \textsf{pk}, m)$ on input a signing key $\textsf{sk}$, a public key $\textsf{pk}$ and a message m, outputs a signature $\sigma$.

• $\textsf{Vf}(\textsf{pk}, m, \sigma )$ on input a public key $\textsf{pk}$, a message m and a signature $\sigma$, the verification algorithm returns 1 if $\sigma$ is a valid signature on m w.r.t. $\textsf{pk}$, and 0 otherwise.

• $\textsf{Accum}((t_1, \textsf{pk}_1), \cdots , (t_k, \textsf{pk}_k))$ on input k public keys $\textsf{pk}_1, \cdots , \textsf{pk}_k$ with respect to tags $t_1, \cdots , t_k$, outputs an accumulated public key $\tilde{\textsf{pk}}$.

Definition 10 (Correctness)

Consider any positive integer k; any tags $t_1, \cdots , t_k \in \{0,1\}^*$; let $(\textsf{sk}, \textsf{pk}) \leftarrow \textsf{KGen}(1^\lambda )$, for all $i\in [k]$ $\textsf{pk}'_i \leftarrow \textsf{ChgPK}(\textsf{sk}, t_i)$, and $\tilde{\textsf{pk}} \leftarrow \textsf{Accum}((t_1, \textsf{pk}'_1), \cdots (t_k, \textsf{pk}'_k))$. An AKRS scheme is correct if for any message m, there exists a negligible function $\epsilon$ such that:

$$ \Pr \left[ \begin{array}{c|c} \begin{array}{c} \textsf{Vf}(\textsf{pk}, m, \sigma )=1 \\ \wedge \forall i\in [k],\, \textsf{Vf}(\textsf{pk}'_i, m, \sigma _i)=1 \\ \wedge \textsf{Vf}(\tilde{\textsf{pk}}, m, \tilde{\sigma })=1 \end{array} &{} \begin{array}{c} \sigma \leftarrow \textsf{Sig}(\textsf{sk},\textsf{pk},m),\\ \forall i\in [k],\, \sigma _i\leftarrow \textsf{Sig}(\textsf{sk},\textsf{pk}'_i,m),\\ \tilde{\sigma }\leftarrow \textsf{Sig}(\textsf{sk},\tilde{\textsf{pk}},m) \end{array} \end{array} \right] = 1-\epsilon (\lambda ). $$

If $\epsilon = 0$ then perfect correctness is satisfied.

3.1 Class Hiding

We ensure that an adversary cannot guess which of two public keys are re-randomised with a tag chosen by the adversary (through oracle $\textsf{OChgPK}$), even while they can obtain signatures on these public keys and the re-randomised keys (via the $\textsf{OSign}$ oracle).

Definition 11 (Class Hiding)

An anonymous key randomisable signature scheme satisfies class hiding if for any PPT adversary $\mathcal {A}=(\mathcal {A}_1, \mathcal {A}_2)$, $\Pr [\textsf{Exp}_{\textsf{A}\textsf{KRS},\mathcal {A}}^{\textsf {class-hiding}}(1^\lambda )=1]$ is negligible in $\lambda$:

3.2 Existential Unforgeability Under Chosen Message Attacks

We ensure that signatures cannot be forged for a public key in the equivalence class of an honest user, even when they can obtain multiple public keys in that equivalence class on tags of their choice. We give the full game in Appendix A.

Definition 12 (Existential Unforgeability under Chosen Message Attacks)

An anonymous key randomisable signature scheme satisfies existential unforgeability under chosen message attacks if for any PPT adversary $\mathcal {A}$, $\Pr [\textsf{Exp}_{\textsf{A}\textsf{KRS},\mathcal {A}}^{\mathsf {euf-cma}}(1^\lambda )=1]$ is negligible in $\lambda$.

3.3 Accumulation Soundness

This is a new requirement necessary due to the accumulation functionality. It must not be possible to produce a signature which verifies for an accumulated public key, if the public keys input to the accumulation algorithm do not belong to the same equivalence class.

Definition 13 (Accumulation Soundness)

An anonymous key randomisable signature scheme satisfies accumulation soundness if for any PPT adversary $\mathcal {A}$, $\Pr [\textsf{Exp}_{\textsf{A}\textsf{KRS},\mathcal {A}}^{\mathsf {acc-sound}}(1^\lambda )=1]$ is negligible in $\lambda$.

4 Constructions for RS-UCL and RS-UCAL

4.1 A RS-UCAL Construction

We provide a generic construction, upgrading a standard ring signature scheme to a scheme with user controlled autonomous linking. We build upon a standard ring signature scheme $\textsf{RS}:=(\textsf{KGen}, \textsf{Sig},\textsf{Vf})$ as described formally in the full version of the paper and an AKRS $\textsf{A}\textsf{KRS}=(\textsf{KGen}, \textsf{ChgPK}, \textsf{Sig}, \textsf{Vf}, \textsf{Accum})$, as defined in Sect. 3.

Our RS-UCAL scheme $\textsf{UCAL}$, given in Fig. 2, works as follows. Key generation is simply the key generation for a standard ring signature, whereas the linking secret is the secret key for an $\textsf{A}\textsf{KRS}$. When signing, the pseudonym is the public key corresponding to the linking secret, randomised with respect to the scope, a one way function of the linking secret and scope as desired. We then included a standard ring signature to ensure that a non-member cannot sign on behalf of the ring, i.e. signature unforgeability. In order to prevent a signature non-frameability attack, where an adversary uses the pseudonym of an honest user’s signature in their own signature, we also include an $\textsf{A}\textsf{KRS}$ signature with respect to the pseudonym as the public key. In order to explicitly link signatures we make use of the accumulation functionality from $\textsf{A}\textsf{KRS}$. A set of signatures that were all generated with the same linking secret contain pseudonyms that can be accumulated. This accumulated public key can be used to sign an $\textsf{A}\textsf{KRS}$ signature, which will be the link proof. Due to the accumulation soundness property and unforgeability of $\textsf{A}\textsf{KRS}$, link non-frameability and link unforgeability are ensured, respectively. Anonymity follows from the anonymity of standard ring signatures, and the class hiding property of the $\textsf{A}\textsf{KRS}$ which ensures $\textsf{A}\textsf{KRS}$ public keys and signatures cannot be linked based on equivalence class, and so $\textsf{UCAL}$ signatures cannot be linked based on the linking secret.

We prove the following theorem that $\textsf{UCAL}$ is a secure UCAL ring signature in the full version of the paper.

Theorem 1

If $\textsf{A}\textsf{KRS}$ is an anonymous key re-randomisable signature scheme and $\textsf{RS}$ is a (standard) ring signature scheme, then $\textsf{UCAL}$ is a ring signature scheme with user controlled autonomous linking.

Fig. 2.

RS-UCAL from standard ring signatures and AKRS.

4.2 Construction for Ring Signatures with User Controlled Linkability

We provide a generic construction for a ring signature scheme with user controlled linking. We build upon a NIZK for the language $\mathcal {L} = \{(\textsf{nym}, \textsf{scp}, (\textsf{vk}_i)_{i \in [n]};\textsf{sk}): \textsf{nym}= \textsf{A}\textsf{KRS}.\textsf{ChgPK}(\textsf{sk}, \textsf{scp}) \wedge \bigvee _{i \in [n]} ( \textsf{vk}_i, \textsf{sk}) = \textsf{A}\textsf{KRS}.\textsf{KGen}(1^\lambda ) \}$ and an AKRS $\textsf{A}\textsf{KRS}=(\textsf{KGen}, \textsf{ChgPK}, \textsf{Sig}, \textsf{Vf}, \textsf{Accum})$, as defined in Sect. 3.

Our RS-UCL scheme $\textsf{UCL}$, given in Fig. 3, works as follows. Key generation (instead of the linking secret generation) is now identical to key generation for an $\textsf{A}\textsf{KRS}$. When signing, the pseudonym, similarly to the $\textsf{UCAL}$ construction, is the $\textsf{A}\textsf{KRS}$ public key randomised with the scope and now with the ring signature secret key corresponding to the $\textsf{A}\textsf{KRS}$ secret key. For the RS-UCL model, we additionally need to prove that the pseudonym was generated with a secret key corresponding to one of the public keys in the ring to ensure signature unforgeability. This ensures that if an adversary holds n keys in the ring, they can only generate n different pseudonyms and so output n unlinked signatures. We therefore attach a non-interactive zero-knowledge proof of knowledge that attests to this, which also fulfills the role of the ring signature in the $\textsf{UCAL}$ construction. The $\textsf{A}\textsf{KRS}$ signature from the $\textsf{UCAL}$ construction is now also not needed to ensure signature non-frameability, because it is necessary to know the secret key corresponding to a pseudonym in order to generate the NIZK. Explicit linking can be done in exactly the same way as the $\textsf{UCAL}$ construction with link non-frameability and link unforgeability satisfied in the same way. Anonymity similarly follows from the class hiding property of the $\textsf{A}\textsf{KRS}$, and now also from the zero knowledge property of the NIZK.

Fig. 3.

RS-UCL from AKRS and non-interactive zero knowledge proofs of knowledge.

We prove the following theorem that $\textsf{UCL}$ is a secure UCL ring signature in the full version of the paper.

Theorem 2

If $\textsf{A}\textsf{KRS}$ is an anonymous key re-randomisable signature scheme and $\textsf{NIZK}$ is a non-interactive zero knowledge proof of knowledge satisfying simulation sound extractability, then $\textsf{UCL}$ is a UCL ring signature.

5 $\textsf{A}\textsf{KRS}$ Instantiations

5.1 Construction from Schnorr Signatures

Consider a group $\mathbb {G}$, of prime order q, generated by g; and hash functions $\textsf{H}_1:\{0,1\}^*\rightarrow \mathbb {G}$, and $\textsf{H}_2:\{0,1\}^*\rightarrow \mathbb {Z}_q$. In Fig. 4, we recall the standard algorithms of the standard Schnorr signature scheme. We also introduce new algorithms $\textsf{ChgPK}$ and $\textsf{Accum}$ which augment the scheme to an $\textsf{A}\textsf{KRS}$.

Fig. 4.

Schnorr $\textsf{A}\textsf{KRS}$

Security Argument. We now provide some intuition as to why the augmented Schnorr signature given in Fig. 4 satisfies our requirements for an AKRS. Unforgeability is, modulo minor technical details, inherent from the unforgeability property of Schnorr Signatures. Class hiding follows from the fact that two public keys in the same equivalence class are of the form $(\textsf{H}_1(t), \textsf{H}_1(t)^x)$ and $(\textsf{H}_1(t'), \textsf{H}_1(t')^x)$, which is a DDH tuple. Therefore, linking public keys by equivalence class can be reduced to distinguishing DDH tuples. In the proof, signatures can be simulated without the secret key, assuming that $\textsf{H}_2$ is a random oracle. Accumulation soundness is the property that involves more novel techniques, in the design of our construction and its security analysis. The accumulation algorithm can be seen as a way to batch $\ell$ Schnorr statements with the same witness into a succinct proof that, to the best of our knowledge, is new. Roughly, accumulation soundness follows from the fact that signing with respect to an accumulated public key $(\prod \tilde{g}_i, \prod \tilde{h}_i)$ requires knowledge of the discrete logarithm of $\prod \tilde{h}_i$ base $\prod \tilde{g}_i$. Letting $\prod \tilde{g}_i = \prod \textsf{H}_1(t_i) = g^{\sum \tilde{t}_i}$, where $\textsf{H}_1(t_i) = g^{\tilde{t_i}}$ the adversary must know $\frac{\sum \textsf{sk}_i \tilde{t_i}}{\sum \tilde{t_i}}$, which entails knowledge of the $\tilde{t}_i$, i.e. breaking the discrete logarithm. For lack of space we leave the formal proofs for the full version of the paper.

Compiling to UCAL and UCL. Combined with any Ring Signature scheme the above AKRS gives a UCAL-Ring Signature with a very small overhead: for the signature size it is 1 additional Schnorr Signature, while all the extra computational costs are insignificant. Then, linking $\ell$ signatures requires a group multiplication of $\ell$ elements and a Schnorr Signature. Verifying the linking of $\ell$ signatures requires $\ell$ group multiplications and a Schnorr-Signature verification. For UCL the main efficiency overhead comes from the NIZK. Our Schnorr-based $\textsf{A}\textsf{KRS}$ allows for the k-out-of-n NIZK by Attema et al. [ACF21] to be used (setting $k=1$), which gives similar asymptotic performance to the state-of-the-art on Ring Signatures [GK15, BCC+15, LPQ18, LRR+19, YSL+20, YEL+21].

5.2 Lattice Construction

Our Lattice-based $\textsf{A}\textsf{KRS}$ is based on the Fiat-Shamir signature scheme by Lyubashevsky [Lyu12], which can be seen as the Lattice analogue of Schnorr signatures. We show how to bootstrap this signature scheme to an $\textsf{A}\textsf{KRS}$. For the sake of simplicity we describe the scheme w.r.t. integer lattices (based on SIS). However, it extends normally to ideal lattices (based on ring-SIS). The construction is in Fig. 5. where in the above $D_{\boldsymbol{v}, \sigma }^\mu (\cdot )$ is the discrete normal distribution over $\mathbb {Z}^\mu$ centered around $\boldsymbol{v} \in \mathbb {Z}^\mu$ ($D_{\sigma }^\mu (\cdot )$ centered around $\boldsymbol{v} = 0$ resp.) with standard deviation $\sigma$ and $n,\mu ,k, \sigma , M, \eta , d$ are parameters. We refer to [Lyu12] for details.

Fig. 5.

Lattice-based $\textsf{A}\textsf{KRS}$

Security and Parameters. For Class hiding to hold it is sufficient to show that $(\boldsymbol{\tilde{A}}_1, \boldsymbol{\tilde{A}}_1 \boldsymbol{S}) \approx (\boldsymbol{\tilde{A}}_2, \boldsymbol{\tilde{A}}_2 \boldsymbol{S}) \approx \ldots \approx (\boldsymbol{\tilde{A}}_\ell , \boldsymbol{\tilde{A}}_\ell \boldsymbol{S})$, where . If we apply the Leftover hash lemma [HILL99] to the hash function:

then the statistical distance of $f(\boldsymbol{S})$ from the uniform over $\mathbb {Z}_{q}^{n \times k}$ is negligible ($2^{- \lambda }$) if $\mu \log (2d+1) \ge k \ell n +2 \lambda$. So if we set $\ell _{\textsf{max}}$ to be the maximum number of re-randomizations of the public key and $\mu \ge (k \ell _{\textsf{max}} n + 2 \lambda )/\log (2d+1)$ then we get class-hiding. The rest of the lattice parameters are set according to [Lyu12].

Unforgeability then comes directly from the unforgeability of [Lyu12] signatures and Accumulation Soundness is analogous to the Schnorr Signatures $\textsf{A}\textsf{KRS}$ construction. Due to space limitations we postpone the detailed proofs for the full version.

Compiling to UCL and UCAL. As in the Schnorr signatures case, the overhead of bootstrapping a ring signature scheme to a UCAL one with the above AKRS is minimal. We further note that concrete costs of our AKRS (and thus the compilation to UCAL) can be optimized using follow-up optimizations on the Lyubashevsky signatures [DDLL13]. For UCL any general purpose NIZK for lattice relations can be used; our AKRS language is a basic lattice one.

6 Conclusions

In this paper, we have introduced Ring Signatures (RS) with User-Controlled Linkability (UCL) and User-Controlled Autonomous Linkability (UCAL). RS-UCL allows for both implicit and explicit linkability of signatures. Thus, signers can decide to make their signatures linkable either when issuing the signatures (by using the same scope in all signatures to be linked) or at a later time (by providing an explicit linking proof). We note that UCL was recently defined for group signatures. However, we argue that ring signatures are better suited for distributed applications, as no group manager is necessary. As such RS-UCL finds direct applicability in smart metering or smart mobility applications as argued in Sect. 1. Also, RS-UCL may be used in e-voting protocols where each election could use a different scope so that (i) double-voting in the same election round would be detected by implicit linkability, and (ii) voters can use the same (registered) key across election rounds.

RS-UCAL gives even more power to signers as they now can ensure unlinkability of their signatures, even if signatures use the same scope. Still, at a later time signers can prove linkability with an explicit linking proof.

We show how to upgrade any RS to RS-UCAL by means of a new cryptographic primitive that we have introduced in this paper and that we have labelled Anonymous Key Randomisable Signatures (AKRS). We have also shown how AKRS can be used to instantiate RS-UCL. We note that AKRS may be of independent interest and we have introduced two AKRS instantiations, one in prime-order groups and one based on lattices.

Appendices

A Full Definitions for our AKRS Model

We here provide the full experiment for our AKRS existential unforgeability under chosen message attacks requirement.

B Full Definitions for our Ring Signature Models

We here provide the full definitions for ring signatures with user controlled (autonomous) linking that were omitted from the main body of the paper.

Signature Unforgeability for RS-UCAL. We next provide the full experiment for the signature unforgeability requirement in the RS-UCAL model.

Non-Frameability. We now provide the full experiments for both the signature non-frameability and link non-frameability requirements in the RS-UC L model.