Geoffroy Couteau
email: geoffroy.couteau@kit.edum.reichle95@outlook.com

Michael Reichle

Non-Interactive Keyed-Verification Anonymous Credentials

Keywords: Anonymous credentials, keyed-verification anonymous credentials, non-interactive anonymous credentials

Anonymous credential (AC) schemes are protocols which allow for authentication of authorized users without compromising their privacy. Of particular interest are noninteractive anonymous credential (NIAC) schemes, where the authentication process only requires the user to send a single message that still conceals its identity. Unfortunately, all known NIAC schemes in the standard model require pairing based cryptography, which limits them to a restricted set of specific assumptions and requires expensive pairing computations. The notion of keyed-verification anonymous credential (KVAC) was introduced in (Chase et al., CCS'14) as an alternative to standard anonymous credential schemes allowing for more efficient instantiations; yet, making existing KVAC non-interactive either requires pairing-based cryptography, or the Fiat-Shamir heuristic. In this work, we construct the first non-interactive keyed-verification anonymous credential (NIKVAC) system in the standard model, without pairings. Our scheme is efficient, attribute-based, supports multi-show unlinkability, and anonymity revocation. We achieve this by building upon a combination of algebraic MAC with the recent designated-verifier non-interactive zero-knowledge (DVNIZK) proof of knowledge of (Couteau and Chaidos, Eurocrypt'18). Toward our goal of building NIKVAC, we revisit the security analysis of a MAC scheme introduced in (Chase et al., CCS'14), strengthening its guarantees, and we introduce the notion of oblivious non-interactive zero-knowledge proof system, where the prover can generate non-interactive proofs for statements that he cannot check by himself, having only a part of the corresponding witness, and where the proof can be checked efficiently given the missing part of the witness. We provide an efficient construction of an oblivious DVNIZK, building upon the specific properties of the DVNIZK proof system of (Couteau and Chaidos, Eurocrypt'18).

Introduction

Anonymous Credentials

Anonymous credentials, introduced in the seminal work of Chaum [START_REF] Chaum | Showing credentials without identification: Signatures transferred between unconditionally unlinkable pseudonyms[END_REF], allow users to authenticate in an anonymous way to a variety of services. Each user can receive credentials from authorities, and register pseudonyms with authorities and verifiers. These pseudonyms are associated to the identity of the user, but should be unlinkable to its exact identity. That is, another entity should not be able to check whether two pseudonyms are associated with the same identity. Authorities can issue credentials to users which can be shown to verifiers, and the presentation of a credential should only leak the information that the user knows the identity associated to the pseudonym, and owns a credential from the authority for this identity. This guarantees the anonymity of users. In order for credentials to make sense, they must be unforgeable: a user should not be able to present a credential without having received one from the authority first. Due to their wide range of real-world applications, anonymous credentials have received a constant attention from the cryptographic community [START_REF] Acar | Revocation for delegatable anonymous credentials[END_REF][START_REF] Barki | Improved algebraic MACs and practical keyedverification anonymous credentials[END_REF][START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF][START_REF] Camenisch | An accumulator based on bilinear maps and efficient revocation for anonymous credentials[END_REF][START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF][START_REF] Camenisch | Dynamic accumulators and application to efficient revocation of anonymous credentials[END_REF][START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF][START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF][START_REF] Damgård | Payment systems and credential mechanisms with provable security against abuse by individuals[END_REF][START_REF] Garman | Decentralized anonymous credentials[END_REF][START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF][START_REF] Izabachène | Block-wise P-signatures and non-interactive anonymous credentials with efficient attributes[END_REF][START_REF] Lysyanskaya | Pseudonym systems[END_REF][START_REF] Sadiah | Anonymous credential system with efficient proofs for monotone formulas on attributes[END_REF]. credentials is considered to be a highly desirable security property, and was the focus on an important research effort [START_REF] Belenkiy | Randomizable proofs and delegatable anonymous credentials[END_REF][START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF][START_REF] Izabachène | Block-wise P-signatures and non-interactive anonymous credentials with efficient attributes[END_REF]. However, a downside of existing NIAC scheme is that all known constructions in the standard model require the use of pairing based cryptography, which limits their efficiency (since pairing are a relatively expensive cryptographic operation) and restricts the set of assumptions their security can be based on. While some interactive anonymous credential schemes can be made non-interactive in the random oracle model under the Fiat-Shamir transform, this is known to provide only heuristic security arguments in the standard model [START_REF] Canetti | The random oracle methodology, revisited (preliminary version)[END_REF][START_REF] Dwork | Magic functions[END_REF][START_REF] Goldwasser | On the (in)security of the Fiat-Shamir paradigm[END_REF]. Keyed-Verification Anonymous Credential. Most commonly, anonymous credential schemes allow for a single credential to be shown more than once to multiple verifiers. The notion of keyed-verification anonymous credentials (KVAC) was introduced in [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF]; it restricts credential to only be valid with respect to one verifier and requires the authority and verifier to share a secret key.

The key observation of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] is that such restricted anonymous credentials can be instantiated very efficiently, using algebraic message authentication codes. Therefore, in numerous applications where the restriction to keyed-verification is not an issue, they can be used to allow for more efficient instantiations. Think for example of a bus company issuing monthly pass, where the pass must be shown each time a user boards a bus; here, it is reasonable to assume that the bus device can share a secret-key with the bus company (since both belong to the same organisation).

A downside of the KVAC scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], however, is that the process of showing possession of a credential requires an interactive protocol between the user and the verifier. This protocol can be made non-interactive, but this either requires the Fiat-Shamir transform (leading to a protocol secure in the random oracle model only), or the use of pairing-based cryptography, nullifying the efficiency advantages of KVAC with respect to their publicly verifiable counterpart.

Our Contribution

In this work, we construct the first non-interactive keyed-verification anonymous credential scheme (NIKVAC) in the standard model, without relying on pairing-based cryptography. Our NIKVAC is very expressive: it natively supports multi-show unlinkability (i.e., when showing possession of a credential multiple time to a verifier, the latter cannot tell whether these correspond to the same user) or pseudonyms (the verifier knows a pseudonym that he can link a credential to, but that he cannot link to the actual identity of the user), without any additional cost (i.e., we do not require to generate an additional commitment to the identity and prove knowledge of its content to obtain pseudonyms, as in most alternative approaches; rather, such commitments are natively and implicitly defined by our scheme). Our NIKVAC is also attribute-based (it supports vectors of attributes as opposed to identities, and can handle a variety of relations on the attributes), and supports anonymity revocation (there exists a global trapdoor which a trusted authority can use to revoke the anonymity of a misbehaving user, efficiently extracting his identity from any accepting credential).

While our scheme is the first NIKVAC in the standard model without pairings, we observe (this is in fact the starting point of our work) that there is a relatively natural construction of a NIKVAC which is obtained by starting with the (interactive) scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], and replacing the underlying zero-knowledge proof system by the designated-verifier non-interactive zero-knowledge proof system of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. While this observation is interesting in itself, the security analysis of the resulting construction does not present major technical difficulties (although it is not entirely straightforward). In this work, we refine this approach, adopting a different strategy to better exploit the structural properties of the proof system of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. Our optimized approach provides strong efficiency improvements (which we detail in Section 1.6) over the previous alternative.

Our Approach

Our starting point is the interactive KVAC scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF]. In this scheme, a credential is an algebraic MAC signature on the identity of the user. Anonymous presentation of a credential is done (informally) by masking the credential, and providing some zero-knowledge proofs of knowledge of the identity together with the masking informations satisfying the appropriate relation, which allows the verifier (who knows the secret MAC key) to check that the masked credential does indeed verify correctly with respect to the (hidden) identity of the user.

To make this scheme non-interactive, the basic observation is that it suffices to rely on a designated-verifier non-interactive zero-knowledge (DVNIZK) proof of knowledge of the appropriate values. Unlike their publicly-verifiable counterpart, there exists efficient constructions of DVNIZK proof systems which does not rely on pairings. However, until recently, all known constructions of DVNIZK proof systems [START_REF] Chaidos | Making sigma-protocols non-interactive without random oracles[END_REF][START_REF] Cramer | Bounded CCA2-secure encryption[END_REF][START_REF] Damgård | Non-interactive zero-knowledge from homomorphic encryption[END_REF] suffered from two important downside, each of them preventing their use in a NIKVAC scheme:

they can only deal with existential statements, while anonymous credentials crucially rely on proving knowledge of the signed identity, and they only satisfy a bounded notion of security, where the soundness of the proof is only guaranteed to hold if the prover is restricted to query a verification oracle an a priori bounded number of times. In an anonymous credential system, however, the users can interact freely with a verifier and receive feedback on whether proofs of credential possession was accepted or not; hence, for all of these scheme, a malicious user could forge a credential which is accepted by the verifier even though it was not issued by the authority, by interacting a sufficient (polynomial) number of times with the verifier.

This situation recently changed with the introduction in [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] of the first DVNIZK proof system which allows to provide proofs of knowledge of a witness, for a wide variety of algebraic statements, where soundness is unbounded (it holds even if the prover is given arbitrary access to a verification oracle). Furthermore, the framework of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] allows for efficient DVNIZK proofs, directly proportional to the size of the algebraic statement to be proven. A natural approach toward building a NIKVAC scheme is therefore to rely on the KVAC scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], and to replace the underlying zero-knowledge proofs by appropriate DVNIZK, using the framework of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. However, while this approach should lead to a secure NIKVAC, it misses the opportunity to exploit the specific structure of the scheme of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] to get improved efficiency guarantees. Therefore, we choose instead to tackle the problem directly and construct an optimized NIKVAC system, heavily building upon the specific structure of the DVNIZK of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF].

Our Techniques

To describe our strategy, it is helpful to start from a natural but insecure approach. As in [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], a credential will simply be a signature on the identity of the user using an algebraic MAC. To show possession of a credential, the user can simply send this credential (but not his identity) and prove with a DVNIZK that he knows an identity such that the MAC verification algorithm returns 1 when given as input this identity and the credential. A first observation is that this approach allows for a straightforward optimization: in the most common setting, the verifier must know a pseudonym associated to the user (which cannot be linked to his identity), which will usually take the form of a commitment to the identity of the user. We observe, however, that a DVNIZK proof of knowledge within the framework of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] does already include an encryption of the witness, and the proof of knowledge property does in particular guarantee that the witness whose knowledge is proven is indeed the one encrypted in the proof. Therefore, it is not necessary to add a commitment to the identity and prove that the committed value is the one for which the user knows a credential; rather, the user can simply compute this encryption ahead of time (this does not require knowing the credential) and send it to the verifier, which will store it as being the user pseudonym. Then, each time the user wants to authenticate, he only have to generate the "missing part" of the proof with respect to this encryption. This strongly reduces the size of the proof (since the proof does not need to include an explicit proof regarding a commitment anymore), and allows to reuse a significant portion of the proof across many authentications.

However, the natural approach of disclosing a credential σ and proving knowledge of an identity that verifies correctly with respect to σ fails, for two reasons:

-First, the above approach does not guarantee anonymity, because the verifier (who knows the secret MAC key) could find out the identity of the user simply by colluding with the authority, and evaluating the MAC verification algorithms on all identities previously submitted to the authority, to find out which one verifies correctly with respect to this credential.

-Second, and more importantly, the MAC verification requires knowledge of the secret MAC key, which the user does not know; hence, he cannot possibly issue a proof that his credential verifies correctly, since checking this statement does already require knowing the secret MAC key.

We first explain how we address the second concern. Our idea is to build upon the specific malleability property of the DVNIZK proof system of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] to build an oblivious DVNIZK proof system, which allows the prover to issue a proof for a statement even if he does not know himself whether the statement does hold. This does not contradict the security of the MAC scheme, since the proof system is not publicly verifiable: hence, even after he builds the proof, the prover cannot check by himself whether this proof verifies correctly. Intuitively, the prover will construct a "partial non-interactive proof" which is malleable in the following sense: given this proof and the secret MAC key, the verifier can reconstruct himself the complete proof that the credential verifies correctly. If the prover does not know the appropriate witness, the reconstructed proof will not verify correctly. The partial proof should not leak any more information about the witness held by the prover than what is leaked by the reconstructed proof; hence, by the zero-knowledge property of the DVNIZK proof system, this proof will only reveal whether the statement (which depends on both the prover witness and the secret key known to the verifier) is true. We believe that the concept of non-interactive oblivious proofs, which allows to prove that a statement is true while knowing only a part of the witness to a verifier knowing the "missing part" of the witness, might be of independent interest (we briefly elaborate on this in Section 1.5); in particular, it formalizes the approach taken (in the interactive setting) in previous works on keyed-verification anonymous credentials [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF].

To tackle the first concern, the prover will randomize his credential and mask it with appropriate random values, and issue a partial proof that the unmasked credential does verify with respect to the secret key. We formalize both properties at once by introducing a new primitive, oblivious designated-verifier non-interactive zero-knowledge proofs of knowledge, which can be used to prove statements non-interactively even when the prover only knows a part of the witness, and can be simulated by a simulator that does not know neither the witness nor the word for which the proof is constructed, guaranteeing that the verifier will not only be unable to recover the witness, but also that he cannot possibly recover the credential, which would allow him to break anonymity by colluding with the authority.

Next, we provide an optimized construction of an oblivious DVNIZK proof system for the language of valid credentials, building upon the DVNIZK proof system of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. Proving security of the resulting proof system, however, runs into a subtle issue: when considering the more general setting of attribute-based anonymous credentials, where the user will have a secret vector of attributes instead of a secret identity, the unforgeability property of the underlying MAC scheme does not suffice to prove the soundness of the oblivious proof system. We provide two alternatives to overcome this issue:

-When the vector of attributes is of length one (i.e., when we restrict our attention to nonattribute-based anonymous credentials, where the secret of the user is only his identity), we show that the public parameters of the MAC scheme suffice to reduce the security directly to the unforgeability of the MAC scheme. This setting already captures many possible applications. -In the general setting, where the vector of attributes can be longer than 1, we show that the security can be proven if the MAC scheme satisfies a stronger notion of unforgeability, which we call extended unforgeability. Then, we revisit the security analysis of one of the two MAC schemes constructed in [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], which is secure in the generic group model, and prove that this scheme does in fact already satisfy extended unforgeability. While the second MAC scheme constructed in [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] (which is based on the decisional Diffie-Hellman assumption) does plausibly satisfy extended unforgeability, we leave it as an interesting open problem to prove it under a standard assumption, or to construct a MAC scheme with extended unforgeability under the DDH assumption. We note that considering algebraic MACs with stronger unforgeability guarantees is a relatively natural approach in the setting of anonymous credentials (see e.g. [START_REF] Belenkiy | Randomizable proofs and delegatable anonymous credentials[END_REF][START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF]), but the specific strengthening we require in our construction was not, to our knowledge, considered in previous works.

There is an additional requirement which we must take care of: the MAC schemes of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] are only proven secure in groups of prime order, while the most natural instantiation of the DVNIZK proof system of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] typically requires composite-order groups. While the security of their DDH-based MAC easily extends to the composite order setting by assuming in addition that it is infeasible for any polytime adversary to find a generator of a strict subgroup (which is a standard and well-studied assumption), the proof of their generic-group-model-based (GGM-based) MAC is unconditional, hence it assumes that the adversary is unbounded, in which case there is an explicit attack on the composite-order variant of the scheme where the unbounded adversary constructs an invalid MAC signature in a strict subgroup of the group. We therefore revisit the security proof of the GGM-based MAC, and show that it holds in the generic group model assuming in addition that the adversary is polynomially bounded, and that the computational subgroup assumption holds. Altogether, we show that this gives rise to a highly optimized NIKVAC. In the next section, we discuss in more details the efficiency of our scheme.

Applications of Oblivious DVNIZK

Given the intermediate abstraction of oblivious designated non-interactive zero-knowledge proofs, the construction of NIKVAC follows very naturally. In fact, we could have provided a direct construction of NIKVAC from this approach, without formalizing the intermediate primitive. However, we believe that oblivious DVNIZKs can be interesting in their own right. We elaborate below.

Secure computation protocols allow a group of parties to securely evaluate a public function on their joint private input. We focus in this discussion on the case of two parties for simplicity. A common approach to secure two-party computation is to first design a scheme secure against passive adversaries, which do not deviate from the specifications of the protocol, and then to use zero-knowledge proofs to let all adversaries prove their honest behavior throughout the protocol. This transformation makes the protocol secure against malicious adversaries, which can deviate arbitrarily from the specifications of the protocol. To obtain round-efficient compilation of passively secure computation protocols into maliciously secure protocols, the most natural strategy is to rely on (designated-verifier) non-interactive zero-knowledge proofs (an alternative is to use implicit zero-knowledge proofs [START_REF] Benhamouda | Implicit zero-knowledge arguments and applications to the malicious setting[END_REF], but this adds two more rounds to the protocol) to prove honest behavior of each user after each round.

Oblivious DVNIZK allow for an alternative compilation strategy, which starts from a protocol with stronger security guarantees, but is in general more efficient. Let us call (informally) halfmaliciously secure a secure computation protocol which is passively secure, and such that no malicious adversary can compromise the privacy of the inputs (but can possibly compromise the correctness of the computation). Let Π be a half-maliciously secure protocol, securely computing a function f . Let (x 1 , x 2 ) denote the inputs of the parties. To convert Π into a fully secure protocol, we first modify Π to include commitments (c 1 , c 2 ) to the inputs (if Π does not already include them). Then, to guarantee full security, one of the parties, which we call the prover, must send a single oblivious DVNIZK to the other party (the receiver) at the very end of the protocol, which is a proof that y = f (x 1 , x 2 ), where y is the output of the protocol, and (x 1 , x 2 ) is committed in (c 1 , c 2 ). Note that the prover does not have the full witness for this statement (since it depends, in particular, on the private input of the verifier), but the prover and the verifier jointly have the full witness, allowing the verifier to check the proof without further interaction. This is in contrast with DVNIZK-based compilation, which requires proving honest behavior of all users at each round (here, we only prove correctness of the computation in the last round). We leave the formal proof of this observation to future work.

Efficiency

There is, to our knowledge, no existing previous construction of NIKVAC in the standard model. However, as we pointed out previously, there is a relatively natural construction which is obtained by starting from the scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], and replacing the underlying zero-knowledge proofs by DVNIZKs instantiated with [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. Let us call this construction the CMZ+CC construction. We use CMZ+CC as a basis for comparison with our improved construction. We focus on the communication cost of showing possession of a credential, since the computation is directly proportional to the communication (hence, an improvement factor with respect to communication translates to a comparable improvement factor with respect to computation), and since the cost of issuing a credential depends on the specific secure computation scheme used to implement it, which is not the focus of our work (we require the same blind issuance of an algebraic MAC as in previous works on KVAC).

For simplicity, we focus on the cost obtained when implementing the MAC with the more efficient GGM-based MAC scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF]; when using the other, DDH-based MAC scheme, all costs must be roughly scaled up by 50% (up to constants), and the improvement factor of our method compared to the naive approach will be essentially identical. Let β denote the length of the vector of attributes. In the minimal setting where the verifier knows a pseudonym, implemented as a commitment to the user's vector of attributes, instantiating the zero-knowledge proofs in [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] using the DVNIZK proof system of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] leads to a proof size of 3β + 3 group elements, and 6β + 2 ciphertexts (in a typical instantiation of the DVNIZK of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF], the group will be a composite order abelian group, and the encryption scheme will be the Paillier encryption scheme).

In comparison, our proof of credential possession requires sending β + 2 group elements, and 2β + 2 ciphertexts. Furthermore, all the ciphertexts can be sent once for all to the verifier (they form the pseudonym of the prover); each new credential presentation then requires only generating and sending β + 2 group elements (in comparison, the pseudonym in [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] is a tuple of β commitments, hence sending the pseudonym ahead of time saves only β group elements). For the important case of β = 1 attribute, and instantiating the DVNIZK with Paillier and a 2048-bit modulus, this corresponds to a factor of improvement of more than 7 in the proof size compared to [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF]. In addition, using an optimization which we describe in Appendix C, the number of ciphertexts can be further reduced, from 2β + 2 to 2β. We summarize the comparison between our scheme and CMZ+CC in the table 1.

Eventually, we sketch a straightforward computational optimization (assuming an instantiation with the Paillier scheme and a 2048-bit modulus for concreteness): the exponents manipulated when constructing and verifying the proof are either attributes, random coins, or masks. If attributes are, say, up to 128-bit long, then under the short-exponent discrete logarithm assumption (which states that it is hard to find x from g x even if x is random but short, e.g. 128-bit long), all exponents can be taken either 128-bit long (for the attributes and the random coins) or 256-bit long (for the masks, since they must statistically mask the attributes over the integers). This makes computing exponentiations and scalar multiplications considerably more efficient than with full-size (i.e., 2048-bit) values. [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF]. We briefly comment on the comparison with the plain scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] (which is either interactive, or non-interactive in the random oracle model). Our main efficiency bottleneck is the fact that we use the DVNIZK of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF], which requires to use a large order group. 1 Therefore, using natural parameters, we manipulate group elements of size 2048 bits, and ciphertexts of size 4096 bits. In constrast, [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] can work exclusively with group elements and exponents over any DDH-hard group, e.g. of size 256 bits. However, the proof size of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] (not counting the size of the pseudonym) is β + 2 group elements and 3β + 2 256-bit exponents, for a total of 256 Byte. Our proof system achieves a proof size 756 Byte, less than three times larger in spite of our use of an 8-time larger group -and unlike [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], it is secure in the standard model (the ratio remains essentially the same if we instantiate instead the underlying MAC scheme with the DDH-based scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF]).

Comparison with Plain

Organization

In Section 2, we recall necessary preliminaries (further preliminaries are given in Appendix A. In Section 3, we recall the definition of MAC schemes, introduce a general algebraic MAC scheme, and define the stronger notion of extended unforgeability. In Section 4, we formally define non-interactive keyed-verification anonymous credentials and their security properties. In Section 5, we introduce the concept of oblivious DVNIZK and their security properties, provide an explicit instantiation tailored to our application, and formally prove its security. In Section 6, we show how to construct a non-interactive keyed-verification anonymous credential from a MAC scheme and an oblivious DVNIZK proof system. Eventually, in Appendix B, we prove that the first MAC scheme of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] satisfies extended unforgeability in the generic group model (with composite order groups), and in Appendix C, we describe further improvements to our NIKVAC construction relying on the short-exponent discrete logarithm assumption.

Preliminaries

Throughout this paper, λ denotes the security parameter. A probabilistic polynomial time algorithm (PPT, also denoted efficient algorithm) runs in time polynomial in the (implicit) security parameter λ. A positive function f is negligible if for any polynomial p there exists a bound B > 0 such that, for any integer k ≥ B, f (k) ≤ 1/|p(k)|. An event depending on λ occurs with overwhelming probability when its probability is at least 1 -negl(λ) for a negligible function negl. Given a finite set S, the notation x $ ← S means a uniformly random assignment of an element of S to the variable x. We represent adversaries as interactive probabilistic Turing machines; the notation A O indicates that the machine A is given oracle access to O. Adversaries will sometime output an arbitrary state st to capture stateful interactions.

Abelian Groups and Modules. We use additive notation for groups for convenience, and write (G, ) for an abelian group of order k. When it is clear from the context, we denote 0 its neutral element (otherwise, we denote it 0 G ). We denote by ord(G) the order of G. We denote by • the scalar-multiplication algorithm (i.e. for any (x,

G) ∈ Z k × G, x • G = G G . . . G,
where the sum contains x terms). Observe that we can naturally view G as a Z k -module (G, , •), for the ring (Z k , +, •). For simplicity, we write G for (-1) • G. We use lower case to denote elements of Z k , upper case to denote elements of G, and bold notations to denote vectors. We extend the notations ( , ) to vectors and matrices in the natural way, and write x • G to denote the scalar product x 1 • G 1 . . . x t • G t (where x, G are vectors of the same length t). For a vector v, we denote by v its transpose. By GGen(1 λ ), we denote a probabilistic efficient algorithm that, given the security parameter λ, generates an abelian group G in which the CSG and DLSE assumption defined below holds in respect to λ. Note that this implies that the normal discrete log problem is hard in this group, as well. In the following, we write (G, k) $ ← GGen(1 λ ). Additionally, we denote by GGen(1 λ , k) a group generation algorithm that allows us to select the order k beforehand.

RSA Groups.

A strong prime is a prime p = 2p + 1 such that p is also a prime. We call RSA modulus a product n = pq of two strong primes. We denote by ϕ Euler's totient function; it holds that ϕ(n) = (p -1)(q -1). We denote by J n the cyclic subgroup of Z * n of elements with Jacobi symbol 1 (the order of this group is ϕ(n)/2), and by QR n the cyclic subroup of squares of Z * n (which is also a subgroup of J n and has order ϕ(n)/4). By Gen(1 λ ), we denote a probabilistic efficient algorithm that, given the security parameter λ, generates a strong RSA modulus n and secret parameters (p, q) where n = pq, such that the best known algorithm for factoring n takes time 2 λ . In the following, we write (n, (p, q)) $ ← Gen(1 λ ) and call abelian groups with order n composite order groups, if n is a RSA modulus.

Generic Group Model. The generic group model (GGM) was introduced in [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] and is an idealized model of groups. It captures groups with no additional structure apart from being a group. In such generic groups, the only possibility of attacking a cryptographic primitive is utilizing generic algorithms which only make use of group operations.

In proofs, the generic group model is captured by giving an adversary access to the group through random encodings of the group elements as bitstrings and a group operation oracle. Note that if a cryptographic primitive is proven secure in the GGM, it only ensures that it can not be broken with generic algorithms. In order to simulate the oracle in this work, we will require the following lemma, based on [START_REF] Schwartz | Fast probabilistic algorithms for verification of polynomial identities[END_REF].

Lemma 1 (Generalised Schwartz-Zippel). Let (n, (p, q)) $ ← Gen(1 λ ), G $ ← GGen(1 λ , n) and F ∈ Z n [x 1 , x 2 , .., x l ] with F = 0 ∧ deg(F ) = d ≥ 0. Let p ∈ {p, q} and P a subgroup of G of order p . It holds that Pr x = (x 1 , x 2 , .., x l ) $ ← P l : F (x) = 0 ≤ d p

Assumptions

Computational Subgroup Assumption (CSG). The computational subgroup assumption states that no bounded adversary can output a generator for a non-trivial subgroup. Or more formally, for all PPT adversaries A , it holds that

Pr   (n, (p, q)) $ ← Gen(1 λ ), G $ ← GGen(1 λ , n), G ← A (G, n), : G = 0 G ∧ (p • G = 0 G ∨ q • G = 0 G )   ≤ µ(λ)
where µ(λ) = negl(λ).

Decisional-Diffie-Hellman (DDH) Assumption. Let G be a group with order n. For all PPT adversaries A it holds that Pr a, b, c

$ ← Z n : A (G, A, B, C) = 1 A ← a • G, B ← b • G, C ← ab • G - Pr a, b, c $ ← Z n : A (G, A, B, C) = 1 A ← a • G, B ← b • G, C ← c • G ≤ µ(λ)

Encryption Schemes

A public-key encryption scheme S is a triple of PPT algorithms (S.KeyGen, S.Enc, S.Dec), such that S.KeyGen generates encryption and decryption keys (ek, dk), S.Enc ek , given a plaintext, outputs a (randomized) ciphertext, and S.Dec dk , given a ciphertext, outputs a plaintext. An encryption scheme must be correct (S.Enc dk (S.Enc ek (m)) = m for every message m) and IND-CPA secure (no adversary can distinguish between the encryptions of two messages of its choice). We defer to Appendix A the formal definition of encryption schemes and their security properties.

In this work, we will focus on additively homomorphic encryption schemes, which are homomorphic for both the message and the random coin. More formally, we require that the message space M and the random source R are integer sets (Z M , Z R ) for some integers (M, R), and that there exists an efficient operation ⊕ such that for any (ek, sk)

$ ← KeyGen(1 λ ), any (m 1 , m 2 ) ∈ Z 2 M and (r 1 , r 2 ) ∈ Z 2 R , denoting (C i ) i≤2 ← (S.Enc ek (m i ; r i )) i≤2 , it holds that C 1 ⊕ C 2 = S.Enc ek (m 1 + m 2 mod M ; r 1 + r 2 mod R).
We say an encryption scheme is strongly additive if it satisfies these requirements. Note that the existence of ⊕ implies (via a standard square-and-multiply method) the existence of an algorithm that, on input a ciphertext C = S.Enc ek (m; r) and an integer ρ ∈ Z, outputs a ciphertext C = S.Enc ek (ρm mod M ; ρr mod R). We denote by ρ C the external multiplication of a ciphertext C by an integer ρ, and by the operation C ⊕ (-1) C for two ciphertexts (C, C ). We will sometimes slightly abuse these notations, and write C ⊕ m (resp. C m) for a plaintext m to denote C ⊕ S.Enc ek (m; 0) (resp. C S.Enc ek (m; 0)). We extend in a natural way the algorithm Enc over vectors: for vectors m = (m i ) i ∈ Z * M and r = (r i ) i ∈ Z * R of the same size, S.Enc ek (m; r) denotes the vector (S.Enc ek (m i , r i )) i . We extend the algorithm Dec to vectors of ciphertexts in a similar way.

The Paillier Encryption Scheme. The Paillier encryption scheme [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] is a well-known additively homomorphic encryption scheme over Z n for an RSA modulus n. We describe here a standard variant [START_REF] Damgård | A generalization of paillier's public-key system with applications to electronic voting[END_REF][START_REF] Lipmaa | Optimally sound sigma protocols under DCRA[END_REF], where the random coin is an exponent over J n rather than a group element. Note that the exponent space of J n is Z ϕ(n)/2 , which is a group of unknown order; however, it suffices to draw exponents at random from Z n/2 to get a distribution statistically close from uniform over Z ϕ(n)/2 . The IND-CPA security of the Paillier encryption scheme reduces to the DCR assumption, which states that it is computationally infeasible to distinguish random n'th powers over Z * n 2 from random elements of Z * n 2 .

-KeyGen(1 λ ): run (n, (p, q))

$ ← Gen(1 λ ), pick g $ ← J n , set h ← g n mod n 2 , and compute δ ← n -1 mod ϕ(n) (n and ϕ(n) are relatively prime). Return ek = (n, h) and dk = δ; -Enc(ek, m; r): given m ∈ Z n , for a random r $ ← Z n/2 , compute and output c ← (1 + n) m • h r mod n 2 ; -Dec(dk, c): compute x ← c dk mod n and c 0 ← [c • x -n mod n 2 ]. Return m ← (c 0 -1)/n.
DVNIZK-Friendly Encryption Scheme. We say that a strongly additive encryption scheme is DVNIZK-friendly, when it satisfies the following additional properties:

-Coprimality Property: we require that the size M of the plaintext space and the size R of the random source are coprime, i.e., gcd(M, R) = 1; -Decodable: for any (ek, sk) $ ← KeyGen(1 λ ), the function f ek : m → Enc ek (m; 0) must be efficiently invertible (i.e., there is a PPT algorithm, which is given ek, computing f -1 ek on any value from the image of f ek ).

Note that the Paillier cryptosystem is DVNIZK-friendly: (gcd(n, ϕ(n)) = 1, and any message m can be efficiently recovered from Enc ek (m; 0) = (1 + n) m mod n 2 ).

Non-Interactive Zero-Knowledge Proof of Knowledge Systems

A (designated-verifier) non-interactive zero-knowledge (DVNIZK) proof system for a language L is a quadruple (Π.Setup, Π.KeyGen, Π.Prove, Π.Verify), as follows: Π.Setup generates the setup parameters; Π.KeyGen generate the (public) proving key and the verification key (which is private in a designated-verifier scheme, and public in a publicly-verifiable one); Π.Prove, given the proving key, a word x an a witness w for x ∈ L , outputs a proof π; and Π.Verify, given the verification key, x, and π, outputs either accept or reject.

A DVNIZK proof system must be complete (if x ∈ L , the verifier accept), sound (if x / ∈ L , no malicious prover can cause the verifier to accept; we usually want a stronger security notion, unbounded extractability, which states that a polytime extractor can extract a valid witness from any accepting proof, even if the proof was adversarially generated with arbitrary access to a verification oracle), and zero-knowledge (the proof can be simulated without knowledge of the witness). We defer to Appendix A the formal definition of DVNIZKs and their security properties.

The DVNIZK of Chaidos and Couteau. This DVNIZK proof of knowledge system was introduced in [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] and satisfies composable zero-knowledge, and statistical adaptive unbounded knowledgeextractability. The proofs are generated for statements defined by a linear map over G: Let k be an integer, (G, ) be an abelian group of order k, and (α, β, γ) be three integers. Let G ∈ G α denote a vector of public parameters, and let C ∈ G β denote a public word. This system considers statements St Γ (G, C) defined by a linear map Γ :

(G α , G β ) → G γ×β such that St Γ (G,
Γ (G, C), pick x $ ← Z γ k , r $ ← Z γ 2 λ B , compute X ← S.Enc ek (x; r), X ← S.Enc ek (x ; 0) (r pk) = S.Enc ek (x ; -e • r), C ← x • Γ(G, C),
and output π ← (X, X , C ). -Π K .Verify(pk, vk, C, π): parse π as (X, X , C ). Check that e X ⊕ X is decodable, and decode it to a vector d ∈ Z γ k . Check that

d • Γ(G, C) = e • C C .
If all checks succeeded, accept. Otherwise, reject.

Message Authentication Codes

In this section, we recall the definition of message authentication codes (MAC), and outline a general MAC scheme (which we call "abstract MAC"), which unifies several existing MAC scheme with a natural algebraic structure. Then, we introduce a stronger unforgeability notion for this abstract MAC scheme. In Appendix B, we prove that one of the MAC schemes of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] does satisfy this security notion in the generic group model.

Definition

Definition 1 (Message Authentication Code). We recall the definition of a message authentication code. A message authentication code (MAC) M is a quadruple of PPT algorithms (M.Setup, M.KeyGen, M.Sign, M.Verify), such that -M.Setup(1 λ ) generates the public parameters pp of the MAC. We assume that pp specifies the tag space S and the message space M; -M.KeyGen(pp) generates and outputs a key sk and optionally public issuer parameters ipp.

-M.Sign sk (m) given the message m ∈ M, outputs a tag σ; -M.Verify sk (m, σ) given the message m ∈ M and a tag σ ∈ S, outputs a bit b whose value depends on the validity of the tag σ with respect to m.

We assume for simplicity that once generated, the public parameters pp are implicitly passed as an argument to the algorithms (M.KeyGen, M.Sign, M.Verify).

Definition 2 (Correctness of a MAC). A Message Authentication

Definition 3 (UF-CMVA Security of a MAC

). A MAC M is UF-CMVA secure if for any PPT adversary A , it holds that Pr    Q ← ∅, pp $ ← M.Setup(1 λ ), sk $ ← M.KeyGen(pp), : M.Verify k (m, σ) = 1 ∧ m / ∈ Q (m, σ) $ ← A O sk [Q] (pp)    ≤ 1 2 + µ(λ)
for some function µ(λ) = negl(λ). A has access to an oracle O sk [Q] which answers to verification and signing queries: In this paper we will need algebraic MACs which means that the signing and verification algorithms require only group operations to be performed.

-O.Sign(m) sets Q ← Q ∪ {m}

An Abstract MAC Scheme

Let G be an abelian group of order n. Given a vector x = (x 0 , • • • , x β ) for some integer β, we denote by

H x : Z β n → Z n the affine function which, on input (m 1 , • • • , m β ), outputs x 0 + β i=1 x i • m i .
Consider now the following generic MAC scheme, parametrized with integers (α, β):

-M.Setup(1 λ ) : pick a generator G of G and output pp ← (G, n, G, α, β); -M.KeyGen(pp) : pick α vectors (k i ) i≤α ∈ (Z β+1 n
) α (which can be either random or fixed) of length β + 1, and α random group elements

(G i ) i≤α $ ← G α . Set H i,j ← k -1 i,j • G for i ∈ [1..α], j ∈ [1..β], G i ← k i,0 • G i for i ∈ [1..α], and ipp ← ((H i,j ) 1≤j≤β ) i≤α , (G i , G i ) i≤α ). Output sk = (k i ) i≤α and ipp. -M.Sign sk (m) : given a message m = (m 1 , .., m β ) ∈ Z β n , pick a random group element U $ ← G and output σ ← (U, (H ki (m) • U ) i≤α ).
-M.Verify sk (m, σ) : parse σ as (U, (V i ) i≤α ) and check that for i = 1 to α,

V i = H ki (m) • U .
Example 1. The scheme MAC GGM from [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] is obtained by setting α = 1, and sampling the key k uniformly at random. This scheme is UF-CMVA-secure in the generic group model. Similarly, we recover the scheme MAC DDH from [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] by setting α = 3, sampling k 1 , k 2 at random, and setting k 3 ← (k 3,0 , 0, • • • , 0) for a uniformly random k 3,0 . This scheme is UF-CMVA-secure under the decisional Diffie-Hellman assumption.

Note that for our construction of an anonymous credential scheme, we will require the security of the underlying MAC scheme to hold in a group of composite order. In Appendix B, we slightly modify MAC GGM and prove that the modified version is secure in non-prime order groups in the generic group model.

Extended Unforgeability

The UF-CMVA security property states that no PPT adversary should be able to forge a MAC on a message, even given access to signing and verification oracles, as long as this message was never queried to the signing oracle. One can consider stronger notions of unforgeability, where the adversary is given access to an additional oracle. In particular, it will be useful in our setting to consider the following extended unforgeability property for the abstract MAC scheme defined above: Definition 4 (Extended Unforgeability). An abstract MAC M is XUF-CMVA secure if for any PPT adversary A , it holds that

Pr    Q ← ∅, pp $ ← M.Setup(1 λ ), sk $ ← M.KeyGen(pp), : M.Verify sk (m, σ) = 1 ∧ m / ∈ Q (m, σ) $ ← A O sk [Q] (pp)    ≤ 1 2 + µ(λ)
for some function µ(λ) = negl(λ). A has access to an oracle O sk [Q] which answers to verification and signing queries, as well as another specific type of query:

-O.Sign(m) sets Q ← Q ∪ {m}
β j=1 k i,j • A i,j = β j=1 k i,j • B i,j
for all i ≤ α, and outputs 1 iff all checks succeed (note: the O.Check oracle could equivalently check whether

β j=1 k i,j • A i,j = 0).
In Appendix B, we will prove that the scheme MAC GGM from [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], which was proven UF-CMVAsecure over prime order groups in the generic group model in [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], is in fact XUF-CMVA-secure in the generic group model over composite order groups (the use of groups of composite order is required for compatibility of the MAC scheme with the DVNIZK scheme of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]), under the computational subgroup assumption. Note that, while it is uncommon to prove security in the GGM under an additional assumption, it is necessary here: there exists an explicit attack against the security of the MAC if the adversary is able to compute a generator of a strict subgroup of G. However, in the usual formulation of the GGM, the adversary is unbounded and receives as input the order of the group, hence he can trivially factor this order and efficiently compute generators of strict subgroups of G, showing that MAC GGM is in fact not unconditionally secure in the GGM over composite order groups.

Non-Interactive Keyed-Verification Anonymous Credentials

In this section, we formally introduce non-interactive keyed-verification anonymous credentials and their security properties. Our definition mostly follows the blueprint of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF].

Definition 5 (Non-Interactive Keyed-Verification Anonymous Credentials

). An noninteractive keyed-verification anonymous credentials (NIKVAC) scheme Θ is a set of algorithms (Θ.Setup, Θ.CredKeyGen, Θ.BlindIssue, Θ.BlindObtain, Θ.Show, Θ.ShowVerify) such that -Θ.Setup(1 λ ), outputs the public parameters pp of the AC and a trapdoor td, the public parameters fix the set of supported statements Φ, the universe of attributes U and are passed to the following algorithms implicitly, the trapdoor can be used to revoke anonymity; -Θ.CredKeyGen(pp), generates a secret key sk and public issuer parameters ipp for an issuing organization; -Θ.BlindIssue(sk, S) ↔ Θ.BlindObtain(ipp, (m 1 , ..., m l )), interactively generates a credential cred for the attributes (m 1 , .., m l ) ∈ U, where S ⊂ {m 1 , .., m l } (here, S refers to the subset of attributes that the user wants to keep private; it allows to flexibly choose which attributes should be revealed, and which should not); -Θ.Show(ipp, cred, (m 1 , ..., m l ), Φ), outputs a proof of possession π of a credential cred for organization with issuer parameters ipp in respect to the attributes (m 1 , .., m l ) ∈ U with associated statements Φ ∈ Φ; -Θ.ShowVerify(sk, π, Φ), checks the proof π with sk with respect to the statements Φ ∈ Φ; which satisfies the correctness, anonymity, unforgeability, blind issuance and key-parameter consistency properties defined below.

We define two extra algorithms to simplify the security definitions:

-Issue(sk, (m 1 , .., m l )): generates a credential for the attributes (m 1 , .., m l ) using sk; -CredVerify(sk, (m 1 , .., m l ), cred): verifies the credential cred using sk.

Here we define correctness, which guarantees that Issue always outputs proper credentials and that a proof of possession for a valid credential verifies correctly.

Definition 6 (Correctness

). A NIKVAC scheme Θ is correct if it holds that Pr     (pp, td) $ ← Θ.Setup(1 λ ), (m 1 , .., m l ) $ ← U, (sk, ipp) $ ← Θ.CredKeyGen(1 λ ), cred $ ← Issue(sk, (m 1 , .., m l )), b $ ← CredVerify(sk, (m 1 , .., m l ), cred) : b = 1     = 1 and Pr           (pp, td) $ ← Θ.Setup(1 λ ), Φ ∈ Φ, (m 1 , .., m l ) $ ← U with Φ(m 1 , .., m l ) = 1, (sk, ipp) $ ← Θ.CredKeyGen(1 λ ), cred $ ← Issue(sk, (m 1 , .., m l )), π $ ← Θ.Show(ipp, cred, (m 1 , ..., m l ), Φ) b $ ← Θ.ShowVerify(sk, π, Φ), : b = 1           = 1
Unforgeability ensures that users cannot successfully show credentials without having received one from the authority.

Definition 7 (Unforgeability). A NIKVAC scheme Θ is unforgeable if for any PPT adversary

A it holds that Pr     pp $ ← Setup(1 λ ), Q ← ∅, (sk, ipp) $ ← Θ.CredKeyGen(1 λ ), (Φ, π) $ ← A O sk [Q] (pp, ipp), b $ ← Θ.ShowVerify(sk, π, Φ), : b = 1 ∧ ∀(m 1 , .., m l ) ∈ Q : Φ(m 1 , .., m l ) = 0     ≤ µ(λ)
for some function µ(λ) = negl(λ). A has access to an oracle O sk [Q] which answers to issuing and verification queries:

-O . Issue(m 1 , .., m l ) sets Q ← Q ∪ {m 1 , .
., m l } and outputs Issue(sk, ipp, (m 1 , .., m l )); -O . Verify(Φ, π) outputs Θ.ShowVerify(sk, π, Φ).

Anonymity ensures that a user that shows a credential stays anonymous. Note that, as observed in [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF], this simulation-style notion of anonymity implies in particular the standard notion of multishow unlinkability, which states that anonymity is preserved throughout multiple presentations of the credential (a property which is not satisfied by e.g. U-Prove [START_REF] Paquin | U-Prove cryptographic specification V1.1[END_REF]).

Definition 8 (Anonymity).

A NIKVAC scheme Θ is anonymous if for any PPT adversary A , there exists a PPT simulator Sim such that it holds that

Pr     (pp, td) $ ← Θ.Setup(1 λ ), (sk, ipp) $ ← Θ.CredKeyGen(1 λ ), (Φ, cred, (m 1 , .., m l ), st) $ ← A (pp, ipp, sk), π $ ← Θ.Show(ipp, cred, (m 1 , ..., m l ), Φ) : CredVerify(sk, (m 1 , .., m l ), cred) = 1 ∧ Φ(m 1 , .., m l ) = 1 ∧ A (st, π) = 1     - Pr     (pp, td) $ ← Θ.Setup(1 λ ), (sk, ipp) $ ← Θ.CredKeyGen(1 λ ), (Φ, cred, (m 1 , .., m l ), st) $ ← A (pp, ipp, sk), π $ ← Sim(ipp, sk, Φ) : CredVerify(sk, (m 1 , .., m l ), cred) = 1 ∧ Φ(m 1 , .., m l ) = 1 ∧ A (st, π) = 1     ≤ µ(λ)
for some function µ(λ) = negl(λ).

Blind Issuance. The protocol BlindIssue ↔ BlindObtain defines a secure two-party protocol for the function f ((S, pp, ipp), (sk, r), (m 1 , .., m l )) for shared input (S, pp, ipp), issuer input (sk, r) and user input (m 1 , .., m l ) which returns cred ← Issue(sk, (m 1 , .., m l ); r) to the user, if the input is correct. Since we will not cover this property explicitly in this paper, refer to [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] for more details.

Definition 9 (Key-Parameter Consistency).

A NIKVAC scheme Θ fulfills the key-parameter consistency property if for any PPT adversary A , it holds that Pr (pp, td)

$ ← Θ.Setup(1 λ ), for i ∈ {0, 1}, (ipp, sk 0 , sk 1 ) $ ← A (pp) : (ipp, sk i ) ∈ {x | x $ ← Θ.CredKeyGen(1 λ )} ≤ µ(λ)
for some function µ(λ) = negl(λ).

Additional Properties

Anonymity Revocation. The following property would allow a trusted third party to revoke anonymity if desired.

Definition 10 (Extractability).

A NIKVAC scheme Θ is extractable if there exists an efficient extractor Ext such that

Pr         (pp, td) $ ← Θ.Setup(1 λ ), Φ ∈ Φ, (m 1 , .., m l ) $ ← U, (sk, ipp) $ ← Θ.CredKeyGen(1 λ ), cred $ ← Issue(sk, (m 1 , .., m l )), π $ ← Θ.Show(ipp, cred, (m 1 , ..., m l ), Φ) : (m 1 , .., m l ) ← Ext(td, π)         = 1

Oblivious Designated-Verifier Non-Interactive Zero-Knowledge

In this section, we introduce oblivious (designated-verifier, non-interactive) zero-knowledge proof system. Intuitively, an oblivious DVNIZK enhances the security and the functionality of a DVNIZK with two properties:

-First, the oblivious DVNIZK on a word x can be used to show knowledge of a witness w such that R sk (x, w) = 1, where R sk is a secret witness relation, which depends on a secret information which is not known to the prover. The knowledge of sk is not required to generate a proof -but it is, obviously, necessary to verify the proof. -Second, we consider words x which can be divided in subwords (x 0 , x 1 ), such that x 0 is a public subword, while x 1 is a private subword. The privacy of x 1 is ensured by requiring, for the zero-knowledge property, the existence of a simulator which can simulate a proof without knowing the witness w and/or x 1 . Note that this formalism is mainly chosen for notational convenience: the word x 1 could always be thought of as being part of the witness. However, defining it as a part of the word allows us to set the secret relation R sk to be exactly the MAC verification, where the word is the signature and the witness is the message, in our concrete instantiation.

Definition

Definition 11 (Oblivious DVNIZK). An oblivious designated-verifier non-interactive zero-knowledge proof of knowledge Π for a family of secret witness relations {R crs (•, •, •)} crs (which take as input triples (sk, x, w) where sk is a secret relation key, x is a word, and w is a witness for the relation R crs (sk, •, •)) is a five-tuple (Π.Setup, Π.RelSetup, Π.KeyGen, Π.Prove, Π.Verify) of efficient algorithms such that -Π.Setup(1 λ ), on input the security parameter in unary, outputs a pair (crs, td) where crs is a common reference string and td is a trapdoor; -Π.RelSetup(crs), on input crs, outputs a pair (sk, ipp), where sk is a secret relation key, and ipp are public issuer parameters; -Π.KeyGen(crs), on input crs, outputs a pair (pk, vk) where pk is a public proving key, and vk is a secret verification key; -Π.Prove(crs, pk, ipp, (x 0 , x 1 ), w), on input crs, the public key pk, the issuer parameters ipp, a word (x 0 , x 1 ), where x 0 is a public subword and x 1 is a secret subword, and a witness w such that R crs (sk, (x 0 , x 1 ), w) = 1, outputs a proof π; -Π.Verify(crs, pk, ipp, x 0 , vk, sk, π), on input crs, the public key pk, the issuer parameters ipp, the public subword x 0 , the verification key vk, the secret relation key sk, and a proof π, outputs a bit b ∈ {0, 1}; which satisfies the completeness, oblivious zero-knowledge, and oblivious knowledge-extractability properties defined below.

Definition 12 (Completeness

). An oblivious DVNIZK proof system Π = (Π.Setup, Π.RelSetup, Π.KeyGen, Π.Prove, Π.Verify) for a family of secret witness relations {R crs } crs satisfies completeness if for every (crs, td) in the image of Π.Setup(1 λ ), every (sk, ipp) in the image of Π.RelSetup(crs), every (pk, vk, sk) in the image of Π.KeyGen(crs), every ((x 0 , x 1 ), w) such that R crs (sk, (x 0 , x 1 ), w) = 1, and every π in the image of Π.Prove(pk, ipp, (x 0 , x 1 ), w), it holds that Π.Verify(pk, ipp, x 0 , vk, sk, π) = 1.

Definition 13 (Oblivious Zero-Knowledge

). An oblivious DVNIZK proof system Π = (Π.Setup, Π.RelSetup, Π.KeyGen, Π.Prove, Π.Verify) for a family of witness relations {R crs } crs satisfies oblivious zero-knowledge if for any stateful PPT Adv, there exists a probabilistic polynomial-time simulator Sim such that

Pr     (crs, td) $ ← λ ), (pk, vk) $ ← Π.KeyGen(crs), : (R crs (sk, (x 0 , x 1 ), w) = 1) ((x 0 , x 1 ), w, ipp, sk) ← A (crs, pk, vk), ∧(A (π) = 1) π ← Π.Prove(crs, pk, ipp, (x 0 , x 1 ), w),     - Pr     (crs, td) $ ← Π.Setup(1 λ ), (pk, vk, sk) $ ← Π.KeyGen(crs), : (R crs (sk, (x 0 , x 1 ), w) = 1) ((x 0 , x 1 ), w, sk, ipp) ← A (crs, pk, vk), ∧(A (π) = 1) π ← Sim(crs, pk, ipp, x 0 , vk, sk),     ≤ µ(λ)
where µ(λ) = negl(λ). Definition 14 ((O 0 , O 1 )-Knowledge-Extractability). An oblivious DVNIZK proof system Π = (Π.Setup, Π.RelSetup, Π.KeyGen, Π.Prove, Π.Verify) for a family of secret witness relations {R crs } crs satisfies (O 0 , O 1 )-knowledge-extractability if the following two conditions hold:

for every PPT adversary A , there is an efficient extractor Ext such that [sk] (crs, pk, ipp), (x 1 , w) ← Ext(crs, pk, ipp, x 0 , td, π), : R crs (sk, (x 0 , x 1 ), w) = 0 ∧ Π.Verify(crs, pk, ipp, x 0 , vk, sk, π) = 1

Pr       (crs, td) $ ← Setup(1 λ ), (sk, ipp) $ ← RelSetup(crs), (pk, vk) $ ← Π.KeyGen(crs), (π, x 0 ) ← A V,O0
      ≈ 0,
where V denotes Π.Verify(crs, pk, ipp, •, vk, sk, •); -there exists an efficient simulator that simulates the answers of Π.Verify(crs, pk, ipp, •, vk, sk, •), which is not given sk but is instead given oracle access to O 1 [sk].

Instantiation

We now provide an instantiation of an oblivious DVNIZK suitable for our construction. At a high level, the secret witness relation we consider will be the one that checks, for triples (sk, x, w), that the message w is the one signed in the credential x (with respect to the secret key sk of the abstract MAC scheme defined in Section 3.1). Our construction heavily builds upon the DVNIZK proof system of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. Let S = (S.KeyGen, S.Enc, S.Dec) denote a DVNIZK-friendly encryption scheme with plaintext space Z n and M = (M.Setup, M.KeyGen, M.Sign, M.Verify) be a MAC scheme, which we assume to have the abstract structure given in Section 3.1, over a group G of order n with generator G. We will consider the following witness relation: R crs (sk, x, w), given as input a vector x = (U, (V i ) i≤α ) ∈ G α+1 of group elements, a witness w = (m 1 , • • • , m β ), and given sk, checks that

M.Ver sk (m 1 , • • • , m β , x) = 1
, where sk = (k i ) i≤α is the MAC key. Since the purpose of the public word x 0 is mainly to allow more expressivity when considering a more complex relation, and we focus here on the most basic relation (the scheme can be enhanced to work with more complex relations), we simply consider that x = x 1 is entirely a secret word. The scheme works as follows:

-Π.Setup(1 λ ) : compute (ek, dk) $ ← S.KeyGen(1 λ ) and pp $ ← M.Setup(1 λ ). Output crs ← (ek, pp). Note that ek defines a plaintext space Z n and a random source Z R . As the IND-CPA and strong additive properties of S require R to be unknown, we assume that a bound B on R is publicly available. We denote ← 2 λ nB.

-Π.RelSetup(crs) : same as M.KeyGen, namely: pick α vectors (k i ) i≤α ∈ (Z β n ) α (which can be either random or fixed) of length β, and α random group elements

(G i ) i≤α $ ← G α . Set H i,j ← k -1 i,j • G for i ∈ [1..α], j ∈ [1..β], G i ← k i,0 • G i for i ∈ [1..α], and ipp ← ((H i,j ) 1≤j≤β ) i≤α , (G i , G i ) i≤α ). Output sk = (k i ) i≤α and ipp.
-Π.KeyGen(crs) : pick e ← Z , set pk ← S.Enc ek (0; e) and vk ← e. Output (pk, vk). -Π.Prove(crs, pk, ipp, x, w) : given x = (U, (V i ) i≤α ) and a witness w = m, pick (m , t, t )

$ ← Z β n ×(Z α n ) 2 , (r m , r t ) $ ← Z β 2 λ B ×Z α 2 λ B , z $ ← Z n . Let (t j ) j≤β = (t 1,j , • • • , t α,j ) j≤β denote uniformly random additive shares of t over Z α n . Compute (U , (V i ) i≤α ) ← (z • U, ((z • V i ) (t i • G)) i≤α ) W i,j ← m j • U (t i,j • H i,j ) for i ∈ [1..α], j ∈ [1..β] (X m , X t ) ← (S.Enc ek (m; r m ), S.Enc ek (t; r t )), X m ← S.Enc ek (m ; 0) (r m pk) = S.Enc ek (m ; -e • r m ), X t ← S.Enc ek (t ; 0) (r t pk) = S.Enc ek (t ; -e • r t ),
and output π ← (U ,

(V i ) i≤α , (W i,j ) i≤α,j≤β , X m , X t , X m , X t ). -Π.Verify(crs, pk, ipp, vk, sk, π) : parse π as (U , (V i ) i≤α , (W i,j ) i≤α,j≤β , X m , X t , X m , X t ).
Check that e X m ⊕ X m and e X t ⊕ X t are decodable, and decode them to vectors d m , d t . Reconstruct

(W i ) i≤α ←   β j=1 k i,j • W i,j   i≤α and check that (e • (V i (k i,0 • U )) W i ) i≤α = (d m • (k i,j • U ) 1≤j≤β ) i≤α d t • G.
Output 1 if and only if all checks succeeded. Theorem 2. The scheme Π is an oblivious designated-verifier zero-knowledge proof of knowledge for the family of secret witness relations {R crs } crs , whose oblivious zero-knowledge property reduces to the semantic security of the DVNIZK-friendly encryption scheme S, and which satisfies statistical (O 0 , O 1 )-knowledge extractability for the oracle O 0 [sk] ≡ M.Sign sk , and an oracle O 1 [sk] which is either

-M.Verify sk (•, •) if β = 1, or -M.Verify sk (•, •) together with M.Check sk (•, •) otherwise.

Extensions and Optimizations

In itself, the above oblivious DVNIZK does not seem to provide a strong unforgeability guarantee. Indeed, recall that the unforgeability of keyed-verification anonymous credential states (informally) that it should be infeasible to come up with a pair (m, σ) such that M.Ver sk (m, σ) = 1 and Φ(m) = 1, if all previous queries to the signing authority where on vectors m such that Φ(m ) = 0. The exact choice of Φ depends on the particular application; typically, Φ(m) could correspond to the statement that m is the value committed in some pseudonym known to the verifier; that way, the condition "all previous queries to the signing authority where on vectors m such that Φ(m ) = 0" boils down to the standard guarantee of anonymous credentials: it should be infeasible to come up with an accepting credential on a vector that was never signed before by the authority. But Φ can also check a more complex statement on the vector of attributes (e.g. it could check that the attribute "age" is above 18).

In the construction given above, we directly focus on enforcing M.Ver sk (m, σ) = 1; there is no additional Φ to, for example, bind m to a commitment. However, we observe that this typical choice of Φ is for free in our construction above. Indeed, a proof π does contain, by construction, a perfectly binding commitment (in fact, an encryption with S) of the vector m, which is X m . Furthermore, it will immediately follow from the security analysis that the proof does not only guarantee the knowledge of a witness w = m (recovered by the extractor): it further guarantees that this witness is exactly the one encrypted in X m . Therefore, to bind the user to a pseudonym known to the verifier, it is unecessary to add a commitment to m. Instead, the user can simply compute (X m , X t , X m , X t ) in advance (observe that this does not require the knowledge of a credential) and send it to the verifier, who will simply define it to be the pseudonym of the user. Then, each time he wants to show possession of a credential (U, (V i ) i≤α ), the user only needs to compute the missing part of the proof, (U , (V i ) i≤α , (W i,j ) i≤α,j≤β ). This significantly reduces the size of a proof of possession, and in scenario where Φ is only intended to check that the vector matches with a pseudonym, the basic construction suffices as is. Of course, it can be extended to more complex statements Φ, as long as they fit in the framework of statements handled by [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF].

Security Analysis

Completeness follows from a straightforward (although tedious) inspection. We now establish oblivious zero-knowledge and (O 0 , O 1 )-knowledge extractability.

Oblivious Zero-Knowledge. We exhibit a simulator Sim which simulates a proof π given (crs, pk, ipp, x 0 , vk = e, sk = (k i ) i≤α ). Note that Sim is not given the witness w nor x 1 . The simulator Sim proceeds as follows:

Pick ( m, m , d m , t, t , d t ) $ ← (Z β n ) 3 ×(Z α n ) 3 , (r m , r t ) $ ← Z β 2 λ B ×Z α 2 λ B . Let (t j ) j≤β = (t 1,j , • • • , t α,j ) j≤β denote uniformly random additive shares of t over Z α n . Compute (U , (V i ) i≤α ) $ ← G α+1 (W i ) i≤α ← (d m • (k i,j • U ) 1≤j≤β ) i≤α d t • G e • (V i (k i,0 • U )) i≤α (X m , X t ) ← (S.Enc ek ( m; r m ), S.Enc ek (t; r t )), (X m , X t ) ← (S.Enc ek (d m -e • m; -e • r m ), S.Enc ek (d t -e • t; -e • r t )).
Then, for i ∈ [1..α], j ∈ [1..β], pick random W i,j conditioned on

W i = β j=1 k i,j • W i,j , and output π ← (U , (V i ) i≤α , (W i,j ) i≤α,j≤β , X m , X t , X m , X t ).
We now show how to use an adversary Adv which outputs ((x 0 , x 1 ), w, ipp, sk) and distinguishes π ← Π.Prove(crs, pk, ipp, (x 0 , x 1 ), w) from π ← Sim(crs, pk, ipp, , x 0 , vk, sk) conditioned on R crs (sk, (x 0 , x 1 ), w) = 1 to break the semantic security of S. The reduction obtains m from Adv, samples a random m, and sends (m, m) to a challenger for the IND-CPA game of S. It receives a ciphertext X m . It samples (m ,d m ,t,t ,d

t ) $ ← (Z β n ) 2 × (Z α n ) 3 , r t $ ← Z α 2 λ B
as before, and sets X m ← S.Enc ek (d m ; 0) X m e. Finally, it computes (U , (V i ) i≤α ), (W i,j ) i≤α,j≤β , and (X t , X t ) as before. Observe that (U , (V i ) i≤α ) are distributed identically in the real game and the simulated game; direct calculations show that when X m encrypts m, the proof π is distributed exactly as in the real game, while when X m encrypts m, the proof π is distributed exactly as in the simulated game.

(O 0 , O 1 )-Knowedge-Extractability. We now turn our attention to the (O 0 , O 1 )-knowledge extractability property. The extractor Ext proceeds as follows: given a proof π = (U , (V i ) i≤α , (W i,j ) i≤α,j≤β , X m , X t , X m , X t ), it computes m ← S.Dec td (X m ), t ← S.Dec td (X t ), and outputs x ← (U , (V i t i • G) i≤α ), and w ← m. We now analyze the probability that R crs (sk, (x 0 , x 1 ), w) = 0 ∧ Π.Verify(crs, pk, ipp, x 0 , vk, sk, π) = 1. To do so, we proceed in two steps: Game 1. In this game, we modify the behavior of the oracle Π.Verify(crs, pk, ipp, vk, •, sk, •) that Adv is given access to. Namely, the oracle is not given vk anymore. Rather, we generate vk as before, and set e R ← vk mod R. Each time Adv sends a query π to the oracle, we proceed as follows: we parse π as π = (U , (V i ) i≤α , (W i,j ) i≤α,j≤β , X m , X t , X m , X t ), and use td to decrypt (X m , X t , X m , X t ), obtaining vectors (m, t, m , t ). Then, we perform the following checks:

1. we check that -e R (X m m) = X m m ; 2. we check that -e R (X t t) = X t t ; 3. we check

V i t i • G = H ki (m) • U for every i ≤ α (that is, we run M.Ver sk (m, σ) on the MAC σ = (U , (V i t i • G) i≤α )); 4. we reconstruct (W i ) i≤α ← β j=1 k i,j • W i,j i≤α and check W i t i • G = β j=1 (k i,j • m j ) • U for every i ≤ α.
Note that this follows exactly the proof strategy of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]Section 3.3]. It follows by the exact same argument that it is statistically infeasible to distinguish the simulated oracle in Game 1 from the real oracle, and the distinguishing advantage is at most Q(α + 1)p, where p is the smallest prime factor of n and Q is the number of queries of Adv to the oracle. Intuitively, the argument stems from the fact that if Adv ever submits a proof that would be accepted by the oracle, but not by the simulated oracle (or the converse), then this proof information-theoretically determines vk. However, even given e R = vk mod R, it follows from the chinese remainder theorem that the value vk mod n remains statistically hidden, since vk was initially picked at random in Z and satisfies > 2 λ nR. Observe that game already suffices to establish that the probability of R crs (sk, (x 0 , x 1 ), w) = 0 ∧ Π.Verify(pk, vk, sk, π) = 1 must be negligible, since in this game the simulation of Π.Verify does in particular check that R crs (sk, (x 0 , x 1 ), w) = 1. However, the simulation of Π.Verify still uses sk; to establish the second property of the (O 0 , O 1 )-knowledge-extractability, we proceed with a second game. Game 2. In this game, we further modify the simulated oracle, so that it does not use sk anymore. Instead, the simulation will itself rely on the MAC verification oracle. More precisely, the key sk is only used in the checks 3 and 4 of Game 1. The third check is straightforward given oracle access to M.Verify sk (•, •): just call M.Verify sk (m, σ) with σ = (U , (V i t i • G) i≤α ) (this is perfectly identical to the third check in the previous game).

The fourth check, however, is more problematic, since it's not clear how to reconstruct the (W i ) i≤α without knowing sk. Rewriting a bit the fourth check, we need to check is

β j=1 k i,j • W i,j t i • G = β j=1 k i,j • (m j • U ) for every i ≤ α. Letting (t i,1 , • • • , t i,β
) denote an arbitrary additive sharing of t i for every i ≤ α, this equation can be rewritten as

β j=1 k i,j • (W i,j t i,j • H i,j ) = β j=1 k i,j • (m j • U )
Now, we distinguish two cases:

-Case 1. If it holds that β = 1, corresponding to the case where the vector of attributes has length 1 (or, equivalently, we consider a simplified scenario without attributes, and credentials computed directly on the identity of the user), then the equation becomes

k i,1 • (m 1 • U W i,1 ) = t i • G.
Observe that this check can be performed efficiently: since we are given

H i,1 = k -1 i,1 • G, this is perfectly equivalent to checking m 1 • U W i,1 = t i • H i,1
for every i ≤ α, which does not require the knowledge of sk.

-Case 2. In the general case, where β can be larger than 1, there is no immediate shortcut. In this case, we have to rely on a MAC with a stronger unforgeability property, the XUF-CMVA security property defined in Section 3, and we simulate the verification using the following two oracles:

• M.Verify(m, σ) outputs M.Verify sk (m, σ); • M.Check((A i,j ) i≤α,j≤β , (B i,j ) i≤α,j≤β ) checks

β j=1 k i,j •A i,j = β j=1 k i,j •B i,j
for all i ≤ α, and outputs 1 iff all checks succeed, where the first oracle allows to check the third equation, and the second oracle allows to check the last equation.

In both cases, it is immediate to see that the answers of the simulated oracle are distributed exactly as in Game 1. Furthermore, the simulation only requires access to an oracle O 1 [sk], which is M.Verify in case 1, and the pair of oracles M.Verify, M.Check in case 2.

A Construction of NIKVAC from Algebraic MAC and Oblivious DVNIZK

In this section, we will use the system introduced in section 5 to construct a NIKVAC scheme Θ.

Construction

Let M be a MAC and Φ a set of statements for attributes m 1 , .., m l . Let Π Φ be an oblivious DVNIZK system which runs on a common Setup algorithm with M for the relation R crs , for crs

$ ← M.Setup(1 λ ), defined as R crs ((x 0 , x 1 ), (m 1 , .., m l ), k) = 1 iff M.Verify k ((m 1 , .., m l ), x 1 ) = 1 ∧ Φ(m 1 , .., m l ),
where x 0 is a public word needed to prove the statements Φ and Π Φ .RelSetup = M.KeyGen. We assume Π Φ satisfies (O 0 , O 1 )-knowledge-extractability, where O 0 [k](•) = M.Sign k (•) and O 1 [k] is either the MAC verification oracle, if M is UF-CMVA secure (and the attribute vectors are of length 1), or the MAC verification and additional check oracle, if M is XUF-CMVA secure. Since x 0 depends on the choice of Φ, we omit it entirely in the following and simply set x = x 1 . Note that Π Φ .Setup, Π Φ .CredKeyGen do not rely on the choice of Φ, so we simply write Π.Setup, Π.CredKeyGen. We now construct a NIKVAC scheme using {Π Φ } Φ .

-Θ.Setup(1 λ ), outputs (pp, td) $ ← Π.Setup(1 λ ), we assume that pp fixes the supported statements Φ, the universe of attributes U is the message space of M ; -Θ.CredKeyGen(pp), runs (pk, vk) $ ← Π.KeyGen(pp), (k, ipp M ) $ ← Π.RelSetup(pp), outputs secret key sk ← (vk, k) and issuer parameters ipp ← (pk, ipp M ), we assume that CredKeyGen satisfies key-parameter consistency; -Θ.BlindIssue(sk, S) ↔ Θ.BlindObtain(ipp, (m 1 , ..., m l )), performs a secure two-party computation that issues a tag of M to the user on valid input, we assume that this protocol satisfies blind issuance property2 ; -Θ.Show(ipp, cred, (m 1 , ..., m l ), Φ), parses ipp as (pk, ipp M ) outputs π $ ← Π Φ .Prove(pk, ipp M , cred, (m 1 , ..., m l )); -Θ.ShowVerify(sk, π, Φ), parses sk as (vk, k) and ipp as (pk, ipp M ), checks Π Φ .Verify(pk, ipp M , vk, k, π).

Security Analysis

For Θ, the functions Issue and CredVerify are defined as follows:

-Issue(sk, (m 1 , .., m l )): for sk = (vk, k) outputs M.Sign k (m 1 , .., m l ); -CredVerify(sk, (m 1 , .., m l ), cred): for sk = (vk, k) outputs M.Verify k ((m 1 , .., m l ), cred).

Theorem 3 (Correctness).

The NIKVAC scheme Θ satisfies correctness if M is correct and Π Φ is complete.

Missing Properties. The missing properties are blind issuance and key-parameter consistency. In practice, key-parameter consistency can easily be fulfilled by adding additional commitments to the components of the secret key and the two-party computation for blind issuance depends highly on the structure of the MAC scheme and can be implemented with any standard two party computation protocol; we briefly outline a possible candidate for an optimized version of our scheme in Appendix C.

Definition 17 (IND-CPA Security Property of a Public-Key Encryption Scheme). A public-key encryption scheme

S is IND-CPA secure if for any PPT adversary A , it holds that Pr    (ek, dk) $ ← S.KeyGen(1 λ ), (m 0 , m 1 , st) $ ← A (ek), b $ ← {0, 1} : A (st, c) = b r $ ← R, c ← S.Enc ek (m b ; r)    ≤ 1 2 + µ(λ)
for some function µ(λ) = negl(λ).

A.2 Preliminaries on Non-Interactive Zero-Knowledge Proofs

We recall the definition of designated verifier non-interactive zero-knowledge proof of knowledge system (DVNIZK) from [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. In the definitions below, we focus on proof systems for NP-languages that admit an efficient (polynomial-time) prover. For an NP-language L , we denote R L its associated relation, i.e., a polynomial-time algorithm which satisfies L = {x | ∃w, |w|= poly(|x|) ∧ R L (x, w) = 1}. We only recall DVNIZKs in the common reference string model. For conciseness, the common reference string is always implictily given as input to all algorithms.

Definition 18 (DVNIZK).

A designated verifier non-interactive zero-knowledge proof of knowledge system Π for a family of languages L = {L crs } crs is a quadruple of probabilistic polynomial-time algorithms (Π.Setup, Π.KeyGen, Π.Prove, Π.Verify) such that -Π.Setup(1 λ ), outputs a common reference string crs (which specifies the language L crs ), -Π.KeyGen(1 λ ), outputs a public key pk and a verification key vk, -Π.Prove(pk, x, w), on input the public key pk, a word x ∈ L crs , and a witness w, outputs a proof π, -Π.Verify(pk, vk, x, π), on input the public key pk, the verification key vk, a word x, and a proof π, outputs b ∈ {0, 1}, which satisfies the completeness, zero-knowledge, and knowledge-extractability properties defined below.

We assume for simplicity that once it is generated, the common reference string crs is implicitly passed as an argument to the algorithms (Π.KeyGen, Π.Prove, Π.Verify). Instead of standard soundness properties, we require the stronger notion of knowledge-extractability in this work.

Definition 19 (Completeness).

A DVNIZK proof system Π = (Π.Setup, Π.KeyGen, Π.Prove, Π.Verify) for a family of languages L = {L crs } crs with relations R crs satisfies the (perfect,statistical) completeness property if for crs $ ← Π.Setup(1 λ ), for every x ∈ L crs and every witness w such that R crs (x, w) = 1, Pr (pk, vk)

$ ← Π.KeyGen(1 λ ), π ← Π.Prove(pk, x, w) : Π.Verify(pk, vk, x, π) = 1 = 1 -µ(λ)
where µ(λ) = 0 for perfect completeness, and µ(λ) = negl(λ) for statistical completeness.

Definition 20 (Composable Zero-Knowledge

← Π.KeyGen(1 λ ), (x, w) ← A (pk, vk), : (R crs (x, w) = 1) ∧ (A (π) = 1) π ← Π.Prove(pk, x, w)   - Pr   (pk, vk) $ ← Π.KeyGen(1 λ ), (x, w) ← A (pk, vk), : (R crs (x, w) = 1) ∧ (A (π) = 1) π ← Sim(pk, vk, x)   ≤ µ(λ)
where µ(λ) = 0 for perfect composable zero-knowledge, and µ(λ) = negl(λ) for statistical composable zero-knowledge. If the composable zero-knowledge property holds against efficient (PPT) verifiers, the proof system satisfies computational composable zero-knowledge.

-O.Operation(ζ i , ζ j , ±): for i, j < q G , sets F q G = F i ± F j ∈ Z n [k 0 , k 1 , h, g, e 1 , .., e q T ], if F q G = F l for l < q G , then sets ζ q G ← ζ l , otherwise picks ζ q G $ ← S with ζ q G = ζ prev for 0 ≤ prev < q G , adds tuple (F q G , ζ q G ) to L, outputs ζ q G and increments q G ; -O.Sign(m): sets F q G ← e q T , picks ζ q G $ ← S with ζ q G = ζ prev for 0 ≤ prev < q G . Then computes F q G +1 ← e q T (mk 1 + k 0 ) ∈ Z n [k 0 , k 1 , h, g, e 1 , .., e q T ]. If F q G +1 = F l for l ≤ q G , then sets ζ q G +1 ← ζ l , otherwise picks ζ q G +1 $ ← S with ζ q G +1 = ζ prev for 0 ≤ prev ≤ q G , adds tuples (F q G , ζ q G ), (F q G +1 , ζ q G +1 ) to L and m to Q tag , outputs ζ q G , ζ q G +1
and finally, increments q T and q G twice;

-O.Verify(m, ζ, ζ ): checks (F, ζ) ∈ L ∧ (F , ζ ) ∈ L and F (mk 1 + k 0 ) = F , finally increments q V and adds m to Q ver . -O.Check(ζ, ζ ): checks (F, ζ) ∈ L ∧ (F , ζ ) ∈ L and F (k 1 ) = F (k 1 ), finllay incremets q C and adds (F, F ) to Q check .
At some point, A outputs (m, ζ, ζ ) after q G group operation queries, q T tag queries, q V verification queries and q C check oracle queries with (F, ζ), (F , ζ ) ∈ L6 . Note that due to the limited amount of query choices of the adversary A , the polynomial F will have the structure

F = ag + bh + sgk 0 + thk 1 + q T i=1 x i e i + q T i=1 y i e i (m i k 1 + k 0 ) + c
for a, b, c, s, t ∈ Z q and where m i ∈ Q tag is the i th queried message via O.Sign. Lastly, we pick a random v7 := (k 0 , k 1 , g, h, e 1 , .., e q T ) $ ← Z 3+q T n , choose i ∈ {1..q T } : x i = 0 and output x i • P to the challenger C . If no such i exists, output P8 .

We now analyze the success probability of the constructed adversary. Without loss of generality, we assume p > q. First, we show that our simulation is perfect with overwhelming probability. All polynomials in L have at most degree two based on the operations available. Let (F i , ζ i ), (F j , ζ j ) ∈ L. If F i = F j , but both polynomials are evaluated to the same value in Z n , the simulation would be invalid because we represented the same value with different representations in S. This is formalized by the following event:

∃i, j ≤ q T : F i (v) = F j (v) mod n ∧ F i = F j .
(

) 1
This is bounded by 2/p using lemma 1 for each fixed i, j 9 . Also, it could be the case that our verification oracle failed. This event is described as:

(F i (mk 1 + k 0 ))(v) = F j (v) mod n (2)
for m ∈ Q ver . This is bounded by 3/p using lemma 1 for fixed i, j, m. Note that F i can be of degree two and thus F i (mk 1 + k 0 ) -F j of degree three. Lastly, the check oracle simulation could fail which is described as:

(F (k 1 ))(v) = (F (k 1 ))(v) mod n (3)
for (F, F ) ∈ Q check . Again, the probability of this event is bounded by 3/p using lemma 1 for fixed F, F . Thus, the probability of event 1 occurring for all pairs (i, j) ∈ Z 2 q G , event 2 for all m ∈ Q ver 10 or event 3 for all (F, F ) ∈ Q check is at most

q G 2 • 2 p + (q V + q C ) • 3 p ≤ 2q 2 G p + 3(q V + q C ) p ≤ 6(q G + q V + q C ) 2 p
In conclusion, the probability of our simulation failing is negligible for the polynomially bounded adversary A .

If A succeeds, it holds that11 F (mk 1 + k 0 ) = F (4)

Due to the restriction of available operations for A , we have

F = ag + bh + sgk 0 + thk 1 + q T i=1
x i e i + q T i=1 y i e i (m i k 1 + k 0 ) + c F = a g + b h + s gk 0 + t hk 1 + q T i=1

x i e i + q T i=1 y i e i (m i k 1 + k 0 ) + c for a, a , b, b , c, c , s, s , t, t ∈ Z q and where m i ∈ Q tag is the i th queried message via O.Sign. First, we look at F = w for some w ∈ Z n . Then F = w(mk 1 + k 0 ). Because F has no subterm k 0 , the equality in 4 is only possible for w = 0. This does not constitute a valid forgery, though. Now, we look at F with deg(F ) > 0. Since the degree of F (mk 1 + k 0 ) will be at least two and the degree of F is at most two, we have deg(F ) = 1, deg(F ) = 2. Thus F = ag + bh + q T i=1 x i e i + c. Since F has no subterm of the form gk 1 , k 0 , k 1 or hk 0 , F has to be of the form q T i=1 x i e i . Thus, equation 4 implies that F = q T i=1 y i e i (m i k 1 + k 0 ). In conclusion, we have

F -F (mk 1 + k 0 ) = 0 =⇒ q T i=1 y i e i (m i k 1 + k 0 ) - q T i=1
x i e i (mk 1 + k 0 ) = 0 =⇒ q T i=1 e i (y i (m i k 1 + k 0 ) -x i (mk 1 + k 0 )) = 0 =⇒ ∀i ∈ {1..q T } : y i • m i k 1 + y i k 0 -x i • mk 1 -x i k 0 = 0 =⇒ ∀i ∈ {1..q T } :

y i • m i k 1 = x i • mk 1 ∧ y i k 0 = x i k 0 xi=y i =⇒ ∀i ∈ {1..q T } : x i • m i k 1 = x i • mk 1 =⇒ ∀i ∈ {1..q T } : x i • m i = x i • m mod n =⇒ m = m j ∈ Q, ∃j ∈ {1.
.q T } : x j ∈ Z * n ∀i ∈ {1..q T } : x i = 0 mod p i , for p i ∈ {p, q} otherwise

In the first case, it holds that m = m j for j ∈ {1..q T }. This is not a valid forgery. In the second case, if ∀i ∈ {1..q t } : x i = 0 mod n implies that F = 0 mod n. This would not constitute a valid forgery. Thus, ∃j ∈ {1..q t } : x j = 0 mod n, but x j = 0 mod p j . Finally, this implies that if A is successful, there exists some j ∈ {1..q t } such that x j • P is a non-trivial subgroup generator.

C Further Improvements from the Short-Exponent Discrete Logarithm Assumption

In this section, we discuss an approach to further improve the efficiency of our NIKVAC scheme, under the additional assumption that it is infeasible to solve discrete logarithms over G, even when the exponent is not uniformly random, but random conditioned on being shorter than some threshold. Considering discrete logarithm with short exponent has been done many times in the past (e.g. [START_REF] Corrigan-Gibbs | The discrete-logarithm problem with preprocessing[END_REF][START_REF] Gennaro | An improved pseudo-random generator based on discrete log[END_REF][START_REF] Koshiba | Short exponent diffie-hellman problems[END_REF][START_REF] Patel | An efficient discrete log pseudo random generator[END_REF][START_REF] Van Oorschot | On Diffie-Hellman key agreement with short exponents[END_REF]), since it is a natural approach to improve the computational efficiency of a scheme when working over a group with a large order. The best known attack on the discrete logarithm with short exponent (DLSE) assumption solves it in time O( √ T ), where T is the length of the interval from which the exponent is drawn [START_REF] Galbraith | Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval[END_REF]. where µ(λ) = negl(λ).

Indistinguishability of Short Exponents. As shown in [START_REF] Koshiba | Short exponent diffie-hellman problems[END_REF], the following statement is equivalent to the DLSE assumption in prime order groups. This is also true in composite order groups, which was shown in [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF].

Let G be a group with order n, G ∈ G a generator and T ∈ Z n , T < n. For all PPT adversaries A it holds that Pr z $ ← {0..T -1} :

A (z • G) = 1 -Pr z $ ← Z n : A (z • G) = 1 ≤ µ(λ)

C.2 Our Approach

Unlike previous works, we seek to use the DLSE assumption to improve not only the computational efficiency of our scheme, but also reduce its communication. The main observation is that in a group G of composite order, where exponents are typically of size at least 2048 bits, there is a clear "waste of space" for attributes: typical attributes will in general be much shorter (say, 128 or 256 bits).

Recalling the Previous Approach. For simplicity, we focus in our explanation on the case of the scheme MAC GGM , with a single attributes -all the results will trivially extend to larger vectors of attributes, and to the more general abstract MAC. A proof with our scheme of possession of a valid credential (U, V = (k 0 + k 1 • m) • U ) on a message m is computed as follows: for random (z, t, m , t , r m , r t ) in the appropriate space, and where H = k -1 1 • G. The purpose of the component t • G in the computation of V = z • V t • G is to perfectly mask V , preventing the verifier to break the anonymity by verifying the credential (U , V ) with respect to several candidate messages m. However, this mask t is also the reason why the proof of possession must include two additional ciphertexts (X t , X t ), since the user must now also prove knowledge of this masking value without revealing it.

-(U , V ) ← (z • U, z • V t • G), -W ← m • U + t •
Alternative Strategy. Under the DLSE assumption, there is a more efficient approach: the idea will be to directly "randomize the message m" to maintain anonymity, by padding it with a random value. Let be the bit-length of the attribute m, which we assume to be much shorter than log n, where n is the order of G: we require ≤ log n -2λ, where λ is the security parameter. We modify the blind issuance protocol such that it does not issue a credential (U, V ) on m anymore: instead, it should output a credential (U, V ) on the value x = m + 2 r mod n, where r is a uniformly random padding picked by the user (and hidden from the signing authority) of bit-length at least 2λ, and at most log n -(to ensure that no wraparound modulo n occurs, which guarantees that x uniquely defines m). Consider now the following simplifies proof of credential possession: The above protocol guarantees that the user knows the r in x = m + 2 r, and furthermore that this padding is short (below n/2 ); to maintain correctness, however, the user must initially choose the padding smaller than n/2 +2λ . This is fine as long as n/2 +2λ > 2 2λ . In a typical scenario, we can have = λ = 128 and n = 2048, in which case the above condition is easily satisfied.

-(U , V ) ← (z • U, z • V ), -W ← m • U , -X m ← S.

  C coresponds to the statement "I know x ∈ Z γ k such that x • Γ(G, C) = C". Let S = (S.KeyGen, S.Enc, S.Dec) denote a DVNIZK-friendly encryption scheme with plaintext space Z k . The algorithms (Π K .Setup, Π K .KeyGen, Π K .Prove, Π K .Verify) form a DVNIZK of knowledge Π K for a statement St Γ (G, C) over a word C ∈ G β , with public parameters G ∈ G α , defined by a linear map Γ : (G α , G β ) → G γ×β : -Π K .Setup(1 λ ) : compute (ek, dk) $ ← S.KeyGen(1 λ ). Output crs ← ek. Note that ek defines a plaintext space Z k and a random source Z R . As the IND-CPA and strong additive properties of S require R to be unknown, we assume that a bound B on R is publicly available. We denote ← 2 λ kB. -Π K .KeyGen(1 λ ): pick e ← Z , set pk ← S.Enc ek (0; e) and vk ← e. -Π K .Prove(pk, C, x): on a word C ∈ Z β k , with witness x for the statement St

  Code M is correct if for any pp $ ← M.Setup(1 λ ), any sk $ ← M.KeyGen(pp), any message m ∈ M and for σ $ ← M.Sign sk (m), it holds that M.Verify sk (m, σ) = 1.

  and outputs M.Sign sk (m); -O.Verify(m, σ) outputs M.Verify sk (m, σ).

C. 1

 1 DefinitionT -Bounded Short Exponent Discrete Logarithm (DLSE) Assumption. Let G be a group with order n, G ∈ G a generator and T ∈ Z n , T < n. For all PPT adversaries A it holds thatPr z $ ← {0..T -1}, z ← A (z • G) : z = z ≤ µ(λ)

  Enc ek (m; r m ), and -The authority and the user executes a standard three-move proof of knowledge of r with statistical security by picking the mask and the challenge in an appropriate set, where the user plays the role of the prover, and the authority of the verifier: • The user picks ρ $ ← [1..n/2 ] and sends G ← ρ • G to the authority. • The authority sends a random λ-bit challenge c. • The users computes and sends d ← r • c + ρ (over the integers). The authority accepts the interaction if and only if d • G = c • G r G , and furthermore d ≤ n/2 .

Table 1 .

 1 Comparison of our optimized NIKVAC to a direct construction from[START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] with the DVNIZK of[START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF].

	NIKVAC 1	CMZ+CC	This Work	This Work (optimized)
	Pseudonym Size	βn	(2β + 2)m	2βm
	Proof Size	(2β + 3)n + (6β + 2)m	(β + 2)n	(β + 2)n
	Prover Computation 2	(5β + 2)A + (3β + 1)(B + C)	(2β + 3)A	(2β + 3)A
	Assumption	GGM+IND-CPA	GGM+IND-CPA	GGM+IND-CPA + short-exp dlog
		(with Paillier) 1 attribute, group element length 2048, ciphertext size 4096
	Pseudonym Size	256 Byte	2048 Byte	1024 Byte
	Proof Size	5,38 kB	756 Byte	756 Byte
	Prover Computation	7A + 4(B + C)	5A	5A
	Assumption	GGM+Paillier	GGM+Paillier	GGM+Paillier + short-exp dlog

β attributes, group element length n, ciphertext size m

  ). A DVNIZK proof system Π = (Π.Setup, Π.KeyGen, Π.Prove, Π.Verify) for a family of languages L = {L crs } crs with relations R crs satisfies the (perfect, statistical) composable zero-knowledge property if for any crs ), there exists a probabilistic polynomial-time simulator Sim such that for any stateful adversary A ,

			(pk, vk)
	Pr	

$ ← Π.Setup(1 λ $

In[START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF], the size of the group must be equal to the size of the plaintext space of a DVNIZK-friendly encryption scheme, such as Paillier.

We consider a minimal setting where the prover shows possession of a valid credential with respect to an identity committed in a pseudonym known to the verifier. We use the GGM-based scheme of[START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] as the underlying algebraic MAC (the efficiency gain of our approach is essentially the same if one uses the DDH-based MAC of[START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF]).

A denotes the cost of an exponentiation in the group G, B denotes the cost of an encryption, C denotes the cost of an homomorphic scalar multiplication. We note that, under the short-exponent discrete logarithm assumptions, all exponentiations in G (resp. all homomorphic scalar multiplications) can be performed with exponents (resp. scalars) of length at most 256 bits.

The protocol depends highly on the chosen MAC scheme. Thus, we omit details in abstract instantiation.

The parameters (crs, pk, ipp M ) are fixed for all Φ ∈ Φ, since they do not depend on the particular choice of Φ.

In this proof, this refers to the first property of definition 14.

Note that we do not need to fix the represented elements yet.

If A outputs non-queried group elements, the success probability negligible.

This finally fixes our group elements represented as polynomials to real group elements.

Since P is a generator of G with overwhelming probability, P will most likely not be a non-trivial subgroup generator, but we show that if A is successful, such i must exist in the following.

We set vp = v mod p and check if (Fi -Fj)(vp) = 0. Since v and thus vp is chosen uniformly random and Fi -Fj = 0, the probability of this happening is bounded by deg(Fi -Fj)/p.

For each m ∈ Qver the queried polynomials are fixed.

The probability of F (mk1 + k0) = F , but (F (mk1 + k0))(v) = F (v) is negligible with the same argument as before.

anonymous credentials where the process of showing possession of a valid credential to a verifier requires sending a single message from the user to the verifier.

Proof. Let (pp, td) ← Θ.Setup(1 λ ), (m 1 , .., m l ) $ ← U, (sk, ipp) $ ← Θ.CredKeyGen(pp) and credIssue(sk, (m 1 , .., m l )). It follows that CredVerify(sk, (m 1 , .., m l ), cred) = 1 from the correctness of the MAC scheme M . Now, let (pp, td) ← Θ.Setup(1 λ ), Φ $ ← Φ, (m 1 , .., m l ) $ ← U with Φ(m 1 , .., m l ) = 1, (sk = (vk, k), ipp) $ ← Θ.CredKeyGen(pp) and cred $ ← Issue(sk, (m 1 , .., m l )). Let π $ ← Θ.Show(ipp, cred, (m 1 , .., m l ), Φ). Note that R k (cred, (m 1 , .., m l )) = 1 and thus Θ.ShowVerify(sk, π, Φ) = 1 by the completeness of Π Φ .

Theorem 4 (Unforgeability). The NIKVAC scheme Θ is unforgeable if M is unforgeable and Π Φ is (O 0 , O 1 )-knowledge-extractable for all Φ ∈ Φ.

Proof. Let A be a PPT adversary on the unforgeability of Θ. We build an adversary B which either breaks the unforgeability of M (so either the UF-CMVA or XUF-CMVA security) or the (O 0 , O 1 )-knowledge-extractability of Π Φ for some Φ ∈ Φ.

B receives (crs, pk, ipp M ) 3 and access to a proof verification oracle V Φ and an MAC issuing oracle O 0 (defined in section 6.1) from the (O 0 , O 1 )-knowledge-extractability 4 game with Π Φ for Φ ∈ Φ. B sends pp ← crs, ipp ← (pk, ipp M ) to A and gives access to the following issuing and verification oracle O:

By the second property of definition 14, V Φ (•) can be simulated only using O 1 without access to the secret key. Now, all answers to queries which require the secret MAC key can be computed using solely access to the MAC oracles. Note that B simulates the unforgeability game of Θ with overwhelming probability. At some point, if A is successful, he will output π, Φ such that the pair (π, Φ) verifies correclty and for all queried (m 1 , .., m l ) ∈ Q : Φ(m 1 , .., m l ) = 0. Subsequently, B forwards π to the (O 0 , O 1 )-knowledge-extractability game for Π Φ , which in turn forwards the extracted values (x 1 , w) to the MAC unforgeability game.

We now analyze the success probability of B assuming A is successful. If B won the (O 0 , O 1 )knowledge-extractability game, we are finished. In the other case, the MAC unforgeability game receives (x 1 = σ, w = (m 1 , .., m l )). Because A is successful, π verifies correctly with regards to Θ and thus also verifies correctly with regards to Π Φ . Because B failed the first game, it necessarily holds that R(σ, (m 1 , .., m l )) = 1. Since ∀(m 1 , .., m l ) ∈ Q : Φ(m 1 , .., m l ) = 0 and Φ(m 1 , .., m l ) = 1, it holds that (m 1 , .., m l ) / ∈ Q and σ verifies correctly. Thus, B breaks the unforgeability of M .

Theorem 5 (Anonymity). The NIKVAC scheme Θ is anonymous if Π Φ satisfies oblivious zeroknowledge.

Proof. Let A be an adversary on the anonymity of Θ. We construct an adversary B that breaks the oblivious zero-knowledge property of Π Φ for some Φ ∈ Φ with overwhelming probability if A is successful.

B receives crs, pk, vk from the zero-knowledge game with Π Φ for some arbitrary Φ ∈ Φ. Note that these values are independent of the particular choice of Φ. B then runs (k, ipp M ) $ ← M.KeyGen(crs) and sends pp ← crs, ipp ← (pk, ipp M ), sk ← (vk, k) to A . In turn, B receives (Φ, cred, (m 1 , .., m l )) from A . Next, B outputs (cred, (m 1 , .., m l ), k, ipp M ) to the oblivious zeroknowledge game for the now fixed Φ and receives π in return which he forwards to A . Note that B simulates the anonymity game with overwhelming probability. Also, R crs (sk, cred, (m 1 , .., m l )) = 1 ⇐⇒ CredVerify(sk, (m 1 , .., m l ), cred) = 1 ∧ Φ(m 1 , .., m l ). The simulation of π in the zeroknowledge game only uses ipp, sk, Φ and will thus be a simulation for the anonymity game. Otherwise, π is built honestly in both games and thus, if A is successful, B is successful with overwhelming probability.

A Classical Preliminaries

A.1 Preliminaries on Encryption Schemes

Definition 15. (Public-Key Encryption Scheme) A public-key encryption scheme S is a triple of PPT algorithms (S.KeyGen, S.Enc, S.Dec), such that -S.KeyGen(1 λ ), generates a pair (ek, dk), ek is the public encryption key and ek is the secret decryption key. We assume that ek specifies the ciphertext space C, the message space M, and the random source R; -S.Enc ek (m; r), given the message m ∈ M and some random coins r ∈ R, outputs a ciphertext c; -S.Dec dk (c), output a message m ∈ M; which satisfies the correctness and IND-CPA security properties defined below.

We extend in a natural way the algorithm Enc over vectors: for vectors m = (m i ) i ∈ Z * M and r = (r i ) i ∈ Z * R of the same size, S.Enc ek (m; r) denotes the vector (S.Enc ek (m i , r i )) i . We extend the algorithm Dec to vectors of ciphertexts in a similar way.

Definition 16 (Correctness of an Encryption Scheme).

A public-key encryption scheme S is correct if for any pair (ek, dk)

B Security of MAC GGM in Composite Order Groups

The DVNIZK scheme from [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] operates in composite order groups if instantiated with the Paillier encryption scheme. Since MAC GGM is only proven to be secure in prime order groups, we prove the following theorem. Definition 22. (MAC GGM in Composite Order Groups.) The modified version of MAC GGM with message length l functions as follows:

., l} and output key sk ← (k 0 , .., k l ) and issuer parameters ipp

Theorem 6 (XUF-CMVA Security of MAC GGM in Composite Order Groups). Let M be MAC GGM over a group G of composite order. Then M is XUF-CMVA-secure in the generic group model under the computational subgroup assumption.

Proof. We follow the proof strategy of [START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF] and only proof the theorem for l = 1 as well. Let A be a PPT adversary on the UF-CMVA security of MAC GGM in the generic group model and C a challenger for the CSG assumption. We show that if A outputs a forgery with non-negligible probability, we can win the game against C with non-negligible probability.

The challenger C computes pp = (G, n) $ ← Setup(1 λ ) for (n, (p, q)) $ ← Gen(1 λ ) and outputs (G, n) to us. Now, if we were to build the public MAC GGM parameters, we would perform the following steps: Let P $ ← G \ {0 G } which is a generator for G with overwhelming probability, we choose

Again, the probability of G, H being generators is overwhelming. In our simulation, we actually fix the exponents k 0 , k 1 , g, h after the interaction with the adversary A .

We count the queries to the group operation oracle with variable q G , the queries to the tag oracle with q T , the queries to the verification oracle with q V and the oracle to the special check oracle with q C . Note that a tag oracle query counts as two group operation queries. Since the adversary is polynomially bounded, it holds that c(q G + q V + q T + q C ) 2 max(p, q) is negligible for any constant c.

Subsequently, we already count the two group oracle queries of the tag oracle in q G . Let S ⊂ {0, 1} * with |S|≥ n. We identify group elements U ∈ G as (log P (U ) mod n) and represent them with random elements ζ $ ← S. The adversary only has access to this representation. Throughout the simulation, we maintain a list of polynomials F ∈ Z n [k 0 , k 1 , h, g, e 1 , .., e q T ] representing the group elements, encoded as ζ. The indeterminates e i represent the random choices from the tag oracle. Also, we remember messages for which a tag was issued in the list Q tag and messages that were queried in the verification oracle in Q ver . Also, we safe the queried group elements of the check oracle in Q check .

In the beginning, we give P, G, H, G 0 , H 1 to A , encoded as distinct strings

., e q T ] 5 . We simulate the oracles O for A as follows:

-X m ← S.Enc ek (m ; 0) (r m pk) = S.Enc ek (m ; -e • r m ).

We explain why the above simplified proof guarantees anonymity. In the anonymity game, we must exhibit a simulator which can generate a valid-looking proof of possession, without knowing the signed message m. The simulator will rely on the security of the blind issuance two-party protocol to simulate his interaction with the signing authority without knowing m. Then, to simulate the proof of credential possession, he simply pick (U , V ) at random, compute W honestly, and simulate the (X m , X m ) using the simulation strategy of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. Now, we argue that this is indistinguishable from an honest proof, using a sequence of games: Game 1. In the first game, the simulator still obtains (U, V ) by playing the blind issuance protocol honestly with m, and computes (U , V ) honestly from (U, V ). He uses the simulation strategy of [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF] to simulate the (X m , X m ) using the verification key vk. By the same argument as in [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF], this game is statistically indistinguishable from the real game.

Game 2. In this game, the simulator will now simulate the blind issuance protocol, without knowing m (hence he does not obtain (U, V )), and generates (U , V ) uniformly at random. Under the security of the two-party computation protocol for blind issuance, his interaction with the signing authority is indistinguishable from an interaction with an honest user. It remains to show that the simulated (U , V ) is indistinguishable from the real one. Note that in the previous game, we had

where U = z • U is random, and x = m + 2 r for an -bit message m and a padding r of size at most log nbits. We can rewrite this as

under the short exponent discrete logarithm assumption, the above is indistinguishable to

where r is now picked uniformly at random in Z n . But then, since r is uniformly random, the above V is distributed perfectly uniformly, which concludes the proof.

C.3 Blind Issuance

Generalizing to vectors of β attributes and an abstract MAC with α components, the above strategy reduces the size of a proof of credential possession from α(1 + β) + 1 group elements and 2(β + α) ciphertexts to α(1 + β) + 1 group elements and 2β ciphertexts. We now exhibit a very simple and efficient blind issuance protocol for the above padding-based strategy. The basic idea is that, because of the padding, the user can simply send G = x • G to the authority, with x = m + 2 r: under the DLSE assumption, this computationally hides the message m. Furthermore, it is straightforward to sign a message "in the exponent" with the abstract MAC: focusing for simplicity on MAC GGM , the authority would just need to compute (U,

, for a random exponent y. It is immediate to check that (U, V ) is a valid MAC signature on x; this issuance protocol is therefore extremely efficient, requiring only three group elements in total. This, however, raises an apparent issue: in many applications, the user will need to prove to the authority that the signed message is indeed m (if, for example, the authority only issues credentials for users with an identity known to him), but still cannot reveal x = m + 2 r to the authority (this would break anonymity when the user authenticate to some verifier). However, this message is only uniquely defined if the value r in x = m = 2 r is guaranteed to be smaller than n/2 ; proving that this is the case seems to require a range proof on r, which is typically very expensive. We observe that there is a very simple way around this issue: it only suffices here to guarantee that r is smaller than n/2 , but it is also fine to ask an honest user to choose a padding r which is smaller than that, as long as it is at least 2λ bits long. Therefore, we get the following simple solution:

-The user picks r