Aisling Connolly
email: aislingmconnolly@gmail.com

Pascal Lafourcade
email: pascal.lafourcade@uca.fr

Octavio Perez Kempner
email: octavio.perez.kempner@ens.fr

Improved Constructions of Anonymous Credentials From Structure-Preserving Signatures on Equivalence Classes

Keywords: Anonymous credentials, Mercurial signatures, SPS-EQ

Anonymous attribute-based credentials (ABCs) are a powerful tool allowing users to authenticate while maintaining privacy. When instantiated from structure-preserving signatures on equivalence classes (SPS-EQ) we obtain a controlled form of malleability, and hence increased functionality and privacy for the user. Existing constructions consider equivalence classes on the message space, allowing the joint randomization of credentials and the corresponding signatures on them. In this work, we additionally consider equivalence classes on the signingkey space. In this regard, we obtain a signer-hiding notion, where the issuing organization is not revealed when a user shows a credential. To achieve this, we instantiate the ABC framework of Fuchsbauer, Hanser, and Slamanig (FHS, Journal of Cryptology '19) with a recent SPS-EQ scheme (ASIACRYPT '19) modified to support a fully adaptive NIZK from the framework of Couteau and Hartmann (CRYPTO '20). We also show how to obtain Mercurial Signatures (CT-RSA, 2019), extending the application of our construction to anonymous delegatable credentials. To further increase functionality and efficiency, we augment the setcommitment scheme of FHS19 to support openings on attribute sets disjoint from those possessed by the user, while integrating a proof of exponentiation to allow for a more efficient verifier. Instantiating in the CRS model, we obtain an efficient credential system, anonymous under malicious organization keys, with increased expressiveness and privacy, proven secure in the standard model.

Introduction

Considering access to online services, designing protocols to manage the information users can be requested to present is of utmost importance to protect the user. A first step in the literature developed the concept of attribute-based credentials (ABC), to model how users could show a credential, containing a set of attributes, to access different services.

Subsequently, the development of anonymous attribute-based credentials made it possible protect the holders identity when showing a credential. Users could present a credential disclosing no information other than that revealed by the attributes they choose to show (anonymity), while also ensuring that the provided information is authentic (unforgeability). Proposed alternatives consider a third property unlinkability which ensures that multiple showings of the same credential cannot be linked. Credential systems that support an arbitrary number of unlinkable showings are said to be multi-show. In contrast, those that only allow a single use of an issued credential in an unlinkable fashion are called one-show.

Initial progress was made with respect to one-show constructions. Here, blind signatures are issued on commitments to attributes so that users can later show the signature and disclose some of the attributes, while proving knowledge of those left unrevealed. Examples include [START_REF] Brands | Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy[END_REF][START_REF] Baldimtsi | Anonymous credentials light[END_REF], and [START_REF] Fuchsbauer | Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions[END_REF].

In the multi-show setting, pioneering constructions (based on Camenisch and Lysyanskaya's (CL) signatures [START_REF] Camenisch | A Signature Scheme with Efficient Protocols[END_REF][START_REF] Camenisch | Signature Schemes and Anonymous Credentials from Bilinear Maps[END_REF]) such as the one underlying the Idemix credential system [START_REF] Zurich | Specification of the identity mixer cryptographic library v2[END_REF] rely on randomizing the signature to then prove in zeroknowledge the correspondence between the set of attributes (disclosed and undisclosed), and the signature.

A major drawback from such an approach is that the zero-knowledge proof used during showings is of variable-length and may require multiple sub-proofs On the other hand, more recent constructions (e.g., [START_REF] Canard | Anonymous Credentials from (Indexed) Aggregate Signatures[END_REF][START_REF] Camenisch | Composable and Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF][START_REF] Sanders | Efficient Redactable Signature and Application to Anonymous Credentials[END_REF][START_REF] Hébant | Traceable Constant-Size Multi-Authority Credentials[END_REF][START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF][START_REF] Derler | A New Approach to Efficient Revocable Attribute-Based Anonymous Credentials[END_REF][START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF]) apply other techniques based on different lines of work to adapt the signature and the message without using Zero-Knowledge Proofs of Knowledge (ZKPoK), providing constant-size showings.

The concept of ABC has been recently extended to consider multi-authority credentials (e.g., [START_REF] Hébant | Traceable Constant-Size Multi-Authority Credentials[END_REF][START_REF] Sonnino | Coconut: Threshold Issuance Selective Disclosure Credentials with Applications to Distributed Ledgers[END_REF][START_REF] Datta | Decentralized Multi-Authority ABE for DNFs from LWE[END_REF]), where users obtain a single credential for a set of attributes not necessarily issued by a single authority. In this work we consider the classical setting (single authority issuance).

Limitations of state-of-the-art ABCs

Constructions in the classical setting differentiate from each other by the expressiveness they provide, their efficiency, on whether or not they provide noninteractive features, on their security model, and on how and if they manage revocation features. Achieving all these properties simultaneously has been challenging and tends to rely on complex or non-standard assumptions.

When considering state-of-the-art credential systems, there are five lines of work with respect to the underlying signature scheme that is used to build them;

(1) CL signatures [START_REF] Camenisch | Signature Schemes and Anonymous Credentials from Bilinear Maps[END_REF]: Idemix [START_REF] Zurich | Specification of the identity mixer cryptographic library v2[END_REF] and [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF]. (2) Aggregatable signatures: [START_REF] Canard | Anonymous Credentials from (Indexed) Aggregate Signatures[END_REF] and [START_REF] Hébant | Traceable Constant-Size Multi-Authority Credentials[END_REF]. (3) Sanitizable signatures: [START_REF] Canard | Protecting Privacy by Sanitizing Personal Data: A New Approach to Anonymous Credentials[END_REF]. (4) Redactable signatures: [START_REF] Camenisch | Composable and Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF] and [START_REF] Sanders | Efficient Redactable Signature and Application to Anonymous Credentials[END_REF]. [START_REF] Belenkiy | Randomizable Proofs and Delegatable Anonymous Credentials[END_REF] Structure-Preserving Signatures on Equivalence Classes (SPS-EQ): [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF].

Proof settings. All previous work with the exception of [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF] rely on security proofs in the Generic Group Model (GGM) [START_REF] Shoup | Lower Bounds for Discrete Logarithms and Related Problems[END_REF]. Our first motivation is to provide an alternative to [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF], building on [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] without relying on the GGM. Signer-hiding properties. Showing protocols of previous constructions (including [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF]), verify signatures with a key that belongs to the authority that issued the credential. This restricts the use of ABC in scenarios where one would like to verify a valid credential without linking it to a particular authority.

Concrete efficiency. Most alternatives provide similar efficiency at the asymptotic level. Yet, an up-to-date fine-grained analysis on their concrete efficiency lacks in the literature.

Summary of contributions

We follow the ABC and SPS-EQ line of work from Fuchsbauer, Hanser and Slamanig [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF], improving over prior work in the following ways:

1. We extend the set-commitment scheme from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] to build a more expressive credential system allowing the generation of witnesses for disjoint sets ( [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] allows only selective disclosure of attributes). 2. We instantiate the ABC from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF], with a new SPS-EQ scheme based on the one from [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] also using a CRS, a tight reduction, and under weaker assumptions. Thus, we move away from a security proof in the GGM when compared to the work from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF], and obtain a more efficient ABC than the one resulting from instantiating [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] with [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] (see Table 1). 3. We incorporate a proof of exponentiation to outsource part of computational cost from the verifier to the prover, which can be useful in some settings. 4. We adapt the signature scheme to build an SPS-EQ where one not only can randomize the message together with the signature, but also the corresponding public key used to verify the signature using a proof of well-formedness. Thus, users can hide the identity of the signer during showings.

By doing so, the verifier can check a signature using a randomized public key, knowing that it comes from a valid authority but not which one. Unlike solutions using ring signatures where it is the signer (credential issuer) who chooses the ring size, we let users do it independently (relying on SPS-EQ and an efficient proof of correct randomization alone). Hence, once users get a credential from a valid authority they can decide on the anonymity set themselves whenever they use their credential. This approach is better aligned with the concept of self sovereign identity and related applications that seek to empower users giving them full control on their identity.

Along the way, we also describe how to build mercurial signatures [START_REF] Crites | Delegatable Anonymous Credentials from Mercurial Signatures[END_REF] with security proofs in the standard model (assuming a CRS). All the previous ones [START_REF] Crites | Delegatable Anonymous Credentials from Mercurial Signatures[END_REF][START_REF] Crites | Mercurial signatures for variable-length messages[END_REF] have security proofs in the GGM. Consequently, our signature construction can also be used to build delegatable anonymous credentials [START_REF] Chase | On Signatures of Knowledge[END_REF][START_REF] Belenkiy | Randomizable Proofs and Delegatable Anonymous Credentials[END_REF] as well.

SPS [START_REF] Gay | More Efficient (Almost) Tightly Secure Structure-Preserving Signatures[END_REF] OR-Proof [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF] OR-Proof [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] OR-Proof [START_REF] Ràfols | Stretching groth-sahai: Nizk proofs of partial satisfiability[END_REF] OR-Proof [42] SPS-EQ [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] ABC [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] SCDS PoE [START_REF] Thakur | Batching non-membership proofs with bilinear accumulators[END_REF] DS [START_REF] Ghosh | Zero-Knowledge Accumulators and Set Algebra[END_REF] SC [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] Our work OR-Proof [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF] Signer-Hiding Fig.

Roadmap

We begin by presenting related work with a focus on the development of SPS-EQ and set-commitment schemes (Section 2) followed by the required cryptographic background in Section 3. Our first contribution, extending the set-commitment scheme (SC) in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] to support non-membership proofs for disjoint sets (DS), is presented in Section 4. We also define here the proof of exponentiation (PoE), which can be seen as an optional plug-in to gain efficiency in this new setcommitment scheme (SCDS).

In Section 5 we present our SPS-EQ scheme. It uses a new malleable NIZK argument based on a recent work from Couteau and Hartmann [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF], which we use to replace the one underlying [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF].

In [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] the authors discuss a concurrently secure variant of their ABC based on a trapdoor commitment scheme to implement ZKPoK, assuming the existence of one-way functions and a CRS. Since our SPS-EQ makes use of a CRS, we instantiate the previous variant with it, incorporate a Pedersen commitment scheme to compute the relevant ZKPoK, and adapt the rest to our set-commitment scheme and the proof of exponentiation (second and third contributions). Thus, we dedicate Section 6 to present the resulting ABC.

Subsequently, we extend the previous construction to support another NIZK argument that allows to hide the identity of the signer during showings. This allows us to build another ABC as our fourth contribution. Furthermore, we also outline in this section how to perform revocation and build mercurial signatures.

In Figure 1 we summarize the dependencies between the different building blocks used in the previously mentioned sections highlighting our contributions.

Finally, a detailed comparison on the concrete efficiency of our constructions when compared to other state-of-the-art alternatives is provided in Section 8, while the conclusions of this work are presented in Section 9.

2 Background and Related Work

Structure-Preserving Signatures on Equivalence Classes

In [START_REF] Hanser | Structure-Preserving Signatures on Equivalence Classes and Their Application to Anonymous Credentials[END_REF], Hanser and Slamanig introduced a novel structure preserving signature (SPS) scheme that allowed joint randomization of messages and their corresponding signatures, coining Structure-Preserving Signatures on Equivalence Classes (SPS-EQ). They observed that if one considers a prime-order group G and defines the projective vector space (G * ) ℓ , there is a partition into equivalence classes given by the following relation R:

m ∈ (G * ) ℓ ∼ R m * ∈ (G * ) ℓ ⇐⇒ ∃ µ ∈ Z * p : m * = µm.
If the discrete logarithm problem is hard in G and one restricts the vector components to be non-zero, given two vectors m and m * , it is difficult to distinguish whether they were randomly sampled or if they belong to the same equivalence class. Hence, Hanser and Slamanig defined SPS-EQ as SPS that produce signatures on an equivalence class instead of messages alone. Given a message and its corresponding signature, SPS-EQ provides a controlled form of malleability in which one can publicly (without requiring access to the secret key) adapt a signature to change the representative (message). The equivalence relation provides indistinguishability on the message space if the DDH assumption holds. If additionally, updated signatures are distributed like fresh signatures, message-signature pairs falling into the same class are unlinkable. For unlinkability to hold, signatures should also be randomized when adapting them to a new representative of the class. As described in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF], given a representative and its corresponding signature, a random representative of the same class with an adapted signature are indistinguishable from a random message-signature pair.

Since their introduction, SPS-EQ have been used to build several cryptographic protocols (e.g., [START_REF] Backes | Signatures with Flexible Public Key: Introducing Equivalence Classes for Public Keys[END_REF][START_REF] Fuchsbauer | Practical Round-Optimal Blind Signatures in the Standard Model[END_REF][START_REF] Fuchsbauer | Practical Round-Optimal Blind Signatures in the Standard Model from Weaker Assumptions[END_REF][START_REF] Backes | Membership Privacy for Fully Dynamic Group Signatures[END_REF][START_REF] Derler | Highly-Efficient Fully-Anonymous Dynamic Group Signatures[END_REF][START_REF] Bultel | Efficient Invisible and Unlinkable Sanitizable Signatures[END_REF][START_REF] Fuchsbauer | Access Control Encryption for Equality, Comparison, and More[END_REF]). They have been used in anonymous credentials [START_REF] Hanser | Structure-Preserving Signatures on Equivalence Classes and Their Application to Anonymous Credentials[END_REF][START_REF] Derler | A New Approach to Efficient Revocable Attribute-Based Anonymous Credentials[END_REF][START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF], and delegatable anonymous credential systems, in this case under the name of mercurial signatures [START_REF] Crites | Delegatable Anonymous Credentials from Mercurial Signatures[END_REF][START_REF] Crites | Mercurial signatures for variable-length messages[END_REF], which are an extension of the equivalence classes to the signing keys. State-of-the-art constructions focus on building schemes under weaker assumptions and with tight security. The first step was the work from Fuchsbauer and Gay [START_REF] Fuchsbauer | Weakly Secure Equivalence-Class Signatures from Standard Assumptions[END_REF]. Subsequently, Khalili et al. [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] proposed a new SPS-EQ which is, to the best of our knowledge, the only one under standard assumptions and with a tight security reduction to date.

The construction of [START_REF] Fuchsbauer | Weakly Secure Equivalence-Class Signatures from Standard Assumptions[END_REF] is based on the family of Matrix-Diffie-Hellman assumptions [START_REF] Escala | An Algebraic Framework for Diffie-Hellman Assumptions[END_REF]. They first modify an affine MAC from [START_REF] Blazy | Hierarchical) Identity-Based Encryption from Affine Message Authentication[END_REF] to obtain a linear structure-preserving MAC, which is made publicly verifiable using a known technique in the context of SPS [42]. This allows to use a tag to randomize both the signature and message.

The resulting scheme is secure under a weaker notion of unforgeability (EUF-CoMA). In [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF], authors observe that using a structure-preserving MAC such as the one from [START_REF] Fuchsbauer | Weakly Secure Equivalence-Class Signatures from Standard Assumptions[END_REF] has an inherent problem in the security game. As messages and Matrix Decision Diffie-Hellman challenges belong to the same source group of the bilinear group, one cannot do better than EUF-CoMA security following this approach. Consequently, they proposed to use an OR-Proof based on that in [START_REF] Gay | More Efficient (Almost) Tightly Secure Structure-Preserving Signatures[END_REF] to then construct tightly secure structure-preserving MACs based on the key encapsulation mechanism of Gay et al. in [34]. This allows to circumvent the previous issue and obtain the first EUF-CMA secure SPS-EQ scheme with a tight security reduction under standard assumptions.

In this work, we present an SPS-EQ scheme where the OR-based proof in [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] is replaced by the one in [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF], while adapting other building blocks accordingly.

Accumulators and Set-Commitments.

In [START_REF] Derler | Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives[END_REF], Derler, Hanser and Slamanig revisited the notion of cryptographic accumulators and proposed a unified formal model which included the notions of undeniability and indistinguishability for accumulators, complementing the classical ones of correctness and collision-freeness. They showed how to construct a commitment scheme using an indistinguishable accumulator in a black-box manner. The relation stems from the fact that indistinguishability and collisionfreeness of accumulators resemble those of hiding and binding for commitments.

In subsequent work [START_REF] Hanser | Structure-Preserving Signatures on Equivalence Classes and Their Application to Anonymous Credentials[END_REF], Hanser and Slamanig built an ABC with constantsize credentials and constant-size showings (for selective disclosure of attributes) based on a polynomial commitment scheme with factor openings. They departed from the work of Kate et al. on constant-size polynomial commitments [START_REF] Kate | Constant-Size Commitments to Polynomials and Their Applications[END_REF] with the following observations; (1) If a credential is seen as a set of attributes mapped to roots of a monic polynomial, then one can generate a polynomial commitment of constant-size to represent the credential using the approach from [START_REF] Kate | Constant-Size Commitments to Polynomials and Their Applications[END_REF]. As a result they proposed an indistinguishable bilinear accumulator ( [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF]) with batch membership proofs (i.e, factor opening), which was subsequently re-stated as a set-commitment scheme in a follow-up work [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF].

A drawback of the ABC from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] is that the achieved level of expressiveness is limited. It allows only to show proofs for the conjunction of attributes in arbitrary subsets of attributes encoded in the credential (selective disclosure). Another potential issue is that verification involves a number of exponentiations that are linear in the size of the subset to be verified. This is undesirable when verification of the credential should be fast.

Thakur [START_REF] Thakur | Batching non-membership proofs with bilinear accumulators[END_REF] proposed a series of protocols for batch membership and nonmembership proofs for bilinear accumulators using proofs of exponentiation (an idea previously introduced for accumulators in groups of unknown order by Boneh et. al [START_REF] Boneh | Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains[END_REF] and by Wesolowski [START_REF] Wesolowski | Efficient Verifiable Delay Functions (extended version)[END_REF]) to shift the computational cost from the verifier to the prover. The main idea is to replace some of the exponentiations by a single polynomial division and to use of a non-interactive proof obtained via the Fiat-Shamir transform.

Batch proofs in the bilinear accumulator setting can be traced back to the works by Papamanthou et al. [START_REF] Papamanthou | Optimal verification of operations on dynamic sets[END_REF] and by Ghosh et al. [START_REF] Ghosh | Zero-Knowledge Accumulators and Set Algebra[END_REF]. The latter presents the same underlying ideas of the (non)membership proofs provided by Thakur, and a Zero-Knowledge Dynamic Universal Accumulator, which strengthens the notion of indistinguishability using the randomization ideas from [START_REF] Derler | Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives[END_REF].

Scheme [13] [14] [15] [START_REF] Camenisch | Composable and Modular Anonymous Credentials: Definitions and Practical Constructions[END_REF] & [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] [50] [START_REF] Sanders | Efficient Redactable Signature and Application to Anonymous Credentials[END_REF] [39] Section 6 Issuing n-attr. credential

Comm. O(n) O(n) O(n) O(1) O(n) O(1) O(n) O(1) User O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) Issuer O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) Showing k-of-n attributes (selective disclosure) |ek| O(n) O(n) O(n) O(n) O(n) O(n 2 ) O(n) O(n) Comm. O(n) O(1) O(k) O(1) O(1) O(1) O(1) O(1) User O(n) O(n) O(k) O(n -k) O(n -k) O(n -k) O(1) O(max{n -k, k}) Verifier O(n) O(n) O(k) O(k) O(k) O(k) O(n) O(1)
Table 2: Asymptotic complexities of ABC systems where n is the number of attributes in the credential and k the number of disclosed ones during a showing.

More recently, a new set-commitment scheme including set intersection and set difference operations was proposed in [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF]. It provides more expressiveness when compared to the one from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] but under a weaker hiding notion.

We incorporate the previous ideas from [START_REF] Derler | Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives[END_REF][START_REF] Ghosh | Zero-Knowledge Accumulators and Set Algebra[END_REF], and [START_REF] Thakur | Batching non-membership proofs with bilinear accumulators[END_REF] to extend the setcommitment scheme from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] to support disjoint sets (batch non-membership proofs), while also allowing a faster verification and a stronger hiding notion. Thus, we obtain a set-commitment scheme that is more expressive than the one in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] and almost as expressive as [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF] (but better in efficiency and strength).

Attribute-based Credentials

We recall in Table 2 the asymptotic complexities for the issuing and showing protocols, considering recent credential systems from each of the lines of work mentioned in the introduction, and our construction in Section 6 . For showing protocols we consider the selective disclosure of attributes (i.e., the ability to show multiple attributes while hiding others during a showing). While the work from [START_REF] Hébant | Traceable Constant-Size Multi-Authority Credentials[END_REF] (based on aggregatable signatures) is the only one with O(1) complexity for the user during a showing, this is obtained at the cost of a more expensive verifier. Our work achieves O(1) complexity for the verifier but keeping better asymptotics for the user. A more detailed comparison on the concrete efficiency of ABC's (as well as an implementation benchmark) was provided in [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF], but the recent works from [START_REF] Sanders | Efficient Redactable Signature and Application to Anonymous Credentials[END_REF] and [START_REF] Hébant | Traceable Constant-Size Multi-Authority Credentials[END_REF] were not included. Therefore, we provide an updated comparison for the most efficient ones in Section 8.

Signer-Hiding

Independent and concurrent work by Bobolz et al. [START_REF] Bobolz | Issuer-hiding attribute-based credentials[END_REF] also addressed the problem of hiding the identity of a credential issuer/signer under the notion of issuerhiding. There, the authors propose a sligthly different setting to avoid using an OR-like proof as done in this work. In brief, the authors consider access policies of the form {σ i , pk i } i∈ [n] , where σ i is a signature on a given authority's public key pk i produced by the verifier. As a result, users can prove the correspondence between a public key (defined in the policy) and the credential verification under that public key in zero knowledge, using a NIZK independent to the number of public keys defined in the policy. In this regard, we note that our work is compatible with their formalization and, furthermore, under the previous setting such NIZK can be avoided in our case. Since we use mercurial signatures, it would suffice to randomize the access policy and the user credential consistently.

Preliminaries

Notation. Let BGGen be a p.p.t algorithm that on input 1 λ with λ the security parameter, returns a description BG = (p, G 1 , G 2 , G T , P 1 , P 2 , e) of an asymmetric bilinear group where G 1 , G 2 , G T are cyclic groups of prime order p with ⌈log 2 p⌉ = λ, P 1 and P 2 are generators of G 1 and G 2 , and e : G 1 × G 2 → G T is an efficiently computable (non-degenerate) bilinear map. BG is said to be of Type-3 if no efficiently computable isomorphisms between G 1 and G 2 are known. For all a ∈ Z p , we denote by [a] s = aP s ∈ G s the implicit representation of a in G s for s ∈ {1, 2, T }. For matrices (or vectors) A, B we extend the pairing notation to e(

[A] 1 , [B] 2 ) := [AB] T ∈ G T . Sampling r from set S uniformly at random is denoted by r $ ← S.
Finally, we use the notation A(x; y) to indicate that a value y (usually computed internally by A), is being passed directly to A on input x.

Assumptions. We recall the Diffie-Hellman assumptions in the billinear group setting and the algebraic framework from [START_REF] Escala | An Algebraic Framework for Diffie-Hellman Assumptions[END_REF] and [START_REF] Morillo | The Kernel Matrix Diffie-Hellman Assumption[END_REF], including a generalization of the Strong Diffie-Hellman assumption from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF], in the full version (Appendix A from [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF]). Besides, we will also use the following generalization of the KerMDH assumption introduced in [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF]. It allows an adversary to extend the given matrix but requiring it to output multiple, linearly independent vectors in the kernel.

Pr   [C] 3-s ∈ G l+1×k+l+1 3 ∧ [B] s ∈ G l×k s ∧ [C] 3-s [D ′ ] s = 0 ∧ rank(C) ≥ l + 1 BG $ ← BGGen(1 λ ); D $ ← D k ([C] 3-s , [B] s ) $ ← A(BG, [D] s ) [D ′ ] s := [ D B ] s   Characteristic Polynomial. For a set X with elements in Z p , we refer to Ch X (X) = x∈X (X + x) = i=n i=0 c i • X i (a monic polynomial of degree n = |X | and defined over Z p [X]
) as its characteristic polynomial. For a group generator P , Ch X (s)P can be efficiently computed (e.g., using the Fast Fourier Transform) when given (s i P )

|X | i=0 but not s. This is because Ch X (s)P = i=n i=0 (c i • s i )P .
In addition to exploiting properties of characteristic polynomials, we will also use the Schwartz-Zippel lemma and the Extended Euclidean Algorithm (EEA) in our constructions following the ideas from [START_REF] Ghosh | Zero-Knowledge Accumulators and Set Algebra[END_REF].

Lemma 1 (Schwartz-Zippel)Let q 1 (x), q 2 (x) be two d-degree polynomials from Z p [X] with q 1 (x) ̸ = q 2 (x), then for s $ ← Z p , the probability that q 1 (x) = q 2 (x) is at most d/p, and the equality can be tested in time O(d).

Non-interactive Zero-Knowledge Arguments and Malleable Proof Systems

We next define fully adaptive NIZK arguments (i.e., the crs does not depend on the language distribution or language parameters), and the notions of malleable proof systems given in [START_REF] Chase | Malleable proof systems and applications[END_REF] and [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] respectively.

NIZK Syntax. A fully adaptive NIZK Π for a family of language distribution {D pp } pp consists of four probabilistic algorithms:

PGen(1 λ ): On input 1 λ generates public parameters pp, a crs and a trapdoor td. Prove(crs, ρ, x, w): On input a crs, a language description ρ ∈ D pp and a statement x with witness w, outputs a proof π for x ∈ L ρ . Verify(crs, ρ, x, π): On input a crs, a language description ρ ∈ D pp , a statement

x and a proof π, accepts or rejects the proof. SimProve(crs, td, ρ, x): Given a crs, the trapdoor td, a language description ρ ∈ D pp and a statement x, outputs a simulated proof for the statement x ∈ L ρ .

The following properties need to hold for NIZK arguments with respect to a family of language distributions D pp .

Perfect Completeness.

Pr Verify(crs, ρ, x, π) = 1 (pp, crs, td)

$ ← PGen(1 λ ); ρ ∈ Supp(D pp ); (x, w) ∈ R ρ ; π $ ← Prove(crs, ρ, x, w) = 1
Computational Soundness. For every efficient adversary A,

Pr Verify(crs, ρ, x, π) = 1 ∧ x / ∈ L ρ (pp, crs, td) $ ← PGen(1 λ ); ρ ∈ Supp(D pp ); (π, x) $ ← A(crs, ρ) ≈ 0
where the probability is taken over PGen.

Perfect Zero-Knowledge. For all λ, all (pp, crs, td) ∈ Supp(PGen(1 λ )), all ρ ∈ Supp(D pp ) and all (x, w) ∈ R ρ , the distributions Prove(crs, ρ, x, w) and SimProve(crs, td, ρ, x) are identical.

Let R L be the witness relation associated to a language L, then a controlled malleable proof system is accompanied by a family of efficiently computable nary transformations T = (T x , T w ) such that for any n-tuple {(x 1 , w 1 ), . . . ,

(x n , w n )} ∈ R n L it holds that (T x (x 1 , . . . , x n ),T w (w 1 , . . . , w n )) ∈ R L .
Intuitively, such a proof system allows when given valid proofs

{Ω i } i∈[n] for words {x i } i∈[n] with associated witnesses {w i } i∈[n]
to publicly compute a valid proof Ω for word x := T x (x 1 , . . . , x n ) corresponding to witness w := T w (w 1 , . . . , w n ) using an additional algorithm ZKEval which is defined as follows:

ZKEval(crs, T , (x i , Ω i ) i∈[n]
) takes as input a common reference string crs, a transformation T ∈ T , words x 1 , . . . , x n and their corresponding proofs Ω 1 , . . . , Ω n , and outputs a new word x ′ := T x (x 1 , . . . , x n ) and proof Ω ′ .

Proofs computed by ZKEval should be indistinguishable from freshly computed proofs for the resulting word x ′ and corresponding witness w ′ . This notion is captured by the following definition. Derivation Privacy. A NIZK proof system Π, malleable with respect to a set of transformations T defined on some relation R is derivation private, if for all p.p.t adversaries A, the following probability is negligible,

Pr           crs $ ← PGen(1 λ ), b $ ← {0, 1} (st, ((x i , w i ), Ω i ) i∈[q] , T ) $ ← A(crs), if (T / ∈ T ∨ (∃ i ∈ [q] : (Verify(crs, x i , Ω i ) = 0) ∨ (x i , w i ) / ∈ R) return ⊥, else if b = 0 : Ω ← Prove(crs, T x ((x i ) i∈[q] ), T w ((w i ) i∈[q] )), else if b = 1 : Ω ← ZKEval(crs, T, (x i , π i ) i∈[q] ), b ′ $ ← A(st, Ω) : b = b ′          

A Set-Commitment Scheme supporting Disjoint Sets

We extend the set-commitment scheme in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] to support non-membership proofs for disjoint sets, while also including an optional proof of exponentiation to replace most of the exponentiations in the verifier (outsourcing them to the prover) with a single polynomial division. To do so, we borrow the previously mentioned ideas in [START_REF] Derler | Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives[END_REF], [START_REF] Ghosh | Zero-Knowledge Accumulators and Set Algebra[END_REF] and [START_REF] Thakur | Batching non-membership proofs with bilinear accumulators[END_REF], and adapt them to the Type-3 setting. SCDS Syntax. A set-commitment scheme supporting disjoint sets (SCDS) consists of the following p.p.t algorithms:

Setup(1 λ , 1 q ) is a probabilistic algorithm which takes as input a security parameter λ and an upper bound q for the cardinality of committed sets, both in unary form. It outputs public parameters pp (including an evaluation key ek), and discards the trapdoor key s used to generate them. Z * p \ {s} defines the domain of set elements for sets of maximum cardinality q. TSetup(1 λ , 1 q ) is equivalent to Setup but also returns the trapdoor key. Commit(pp, X ) is a probabilistic algorithm which takes as input pp and a set VerifyDS(pp, C, D, wit) takes as input pp, a commitment C, a non-empty set D, and a witness wit. If wit is a valid witness for D being disjoint from the set committed to in C, it outputs 1 and otherwise ⊥. PoE(pp, X , α) takes as input pp, a non-empty set X , and a randomly-chosen value α. It computes a proof of exponentiation for the characteristic polynomial of X and outputs a proof π Q and a witness Q.

X with 1 ≤ |X | ≤ q. It
A SCDS scheme is secure if it satisfies the properties of correctness, binding, hiding, and soundness. These notions are defined next, modified to suit the scheme, but following the usual convention.

Correctness. An SCDS scheme is correct if for all q > 0, all λ > 0, all pp ∈ [Setup(1 λ , 1 q )], all non-empty S ⊆ X and all non-empty D : D ∩ X = ∅, the following probabilities equal 1:

1.

Pr (C, O) $ ← Commit(pp, X ) : Open(pp, C, X , O) = 1 2. Pr (C, O) $ ← Commit(pp, X ); wit ← OpenSS(pp, C, X , O, S) : VerifySS(pp, C, S, wit) = 1 3. Pr (C, O) $ ← Commit(pp, X ); wit ← OpenDS(pp, C, X , O, D) : VerifyDS(pp, C, D, wit) = 1
Binding. An SCDS scheme is binding if for all q > 0 and all p.p.t adversaries A, the following probability is negligible,

Pr pp $ ← Setup(1 λ , 1 q ), (C, X , O, X ′ , O ′ ) $ ← A(pp) : Open(pp, C, X , O) = 1 ∧ Open(pp, C, X ′ , O ′ ) = 1 ∧ X ̸ = X ′
Hiding. We say that an SCDS scheme is hiding if for all q > 0 and all p.p.t adversaries A with access to O SS , an opening oracle which allows queries for sets X ′ ⊆ X 0 ∩ X 1 , and to O DS , for sets X ′ s.t. X ′ ∩ {X 0 ∪ X 1 } = ∅, there is a negligible function ϵ(•) such that:

Pr      b $ ← {0, 1}; pp $ ← Setup(1 λ , 1 q ); (X 0 , X 1 , st) $ ← A(pp); (C, O) $ ← Commit(pp, X b ); b * $ ← A O SS (pp,C,X b ,O,•),O DS (pp,C,X b ,O,•) (st, C) : b * = b      - 1 2 ≤ ϵ(k).
where X 0 and X 1 are two distinct sets s.

t. 1 ≤ |X b | ≤ q.
If the above holds for ϵ ≡ 0, the scheme is said to be perfectly hiding.

Soundness. An SCDS scheme is sound if for all q > 0 and all p.p.t adversaries A, the following probabilities are negligible, Our construction is presented in Figure 2. As in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] we use a special opening for the case in which the commited set contains the trapdoor to achieve perfect correctness and perfect hiding. To prove that a given set is disjoint with respect to the commited set, the EEA is computed to obtain the Bézout coefficients. This way, equality is checked randomizing q 1 , q 2 and using a single PPE. Finally, the PoE computes a polynomial division, and produces the corresponding proof.

1. Pr pp $ ← Setup(1 λ , 1 q ); (C, X , O, S, wit) $ ← A(pp) : S ⊈ X ∧ OpenSS(C, X , O) = 1 ∧ VerifySS(C, S, wit) = 1 2. Pr pp $ ← Setup(1 λ , 1 q ); (C, X , O, D, wit) $ ← A(pp) : D ∩ X ̸ = ∅ ∧ OpenDS(C, X , O) = 1 ∧ VerifyDS(C, D, wit) = 1 SCDS.Setup(1 λ , 1 q ): BG $ ← BGGen(1 λ ); s $ ← Z * p pp ← (BG, (s i P1, s i P2) i∈[q] ) return pp SCDS.TSetup(1 λ , 1 q ): BG $ ← BGGen(1 λ ); s $ ← Z * p pp ← (BG, (s i P1, s i P2) i∈[q] ) return (pp, s) SCDS.PoE(pp, X , α): Q ← ChX (s)P2; Let h(X) and β s.t. ChX (X)=(X+α)•h(X)+β; πQ ← h(s)P2 return (πQ, Q) SCDS.Commit(pp, X ): if |X | > q return ⊥; r $ ← Z * p if ∃ s ′ ∈ X : s ′ P1 = sP1 C ← rP1; O ← (1, (r, s ′ )) else C ← r • ChX (s)P1; O ← (0, r) return (C, O) SCDS.Open(pp, C, X , O): if O = (1, (r, s ′ )) ∧ s ′ P1 = sP1 if C = rP1 return 1 else 0 if O = (0, r) if C = r • ChX (s)P1 return 1 else 0 SCDS.OpenSS(pp, C, X , O, S): if SCDS.Open(C, X , O) = 0 ∨ S ⊈ X ∨ S = ∅ return ⊥ if O = (1, (r, s ′ )) if s ′ / ∈ S return ChS (s ′ ) -1 C if O = (0, r) return r • Ch X \S (s)P1 else return ⊥ SCDS.VerifySS(pp, C, S, wit, [PoE]): if (S = ∅ ∧ wit = ⊥) return 1 if ∃ s ′ ∈ S : s ′ P1 = sP1 if wit = ⊥ return 1 else 0 if PoE = ⊥ return e(wit, ChS (s)P2) = e(C, P2) else parse PoE = (α, πQ, Q) β ← ChS (X)(mod (X + α)) return e(sP1+αP1, πQ)+e(βP1, P2) = e(P1, Q) ∧ e(wit, Q) = e(C, P2) SCDS.OpenDS(pp, C, X , O, D): if (t = 0 ∨ |D ∩ X | > 0) return ⊥ if O = (1, (r, s ′ )) if s ′ ∈ D return ⊥ else γ $ ← Z * p ; (w0, w1) ← (γP2, 1-γ•r Ch D (s) P1) if O = (0, r) γ $ ← Z * p ; Let q1(X) and q2(X) s.t. ChX (X) • q1(X) + ChD(X) • q2(X) = 1 q ′ 1 (s) ← q1(s) + γ • ChD(s) q ′ 2 (s) ← q2(s) -γ • ChX (s) (w0, w1) ← ((r -1 • q ′ 1 (s))P2, q ′ 2 (s)P1) return (w0, w1) SCDS.VerifyDS(pp, C, D, wit, [PoE]): if (D = ∅ ∧ wit = ⊥) return 1 if ∃ s ′ ∈ D : s ′ P1 = sP1 if wit = ⊥ return
Theorem 1. The SCDS construction from Figure 2 is correct and perfectly hiding. Furthermore, if the q-co-DL (resp. q-co-GSDH) assumption holds, SCDS is computationally binding (resp. sound).

Proof. The proof strategy follows closely that of [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF]. We extend these proofs in a similar manner to consider disjoint sets. The full proof is provided in [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF] (Appendix B).

Our SPS-EQ construction

The starting point for the SPS-EQ construction in [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] was the tightly secure SPS from [START_REF] Gay | More Efficient (Almost) Tightly Secure Structure-Preserving Signatures[END_REF], which builds on a structure-preserving MAC (based on the works from [START_REF] Gay | Kurosawa-Desmedt Meets Tight Security[END_REF] and [START_REF] Hofheinz | Adaptive partitioning[END_REF]) and a NIZK OR-Proof from [START_REF] Ràfols | Stretching groth-sahai: Nizk proofs of partial satisfiability[END_REF]. To couple with equivalence classes, the authors proposed a way to adapt the OR-Proof so that it could be randomized and malleable. Unfortunately, as the CRS used in the OR-Proof from [START_REF] Ràfols | Stretching groth-sahai: Nizk proofs of partial satisfiability[END_REF] was incompatible with the required randomization properties, the authors were forced to build a QA-NIZK on top to overcome the limitation.

In this section we introduce a new SPS-EQ scheme based on the one from [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF], which we obtain replacing the underlying OR-Proof from [START_REF] Ràfols | Stretching groth-sahai: Nizk proofs of partial satisfiability[END_REF] with one given in [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF], while adapting accordingly. As a result we obtain a more efficient signature scheme based on a new malleable OR-NIZK argument. Before giving the intuition of our construction, we recall the syntax and security properties for SPS-EQ introduced in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] and [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF].

SPS-EQ Syntax. An SPS-EQ consists of the following p.p.t algorithms:

ParGen(1 λ )is a probabilistic algorithm which takes as input a security parameter λ and returns public parameters pp including an asymmetric bilinear group, but without the related trapdoor. TParGen(1 λ )is like the ParGen algorithm but it also returns the trapdoor. KGen(pp, ℓ)is a probabilistic algorithm which takes as input pp and a vector length ℓ > 1, and outputs a key pair (sk, pk). Sign(pp, sk, m)is a probabilistic algorithm which takes as input pp, a representative m ∈ (G * i ) ℓ for class [m] R , a secret key sk, and outputs a signature σ ′ = (σ, τ ) (potentially including a tag τ ) on the message m. ChgRep(pp, m, (σ, τ ), µ, pk)is a probabilistic algorithm which takes as input pp, a representative message m ∈ (G * i ) ℓ , a signature σ (and potentially a tag τ ), a scalar µ and a public key pk. It computes an updated signature σ ′ on new representative m * = µm and returns (m * , σ ′ ). Verify(pp, m, (σ, τ ), pk)is a deterministic algorithm which takes as input pp, a representative message m, a signature σ (potentially including a tag τ ) and public key pk. If σ is a valid signature on m it outputs 1 and 0 otherwise.

Correctness. An SPS-EQ scheme over (G * i ) ℓ is correct if for any λ ∈ N, any ℓ > 1, any pp $ ← ParGen(1 λ ), any pair (sk, pk), any message m ∈ (G * i ) ℓ , and any µ ∈ Z * p , the following holds:

Pr Verify(m, Sign(sk, m), pk) = 1 = 1, and Pr Verify(ChgRep(m, Sign(sk, m), µ, pk), pk) = 1 = 1.

EUF-CMA. An SPS-EQ scheme over (G * i ) ℓ is existentially unforgeable under adaptively chosen-message attacks, if for all ℓ > 1 and p.p.t adversaries A with access to a signing oracle Sign, the following probability is negligible,

Pr    pp $ ← ParGen(1 λ ), (sk, pk) $ ← KGen(pp, ℓ), ([m] * i , σ * ) $ ← A Sign(sk,•) (pk) : [m * ] R ̸ = [m] R ∀ [m] i ∈ Q ∧ Verify([m] * i , σ * , pk) = 1    ,
where Q is the set of queries that A has issued to the signing oracle Sign. Note that in the tag-based case this oracle returns (σ i , τ i ).

The following notion is based on Definition 10 from [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF], which defines perfect adaption of signatures in the CRS model. Perfect adaption mandates that signatures output by the algorithm ChgRep are distributed identically to new signatures on the respective representative. When this notion is defined considering adversaries who could maliciously generate signing keys, one obtains the strongest possible notion for perfect adaption. Unlike [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF], we opt to explicitly state that perfect adaption is defined with respect to the message space. We do this, as later on we will introduce a new a definition for perfect adaption with respect to the key space.

Perfect adaption of signatures (under malicious keys in the honest parameters model) with respect to the message space: An SPS-EQ over S m perfectly adapts signatures with respect to the message space if for all tuples (pp, pk, [m] i , σ, µ) where pp

Our Malleable NIZK argument

Our malleable NIZK argument is based solely on the fully-adaptive OR-Proof from [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF]. This allows us to circumvent the randomization problem in the OR-Proof from [START_REF] Ràfols | Stretching groth-sahai: Nizk proofs of partial satisfiability[END_REF], and to avoid the need to build a QA-NIZK atop.

As a result, we reduce the number of exponentiations required in the proving and ZKEval algorithms, which leads to a more efficient signature scheme. This comes at the cost of relying on the L 1 -1-extKerMDH assumption. We argue that the change is justified as the extKerMDH is a natural extension of the KerMDH assumption and in this case, the assumption is also falsifiable.

Intuition. We look for a NIZK proof which can be randomizable and malleable so that randomized proofs look like fresh proofs, while the malleability allows to update the proof statements. The goal is to obtain derivation privacy, which is crucial to perform the change of representative in the signature scheme.

The fully-adaptive NIZK argument from [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF] is based on a challenge z = z 0 + z 1 , where z is in the CRS, and z 0 and z 1 are elements of the proof and PGen(1 λ ):

BG $ ← BGGen(1 λ ); z $ ← Zp return ((BG, [z]2), z) PPro(crs, [x1]1, w1, [x2]1, w2): // [xj]1 = Aiwj with A ∈ M 2k×k sj $ ← Z k p ; z1-i $ ← Z * p ; δ $ ← Z * p [zi]2 ← δ[z]2 -[z1-i]2 [d j i ]2 ← [zi]2wj + [sj]2 [a j i ]1 ← [Ai]sj d j 1-i $ ← Z k p [a j 1-i ]1 ← A1-id j 1-i -z1-ixj return ([a j i ]1, [d j i ]2, [zi]2, δP1) j∈{1,2} i∈{0,1} PSim(crs, z, [x1]1, [x2]1): z0 $ ← Zp; δ $ ← Z * p ; z1 ← δz -z0 for all i ∈ {0, 1}, j ∈ {1, 2} do d j i $ ← Z k p ; [a j i ]1 ← Aid j i -zixj return ([a j i ]1, [d j i ]2, [zi]2, δP1) j∈{1,2} i∈{0,1} PRVer(crs, [x]1, π): parse π = ([ai]1, [di]2, [zi]2, Z1) i∈{0,1} check e(Z1, [z]2)=e([1]1, [z0]2 + [z1]2) for all i ∈ {0, 1} check e([Ai]1, [di]2)=e([x]1, [zi]2)+e([ai]1, [1]2) PVer(crs, [x1]1, [x2]1, Ω): parse Ω = ([a j i ]1,[d j i ]2,[zi]2,Z1) j∈{1,2} i∈{0,1} check e(Z1, [z]2) = e([1]1, [z0]2 + [z1]2) for all i ∈ {0, 1}, j ∈ {1, 2} check e([Ai]1, [d j i ]2)=e([xj]1, [zi]2)+e([a j i ]1, [1]2) ZKEval(crs, [x1]1, [x2]1, Ω): parse Ω = ([a j i ]1,[d j i ]2,[zi]2,Z1) j∈{1,2} i∈{0,1} check PVer(crs, [x1]1, [x2]1, Ω) α, β $ ← Z * p ; Z ′ 1 ← αZ1 for all i ∈ {0, 1} [z ′ i ]2 ← α[zi]2; [a ′ i ]1 ← α[a 1 i ]1 + αβ[a 2 i ]1 [d ′ i ]2 ← α[d 1 i ]2 + αβ[d 2 i ]2 return ([a ′ i ]1, [d ′ i ]2, [z ′ i ]2, Z ′ 1 )
Fig. 3: Malleable NIZK argument for language L ∨ A0,A1

chosen such that the equation holds. To randomize a proof we need to randomize z 0 and z 1 and so, instead of checking the original equation we will check for linear combinations of the equation αz = z 0 + z 1 . We modify the original proof to compute a random α and add an extra element Z = αP 1 to the proof. Consequently, the verification algorithm will now check an extra pairing. As observed in [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF], the malleability of the OR-NIZK proof can be achieved by using a tag and a second NIZK for that tag with shared randomness. We follow the same approach. The resulting malleable NIZK argument for the ORlanguage (for fixed A 0 and A 1 ) is defined below and presented in Figure 3.

L ∨ A0,A1 = {[x] 1 ∈ G 2k 1 |∃ w ∈ Z k p : [x] 1 = [A 0 ] 1 • w ∨ [x] 1 = [A 1 ] 1 • w},
Theorem 2. The protocol in Figure 3 is a fully adaptive NIZK argument for the OR-language L ∨ A0,A1 if the falsifiable L 1 -(4k + 1)-extKerMDH assumption holds in G 2 .

Proof. The proof follows [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF] and is provided in [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF] (Appendix C).

Signature Construction

Our construction is shown in Figure 4, where the higlighted sections note the main differences to the scheme presented in [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF]. In [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF] (Appendix H), we also show how to extend it to obtain mercurial signatures (later explained in Section 7.1).

SPS-EQ.ParGen(1 λ ):

BG $ ← BGGen(1 λ ); A, A0, A1 $ ← D1 (crs, td) $ ← PGen(1 λ ; BG) return (BG, [A]2, [A0]1, [A1]1, crs) SPS-EQ.TParGen(1 λ ): BG $ ← BGGen(1 λ ); A, A0, A1 $ ← D1 (crs, td) $ ← PGen(1 λ ; BG) pp ← (BG, [A]2, [A0]1, [A1]1, crs) return (pp, td) SPS-EQ.KGen(pp, 1 λ ): K0 $ ← Z 2×2 p ; K $ ← Z ℓ×2 p [B]2 ← [K0]2[A]2; [C]2 ← [K]2[A]2 sk ← (K0, K); pk ← ([B]2, [C]2) return (sk, pk) SPS-EQ.Sign(pp, sk, [m]1): r1, r2 $ ← Zp [t]1 ← [A0]1r1; [w]1 ← [A0]1r2 Ω ← PPro(crs, [t]1, r1, [w]1, r2) parse Ω = (Ω1, Ω2, [z0]2, [z1]2, Z1) u1 ← K ⊤ 0 [t]1 + K ⊤ [m]1; u2 ← K ⊤ 0 [w]1 σ ← ([u1]1, [t]1, Ω1, [z0]2, [z1]2, Z1) τ ← ([u2]1, [w]1, Ω2) return (σ, τ ) SPS-EQ.Verify(pp, [m]1, (σ, τ ), pk): parse σ = ([u1]1, [t]1, Ω1, [z0]2, [z1]2, Z1) parse τ ∈ {([u2]1, [w]1, Ω2) ∪ ⊥} check PRVer(crs, [t]1, Ω1, [z0]2, [z1]2, Z1) check e([u1] ⊤ 1 , [A]2) = e([t] ⊤ 1 , [B]2) + e([m] ⊤ 1 , [C]2) if τ ̸ =⊥ check PRVer(crs, [w]1, Ω2, [z0]2, [z1]2, Z1) e([u2] ⊤ 1 , [A2]) = e([w] ⊤ 1 , [B]2) SPS-EQ.ChgRep(pp, [m]1, σ, τ, µ, pk): parse σ = ([u1]1, [t]1, Ω1, [z0]2, [z1]2, Z1) parse τ ∈ {([u2]1, [w]1, Ω2) ∪ ⊥} Ω ← (Ω1, Ω2, [z0]2, [z1]2, Z1) check PVer(crs, [t]1, [w]1, Ω) check e([u2] ⊤ 1 , [A]2) ̸ = e([w] ⊤ 1 , [B]2) check e([u1] ⊤ 1 , [A]2) ̸ = e([t] ⊤ 1 , [B]2) + e([m] ⊤ 1 , [C]2) α, β, $ ← Z * p [u ′ 1 ]1 ← µ[u1]1 + β[u2]1 [t ′ ]1 ← µ[t]1 + β[w]1 = [A0]1(µr1 + βr2) for all i ∈ {0, 1} [z ′ i ]2 ← α[zi]2 [a ′ i ]2 ← αµ[a 1 i ]2 + αβ[a 2 i ]2 [d ′ i ]1 ← αµ[d 1 i ]1 + αβ[d 2 i ]1 Ω ′ ← (([a ′ i ]1, [d ′ i ]2, [z ′ i ]2) i∈{0,1} , αZ1) σ ′ ← ([u ′ 1 ]1, [t ′ ]1, Ω ′ ) return (µ[m]1, σ ′ )
Fig. 4: Our SPS-EQ scheme.

Theorem 3. The SPS-EQ in Figure 4 perfectly adapts signatures (under malicious keys in the honest parameter model) with respect to the message space.

To prove Theorem 3 we follow almost verbatim the original proof from [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF].

Proof. For all [m] 1 and pk = ([K

0 A] 2 , [KA] 2 ), a signature σ=([u 1 ] 1 , [t] 1 , Ω 1 ,[z 0 ] 2 , [z 1 ] 2 , Z 1 ) generated according to the CRS ([A] 2 , [A 0 ] 1 , [A 1 ] 1 , [z]
2 ) satisfying the verification algorithm must be of the form:

σ=(K ⊤ 0 [A 0 ] 1 r 1 +K ⊤ [m] 1 , [A 0 ] 1 r 1 , [A 0 ]s 1 , [A 1 ]d 1 1 -z 1 [A 0 ] 1 r 1 , [z 0 ] 2 r 1 +[s 1 ] 2 , [d 1 1 ] 2 , [z 0 ] 2 , [z 1 ] 2 , Z 1 ). A sig- nature output by ChgRep has the form σ=(K ⊤ 0 [A 0 ] 1 (µr 1 + βr 2 )+K ⊤ [µm] 1 , [A 0 ] 1 (µr 1 + βr 2 ), [A 0 ]α(µs 1 + βs 2 ), [A 1 ]α(µd 1 1 + βd 2 1 ) -z 1 [A 0 ] 1 α(µr 1 + βr 2 ), α([z 0 ] 2 (µr 1 + βr 2 )+µ[s 1 ] 2 +β[s 2 ] 2 ), α(µ[d 1 1 ] 2 + β[d 2 1 ] 2 ), α[z 0 ] 2 , α[z 1 ] 2 , αZ 1 )
, for new independent randomness α, β and µ so is a random element in the space of all signatures. Furthermore, the signature output by ChgRep is distributed identically to a fresh signature on message Proof. The proof is provided in [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF] (Appendix D).

6 Extending the ABC Model from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] In this section we present a new ABC model which extends [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] to consider NAND showing proofs and the use of a CRS (denoted as pp). A NAND showing proof allows users to demonstrate that a given set of attributes is not present in their credential. The core differences in this extended ABC model follow naturally from (1) the addition of disjoint sets in the SCDS scheme in section 4, and

(2) the removal of the key verification algorithm (as we work with a CRS).

ABC Syntax. An ABC scheme consists of the following p.p.t algorithms:

Setup(1 λ , 1 q ) takes a security parameter λ and an upper bound q for the size of attribute sets, and outputs public parameters pp discarding any trapdoor. TSetup(1 λ , 1 q ) similar to Setup but it also returns a trapdoor (if any). OrgKeyGen(pp) takes pp as input and outputs an organization key pair (osk, opk). UserKeyGen(pp) takes pp as input and outputs a user key pair (usk, upk). Obtain(pp, usk, opk, X ) and Issue(pp, upk, osk, X ) are run by a user and the organization respectively, who interact during execution. Obtain takes as input pp, the user's secret key usk, an organization's public key opk, and an attribute set X of size |X | < t. Issue takes as input pp, a user public key upk, the organization's secret key osk, and an attribute set X of size |X | < t. At the end of this protocol, Obtain outputs a credential cred on X for the user or ⊥ if the execution failed. Show(pp, opk, X , S, D, cred) and Verify(pp, opk, S, D) are run by a user and a verifier respectively, who interact during execution. Show takes as input pp, an organization public key opk, a credential cred for the attribute set X , potentially non-empty sets S ⊆ X , D ⊈ X representing attributes sets being a subset (S) or disjoint (D) to the attribute set (X ) committed in the credential. Verify takes as input pp, an organization public key opk, the sets S and D. At the end, Verify outputs 1 or 0 indicating whether or not the credential showing was accepted.

Security Properties

The following notions are based on the security model from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] (Section 5.1), which we adapt to consider the use of a crs (pp) and NAND showing proofs. Informally, an ABC scheme is secure if it has the following properties:

Correctness. A showing of a credential with respect to a non-empty sets S and D of attributes always verify if the credential was issued honestly on some attribute set X with S ⊂ X and D ⊈ X .

Unforgeablility. Given at least one non-empty set S ⊂ or D ⊈ X , a user in possession of a credential for the attribute set X cannot perform a valid showing for D ⊂ X nor for S ⊈ X . Moreover, no coalition of malicious users can combine their credentials and prove possession of a set of attributes which no single member has. This holds even after seeing showings of arbitrary credentials by honest users (thus, covering replay attacks). Anonymity. During a showing, no verifier and no (malicious) organization (even if they collude) is able to identify the user or learn anything about the user, except that she owns a valid credential for the shown attributes. Furthermore, different showings of the same credential are unlinkable.

To introduce the corresponding formal definitions, the following global variables and oracles are listed below.

Global variables. At the beginning of each experiment, either the experiment computes an organization key pair (osk, opk) or the adversary outputs opk. In the anonymity game there is a bit b, which the adversary must guess.

In order to keep track of all honest and corrupt users, we introduce the sets HU, and CU, respectively. We use the lists UPK, USK, CRED, ATTR and OWNR to track user public and secret keys, issued credentials and corresponding attributes and to which user they were issued. Furthermore, we use the sets J LoR and I LoR to store which issuance indices and corresponding users have been set during the first call to the left-or-right oracle in the anonymity game. O CU (i, upk) takes as input a user identity i and (optionally) a user public key upk; if user i does not exist, a new corrupt user with public key upk is registered, while if i is honest, its secret key and all credentials are leaked. In particular, if i ∈ CU or if i ∈ I LoR (that is, i is a challenge user in the anonymity game) then the oracle returns ⊥. If i ∈ HU then the oracle removes i from HU and adds it to CU; it returns USK[i] and CRED[j] for all j with OWNR[j] = i. Otherwise (i.e., i / ∈ HU ∪ CU), it adds i to CU and sets UPK[i] ← upk. O ObtIss (i, X ) takes as input a user identity i and a set of attributes X . If i / ∈ HU, it returns ⊥. Otherwise, it issues a credential to i by running

(cred, ⊤) $ ← Obtain(pp, USK[i], opk, X ), Issue(pp, UPK[i], osk, X ).
If cred = ⊥, it returns ⊥. Else, it appends (i, cred, X ) to (OWNR, CRED, ATTR) and returns ⊤. O Obtain (i, X ) lets the adversary A, who impersonates a malicious organization, issue a credential to an honest user. It takes as input a user identity i and a set of attributes X . If i / ∈ HU, it returns ⊥. Otherwise, it runs

(cred, •) $ ← Obtain(pp, USK[i], opk, X ), •),
where the Issue part is executed by A. If cred = ⊥, it returns ⊥. Else, it appends (i, cred, X ) to (OWNR, CRED, ATTR) and returns ⊤.

Issue (i, X ) lets the adversary A, who impersonates a malicious user, obtain a credential from an honest organization. It takes as input a user identity i and a set of attributes X . If i / ∈ CU, it returns ⊥. Otherwise, it runs

(•, I) $ ← (•, Issue(pp, UPK[i], osk, X )),
where the Obtain part is executed by A. If I = ⊥, it returns ⊥. Else, it appends (i, ⊥, X ) to (OWNR, CRED, ATTR) and returns ⊤. O Show (j, S, D) lets the adversary A play a dishonest verifier during a showing by an honest user. It takes as input an index of an issuance j and attributes sets S and D. Let i

$ ← OWNR[j]. If i / ∈ HU, it returns ⊥. Otherwise, it runs (S, •) $ ← Show(pp, opk, ATTR[j], S, D, CRED[j]), •)
where the Verify part is executed by A. O LoR (j 0 , j 1 , S, D) is the challenge oracle in the anonymity game where A must distinguish (multiple) showings of two credentials CRED[j 0 ] and CRED[j 1 ]. The oracle takes two issuance indices j 0 and j 1 and attribute sets S and D. If

J LoR ̸ = ∅ and J LoR ̸ = {j 0 , j 1 }, it returns ⊥. Let i 0 $ ← OWNR[j 0 ] and i 1 $ ← OWNR[j 1 ]. If J LoR ̸ = ∅ then it sets J LoR $ ← {j 0 , j 1 } and I LoR $ ← {i 0 , i 1 }. If i 0 , i 1 ̸ = HU ∨ S ⊈ ATTR[j 0 ] ∩ ATTR[j 1 ] ∨ D ∩ {ATTR[j 0 ] ∪ ATTR[j 1 ]} ̸ = ∅, it returns ⊥. Else, it runs (S, •) $ ← (Show(opk, ATTR[j b ], S, D, CRED[j b ]), •),
(with b set by the experiment) where the Verify part is executed by A.

Correctness. An ABC system is correct, if for all λ > 0, all t > 0, all X with 0 < |X | ≤ t and all ∅ ̸ = S ⊂ X and ∅ ̸ = D ⊈ X with 0 < |D| ≤ t it holds that:

Pr        pp $ ← Setup(1 λ , 1 q ); (osk, opk) $ ← OrgKGen(pp); (usk, upk) $ ← UsrKGen(pp); (cred, ⊤) $ ← (Obtain(pp, usk, opk, X ),
Issue(pp, upk, osk, X )) :

(⊤, 1) $ ← (Show(pp, opk, X , S, D, cred), Verify(pp, opk, S, D))

       = 1.
Unforgeability. An ABC system is unforgeable, if for all λ > 0, all q > 0 and p.p.t adversaries A having oracle access to O := {O HU , O CU , O ObtIss , O Issue , O Show } the following probability is negligible.

Pr      pp $ ← Setup(1 λ , 1 q ); (osk, opk) $ ← OrgKGen(pp); (S, D, st) $ ← A O (pp, opk); (•, b * ) $ ← (A(st), Verify(pp, opk, S, D)) : b * = 1 ∧ ∀ j : OWNR[j] ∈ CU =⇒ (S / ∈ ATTR[j] ∨ D ∈ ATTR[j])     
Anonymity. An ABC system is anonymous, if for all λ > 0, all q > 0 and all p.p.t adversaries A having oracle access to

O := {O HU , O CU , O Obtain ,O Issue , O Show , O LoR } the following probability is negligible. Pr pp $ ← Setup(1 λ , 1 q ); b $ ← {0, 1}; (opk, st) $ ← A(pp); b * $ ← A O (st) : b * = b -1 7

Our ABC construction

As previously explained in Section our ABC scheme is based on the one from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF]. The main changes are the following:

-As we use a signature scheme that relies on a CRS, we move the parameters of the set-commitment scheme from the organization's key pair to the public parameters pp that include the previous CRS. Furthermore, we instantiate the ZKPoK's using Pedersen commitments and the construction from [START_REF] Damgård | Efficient concurrent zero-knowledge in the auxiliary string model[END_REF], as suggested in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] (Remark 1). -Our showing protocol can be instantiated with two sets S and D, one to compute AND proofs (selective disclosure) and one to compute NAND proofs. -We integrate the proof of exponentiation to the showing protocol 5 .

Intuition. We begin explaining the difference to [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] with respect to malicious organizations as it clarifies the changes introduced in the issuing protocol. We recall that in this context the term malicious organizations refers to organizations whose key-pairs are generated in a way that trapdoor information is included. Such trapdoor information could later be used by an organization to break anonymity, provided that extra information (a transcript of a given showing protocol containing a credential issued by the organization) is available. The ABC scheme from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] defines a ZKPoK in the issuing protocol (Π R O ) for which the organization needs to prove knowledge of the corresponding secret key to avoid the previous scenario. Since the signing keys in our SPS-EQ need to be generated using the CRS (which includes the matrix A), we do not need to request a ZKPoK from the organization in the issuing protocol as the signature's verification algorithm a pairing involving the matrix A and the organization's public key opk = (B, C) is used to check the signature. Hence, a signature that verifies rules out that 1) someone impersonated the issuer signing with a different secret key, and 2) that the public key was maliciously generated. Regarding the showing protocol, the only changes are the addition of NAND and exponentiation proofs. For the latter, we require the verifier to randomly pick the challenge and send it to the user.

For ease of exposition, we present the resulting construction (Scheme 1) in Figure 5 considering selective disclosures only. We highlight in gray the required changes to do NAND proofs, but both types of proofs could be computed while executing a single showing. If so, a NAND proof increases bandwidth by 4 elements (two from G 1 and two from G 2 ), as the PoE can reuse the same challenge.

Theorem 5. Scheme 1 is correct. Theorem 6. If the q-co-DL assumption holds, the ZKPoK's have perfect ZK, SCDS is sound, and SPS-EQ is EUF-CMA secure, then Scheme 1 is unforgeable. Theorem 7. If the DDH assumption holds, the ZKPoK's have perfect ZK, and the SPS-EQ perfectly adapts signatures, then Scheme 1 is anonymous. ← SPS-EQ.ChgRep(spspp, (C, rC, P1), σ, τ, µ, opk) PGen(1 ): We now explain how the above NIZK can be used to hide the identity of a signer. First, we need to consider a scenario in which n-authorities can issue credentials to different sets of users. As we are in the classical setting, we also assume that every user gets a credential from one of the n-authorities and that the organization keys are certified and publicly available.

$ ← Z * p ; a ← r1P1 c ← Commit(ck, a, r2) c ----→ z ← r1 + e • usk e ← ----e $ ← Z * p (C, O) ← SCDS.Commit(scdspp, X ; usk) C, R, r3 $ ← Z * p ; R ← r3C z,a,r 2 ----→ if (zP1 ̸ = a + e • upk ∨ c ̸ = Commit(ck, a, r2)) return ⊥ if (e(C, P2) ̸ = e(upk, ChX (s)P2) ∧ ∀ x ∈ X : xP1 ̸ = ek 0 1 ) return ⊥ (σ,τ ) ← ----(σ,
(C1, C2, C3) ← µ • (C, rC, P1) cred ′ ← (C1, C2, C3, σ ′ ) wit ← SCDS.OpenSS(scdspp, µC, S, ek, O ′ ) r1, r2, r3, r4 $ ← Z * p ; a1 ← r1C1; a2 ← r3P1 c1 ← Commit(ck, a1, r2) cred ′ , wit, c2 ← Commit(ck, a2, r4) c 1 ,c 2 ----→ parse cred ′ = (C1, C2, C3, σ) π ← SCDS.PoE(scdspp, S, ẽ) e,ẽ ← ----e, ẽ $ ← Z * p z1 ← r1 + e • (r • µ); z2 ← r3 + e • µ Ω = ((zi, ai, ri) i∈{1,2} , π) Ω ----→ parse Ω = ((zi, ai, ri) i∈{1,2} ,
BG $ ← BGGen(1 λ ); z $ ← Zp; td ← z return (BG, crs, [z]1) PPrv(crs, (Bi, Ci) i∈[n] , (B ′ i , C ′ i ), ρ): // B ′ i = Bi • ρ ∧ C ′ i = Ci • ρ s1, s2, z1, ..., zn-1 $ ← Zp [zn]1 ← [z]1 -j=n-1 j=1 [zj]1 [a 1 i ]2 ← s1Bi; [a 2 i ]2 ← s2Ci [d 1 i ]1 ← ρ[zi]1+[s1]1; [d 2 i ]1 ← ρ[zi]1+[s2]1 for all j ̸ = i ∈ [n] do d 1 j , d 2 j $ ← Zp [a 1 j ]2 ← d 1 j Bj-zjB ′ i ; [a 2 j ]2 ← d 2 j Cj-zjC ′ i return (([a k n ]2, [d k n ]1) k∈[2] n∈[n] , ([zj]1) j∈[n-1] ) PSim(crs, td, (Bi, Ci) i∈[n] , (B ′ i , C ′ i )): z1, ..., zn-1 $ ← Zp [zn]1 ← [td]1 -j=n-1 j=1 [zj]1 for all i ∈ [n] do d 1 i , d 2 i $ ← Zp [a 1 i ]2 ← d 1 i Bi-ziB ′ i ; [a 2 i ]2 ← d 2 i Ci-ziC ′ i return (([a k n ]2, [d k n ]1) k∈[2] n∈[n] , ([zj]1) j∈[n-1] ) PVer(crs, (Bi, Ci) i∈[n] , (B ′ i , C ′ i ), π): parse π=(([a k n ]2, [d k n ]1) k∈[2] n∈[n] , ([zj]1) j∈[n-1] ) [zn]1 = [z]1 -j=n-1 j=1 [zj]1 for all i ∈ [n] check e([d 1 i ]1, Bi)=e([zi]1, B ′ i )+e([1]1, [a 1 i ]2) e([d 2 i ]1, Ci)=e([zi]1, C ′ i )+e([1]1, [a 2 i ]2)
When showing a credential, the verifier needs to check the signature using the corresponding public key. The idea is to use the above NIZK proof so that a user can randomize the public key and present this randomized key to the verifier, which in turn will check the NIZK to verify that the public key is valid (i.e., it belongs to the equivalence class of one of the n-authorities).

Signatures need to be adapted by the users so that they can be verified with the randomized public key. Therefore, we consider the definition of mercurial signatures [START_REF] Crites | Delegatable Anonymous Credentials from Mercurial Signatures[END_REF], which includes algorithms ConvertPK, ConvertSK and ConvertSig, and introduce the following notion.

Perfect adaption of signatures (under malicious keys in the honest parameters model) with respect to the key space; An SPS-EQ over a message space S m perfectly adapts signatures with respect to the key space S pk if for all tuples (pp,[pk] j ,[m] i ,(σ, τ ),ρ) where pp

$ ← ParGen(1 λ ), [pk] j ∈ S pk , [m] i ∈ S m , Verify([m] i , (σ, τ ), [pk] j ) = 1 and ρ ∈ Z * p , we have that the output of ConvertSig([m] i , (σ, τ ), ρ, [pk] j ) is σ * , with σ * being a random element in the space of signatures, conditioned on Verify([m] i , σ * , ConvertPK([pk] j , ρ)) = 1.
ConvertSig is analogous to the ChgRep algorithm, but restricted to act on the equivalence class defined by the key space. The algorithms ConvertPK and ConvertSK are just defined to abstract the computation of new representatives.

As our signature construction is compatible with the joint executions of the algorithms ChgRep and ConvertSig, we define below a general notion for perfect adaption where the ChgRep algorithm acts on all the equivalence classes.

Perfect adaption of signatures (under malicious keys in honest parameters model); An SPS-EQ over S m perfectly adapts signatures with respect to the key space S pk if for all tuples (pp, [pk] j , [m] i , (σ, τ ), µ, ρ) where pp

$ ← ParGen(1 λ ), [pk] j ∈ S pk , [m] i ∈ S m , Verify([m] i , (σ, τ ), [pk] j ) = 1 and µ, ρ ∈ Z * p we have that the output of ChgRep([m] i , (σ, τ ), µ, ρ, [pk] j ) is ([µ • m] i , σ * )
, with σ * being a random element in the space of signatures, conditioned on Verify(

[µ • m] i , σ * , ConvertPK([pk] j , ρ)) = 1.
Theorem 9. The above extension applied to the SPS-EQ from Figure 4 perfectly adapts signatures (under malicious keys in the honest parameter model).

Proof. It follows from the security of SPS-EQ and the definition of perfect adaption for mercurial signatures (Appendix D and H from [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF]).

We now formalize the signer-hiding notion and show that our construction satisfies it as it perfectly adapts signatures.

Signer-Hiding. An ABC system supports signer-hiding if for all λ > 0, all q > 0, all n > 0, all t > 0, all X with 0 < |X | ≤ t, all ∅ ̸ = S ⊂ X and ∅ ̸ = D ⊈ X with 0 < |D| ≤ t, and p.p.t adversaries A, the following holds.

Pr        pp $ ← Setup(1 λ , 1 q ); ∀ i ∈ [n] : (osk i , opk i ) $ ← OrgKGen(pp); (usk, upk) $ ← UsrKGen(pp); j $ ← [n]; (cred, ⊤) $ ← (Obtain(usk, opk j , X ), Issue(upk, osk j , X )); j * $ ← A O Show (pp, S, D, (opk i ) i∈[n] ) : j * = j        ≤ 1 n
where the oracle O Show is defined as in Section 6.

Theorem 10. If the underlying signature scheme is a SPS-EQ which perfectly adapts signatures (under malicious keys in the honest parameter model), the resulting ABC from Section 7.

[µ • m] i , σ * ) ← ChgRep([m] i , (σ, τ ), µ, ρ, [opk] j ) and [ρ • opk] j ← ConvertPK(opk j , ρ). Furthermore, we also have that σ * is a random element in the space of signatures conditioned on Verify([µ • m] i , σ * , [ρ • opk] j ) = 1.
Therefore, an adversary with access to [µ • m] i , σ * and [ρ • opk] j can only guess the bit j * with probability at most 1/n. □ Integration with our ABC scheme. As our NIZK argument is fully adaptive, users can choose the size of the anonymity set (i.e., the set of public keys in the OR-Proof). We find this approach much simpler than using delegatable credentials to achieve a similar result as users do not need to interact with the organizations to compute the NIZK proof nor to adapt the signature. Moreover, there is no need to use pseudonyms for public and secret keys. We essentially compute public key's pseudonyms "on-the-fly" guaranteeing that the signature adaption done with respect to a valid public key. In other words, our NIZK argument is a proof of correct randomization, where the same randomizer is used to adapt the signature and generate a pseudonymous public key. A complete figure for the proposed ABC, including the signer-hiding extension as well as NAND proofs, is given in [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF] (Appendix I).

Efficiency analysis. As the proof size is 9n -1 for an anonymity set of nauthorities, communication bandwidth will no longer be constant. Nevertheless, given the previously mentioned advantages we believe that this is a fair trade-off for the added functionality. In terms of computational cost, it is also substantially more efficient than similar variants (see, for instance, Table 2 from [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF]).

Comparison of state-of-the-art ABC

We provide comparisons on the efficiency of state-of-the-art ABC and ours (Section 7) on Table 3. For ease of exposition, we list the work from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] next to ours, and consider an instantiation of it in the CRS model, and using the same ZKPoK's as the ones used in Section 7.

When looking at a whole, the work from Sanders [START_REF] Sanders | Efficient Redactable Signature and Application to Anonymous Credentials[END_REF] presents very good results while also allowing showings to prove relationships between attributes and to consider malicious keys. Nevertheless, security of the related construction is proven in the GGM model and thus, falls short in that aspect. The same also applies to the works from [START_REF] Hébant | Traceable Constant-Size Multi-Authority Credentials[END_REF] and [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF].

While for the comparisons only the classical setting (credentials are issued by a single authority) was considered, it is worth to mention that [START_REF] Hébant | Traceable Constant-Size Multi-Authority Credentials[END_REF] does consider multi-authorities. As authors point out, in order to allow multi-authorities they base their construction on aggregate signatures, and obtain the most efficient showing for the users. Their security model follows the game-based approach from [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] but because of the multi-authority setting, they also consider malicious credential issuers, with adaptive corruptions, and collusions with malicious users. Unfortunately, this is done assuming that the keys are honestly generated.

[50] uses a set-commitment scheme which alongside an SDH-based signature, leads to a credential system that supports a variety of show proofs for complex statements among which AND and NAND are included. For this reason, we also compare our work with the one from [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF] considering NAND showings. In terms of security models, authors provide a formalization for impersonation attacks and prove their scheme secure against impersonation under active and concurrent attacks. The security of their ABC scheme is proven in the standard model and providing a tight reduction.

Considering the different trade-offs, our ABC provides very similar performance when compared to [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] and it is not too distant from the most efficient ones either. Unlike the rest, it can be adapted to different scenarios in case that reducing the verification cost is not needed, and it can also be efficiently adapted to provide revocation features. Furthermore, as for many practical applications the ability to perform AND and NAND showings suffices, we also achieve a good level of expressiveness too. Finally, the signer-hiding feature makes it suitable for scenarios in which the rest of the alternatives struggle.

(n + 1) G 2 Cred 2 G 2 4 G 1 1 G 1 + 6 Zp 3 G 1 +1 G 2 + 2 Zp 18 G 1 +6 G 2 +3 Zp Bandwidth Issue 4 G 2 + 2 Zp n G 1 3 G 1 +(n+3) Zp 12 G 1 +1 G 2 +8 Zp 14 G 1 +11 G 2 +7 Zp Show 2 G 1 +2 G 2 +1 G T +2 Zp 3 G 1 +1 Zp 3 G 1 +5 Zp 10 G 1 +1 G 2 +8 Zp 18 G 1 +14 G 2 +4 Zp k-of-n attributes (AND) Usr (2(n-k)+2) G 1 ,2 G 2 , 6 G 1 (6+n-k) G 1 (11+n-k) G 1 ,1 G 2 , (20+n-k) G 1 , 1 8 (k

Conclusions and Future Work

Our results explore multiple paths to extend the ABC framework of [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] to include more applications and scenarios where it can be used. In order to improve expressiveness of the set-commitment scheme in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] we allow openings on sets of attributes disjoint from those possessed by a user. We also enhance efficiency by employing the trick of allowing the prover to compute a proof of exponentiation leaving the verifier only to compute a polynomial division. Our signature scheme is based on [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] where we adapt the SPS-EQ scheme by alleviating the need to build a QA-NIZK incorporating results from the recent framework of [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF]. With this fully adaptive NIZK, we find further interesting applications by looking at equivalence classes on the key-space. We develop a signer-hiding notion to allow a credential-bearing user to hide their issuing organization upon presentation of the credential. As we increasingly see cases of (algorithmic) bias against users, notions such as this are of growing importance. Moreover, we also present interesting directions to integrate revocation features.

We worked in the classical setting where each credential is issued by a single authority. It would be interesting to follow the related work on aggregatable signatures to see if we could lift SPS-EQ to the multi-authority setting.

While our set-commitment scheme is more expressive than [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] it is still less expressive than [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF]. Hence, it would be interesting to see if the set-commitment scheme introduced there would yield greater expressiveness to the ABC scheme from this work. Likewise, to verify if the stronger security notions presented here, could enhance the construction in [START_REF] Tan | MoniPoly -An Expressive q-SDH-Based Anonymous Attribute-Based Credential System[END_REF].

( 2 )

 2 Instead of evaluating the polynomial at certain points, what is important to prove possession of an attribute is to open factors of the polynomial instead. (3) If one can open multiple factors in constant-size, a showing involving a selective disclosure of attributes can be done in constant-size as well.

D

  k -extKerMDHAssumption. Let D k be a matrix distribution, l, k ∈ N, and s ∈ {1, 2}. We say that the D k -extKerMDH assumption holds in G s relative to BGGen, if for every BG $ ← BGGen(1 λ ), D $ ← D k , and all p.p.t. adversaries A the following probability is negligible.

1 Fig. 2 :

 12 Fig. 2: Our SCDS construction

$←

  ParGen(1 λ ), [m] i ∈ S m , µ ∈ Z * p , and Verify([m] i , σ, pk) = 1, we have that the output of ChgRep([m] i , (σ, τ ), µ, pk) is ([µ • m] i , σ * ), with σ * being a uniformly random element in the space of signatures, conditioned on Verify([µ • m] i , σ * , pk) = 1.

Theorem 4 .

 4 [m] 1 output by Sign. □ If the KerMDH and MDDH assumptions hold, the SPS-EQ in Figure 4 is unforgeable.

Oracles.$←

  Considering an adversary A the oracles are as follows: O HU (i) takes as input a user identity i. If i ∈ HU ∪ CU, it returns ⊥. Otherwise, it creates a new honest user i by running (USK[i], UPK[i]) UsrKGen(opk), adding i to the honest user list HU and returning UPK[i].

  τ ) ← SPS-EQ.Sign((C, R, P1), osk) check SPS-EQ.Verify(spspp, (C, R, P1), (σ, τ ), opk) return cred = (C, (σ, τ ), r3, O) ABC.Show(pp, usk, opk, ek, S, cred) ABC.Verify(pp, opk, S) parse cred = (C, σ, r, O); µ $ ← Z * p if O = (1, (o1, o2)) then O ′ = (1, (µ • o1, o2)) else O ′ = µO σ ′ $

Fig. 5 :

 5 Fig. 5: Scheme 1.

Fig. 6 :

 6 Fig. 6: Fully adaptive NIZK argument for L ∨ (Bi∧Ci) i∈[n]

Table 1 :

 1 Signatures comparison including pairings and exponentiations.

	Scheme	|σ|	|pk|	Sign Verify ChgRep	Assumptions
	[41]	8|G1| + 9|G2| (2 + ℓ)|G2| 29E 11P 19P+38E	SXDH
	Section 5 9|G1| + 4|G2| (2 + ℓ)|G2| 10E 11P 19P+21E extKerMDH, SXDH

  OpenDS(pp, C, X , O, D) is a deterministic algorithm which takes as input pp, a commitment C, a set X , opening information O, and a non-empty set D. If D is disjoint from X committed to in C, OpenDS outputs a witness wit that attests to it. Otherwise, outputs ⊥. VerifySS(pp, C, S, wit) is a deterministic algorithm which takes as input pp, a commitment C, a non-empty set S, and a witness wit. If wit is a valid witness for S a subset of the set committed to in C, it outputs 1 and otherwise ⊥.

outputs a commitment C on set X and opening information O. Open(pp, C, X , O) is a deterministic algorithm which takes as input pp, a commitment C, a set X , and opening information O. It outputs 1 if and only if O is a valid opening of C on X . OpenSS(pp, C, X , O, S) is a deterministic algorithm which takes as input pp, a commitment C, a set X , opening information O, and a non-empty set S. If S is a subset of X committed to in C, OpenSS outputs a witness wit that attests to it. Otherwise, outputs ⊥.

  ABC.Setup(1 λ , 1 q ): ck td ← r; return ((BG, scdspp, spspp, ck), (scds td , sps td , ck td ))

	(BG, scdspp)	← SCDS.Setup(1 λ , q); (spspp)	$ ← SPS-EQ.ParGen(1 λ ; BG);
	r	$ ← Z * p ; ck ← (P1, rP1); return (BG, scdspp, spspp, ck)
	ABC.TSetup(1 λ , 1 q ):
	(BG, scdspp, scds td )	$ ← SCDS.TSetup(1 λ , q); (spspp, sps td )	$ ← SPS-EQ.TParGen(1 λ ; BG);
	r p ; ck ← (P1, rP1); ABC.OrgKGen(pp): $ ← Z *	ABC.UsrKGen(pp):
	return SPS-EQ.KGen(BG, spspp, 3)	usk	$ ← Z * p ; upk ← uskP1
				return (usk, upk)
	ABC.Obtain(pp, usk, opk, X )	ABC.Issue(pp, upk, osk, X )
	r1, r2

  -1) G 2 ,19 Ver (k+1) G 1 ,1 G T ,5 4 G 1 ,2n G 2 ,3 5 G 1 ,(k+1) G 2 ,3 4 G 1 ,(k+1) G 2 ,10 10 G 1 ,16 k-of-n attributes (NAND)

	Usr N/A	N/A	(6+n) G 1	N/A	(31+n) G 1 ,
					(9+2k) G 2 ,19
	Ver N/A	N/A	(2k+5) G 1 ,	N/A	10 G 1 ,17
			(k+3) G 2 ,3

Table 3 :

 3 Efficiency of ABCs considering issuing and showing interactions (the number of pairings is marked in bold).

The security of this integration is discussed in[START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF] (Appendix J).

Acknowledgements. We thank the anonymous reviewers for their valuable feedback. The Commission partially supported Octavio Perez Kempner's work as part of the CUREX project (H2020-SC1-FA-DTS-2018-1 under grant agreement No 826404).

Proof of Theorem 6 follows closely to that presented in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] but extended to include disjoint sets. Proof of Theorem 7 also follows that in [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF] with the exception that we work with a CRS and an accordingly modified definition of perfect adaption. All proofs are provided in [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF] (Appendix E).

Revocation strategies

The natural approach to revocation would be to follow that described in [START_REF] Derler | A New Approach to Efficient Revocable Attribute-Based Anonymous Credentials[END_REF] where they use the fact that randomization of a credential is compatible with the randomization of the accumulator and its corresponding witness. This approach requires the revocation authority to compute and maintain the witness list. As it uses the accumulator from [START_REF] Au | Dynamic universal accumulators for ddh groups and their application to attribute-based anonymous credential systems[END_REF], the cost of non-membership proofs is linear in the size of the accumulator (i.e., revoked users), and this should be done at least once by the manager for every user. If, instead, the dynamic variant is used (as discussed in [START_REF] Derler | A New Approach to Efficient Revocable Attribute-Based Anonymous Credentials[END_REF]), then users could be given their non-membership witness once and subsequently update it with a single constant size operation. Other approaches for revocation are discussed in [START_REF] Connolly | Improved constructions of anonymous credentials from structure-preserving signatures on equivalence classes[END_REF] (Appendix F).

Signer-Hiding

We recall that our signature scheme is based on the one from [START_REF] Khalili | Structure-Preserving Signatures on Equivalence Classes from Standard Assumptions[END_REF] and that we are using the credential framework of [START_REF] Fuchsbauer | Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials[END_REF]. Therefore, as we have k = 1 and ℓ = 3, the public keys consist of two vectors

, we can efficiently prove that a given public key (B ′ i , C ′ i ) belongs to the equivalence class of one of the public keys (B 1 , C 1 ), ..., (B n , C n ) for some (B i , C i ). The idea is to use a generalized version of the OR-Proof from [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF], and building a generalized NIZK OR-Proof for the AND statements of the two components. The new language is defined as follows (remember we use ℓ = 3):

The resulting NIZK argument is given in Figure 6.

Theorem 8. The proof system given in Figure 6 is a fully-adaptive NIZK argument for the language L (Bi∧Ci) i∈ [n] .

Proof. The proof follows from Theorem 19 in [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF]. The only difference is that we rely on the AND composition for sigma protocols to compile the one in [START_REF] Couteau | Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages[END_REF] using the same challenge for both proofs.