Delegatable Anonymous Credentials from Mercurial Signatures with Stronger Privacy

Anonymous credentials (ACs) allow an authority (the issuer) to issue user credentials that can then be used for anonymous authentication. This primitive was envisioned by Chaum in [15] and later technically realized by Camenisch and Lysyanskaya in [12]. Importantly, in an AC scheme, a verifier and a user (also called a “credential holder”) engage in a showing (also called a “proof” or “presentation”) which proves to the verifier that the user has a valid credential. The scheme is anonymous if a user can show their credential multiple times in an unlinkable fashion. Intuitively, anonymity means that after verifying the credentials of two users, an adversary should not be able to tell if the credentials are both from a single user or from two different users.

Delegatable anonymous credentials (DACs) were introduced by Chase and Lysyanskaya [14]. As the name suggests, DAC schemes allow a root issuer to delegate their credential-issuing power to other “intermediate” issuers. This delegation allows any intermediate issuer to issue credentials on behalf of the root issuer (or possibly, re-delegate their issuing power), creating a delegation chain between the root issuer, the intermediate issuers, and the credential holder. Belenkiy, Camenisch, Chase, Kohlweiss, Lysyanskaya and Shacham showed how to realize DACs for arbitrarily long delegation chains [2].

Delegation alleviates the burden on the root issuer without revealing the root issuer’s secrets to any other issuer, similar to a key hierarchy in a public key infrastructure (PKI) system. Unlinkability of DACs ensures the anonymity of credential holders, as well as the anonymity of any issuers who participated in that credential’s delegation chain. The anonymity of intermediate issuers implies that given the showing of two credentials, an adversarial verifier cannot determine if they were issued by the same intermediate issuer or different intermediate issuers. Hiding the intermediate issuer is important for a DAC scheme as revealing the identities of these intermediate issuers might reveal information about the end user. The root issuer is always identified in a showing as the verifier must trust some key for unforgeability.

An important property when practically using ACs and DACs is non-transferability. This property ensures that users cannot easily share their credentials with other users. One way of providing this is to ensure that a user cannot share one of her credentials without sharing all of her credentials (and corresponding secrets). This is known as the “all-or-nothing” approach [12] and should disincentivize sharing of credentials by users’ fear of losing control over their credentials. Another feature that is particularly important for the practical application of (delegatable) anonymous credentials is revocation. Unfortunately, this property is often neglected. It is quite clear that when preserving user’s privacy, standard approaches to recovation known from classical PKI schemes do not work. While there are various different approaches to revocation of anonymous credentials [7, 9,10,11,12,13, 19], in the delegatable setting this seems much harder to achieve and the topic is largely unexplored [1].

1.1 Previous Work on DAC and Motivation for Our Work

As in the recent work of Mir, Slamanig, Bauer, and Mayrhofer [28], we are particularly interested in developing practical DAC schemes. For a broader understanding, readers are directed to their comprehensive overview. The first practical DAC was proposed by Camenisch, Drijvers, and Dubovitskaya [8], but unfortunately they do not support an anonymous delegation phase. This, however is a crucial privacy requirement. The DACs by Blömer and Bobolz [4] as well as [28] represent two relevant and efficient DAC candidates as they have anonymous delegations and additionally, compact credentials. Unfortunately, [28] does not provide the important property of non-transferability, and for both [4, 28] the delegated credential is distributed independently of any of the previous delegators. Consequently, it seems very hard to efficiently achieve revocation of delegators for those schemes.

Crites and Lysyanskaya [17] came up with a simple architecture (which we will call “CL-type DAC”) for delegatable anonymous credentials that uses mercurial signatures (MS). These CL-type DACs bring the use of equivalence class signatures, extensively used in anonymous credentials [16, 19, 20, 25, 26, 28], to the DAC setting (with numerous follow up works [18, 27, 29, 31] on various aspects). In CL-type DACs, the “links” in a delegation chain are signatures; this chain includes the root’s signature on the first intermediate issuer’s public key; then for \(i \ge 1\), the \(i^\textit{th}\) intermediary’s signatures on the \(i+1^\textit{st}\) intermediary’s public key, and finally the last intermediate issuer’s signature on the credential holder’s public key. In order to ensure unlinkability, mercurial signatures allow randomization of both the signer’s public key to an equivalent but unlinkable public key, and the randomization of the message to an equivalent but unlinkable message. As an example delegation chain in a CL-type DAC, would first require a root (or certification) authority (CA) which holds a signing key of an MS scheme and to issue a credential to a user, Alice. To do this, the root authority produces a signature \(\sigma _{{ CA },A}\) on an MS public key \(\textsf{pk}_A\) of Alice. By demonstrating knowledge of the corresponding secret key to \(\textsf{pk}_A\) along with the root’s signature on \(\textsf{pk}_A\), Alice can authenticate herself. Now if Alice wants to delegate a credential to Bob, she uses her corresponding secret key to produce a signature \(\sigma _{A,B}\) on Bob’s MS public key \(\textsf{pk}_B\), where the signature acts as a credential for Bob. Now Bob can authenticate himself by demonstrating knowledge of the corresponding secret key (to \(\textsf{pk}_B\)) and showing the signatures from both the root (\(\sigma _{{ CA },A})\) and from Alice (\(\textsf{pk}_A,\sigma _{A,B})\). This principle can be applied to an arbitrarily long delegation chain. Now assume that Bob wants to show in a privacy-preserving way that he has been delegated a credential by CA. He can do this by demonstrating \(({\textsf{pk}_{CA}}, {\textsf{pk}_{A}}',{\textsf{pk}_{B}}'),(\sigma _{{ CA },A}',\sigma _{A,B}')\) where \({\textsf{pk}_{A}}'\) and \({\textsf{pk}_{B}}'\) are new representatives of the respective key classes (and by the properties of MS, they are unlinkable to the previous ones) and the signatures \((\sigma _{{ CA },A}',\sigma _{A,B}')\) are adapted to the new messages and public keys respectively (which are similarly unlinkable). In the concrete CL construction [17], the MS scheme works in a bilinear group setting where w.l.o.g. the public key of the CA lives in the second source group, \(\mathbb {G}_2\), and the public key of Alice in \(\mathbb {G}_1\). Consequently, since the public keys of the MS scheme on the next level need to live in the message space of the MS scheme of the previous level, one always needs to switch the groups for the MS scheme on every level, which is an important detail to keep in mind.

One important limitation of existing DAC approaches [17, 18, 28, 31], besides not yet supporting revocation, is that they only satisfy a weak notion of privacy. In particular it is not possible to guarantee anonymity even in the case of an honest-but-curious delegator in the credential chain (or when the root authority and a single delegator on the delegation chain collaborate, in the case of [28]). In prior constructions of CL-type credentials [17, 18, 31] this is because public keys in these constructions are traceable (using the secret key) regardless of how they have been randomized. Thus, a malicious delegator can identify itself on a chain and break anonymity.

When it comes to revocation in DAC, the only work so far is by Acar and Nguyen [1], which is based on the generic DAC template in [2] from randomizable NIZK proofs and in addition uses homomorphic NIZK proofs. While this can be instantiated from the Groth-Sahai [24] proof system, this is not very attractive from a practical perspective due to significant costs. So having practical DACs with revocation is an open problem.

Our work can be seen as the continuation of the research initiated by Crites and Lysyanskaya in [17], closing these existing gaps for practical DAC schemes. To do this, we create a mercurial signature scheme with a stronger privacy property called adversarial public key class-hiding. An overview of this approach is outlined in the technical overview in Sect. 1.3. Ensuring that maliciously created public keys in mercurial signatures are not traceable by their owners after being randomized has been an open problem since their introduction in [17]. A very recent work introduced the notion of interactive threshold mercurial signatures [29] to overcome said limitation, but it requires an interactive signing protocol that computes a signature from shares of a secret key that are distributed among parties. While such an approach is satisfactory for anonymous credentials and can also be used to distribute trust of the root authority in DAC schemes, it’s unclear how it can be used to efficiently manage delegations. Instead, we introduce structured public parameters which we carefully glue over the delegation levels to enable strong privacy features (and without requiring any interaction). Since the setup of these parameters also produces trapdoors that endanger privacy, we show how to overcome this problem by using techniques well-known from updatable structured reference string in zero-knowledge proof systems [23]. For revocation in DAC, we introduce a new and practical approach that is applicable to any CL-type DAC scheme.

1.2 Our Contributions

Subsequently, we summarize our contributions:

New Mercurial Signatures. First, as our core building block, we define a new flavor of a mercurial signature scheme which satisfies a stronger class hiding property, namely adversarial public-key class hiding (APKCH). Unlike in the mercurial signature definition of Crites and Lysyanskaya [17], here the adversary comes up with a public key and signs a message of its choice; the challenge for an adversary is to distinguish between a randomized version of his own public key and signature and a fresh, unrelated public key and a signature on the same message under that fresh public key. We give a construction of an APKCH signature scheme in the generic group model. Adversarial public-key class hiding is sufficient to construct a DAC scheme with strong privacy.

New Technique for Revocation in DAC. We introduce a new revocation approach for DACs. The basic idea is that a revocation authority maintains a public deny list, which verifiers can use to ensure that a credential shown to them does not contain any revoked delegators. Thereby any user who wants to receive a credential or obtain delegation rights (while still supporting later revocation) must first register their key with the revocation authority. This registration is anonymous and neither a verification of the user’s identity is needed nor a proof of knowledge of their key needs to be performed. This gives a simple privacy-preserving way for revocation in DAC, can be used for any CL-type DAC and does so without resorting to heavy tools such as malleable NIZKs as done in [1].

Model and Instantiation of DAC with Strong Privacy and Revocation. We introduce a conceptually simple model for revocable DAC schemes with strong privacy using game-based security definitions. We believe that this notion is easier to use than the simulation-based security notions provided in [1]. Then, using our mercurial signature scheme with \(\ell =2\), we construct a conceptually simple DAC scheme with delegator revocation and without requiring extensive use of zero-knowledge proofs. We stress that this gives a CL-type DAC scheme, where privacy holds even when the adversary is allowed to corrupt the root and all delegators simultaneously.

1.3 Technical Overview

Public keys in the mercurial signature from [17] are \(\ell \)-length vectors of group elements and are constructed as \(\textsf{pk}=\{{\hat{X}}_i\}_{i\in [\ell ]}=\{{{\hat{P}}}^{x_i}\}_{i\in [\ell ]}\) where the secret key is \(\textsf{sk}=\{x_i\}_{i\in [\ell ]} \in (\mathbb {Z}_p^*)^{\ell }\) and \({{\hat{P}}}\) is the generator the second source group of a bilinear pairing. Anyone can randomize a public key \(\textsf{pk}\) to a new representative of the equivalence class to get \(\textsf{pk}'=\textsf{pk}^\rho =\{{\hat{X}}_i^\rho \}_{i\in [\ell ]}\) for \(\rho \in \mathbb {Z}_p\). Unfortunately, such public keys are immediately recognizable to an adversary who holds the corresponding secret key. For an adversary to recognize a public key, it suffices to exponentiate each element in the public key by the inverse of the corresponding element in the secret key and check that the result has the form: \(\{{{\hat{P}}}^\rho \}_{i\in [\ell ]}\) (a vector of equal elements).

One approach to overcome the above limitation is to ensure that each element in a public key is computed over a distinct generator of the group where the discrete logarithms between these generators are random and not known. For example, if we add a trusted setup to the scheme from [17]: \(\textsf{Setup}(1^\lambda )\rightarrow \textsf{pp}=\{{{\hat{P}}}_1,{{\hat{P}}}_2,...,{{\hat{P}}}_\ell \}\) where \({{\hat{P}}}_i={{\hat{P}}}^{{\hat{b}_{i}}}\) for \(\ell \) randomly sampled \({\hat{b}_{i}}\) scalars in \(\mathbb {Z}_p\) and public keys are computed as \(\textsf{pk}=\{{\hat{X}}_i={{\hat{P}}}_i^{x_i}\}_{i\in [\ell ]}\) then it can be shown that under the DDH assumption that an adversary cannot distinguish a randomization of their public key from a freshly sampled key.

This appears promising, especially since these \({{\hat{P}}}_i\) values are all distinct and can be efficiently sampled in the ROM. But, if an honest user receives a public key, it is not immediately clear how to ensure that it wasn’t created maliciously so that they are recognizable (e.g., ensure the adversary did not compute the public key independent of the public parameters as \(\textsf{pk}=\{{{\hat{P}}}^{x_i}\}_{i\in [\ell ]}\) which would be recognizable). To ensure that maliciously created public keys are computed over these bases without the need for zero knowledge proofs, we add what we call “verification bases” to the public parameters. The verification bases are structured so that they can be paired with the key to prove that it was computed using the trusted public parameters. To accomplish this, we need to expand the size of the public key vectors to double their length (\(2\ell \)). This extra half of the public key will be the result of exponentiating different bases in the public parameters with the same secret key as in the first half. Specifically, our public parameters (w.r.t. public keys) consist of \(\mathbf {{\hat{B}}}=\{{{\hat{B}}_{i}}\}_{i\in [2\ell ]}=\{{{\hat{P}}}^{{\hat{b}_{1}}},\ldots ,{{\hat{P}}}^{{\hat{b}_{\ell }}},{{\hat{P}}}^{{\hat{b}_{1}}\hat{d}_{1}},\ldots ,{{\hat{P}}}^{{\hat{b}_{\ell }}\hat{d}_{\ell }}\}\) such that \(\textsf{dlog}_{{{\hat{B}}_{i}}}({{\hat{B}}_{\ell +i}})=\hat{d}_{i}\). We then include the verification bases in the public parameters which are computed as: \(\textbf{V}=\{{V_{i}}\}_{i\in [\ell ]}=\{{P}^{v_{1}\hat{d}_{1}},\ldots ,{P}^{v_{\ell }\hat{d}_{\ell }},{P}^{v_{1}},\ldots ,{P}^{v_{\ell }}\}\) (for randomly sampled scalars, \(\{v_{i}\}_{i\in [\ell ]}\)) such that \(\forall i\in [\ell ],e({V_{i}},{{\hat{B}}_{i}})=e({V_{\ell +i}},{{\hat{B}}_{\ell +i}})\). Then, key pairs are computed as , \(\textsf{pk}=\{{\hat{X}}_i\}_{i\in [\ell ]}=\{{{\hat{B}}_{i}}^{x_i}\}_{i\in [\ell ]}\Vert \{{{\hat{B}}_{\ell +i}}^{x_i}\}_{i\in [\ell ]}\). We can see now that \(\forall i\in [\ell ],e({V_{i}},{\hat{X}}_{i})=e({V_{\ell +i}},{\hat{X}}_{\ell +i})\). Thus, a verifier can take this length \(2\ell \) public key and use the verification bases (\(\textbf{V}\)) to verify it by computing these pairings. If these pairing equations hold, then, because the elements in the upper half of \(\mathbf {{\hat{B}}}\) are the only elements in the second source group that are exponentiated with \(\hat{d}_{i}\), the adversary must have computed the upper half of the public key with these bases. Through a similar argument, the lower half of the public key must be computed over the lower half of the public key bases in the public parameters. Thus, if these pairing equations hold for a public key, then randomizations of that public key are unrecognizable to the adversary. Because we need correlated randomness in the trapdoors (e.g. both \({V_{i}}\) and \({{\hat{B}}_{\ell +i}}\) are computed using \(\hat{d}_{i}\)) we can no longer use the ROM to generate these parameters and instead must use the common reference string (CRS) model.

We quickly run into a second problem as with these modified public keys as correctness falls apart when we attempt to sign messages. In [17], signatures are computed as \(\sigma =(Z,Y,{\hat{Y}})\) with \(Z=(\prod _{i\in [\ell ]} M_i^{x_i})^y\), \(Y={P}^{1/y}\), and \({\hat{Y}}={{\hat{P}}}^{1/y}\). Verification is done via a pairing product equation: \(e(Z,{\hat{Y}})=\prod _{i\in [\ell ]} e(M_i,{\hat{X}}_i)\), which will not verify with the new structure of public keys that we’ve introduced in this section. Therefore, we expand the message space to vectors of \(2\ell \) elements instead of \(\ell \) elements and include \(\forall i\in [\ell ],{P}_i={P}^{{\hat{b}_{i}}}\) in the public parameters. Messages then have the form: \(M=\{{P}^{m_i}\}_{i\in [\ell ]}||\{{P}_i^{m_i}\}_{i\in [\ell ]}\) for some vector \(\{m_i\}_{i\in [\ell ]}\in \mathbb {Z}_p^\ell \). In this modified scheme, the structure of Y and \({\hat{Y}}\) remains unchanged, but we then use the upper half of the message vector in our \(\textsf{Sign}\) function and the lower half of the message vector in our \(\textsf{Verify}\) function. This modification leads to a correct verification, now given by: \(e(Z,{\hat{Y}})={e({P},{{\hat{P}}})}^{\sum _{i\in [\ell ]} m_ix_i{\hat{b}_{i}}}=\prod _{i\in [\ell ]}e(M_i,{\hat{X}}_i)\). We also have to add more structure to achieve a signature that yields DAC as the lower half of the message (which will be another public key in a DAC credential chain) is recognizable. We add this extra structure in Sect. 3.

Constructing a Strongly Private DAC. As previously mentioned, [17] works by alternating the use of two signature schemes so that even delegation levels are signed with one of the schemes and the odd ones with the other. This way, the message space in one of the schemes is the public key space of the other.

Our approach is to build a structured random string so that each scheme can sign public keys for the next level of the credential chain using unique blinding factors taken from the CRS for each level. This poses a challenge as we need to correlate the structure of both schemes for messages and public keys. To this end, the keys used in our scheme are twice the size of the keys in [17]. Fortunately, for CL-type DACs \(\ell =2\) and typical applications that use delegation do not require long delegation chains (e.g., driving licenses or official identity documents), making this approach entirely practical. To illustrate it, we consider a DAC scheme for \(L=3\). We can generate the public parameters, , , . We can see that the bases from \(\textsf{pp}\) and \(\textsf{pp}'\) have a structure that satisfies: and similar for \(\textsf{pp}'\) and \(\textsf{pp}^*\). Hence, such public parameters can be used to build public keys for the credential chain as: , , . It follows from inspection that if we use \(\textsf{sk}=\{x_0,x_1\}\) to sign the third and fourth elements of \(\textsf{pk}'\), the signature will verify using the first and second elements from \(\textsf{pk}'\). Similarly, if we use \(\textsf{sk}'=\{x_0',x_1'\}\) to sign the third and fourth elements in \(\textsf{pk}^*\), the signature will verify under the first half of \(\textsf{pk}'\) with the first half of \(\textsf{pk}^*\) as the message. Because these trapdoors are shared across schemes, we need the security properties of our signature scheme to hold when multiple correlated copies of the scheme are generated. We describe this requirement of our signature scheme further in Sect. 3.3 where we present the above example with more detail in Fig. 5.

Removing Trust in the Parameter Generation. As it is apparent from our above discussion, the generation of parameters in setup involves a number of exponents that must not be available to any party. Putting trust in the party running this setup to discard these values is typically not desirable, especially in a DAC setting where there are numerous parties involved. One way to deal with this issue is to run specific multi-party computation protocols to generate the parameters [3, 6], e.g., running distributed key generation protocols. In order to avoid interaction among many parties, one particularly appealing approach was proposed by Groth et al. [23] in the context of zk-SNARKs, i.e., so called updatable reference strings. This means that some (potentially malicious) party can generate a reference string and any (potentially malicious) party in the system can update the reference string. Thereby every party outputs a proof that the computation was performed honestly and when the chain of proofs from the generation until the last update of the reference string verifies and at least one of the involved parties is honest, it is ensured that no one knows the trapdoors. Since this process can be done strictly sequentially this seems much more interesting for practical application, as for instance demonstrated by the powers of tau ceremony recently run by Ethereum^{Footnote 1}, with around 95k contributors (cf. [30]). We note that in our case this can be done very efficiently using Fiat-Shamir transformed Schnorr proofs for discrete logarithm relations. In the full version of this paper [22] we present the concrete relations for the updates. In brief, the costs are \(5\ell \) Pedersen commitments for the trapdoors, \(8\ell \) group elements for the Schnorr proofs for the base group elements in \(\textsf{pp}\) and \(10\ell \) \(\mathbb {Z}_p\) elements for the Schnorr proofs which include the trapdoors. Concretely, for \(\ell =2\) this amounts to 26 group elements and 20 \(\mathbb {Z}_p\) elements per level (where for usual applications \(L\le 5\)) being several orders of magnitude smaller than the one run by Ethereum. We also note that the computation and verification of these Schnorr proofs is highly efficient.

Revoking Intermediate Issuers and Users in a DAC Scheme. Conceptually (but not technically) our approach to revocation shares similarities with verifier local revocation kown from group signatures [5]. In particular, to revoke these credentials, we generate revocation tokens that verify with a given public key and can later be provided to a trusted revocation authority (TRA). The TRA adds these tokens to a deny list. To achieve this, the TRA first creates the ephemeral secret and public keys. The TRA then registers the user by signing the user’s public keys with the corresponding ephemeral secret key. This forms a signature chain similar to the mercurial scheme described in [17].

When a user needs to prove their credentials, they present a revocation token for each public key in their chain. Since this revocation method mirrors the credential chain approach in [17], i.e., mercurial signatures on public keys, the tokens can be randomized to maintain user anonymity during the presentation.

To revoke a user or issuer in a credential chain (perhaps if the credential chain is used to perform some illegal action) these revocation tokens can be supplied from the verifier to the TRA who can then look through all the secret ephemeral keys they generated to recognize the credential chain and add the respective ones to a deny list.

Later, any verifier can verify the TRA’s signature in the revocation token and iterate through the deny list, using each secret key to attempt to match each public key in the chain. More specifically, the verifier exponentiates the ephemeral public key in the revocation token with the inverses of the secret keys in the deny list (as described earlier in Sect. 1.3). If a match is found, the verifier can confirm that the credential has been revoked (cf. Section 4 for details).

Notation. We use \([\ell ]\) to denote the set, \(\{1,2,\ldots ,\ell \}\). We use the notation \(x\in \textsf{Func}\) to mean that x is a possible output of the function, \(\textsf{Func}\). When drawing multiple values from a set, we may omit notation for products of sets, e.g. \((x,y)\in \mathbb {Z}_p\) is the same as \((x,y)\in (\mathbb {Z}_p)^2\) where only the latter is formally correct. For a map from the set Z to the set S, \(m:Z\rightarrow S\), we will denote \(m[i]\in S\) as the output of the map in S with input \(i\in Z\). We use bold font to denote a vector (e.g. \(\textbf{V}\)). For brevity, we will sometimes denote the elements in a vector as \(\textbf{V}=\{V_i\}_{i\in [\ell ]}=\{V_1,\ldots ,V_\ell \}\). For a vector, \(\textbf{V}=\{V_1,\ldots ,V_\ell \}\), of group elements, we denote the exponentiation of each element by a scalar (\(\rho \in \mathbb {Z}_p\)) with the notation: \(\textbf{V}^\rho =\{V_1^\rho ,\ldots ,V_\ell ^\rho \}\). We use “wildcards” (\(*\)) in equations. For example, the equation \((a,b)=(a',*)\), holds if \(a=a'\) no matter what the value of b is. By \((m,*)\in S\) we mean there is a tuple in the set S such that the first element of the tuple is m and the second element is another value which could be anything. \(\{(m,*)\in S:A(m)\}\) is the set of all tuples in S with m as their first element meeting condition A. For two distributions, A and B, we use the notation, \(A\sim B\), to denote that they are computationally indistinguishable.

2.1 Bilinear Pairings

A bilinear pairing is a set of cyclic groups \(\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T\) of prime order p, along with a pairing function, e (where \(e:\mathbb {G}_1\times \mathbb {G}_2\rightarrow \mathbb {G}_T\)) which preserves structure. We call \(\mathbb {G}_T\) the “target group” and call \(\mathbb {G}_1\) and \(\mathbb {G}_2\) the first and second “source groups” respectively. In this work, we use Type III pairings, which means that there is no efficient, non-trivial homomorphism between \(\mathbb {G}_1\) and \(\mathbb {G}_2\). The pairing function is efficiently computable and has a bilinearity property such that if \(\langle {P}\rangle =\mathbb {G}_1\) and \(\langle {\hat{P}}\rangle =\mathbb {G}_2\), then for \(a,b\in \mathbb {Z}_p^* \), \(e({{P}}^{a},{{\hat{P}}}^{b})=e({P},{\hat{P}})^{ab}\). In our pairing groups, the Diffie-Hellman assumptions hold in the related groups, such that for , \(({{P}}^{a},{{P}}^{b},{{P}}^{ab})\sim ({{P}}^{a},{{P}}^{b},{{P}}^{c})\). Also, given \(({{P}}^{a},{{P}}^{b})\) it is difficult to compute \({{P}}^{ab}\). We’ll use hats to denote elements in the second source group, e.g. \({\hat{X}}\in \mathbb {G}_2,X\in \mathbb {G}_1\). We also use the generic group model in the bilinear pairing setting [33].

2.2 Mercurial Signatures

The original scheme from [17] comprises the following algorithms: \(\textsf{Setup}\), \(\textsf{KeyGen}\), \(\textsf{Sign}\), \(\textsf{Verify}\), \(\textsf{ConvertPK}\), \(\textsf{ConvertSK}\), \(\textsf{ConvertSig}\), and \(\textsf{ChangeRep}\). The scheme is parametrized by a length, \(\ell \), which determines the upper bound on the size of messages that can be signed. A mercurial signature scheme is parameterized by equivalence relations for the message, public key, and secret key spaces: \(\mathcal {R}_M\), \(\mathcal {R}_\textsf{pk}\), \(\mathcal {R}_\textsf{sk}\). These relations form equivalence classes for messages and keys and define exactly how messages and signatures can be randomized such that their corresponding signatures can correctly be updated to verify with the updated keys and messages. Allowing the keys and messages to be randomized is what gives this signature scheme its privacy-preserving properties. In this work, we introduce auxiliary algorithms to verify the correctness of messages and public keys with respect to the scheme parameters. These are \(\textsf{VerifyMsg}\) and \(\textsf{VerifyKey}\), respectively. Thus, the syntax of mercurial signatures used in this work is given by:

• \(\textsf{Setup}(1^\lambda ,1^\ell )\rightarrow (\textsf{pp}, td )\): Outputs public parameters \(\textsf{pp}\), including parameterized equivalence relations for the message, public key, and secret key spaces: \(\mathcal {R}_M\), \(\mathcal {R}_\textsf{pk}\), \(\mathcal {R}_\textsf{sk}\) and the sample space for key and message converters. This function also outputs a trapdoor (\( td \)) that can be used (in conjunction with the corresponding secret key) to recognize public keys.

• \(\textsf{KeyGen}(\textsf{pp})\rightarrow (\textsf{pk},\textsf{sk})\): Generates a key pair.

• \(\textsf{Sign}(\textsf{pp},\textsf{sk},M)\rightarrow \sigma \): Signs a message M with the given secret key.

• \(\textsf{Verify}(\textsf{pp},\textsf{pk},M,\sigma )\rightarrow (0\text { or }1)\): Returns 1 iff \(\sigma \) is a valid signature for M w.r.t. \(\textsf{pk}\).

• \(\textsf{ConvertPK}(\textsf{pp},\textsf{pk},\rho )\rightarrow \textsf{pk}'\): Given a key converter \(\rho \), returns \(\textsf{pk}'\) by randomizing \(\textsf{pk}\) with \(\rho \).

• \(\textsf{ConvertSK}(\textsf{pp},\textsf{sk},\rho )\rightarrow \textsf{sk}'\): Randomize a secret key such that it now corresponds to a public key which has been randomized with the same \(\rho \) (i.e. signatures from \(\textsf{sk}'=\textsf{ConvertSK}(\textsf{pp},\textsf{sk},\rho )\) verify by the randomized \(\textsf{pk}'=\textsf{ConvertPK}(\textsf{pk},\rho )\)).

• \(\textsf{ConvertSig}(\textsf{pp},\textsf{pk},M,\sigma ,\rho )\rightarrow \sigma '\): Randomize the signature so that it verifies with a randomized \(\textsf{pk}'\) (which has been randomized with the same \(\rho \)) and M, but \(\sigma '\) is otherwise unlinkable to \(\sigma \).

• \(\textsf{ChangeRep}(\textsf{pp},\textsf{pk},M,\sigma ,\mu )\rightarrow (M',\sigma ')\): Randomize the message-signature pair such that \(\textsf{Verify}(\textsf{pk},M',\sigma ')=1\) (i.e., \(\sigma '\) and \(\sigma \) are indistinguishable) where \(M'\) is a new representation of the message equivalence class defined by M.

• \(\textsf{VerifyKey}(\textsf{pp},\textsf{pk}) \rightarrow \{0, 1\} \): Takes a public key and verifies if it is well-formed w.r.t the public parameters \(\textsf{pp}\).

• \(\textsf{VerifyMsg}(\textsf{pp},M) \rightarrow \{0, 1\} \): Takes a message and verifies if it is well-formed w.r.t the public parameters \(\textsf{pp}\).

Along with defining the functions above, a mercurial signature construction also defines the equivalence classes that are used in the correctness and security definitions. In the construction of [17], relations and equivalence classes for messages, public keys, and secret key are defined as follows:

Equivalence classes are denoted as \([M]_{\mathcal {R}_M}\), \([\textsf{pk}]_{\mathcal {R}_\textsf{pk}}\), \([\textsf{sk}]_{\mathcal {R}_\textsf{sk}}\) for messages, public keys, and secret keys respectively, such that: \([M]_{\mathcal {R}_M}=\{M':(M,M')\in \mathcal {R}_M\}\), \([\textsf{pk}]_{\mathcal {R}_\textsf{pk}}=\{\textsf{pk}':(\textsf{pk},\textsf{pk}')\in \mathcal {R}_\textsf{pk}\}\), \([\textsf{sk}]_{\mathcal {R}_\textsf{sk}}=\{\textsf{sk}':(\textsf{sk},\textsf{sk}')\in \mathcal {R}_\textsf{sk}\}\). Effectively, this means that two messages (M, \(M'\)) are in the same equivalence class if there exists a randomizer, \(\mu \in {\mathcal{M}\mathcal{C}}\), such that \(M'=M^\mu \) with a similar definition for public keys and secret keys. Because of the properties of equivalence classes (reflexivity, symmetry, and transitivity), the following relations hold: \([M]_{\mathcal {R}_M}=[M']_{\mathcal {R}_M}\) iff \((M,M')\in \mathcal {R}_M\), \([\textsf{pk}]_{\mathcal {R}_\textsf{pk}}=[\textsf{pk}']_{\mathcal {R}_\textsf{pk}}\) iff \((\textsf{pk},\textsf{pk}')\in \mathcal {R}_\textsf{pk}\), and \([\textsf{sk}]_{\mathcal {R}_\textsf{sk}}=[\textsf{sk}']_{\mathcal {R}_\textsf{sk}}\) iff \((\textsf{sk},\textsf{sk}')\in \mathcal {R}_\textsf{sk}\).

Besides the usual notions for correctness and unforgeability, security of mercurial signatures requires message class-hiding, origin-hiding and public key class-hiding. We recall the original definitions and provide some intuition.

Definition 1

(Correctness [17]). A mercurial signature for parameterized equivalence relations, \(\mathcal {R}_\mathcal {M}\), \(\mathcal {R}_\textsf{pk}\), \(\mathcal {R}_\textsf{sk}\), message randomizer space, \(\textsf{sample}_\mu \), and key randomizer space, \(\textsf{sample}_\rho \), is correct if for all parameters (\(\lambda ,\ell \)), \(\forall (\textsf{pp}, td )\in \textsf{Setup}(1^\lambda ,1^\ell )\), and \(\forall (\textsf{sk},\textsf{pk})\in \textsf{KGen}(1^\lambda )\), the following holds:

• Verification. \(\forall M\in \mathcal {M},\sigma \in \textsf{Sign}(\textsf{sk},M):\textsf{Verify}(\textsf{pk},M,\sigma )=1\) \(\wedge \) \(\textsf{VerifyMsg}(\textsf{pp}\), \(M)=1 \wedge \textsf{VerifyKey}(\textsf{pp},\textsf{pk})=1\).

• Key conversion. \(\forall \rho \in \textsf{sample}_\rho ,(\textsf{ConvertPK}(\textsf{pk},\rho ),\textsf{ConvertSK}(\textsf{sk},\rho ))\in \textsf{KGen}(1^\lambda )\), \(\textsf{ConvertSK}(\textsf{sk},\rho )\in [\textsf{sk}]_{\mathcal {R}_\textsf{sk}}\), and \(\textsf{ConvertPK}(\textsf{pk},\rho )\in [\textsf{pk}]_{\mathcal {R}_\textsf{pk}}\).

• Signature conversion. \(\forall M\in \mathcal {M},\sigma ,\rho \in \textsf{sample}_\rho ,\sigma ',\textsf{pk}'\) s.t \(\textsf{Verify}(\textsf{pk},M,\sigma )=1\), \(\sigma '=\textsf{ConvertSig}(\textsf{pk},M,\sigma ,\rho )\), and \(\textsf{pk}'=\textsf{ConvertPK}(\textsf{pk},\rho )\), then \(\textsf{Verify}(\textsf{pk}',M,\sigma ')=1\).

• Change of message representation. \(\forall M\in \mathcal {M},\sigma ,\mu \in \textsf{sample}_\mu ,M',\sigma '\) such that \(\textsf{Verify}(\textsf{pk},M,\sigma )=1\) and \((M',\sigma ')=\textsf{ChangeRep}(\textsf{pk},M,\sigma ;\mu )\) then \(\textsf{Verify}(\textsf{pk},M',\sigma ')=1\) and \(M'\in [M]_{\mathcal {R}_M}\).

Unforgeability rules out forgeries on the same equivalence class for messages that have been queried to the signing oracle and public keys as these “forgeries” are actually guaranteed to be computable by correctness. Thus, only forgeries on new equivalence classes are accepted as valid forgeries.

Definition 2

(Unforgeability [17]). A mercurial signature scheme for parameterized equivalence relations \(\mathcal {R}_\mathcal {M}\), \(\mathcal {R}_\textsf{pk}\), \(\mathcal {R}_\textsf{sk}\), is unforgeable if for all parameters (\(\lambda ,\ell \)) and all PPT adversaries \(\mathcal {A}\), having access to a signing oracle, there exists a negligible function \( negl \) such that:

Where Q is the list of messages that the adversary queried to the \(\textsf{Sign}\) oracle.

Message class-hiding provides unlinkability in the message space, and it’s implied by the DDH assumption in the original scheme from [17].

Definition 3

(Message class-hiding [17]). For all \(\lambda ,\ell \) and all PPT adversaries \(\mathcal {A} \), there exists a negligible function \( negl \) such that:

Importantly, converted signatures should look like freshly computed signatures in the space of all valid ones. This notion is captured with the origin-hiding definitions as shown below.

Definition 4

(Origin-Hiding for \(\mathsf ConvertSig\) [17]). A mercurial signature scheme is origin-hiding for \(\mathsf ConvertSig\) if, given any tuple \((\textsf{pk},\sigma ,M)\) that verifies, and given a random key randomizer \(\rho \), \(\textsf{ConvertSig}(\sigma ,\textsf{pk},\rho )\) outputs a new signature \(\sigma '\) such that \(\sigma '\) is a uniformly sampled signature in the set of verifying signatures, \(\{\sigma ^*|\textsf{Verify}(\textsf{ConvertPK}(\textsf{pk},\rho ),M,\sigma ^*)=1\}\).

Definition 5

(Origin-Hiding for \(\mathsf ChangeRep\) [17]). A mercurial signature scheme is origin-hiding for \(\mathsf ChangeRep\) if, given any tuple \((\textsf{pk},\sigma ,M)\) that verifies, and given a random message randomizer \(\mu \), \(\textsf{ChangeRep}(\textsf{pk},M,\sigma ,\mu )\) outputs a new message and signature \(M',\sigma '\) such that \(M'\) is a uniform sampled message in the equivalence class of M, \([M]_{\mathcal {R}_M}\), and \(\sigma '\) is uniformly sampled verifying signature in the set of verifying signatures for \(M'\), \(\{\sigma ^*|\textsf{Verify}(\textsf{pk}, M',\sigma ^*)=1\}\).

For anonymous credentials such as the attribute-based credential (ABC) scheme from [20], the notion of message class-hiding is sufficient to provide unlinkability alongside origin-hiding. This is because in ACs the adversary doesn’t know the Diffie-Hellman coefficients of the message vector that is signed to produce a credential (these coefficients are only known to the honest user who created the message). In DAC’s schemes from mercurial signatures the messages to be signed are public keys, which may be provided by the adversary. Since the adversary knows the corresponding secret key, achieving a class-hiding notion for public keys is much harder. The definition below only considers honestly generated keys for which the adversary doesn’t know the secret key. This is similar to the case of message-class hiding but it clearly restricts applications.

Definition 6

(Public key class-hiding [17]).For all \(\lambda ,\ell \) and all PPT adversaries \(\mathcal {A} \), there exists a negligible function (\( negl \)) such that:

Mercurial Signature Construction CL19 [17]. We review the mercurial signature construction from [17] in Fig. 1, so that the differences are clear when we present our construction in Sect. 3.

CL19 Mercurial Signature Construction [17]

Full size image

We note that a function (\(\textsf{RecognizePK}\) shown in Def. 7) can be added to this scheme to recognize any randomization of a public key given a secret key [21]. We use this in our DAC construction to tell if users have been revoked.

Definition 7

(Recognize function for CL19 public keys [21]).

• \(\textsf{RecognizePK}(\textsf{pp},\textsf{sk},\textsf{pk})\rightarrow \{0, 1\} \) Parse \(\textsf{pk}\) as \(\textsf{pk}=\{{\hat{X}}_i\}_{i\in [\ell ]}\). Parse \(\textsf{sk}=\{x_i\}_{i\in [\ell ]}\). Check if \(\forall i\in [\ell -1],{\hat{X}}_i^{x_{i+1}/x_i}={\hat{X}}_{i+1}\).

In this section we present our core mercurial signature scheme satisfying a stronger notion of adversarial public key class-hiding (APKCH), which will then build the basis for our DAC construction with strong privacy.

3.1 Modified Security Definitions

Subsequently, we present security definitions for our mercurial signature scheme that are modified (or added) when compared to previous work and before going into details we discuss their generality.

On the Generality of our Definitions. Since our main focus in this work is the construction of DAC, we include in our basic definitons (adversarial public-key class hiding and unforgeability) a “levels” parameter L, which tells the challenger how many correlated schemes to construct (i.e., how many levels there will be in the delegation chain of the DAC). In our definitions, after receiving the public parameters for every level, the adversary picks a level, i, and the challenger generates a public key for that level to complete the game with. This allows the reductions in our proofs to ensure that the DAC scheme appears correct to the adversary while reducing APKCH to the anonymity of the DAC scheme. To reduce to unforgeability, we need a similarly modified definition for unforgeability where the challenger generates a number of levels and the adversary chooses which level to continue the game with. Clearly, by setting \(L=i=1\) we obtain versions of the definitions for a standalone mercurial signature scheme. In our definitions, \(\textsf{Setup}\) outputs a set of correlated parameters of different signature schemes (\(\textsf{pp}\)) and we use \(\textsf{pp}_i\) to refer to the parameters that define level i.

First, we formalize the \(\textsf{APKCH} \) notion in Def. 8. In this definition, first the challenger generates the public parameters and a public key and gives these to the adversary. The adversary then constructs a message, a key pair and a signature and returns these to the challenger. The challenger then either randomizes the adversary’s public key and signature or creates a new signature on the same message from a randomization of the challenger’s key. The randomizers are drawn from the “key converter space”, \({\mathcal{K}\mathcal{C}}\), which is defined by the construction (commonly, \(\mathbb {Z}_p^* \)). The adversary is then challenged to determine if the returned key/signature pair is randomized from their own key/signature that they supplied, or if it is a signature from the randomized challenger key. Looking ahead, this property ensures that in a DAC scheme, an adversary cannot determine if they themselves provided a credential to the prover (user) or if another issuer created the credential.

Definition 8

(Adversarial public key class-hiding). A mercurial signature, \(\varGamma \), has adversarial public key class-hiding if for all parameters (\(\lambda ,\ell ,L\)), the advantage of any PPT set of algorithms \(\mathcal {A} =\{\mathcal {A} _0,\mathcal {A} _1,\mathcal {A} _2\}\), (labeled as \(\textsf{Adv}^{\textsf{APKCH}}_{\varGamma ,\mathcal {A}}(\lambda )\)) is negligible,

where \({\textbf {Exp}}^{\textsf{APKCH},b}_{\varGamma ,\mathcal {A}}(\lambda )\) is the experiment shown in Fig. 2.

Adversarial public key class-hiding experiment \({\textbf {Exp}}^{\textsf{APKCH},b}_{\varGamma ,\mathcal {A}}(\lambda )\).

Full size image

Finally, we provide the unforgeability definition that also considers multiple levels in Def. 9.

Definition 9

(Unforgeability). A mercurial signature scheme for parameterized equivalence relations \(\mathcal {R}_\mathcal {M}\), \(\mathcal {R}_\textsf{pk}\), \(\mathcal {R}_\textsf{sk}\), is unforgeable if for all parameters (\(\lambda ,\ell ,L\)) and all PPT adversaries \(\mathcal {A}\), having access to a signing oracle, there exists a negligible function \( negl \) such that:

Where Q is the list of messages that the adversary queried to the \(\textsf{Sign}\) oracle.

3.2 Construction

In Fig. 3, we construct a mercurial signature (MS) scheme which in particular provides adversarial public key class-hiding (APKCH) as defined in Def.  8. We fix \(L=1\) for this construction and explain how we can set correlated parameters while still achieving APKCH in Sect. 3.3.

As in prior MS constructions, our equivalence classes will be parameterized by the public parameters consisting of a description of the bilinear group \((\mathbb {G}_1,\mathbb {G}_2,\mathbb {G}_T,e, p, P, \hat{P})\). Unlike prior constructions, they will also be parameterized by several length-\(2\ell \) vectors that are part of the public parameters of the system. Specifically, the public parameters will include the vectors \(\textbf{B}= ({B_{1}},\ldots ,{B_{2\ell }})\), \(\mathbf {{\hat{B}}}=({{\hat{B}}_{1}},\ldots ,{{\hat{B}}_{2\ell }})\), and \(\mathbf {{\hat{V}}}= ({{\hat{V}}_{1}},\ldots ,{{\hat{V}}_{2\ell }})\), \(\textbf{V}=({V_{1}},\ldots ,{V_{2\ell }})\). These public parameters have trapdoors which include \(\textbf{b}= (b_{1},\ldots ,b_{\ell })\), \(\mathbf {\hat{b}}= ({\hat{b}_{1}},\ldots ,{\hat{b}_{\ell }})\), and \(\mathbf {\hat{d}}= (\hat{d}_{1},\ldots ,\hat{d}_{\ell })\) which are vectors in \(\mathbb {Z}^\ell _p\) and sampled uniformly randomly by \(\textsf{Setup}\). The vector \(\textbf{B}\) will be used to define the message space (and construct messages), while the vector \(\mathbf {{\hat{B}}}\) defines the public key space and allows users to create valid public keys. These public parameters are structured based on the trapdoors, such that \(\forall i\in [\ell ],{B_{i}} = {P}^{b_{i}}\), \({B_{\ell +i}} = {B_{i}}^{{\hat{b}_{i}}}\), \(\forall i\in [\ell ],{{\hat{B}}_{i}} = \hat{P}^{{\hat{b}_{i}}}\) and \({{\hat{B}}_{\ell +i}} = {{\hat{B}}_{i}}^{\hat{d}_{i}}\). To verify that keys and messages are computed over these bases, we include the verification bases (shown above as \(\mathbf {{\hat{V}}}\) and \(\textbf{V}\)) in the public parameters which are constructed as: \(\forall i\in [\ell ],{{\hat{V}}_{i}} = {{\hat{P}}}^{{\hat{v}_{i}}b_{i}}\), \({{\hat{V}}_{\ell +i}} = {{{\hat{P}}}^{{\hat{v}_{i}}}}\), \(\forall i\in [\ell ],{V_{i}} = {P}^{v_{i}\hat{d}_{i}}\) and \({V_{\ell +i}} = {P}^{v_{i}}\). The vector \(\mathbf {{\hat{V}}}\) is used to verify messages while the vector \(\textbf{V}\) is used to verify keys as described in Sect. 1.3. Structuring the parameters in this way ensures that our construction achieves adversarial public key class-hiding as discussed in Sect. 1.3 and defined in Def. 8. Let \(\textsf{pp}\) denote the public parameters.

Our message space will consist of vectors of \(2\ell \) dimensions over \(\mathbb {G}_1\) that have certain structure determined by \(\textsf{pp}\); i.e., not every \(2\ell \)-dimensional vector will be a valid message. Specifically, our message space, \(\mathcal {M}^{ pp,\ell }\) is defined as:

Note that, using \(\textsf{pp}\), it is possible to verify that a \(2\ell \)-dimensional vector is in the message space. In our scheme, the public parameters will include extra bases \(\mathbf {{\hat{V}}}=\{{\hat{V}}_1,\ldots ,{\hat{V}}_{2\ell }\}\) to pair with messages to verify them, i.e. ensuring that \(e(M_i,{\hat{V}}_i)=e(M_{i+\ell },{\hat{V}}_{i+\ell })\)). Moreover, they include extra bases \(\textbf{V}=\{V_1,\ldots ,V_{2\ell }\}\), to pair with public keys in the same manner, i.e. \(e(V_i,{\hat{X}}_i)=e(V_{i+\ell },{\hat{X}}_{i+\ell })\). We label messages as \(\textbf{M}=\{M_1,\ldots ,M_{2\ell }\}\) and public keys as \(\textsf{pk}=\{{\hat{X}}_1,\ldots ,{\hat{X}}_{2\ell }\}\). We are now ready to define our equivalence class over the message space, which is the same as in prior work [17]:

Our public key space will be defined similarly to our message space, but defined over vectors \(\mathbf {{\hat{B}}}=({\hat{P}}^{{\hat{b}_{1}}},\ldots ,{\hat{P}}^{{\hat{b}_{\ell }}},{\hat{P}}^{{\hat{b}_{1}}\hat{d}_{1}},\ldots ,{\hat{P}}^{{\hat{b}_{\ell }}\hat{d}_{\ell }})\) included in \(\textsf{pp}\) as well. Like messages, our public key space is a strict subset of the space of \(2\ell \)-dimension vectors in \(\mathbb {G}_2^{2\ell }\), defined below:

We define our equivalence classes over the public key space (similarly to [17]):

We will see in the construction that the related structure of these messages and public keys (i.e. the fact that they both use the values \(\textbf{b}\) and \(\mathbf {\hat{b}}\)) ensures that randomized keys and signatures are not linkable even when the adversary holds the secret key \(\{x_1,\ldots ,x_\ell \}\), while also ensuring that signatures still correctly verify.

Our secret key space takes up the entire space of \(\ell \)-dimensional vectors in \(\mathcal{S}\mathcal{K}^ pp,\ell =(\mathbb {Z}_p)^\ell \) and is defined identically to [17] as:

In the sequel, when clear from the context, we will omit the superscript \( pp,\ell \). In our construction, the key and message converter spaces are \({\mathcal{K}\mathcal{C}}= \mathbb {Z}_p^* \) and \({\mathcal{M}\mathcal{C}}= \mathbb {Z}_p^* \).  

Our Construction. We are now ready to present our MS construction in Fig. 3 which achieves our \(\textsf{APKCH}\) definition for \(L=1\). In Sect. 3.3, we will discuss modifications to the public parameter generation, allowing the scheme’s extension for constructing DAC. While verifying the message or public key is not required for unforgeability, we include it in the \(\textsf{Verify}\) function as it is needed for public key class-hiding and message class-hiding.

Our Mercurial Signature Construction.

Full size image

Theorem 1

(Correctness). The mercurial signature construction in Fig. 3 is correct as described Def. 1.

Theorem 2

(Unforgeability). The mercurial signature construction in Fig. 3 meets the unforgeability definition in Def. 2 assuming that the mercurial signature construction in [17] is unforgeable in the generic group model.

We prove Theorem 2 by noting that the CL19 construction [17] is unforgeable in the generic group model, and thus, by showing that our construction’s unforgeability relies solely on the unforgeability of the construction of CL19, our construction is also unforgeable in the generic group model.

Theorem 3

(APKCH). The mercurial signature construction in Fig. 3 meets the \(\textsf{APKCH}\) definition in 8 in the generic group model.

Theorem 4

(Origin-hiding of signatures). The mercurial signature construction in Fig. 3 meets the Origin-hiding of signatures definition in Def. 4.

Theorem 5

(Origin-hiding of \(\textsf{ChangeRep}\) ). The mercurial signature construction in Fig. 3 meets the Origin-hiding of \(\textsf{ChangeRep}\) definition in Def. 5.

Theorem 6

(Message class-hiding). The mercurial signature construction in Fig. 3 meets the Message class-hiding definition in Def. 3.

The proofs of theorems 4, 5, and 6, follow directly from those of CL19, and are thus omitted here. The proofs of unforgeability (Theorem 2) and \(\textsf{APKCH}\) (Theorem 3) are provided in the full version of this paper [22].

3.3 Extending Our Construction to Multiple Levels

In a CL-type DAC scheme, we need chains of public keys that can sign each other. In [17], this is achieved by alternating the source groups of the mercurial signature scheme for each level in the chain. For example, to sign public keys in the highest level of the delegation chain L, if the public keys in level L are in source group \(\mathbb {G}_2\), then, in the level \(L-1\), a scheme with public keys in \(\mathbb {G}_1\) will be used to sign the public keys of level L.

This approach works in [17] because the scheme is symmetric, meaning the public parameters are the same whether public keys are in \(\mathbb {G}_2\) or \(\mathbb {G}_1\). Unfortunately, our scheme is not symmetrical. Looking at the \(\textsf{Setup}\) function in Fig. 3, we see that if we split our message bases and public key bases into halves, \(\textbf{B}=\mathbf {B^l}\Vert \mathbf {B^u}\) and \(\mathbf {{\hat{B}}}=\mathbf {{\hat{B}}^l}\Vert \mathbf {{\hat{B}}^u}\), the second half of the bases for messages includes the trapdoors \({\hat{b}_{i}}\), being formed as \(\mathbf {B^u}=\{{P}^{b_{i}{\hat{b}_{i}}}\}_{i\in [\ell ]}\). This trapdoor is included in the first half of the bases for public keys (\(\mathbf {{\hat{B}}^l}=\{{{\hat{P}}}^{{\hat{b}_{i}}}\}_{i\in [\ell ]}\)). But, the upper half of the bases for public keys includes the trapdoors, \(\hat{d}_{i}\) (\(\mathbf {{\hat{B}}^u}=\{{{\hat{P}}}^{{\hat{b}_{i}}\hat{d}_{i}}\}_{i\in [\ell ]}\)). The trapdoors \(\hat{d}_{i}\) are not seen in the lower bases for messages (\(\mathbf {B^l}=\{{P}^{b_{i}}\}_{i\in [\ell ]}\)). Due to this asymmetry, we cannot simply invert the groups to start signing public keys from higher levels. At first glance, it appears we could fix this by setting \(\hat{d}_{i}=b_{i}\) (thus allowing messages to be used to sign public keys by computing the signatures on the second half of the public key). Unfortunately, this solution would break the APKCH property of our scheme as computing public keys over \({{\hat{P}}}^{b_{i}{\hat{b}_{i}}}\) permits a recognition attack using the bases \({P}^{b_{i}{\hat{b}_{i}}}\). This forces us to choose a more involved solution.

We can solve this problem using the \(\textsf{Setup}\) function in Fig. 4. This function produces \(L-1\) levels where the message space of each scheme is exactly the public key space of the subsequent scheme (with the equivalence classes matching as well). To better explain this solution (and simplify our proofs) we discuss the notion of “extending” schemes in this rest of this Section.

Parameter generation for multiple levels

Full size image

We will use the terms “lower” and “higher” to refer to different levels of signature scheme that will be used to construct DAC. The root key is at level 0 which is the lowest level of the delegation chain and user’s keys are messages in the \(L-1\) (highest) level. In order to sign higher-level public keys with lower-level public keys, starting from our construction in Fig. 3, we need to create multiple levels of the signature scheme so that lower level public key bases can be used to sign public keys from higher levels scheme. To do this, we need to create a new scheme (with public keys in the opposite source group, \(\mathbb {G}_1\)) with similar structure as in our original scheme in Fig. 3. We recall that in this scheme the message bases and public key bases share the \({\hat{b}_{i}}\) trapdoor values as described in the above paragraph. This can be imagined as “extending” a scheme to lower levels. When extending a scheme to enable signatures on the public keys, we’ll treat \(\hat{d}_{i}\) as this shared value, setting \({\hat{b}_{i}}\) for the lower scheme to be equal to \(\hat{d}_{i}\) in the higher scheme (remember, \(\hat{d}_{i}\) is used in the upper half of the public key bases, \(\mathbf {{\hat{B}}}\) in the public parameters). For example, say we have a higher scheme (with bases \(\mathbf {{\hat{B}}}=\{{{\hat{B}}_{i}}\}_{i\in [2\ell ]}\)) with key pair \((\textsf{sk},\textsf{pk})\), where \(\textsf{sk}=\{x_i\}_{i\in [\ell ]}\), \(\textsf{pk}=\{{\hat{X}}_i\}_{i\in [2\ell ]}=\{{{\hat{B}}_{i}}^{x_i}\}_{i\in [\ell ]}\Vert \{{{\hat{B}}_{\ell +i}}^{x_i}\}_{i\in [\ell ]}\), \(\forall i\in [\ell ],{{\hat{B}}_{i}}={{\hat{P}}}^{{\hat{b}_{i}}},{{\hat{B}}_{\ell +i}}={{\hat{P}}}^{{\hat{b}_{i}}\hat{d}_{i}}\) and \({\hat{b}_{i}}\) and \(\hat{d}_{i}\) are randomly sampled as a trapdoor of the public parameters. We can create a lower scheme (with bases \(\mathbf {{{\hat{B}}^{\prime }}}=\{{({\hat{B}}_{i}')}\}_{i\in [2\ell ]}\)) and key pair (\(\textsf{sk}',\textsf{pk}'\)) where \(\textsf{sk}'=\{x_i'\}_{i\in [\ell ]}\), \(\textsf{pk}'=\{X_i'\}_{i\in [2\ell ]}=\{{({\hat{B}}_{i}')}^{x_i'}\}_{i\in [\ell ]}\Vert \{{({\hat{B}}_{\ell +i}')}^{x_i'}\}_{i\in [\ell ]}\) and \(\forall i\in [\ell ],{({\hat{B}}_{i}')}={P}^{\hat{d}_{i}},{({\hat{B}}_{\ell +i}')}={P}^{\hat{d}_{i}\hat{d}_{i}'}\) and \(\hat{d}_{i}'\) is randomly sampled as a trapdoor of the public parameters. We can now use this lower level scheme to sign the keys in the higher level. We can see that if we form signatures as we did in Fig. 3, these signatures still verify. In Fig. 3, (if we swap the source groups) signatures are formed as \(\sigma =(Z,Y,{\hat{Y}})\) where \(Z=(\prod _{i\in [\ell ]} ({\hat{X}}_{\ell +i})^{x_i'})^y\), \(Y={{\hat{P}}}^{1/y}\), \({\hat{Y}}={P}^{1/y}\) and y is randomly sampled. We see that \(e({\hat{Y}},Z)={e({P},{{\hat{P}}})}^{\sum _{i\in [\ell ]}\hat{d}_{i}{\hat{b}_{i}}x_ix_i'}=\prod _{i\in [\ell ]}e({\hat{X}}_i,X_i')\) which means that this signature verifies. We provide Fig. 5 to make multi-level signature schemes more clear. In Fig. 5, we can see that when the lower level bases of levels 1 and 2 are paired together, they are equal to the pairing of the higher level bases of level 2, i.e. \(e({{\hat{B}}_{2,i}},{{\hat{B}}_{1,i}})=e({P}^{{\hat{b}_{2,i}}},{{\hat{P}}}^{{\hat{b}_{1,i}}})={e({P},{{\hat{P}}})}^{{\hat{b}_{2,i}}{\hat{b}_{1,i}}}=e({{\hat{B}}_{2,\ell +i}},{{\hat{P}}})\). This structure is what ensures that our signatures verify (as described in Sect. 1.3). We’ve pointed out this structure by highlighting \({\hat{b}_{1,i}}\) in orange and \({\hat{b}_{2,i}}\) in blue in 5. This relation holds for levels 2 and 3 as well. Note that in 5, the source groups for level 2 are flipped, meaning that the \({{\hat{B}}_{2,i}}\) elements are in \(\mathbb {G}_1\) and the \(Z_2\) element is in \(\mathbb {G}_2\). For clarity, we keep the notation of the generators, \({P}\) and \({{\hat{P}}}\), correct with respect to levels 1 and 3.

A series of compatible mercurial signature schemes and a credential chain.

Full size image

In the full version of this paper [22], we introduce the formal definition of extending parameters. This eases the readability of our proof as a generic group model proof for \(L-1\) sets of public parameters simultaneously might be difficult to comprehend. Instead, we prove the APKCH security of a scheme for a single level that reveals enough secrets about the parameters so that the scheme can be extended to match the distribution of the parameters in Fig. 4. A simple hybrid arugment can then be used to prove that our multi-level scheme achieves APKCH as described in Def. 8. More specifically, in the proof of APKCH in the full version, we use a \(\textsf{Setup}\) function (similar to Fig. 3) that also reveals \(\textbf{D}=\{D_i\}_{i\in [\ell ]}=\{{P}^{\hat{d}_{i}}\}_{i\in [\ell ]}\) such that if the keys for this scheme live in \(\mathbb {G}_2\), then \(D_i\) is in \(\mathbb {G}_1\). This allows a second setup to be run to create a lower level scheme that is compatible with the first scheme by computing: \(\forall i\in [\ell ],{({\hat{B}}_{i}')}=D_i,{({\hat{B}}_{\ell +i}')}=D_i^{\hat{d}_{i}'}\). We can see that this is exactly how the extended scheme computed their public parameters, \({({\hat{B}}_{\ell +i}')}\) (explained earlier in this section) but now the second scheme does not know \(\hat{d}_{i}\), which prevents attacks on class-hiding. Further, because \(\textbf{D}\) lives in \(\mathbb {G}_1\) instead of \(\mathbb {G}_2\), the adversary cannot use it to create malicious public keys that verify for the original scheme. While the real setup (in Fig. 4) will not reveal \(\textbf{D}\) to an adversary, it is important that the signatures retain their security properties even when this is revealed. Intuitively, this is because schemes built on top of a signature scheme requires some correlated structure. Revealing \(D_i={P}^{\hat{d}_{i}}\) in our security games ensures that this correlated structure cannot be leveraged to defeat the security of the schemes at other levels.

In this section, we introduce a new DAC construction, showcasing advanced features as strengthened privacy, revocation capabilities, and non-transferability, all while preserving efficiency.

4.1 DAC Functionality

In contrast to non-revocable DAC schemes, our approach integrates a Trusted Revocation Authority (TRA) to efficiently revoke malicious users and maintain a deny list. We outline the high-level functionality of our DAC scheme in Def. 10. This consists of the algorithms: \({\textsf{Setup}}\) which initializes the scheme, \(\mathsf{T\textsf{KeyGen}}\) which generates the TRA’s keys, \({\textsf{RootKeyGen}}\) which generates the root’s keys, \({\textsf{UKeyGen}}\) which generates a user’s or issuer’s keys, \({\textsf{RegisterUser}}\) which allows the TRA to distribute revocation tokens, and \({\textsf{RevokeUser}}\) which allows the TRA to revoke users. The scheme also consists of the interactive protocols to issue and show credentials: \(({\textsf{Issue}}\leftrightarrow {\textsf{Receive}})\) and \(({\textsf{Prove}}\leftrightarrow {\textsf{Verify}})\). This scheme begins with a trusted \(\textsf{Setup}\)^{Footnote 2}. Then, the TRA generates an opener secret key and public key using \(\mathsf T\textsf{KeyGen} \). A root authority (who can be malicious for the sake of anonymity) generates the root key using \(\textsf{RootKeyGen}\) and distributes the root public key to users. A user who wishes to receive a credential runs \(\mathsf U\textsf{KeyGen} \) and then interacts with the TRA to receive a revocation token by providing their public key to the TRA so that the TRA can run \(\textsf{RegisterUser}\) on it. Subsequently the user interacts with the root (or an issuer that the root has delegated to) using \(({\textsf{Issue}}\leftrightarrow {\textsf{Receive}})\) and receives a credential (which includes their revocation token). The user then uses their credential and secret key in an interactive protocol (\({\textsf{Prove}}\leftrightarrow {\textsf{Verify}}\)) with any verifier. These verifications can occur at any level within [L] (i.e. for some level, \(L'\) such that \(L'\le L\)). The verifier can check if the user has been authorized and has not been revoked using the TRA’s public key \( tpk \). More specifically, the verifier receives a revocation token for each level in the credential chain from the credential presentation. If the verifier discovers that the prover was malicious through an out-of-band method, they can submit these tokens to the TRA. The TRA will then update their deny list (this deny list is included in the TRA public key for the sake of simplifying the presentation), preventing any future showings that include the user or issuer corresponding to the revocation token from being verified.

We note that our scheme supports a strong model for anonymity where the holder of the root key (colluding with intermediate issuers) cannot de-anonymize users. To model this, we allow the adversary in the anonymity game to choose the root public key along with the corruption of any users of their choice. This allows the adversary to choose any honest user’s delegation path from a malicious root with all malicious delegations.

Definition 10

(Delegatable Anonymous Credentials). A DAC scheme includes the following algorithms and protocols:

• \({\textsf{Setup}}(1^\lambda ,{1^L})\rightarrow (\textsf{pp}, td )\): Initializes the scheme, outputting public parameters and a trapdoor \( td \).

• \(\mathsf{T\textsf{KeyGen}}(\textsf{pp})\rightarrow ( tsk , tpk )\): Takes \(\textsf{pp}\) and outputs a keypair \(( tsk , tpk )\) for the TRA. The \( tpk \) includes a deny list of revoked users and is continously updated.

• \({\textsf{RootKeyGen}}(\textsf{pp})\rightarrow (\textsf{sk}_{ rt},\textsf{pk}_{ rt})\): Generates a key pair used for the root key \(\textsf{pk}_{ rt}\) (i.e. for level 0) which is trusted for integrity but does not need to be trusted for anonymity.

• \(\mathsf{U\textsf{KeyGen}}(\textsf{pp},L')\rightarrow (\textsf{sk},\textsf{pk})\): Generates a user’s key pair for a specified level.

• \({\textsf{RegisterUser}}(\textsf{pp}, tsk ,\textsf{pk})\rightarrow (tok)\): Creates a revocation token on the given public key so that the public key can be revoked later with a deny list.

• \(({\textsf{Issue}}(\textsf{sk}_I,\textsf{cred}_I,L')\leftrightarrow {\textsf{Receive}}(\textsf{sk}_R,tok,L'))\rightarrow \textsf{cred}_R\): An interactive protocol to receive a signature on a pseudonym. It is run between the two users distinguished by I for issuer or R for receiver. If \(L'=1\) (issuing from the root) then \(\textsf{cred}_I = \bot \).

• \(({\textsf{Prove}}(\textsf{sk}_P,\textsf{cred}_P, L')\leftrightarrow {\textsf{Verify}}(\textsf{pk}_{ rt},L', tpk ))\rightarrow (b,\{ tok _i\}_{i\in [L']})\): A user proves they know a credential on a pseudonym that verifies under the given root key, \(\textsf{pk}_{ rt}\). If the verification is successful, the verifier outputs 1 along with a list of revocation tokens for the prover and the chain of credentials. If the verification is unsuccessful, the verifier outputs 0.

• \({\textsf{RevokeUser}}(\textsf{pp}, tsk , tpk , tok )\rightarrow tpk '\): Takes in the TRA’s key pair \(( tsk , tpk )\) as well as the token for a registered public key and outputs an updated public key \( tpk '\) that can be used to recognize any showings in which this public key is part of the chain. For security reasons, this can fail, outputting \(\perp \). As an example, we want this function to fail if a malicious \( tok \) is provided.

4.2 DAC Security Definitions

In Fig. 6 we formally define the oracles used in our security games. Any formal outputs of oracles are received by the adversary and any modified internal state of the challenger is listed in the description. When calling interactive functions from the DAC scheme (such as \(\textsf{Prove}(\cdot )\leftrightarrow \textsf{Verify}(\cdot )\)), the challenger records the transcript of the interaction in addition to the output of the function. For example, in the \(\textsf{VerifyCred}\) oracle in Fig. 6, we have the challenger interact with the adversary using the \(\textsf{Verify}\) function, and in addition to outputting the result of the verification (b) and the list of revocation tokens, \(\{ tok _i\}_{i\in [L']}\), the protocol also outputs a transcript (\(\tau \)) of the interaction between the prover and the verifier. Throughout the game, the challenger maintains some state to keep track of honest users and credentials that were given to the adversary. This global state is used in the unforgeability game. Specifically, the challenger keeps track of one set, \(\textsf{DEL}_\mathcal {A}\) to keep track of what has been delegated to the adversary. Moreover, the challenger initializes three maps to keep track of honest user state, \(\textsf{SK}\) holds user secret keys, \(\textsf{CRED}\) holds user credentials, and \(\textsf{LVL}\) records what level a user’s credential is for. They are as follows: \(\textsf{SK}:\mathcal {H}\rightarrow \mathcal{S}\mathcal{K}\), \(\textsf{CRED}:\mathcal{S}\mathcal{K}\rightarrow \mathcal {CRED}\) and \(\textsf{LVL}:\mathcal{S}\mathcal{K}\rightarrow [L]\), where \(\mathcal {H}\) is the set of all honest user handles (which the adversary uses to refer to honest users), \(\mathcal{S}\mathcal{K}\) is the set of all secret keys, and \(\mathcal {CRED}\) is the set of all credentials.

Definition of Oracles. \(^\dag \) The oracle uses \(\mathcal {E}_\textsf{pk}\) to ensure \(\textsf{SK}[ id ]\) holds a canonical representation of the secret key.

Full size image

The root key is included in \(\textsf{SK}\) with handle \( id =0\) where \(\textsf{LVL}[\textsf{SK}[0]]=0\) and \(\textsf{CRED}[\textsf{SK}[0]]=\perp \). The challenger also keeps track of what keys have been added to the deny list with the list \(\textsf{SK}_{ DL }\subset \mathcal{S}\mathcal{K}\). At the start of any game, the challenger initializes all sets to the empty set and initializes all maps to be degenerate, such as mapping \(\forall i\in \mathcal {H},\textsf{SK}[i]=\perp \). In the unforgeability game, we give the adversary access to all of the oracles. In the \(\mathcal {O}^{\textsf{CreateHonestUser}}\) oracle, the adversary specifies two users with one issuing a credential to the other. We initialize users at the same time that they are issued a credential to simplify the scheme. As an example use of this oracle, the adversary can specify \( id _I=0\) at the start of a game to have a credential be issued from the root. We do not allow the adversary to issue to a user multiple times, and thus if the specified user already exists when the adversary calls \(\mathcal {O}^{\textsf{CreateHonestUser}}\), then the challenger aborts. We allow the adversary to issue credentials to honest users using the \(\mathcal {O}^{\textsf{ReceiveCred}}\) oracle. In this oracle, the adversary specifies a user to receive a credential at a specified level. If the adversary was never issued a credential that would allow them to delegate this credential to the honest user, the challenger set a forgery flag in the global state (labeled \( forgery \)) which is checked in the unforgeability game. In the \(\mathcal {O}^{\textsf{IssueFrom}}\) oracle, the adversary receives a credential from an honest user and the challenger records which adversarial key received this credential at which level. In the \(\mathcal {O}^{\textsf{ProveTo}}\) oracle, the adversary acts as the verifier for a user. In the \(\mathcal {O}^{\textsf{RegisterUser}}\) oracle the adversary can receive a revocation token for one of their public keys. In the \(\mathcal {O}^{\textsf{RevokeUser}}\) oracle, the adversary can add a user to the deny list.  

Anonymity: Our anonymity definition is shown in Def 11. The anonymity game involves the adversary and the challenger. The adversary controls all participants, including the root credential authority (but does not control the TRA). The game proceeds as follows: The challenger generates the public parameters, which are given to the adversary along with the registrar’s public key and access to a registration and revocation oracle. The adversary creates two credential chains of the same length and provides the secret keys of the end users of these chains to the challenger. The challenger ensures that they are valid credential chains. The challenger randomly selects one of the users and proves possession of the corresponding credential chain to the adversary. The adversary wins if it can correctly identify which user the challenger picked. No honest users are created in this game, as the adversary controls all aspects except for the registration and revocation oracles. To model issuer privacy and showing privacy, the adversary outputs a bit, j, to indicate whether the challenger should act as the issuer or the shower. We formalize this game in Def. 11.

Definition 11

(Anonymity). A DAC scheme is anonymous if the advantage any PPT adversary (\(\mathcal {A}=\{\mathcal {A}_0,\mathcal {A}_1\}\)) in the following anonymity game, defined by the chance that the game outputs 1, is \(1/2+ negl (\lambda )\):

Unlike the anonymity definition in [17], we allow the adversary to participate in the challenge credential chain. Therefore, we do not need to control the state of the game with the challenger; in the anonymity game, the challenger only performs the role of the TRA and the challenge user. In addition, we aim to maintain the anonymity of honest users even when the anonymity of some adversarial users is revoked. This new definition represents a simplified and more comprehensive anonymity model, which we present as a novel contribution.  

Unforgeability: Our unforgeability game is simpler than [17], even though it is conceptually similar. We remove oracles that reveal pseudonyms of honest users. Revealing pseudonyms alone has no real-world use-case in DAC and the adversary effectively reveals pseudonyms during a showing anyway. Also, we integrate user creation with credential issuance, as a user’s key pair is not used until it is associated with a credential. Otherwise, our unforgeability definition (Def. 12) is mostly unchanged from [17], but we add the \(\textsf{RegisterUser}\) and \(\textsf{RevokeUser}\) functions that facilitate revocation.

Moreover, our unforgeability definition ensures that the adversary was correctly delegated a credential on line 10 in Def. 12, and that none of the keys in the adversary’s credential are on the deny list, on line 11.

To ensure that the challenger can check the key classes, we parameterize the definition with the extractor, \(\mathcal {E}_\textsf{pk}\), which takes in a public key and extracts a secret key from it. If \(\mathcal {E}_\textsf{pk}\) is run on the transcript of a showing, it extracts the secret key of the credential holder. If \(\mathcal {E}_\textsf{pk}\) is run on the transcript of an issuing, it extracts the secret key of the issuer. We denote these by \(\mathcal {E}_{\textsf{pk},R}\) for receiver and \(\mathcal {E}_{\textsf{pk},I}\) for issuer. This extractor must extract the same secret key no matter how the public key has been randomized. For mercurial signatures, this means that the extractor extracts a canonical secret key which is constant over any representation of the equivalence class of secret keys. We also assume an extractor \(\mathcal {E}_\textsf{cred}\) that can take in a credential or the transcript of a showing of a credential and output the canonical secret keys used in the delegation chain including the end user of the credential.

Definition 12

(Unforgeability). A DAC scheme is unforgeable if any PPT adversary’s advantage in the following game, defined by the chance that the game outputs 1, is negligible in \(\lambda \). \(\mathcal {A} \) is given all the oracles from Fig 6 labeled as \(\mathcal {O}\).

4.3 DAC Construction

Our DAC construction uses the multi-level setup function from Fig. 4.

To simplify our DAC construction, we add a function \(\textsf{TracePK} \), which takes in a “linker” and a revocation token and returns if this linker is associated with the revocation token. These linker values will be stored in the deny list in the TRA’s public key \( tpk \).

Definition 13

(DAC construction).

• \({\textsf{Setup}}(1^\lambda ,1^L)\rightarrow (\textsf{pp}, td )\): Call the setup function described in Fig. 4 which generates L correlated parameters for our signature scheme in Fig. 3, \(\{\textsf{pp}_i\}_{i\in [L]}=\textsf{MultiSetup}(1^\lambda ,1^{\ell =2},1^L)\). Then initialize extra bases for the revocation authority and the root authority using the CL19 scheme, \((\textsf{pp}_\textsf{CL19})\leftarrow \textsf {Setup} _\textsf{CL19}(1^\lambda ,1^{\ell =2})\). Output \(\textsf{pp}=(\{\textsf{pp}_i\}_{i\in [L]},\textsf{pp}_\textsf{CL19}), td =(\{ td _i\}_{i\in [\ell ]})\).

• \({\textsf{RootKeyGen}}(\textsf{pp})\rightarrow (\textsf{sk}_{ rt},\textsf{pk}_{ rt})\): Generate a CL19 key pair using \(\textsf{pp}_\textsf{CL19}\).

• \({\textsf{UKeyGen}}(\textsf{pp},L')\rightarrow (\textsf{sk},\textsf{pk})\): Create a secret key for the corresponding scheme, \((\textsf{sk},\textsf{pk})\leftarrow \textsf{KGen}(\textsf{pp}_{L'})\). The user initializes their credential chain as \( chain =\perp \).

• \(\mathsf{T\textsf{KeyGen}}(\textsf{pp})\rightarrow ( tsk , tpk )\): Create a CL19 key \((\textsf{sk},\textsf{pk})\) of length \(\ell =2\), \(( tsk _\textsf{sk}, tpk _\textsf{pk})\leftarrow \textsf{KGen}(\textsf{pp}_\textsf{CL19})\). Initialize a set of linkers, \( tsk _ link =\emptyset \). Initialize a deny list, \({ DL }=\emptyset \). Let \( tsk _\textsf{sk}=\textsf{sk}\), \( tsk =( tsk _\textsf{sk}, tsk _ link )\), and \( tpk =( tpk _\textsf{pk},{ DL })\).

• \({\textsf{RegisterUser}}(\textsf{pp}, tsk ,\textsf{pk})\rightarrow ( tok )\): Generate a new key pair (\(\textsf{sk}_{ rev},\textsf{pk}_{ rev}\)) using \(\textsf{pp}_\textsf{CL19}\). Sign \(\textsf{pk}_{ rev}\) using \( tsk _\textsf{sk}\) where \( tsk =( tsk _\textsf{sk}, tsk _ link )\) yielding \(\sigma _0\). Then, use \(\textsf{sk}_{ rev}\) to sign \(\textsf{pk}\), yielding \(\sigma _1\). This yields the revocation token, \( tok =(\textsf{pk}_{ rev},\sigma _0,\sigma _1)\). The secret key, \(\textsf{sk}_{ rev}\), will serve as the linker for this revocation token and it is denoted as \( link \). Save this linker in the TRA’s state, \( tsk _ link '= tsk _ link \cup \{ link \}\) and update the state: \( tsk '=( tsk _\textsf{sk}, tsk _ link ')\). Output revocation token \( tok \).

• \(\textsf{RevokeUser}(\textsf{pp}, tsk , tpk , tok )\rightarrow tpk '\): Iterate through the linkers (\( link _i\)) in \( tsk _ link \) and check if \(\textsf{TracePK} (\textsf{pp}, link _i, tok )=1\) for each of them. If this holds for a linker, \( link _i\), concatenate \( link _i\) to the linkers in \( tpk \) (the deny list) and output this new public key as \( tpk '\).

• \(\textsf{TracePK} (\textsf{pp}, link , tok )\rightarrow \{0, 1\} \): Parse \( tok \) as \( tok =(\textsf{pk}_{ rev},\sigma _0,\sigma _1)\). Check if \(\textsf{RecognizePK}(\textsf{pp}_\textsf{CL19}, link ,\textsf{pk}_{ rev})=1\) (cf. Section 2), i.e., parse \(\textsf{pk}_{ rev}\) as \(\textsf{pk}_{ rev}=({\hat{X}}_1,{\hat{X}}_2)\). Parse \( link =(x_1,x_2)\). Check if \({\hat{X}}_1^{x_2/x_1}={\hat{X}}_2\). If this holds, output 1. Otherwise, output 0.

• \(({\textsf{Issue}}(\textsf{sk}_I,\textsf{cred}_I,L')\leftrightarrow {\textsf{Receive}}(\textsf{sk}_R,tok,L'))\rightarrow \textsf{cred}_R\): The receiver samples \(\rho \leftarrow {\mathcal{K}\mathcal{C}}\) (from the set of key converters) and generates a randomized public key from their secret key, \(\textsf{pk}'\), using the randomization factor, \(\rho \). They also randomize their revocation token, \( tok \), yielding, \( tok =(\textsf{pk}_{ rev}',\sigma _0',\sigma _1')\), such that \(\textsf{Verify}_\textsf{CL19}(\textsf{pp}_\textsf{CL19}, tpk ,\textsf{pk}_{ rev}',\sigma _0')=1\) and \(\textsf{Verify}_\textsf{CL19}(\textsf{pp}_\textsf{CL19},\textsf{pk}_{ rev}',\textsf{pk}',\sigma _0')=1\). The receiver sends over \(\textsf{pk}'\). The issuer then randomizes all public keys in their credential chain along with the signatures, randomizing their secret key to match. They also randomize all revocation tokens in their chain as described above. They then sign \(\textsf{pk}'\) yielding a signature, \(\sigma \). They send their randomized credential chain, \( chain \), along with \(\sigma \) to the receiver. The receiver computes the chain, \( chain '= chain \Vert (\textsf{pk}',\sigma , tok ')\). The receiver stores their credential as \(\textsf{cred}=( chain ',\rho )\). The randomizer is also stored to ensure the receiver can correctly randomize their secret key to match their public key in the chain.

• \(({\textsf{Prove}}(\textsf{sk}_P,\textsf{cred}_P, L')\leftrightarrow {\textsf{Verify}}(\textsf{pk}_{ rt},L', tpk ))\rightarrow (b,\{ tok _i\}_{i\in [L']})\): The prover randomizes all public keys and signatures in their credential \(\textsf{cred}\) using \(\rho ^*=\rho *\rho '\) where \(\rho \) is the randomizer found in their credential and \(\rho '\) is randomly sampled. They send over their randomized credential chain, \( chain \), and perform an interactive proof of knowledge that they know the \(\textsf{sk}\) that corresponds to the last public key in the chain. The verifier then verifies each public key with the signatures. The verifier also iterates through the revocation tokens in the credential chain checks that for each public key \(\textsf{pk}_i\) and \( tok _i=(\textsf{pk}_{{ rev},i},\sigma _{i,0},\sigma _{i,1})\) in the chain it holds that \(\textsf{Verify}_\textsf{CL19}( tpk ,\textsf{pk}_{{ rev},i},\sigma _{i,0})=1\) and \(\textsf{Verify}_\textsf{CL19}(\textsf{pk}_{{ rev},i},\textsf{pk}_i,\sigma _{i,1})=1\). They then also iterate through each \( link _j\in tpk \) and ensure that \(\textsf{TracePK} (\textsf{pp}, link _j, tok _i)=0\) for each level i in the length of the chain. If all these checks hold, the verifier outputs 1 and if any checks fail, the verifier outputs 0. The verifier also outputs all of the \( tok _i\) values received from the prover.

Theorem 7

(Correctness of the construction in Def. 13). Our construction in Def. 13 is correct as defined in the full version of this paper [22].

Theorem 8

(Unforgeability of the construction in Def. 13). If the underlying signature scheme is unforgeable with respect to Def. 2, our construction in Def. 13 is unforgeable with respect to Def. 12.

Theorem 9

(Anonymity of the construction in Def. 13). If the underlying signature scheme has origin-hiding and has adversarial public key-class hiding, the DAC scheme in Def. 13 is anonymous with respect to definition 11.

We prove these theorems (and define correctness) in the full version of this paper [22].

In this paper, we constructed mercurial signatures with stronger security properties than seen in the literature, which could potentially be used for many privacy-preserving schemes just as the first such signatures in [17]. We use it as a basis for an efficient DAC scheme with strong privacy guarantees and delegator revocation functionality. Our DAC construction could be further adapted to support attributes extending its functionality, where the technique from [32] seems promising. We leave this extension to future work.