Malika Izabachène

Benoît Libert

Damien Vergnaud

Block-wise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes

Keywords: P-signatures, anonymous credentials, efficient attributes, non-interactive proofs, standard model

Anonymous credentials are protocols in which users obtain certificates from organizations and subsequently demonstrate their possession in such a way that transactions carried out by the same user cannot be linked. We present an anonymous credential scheme with noninteractive proofs of credential possession where credentials are associated with a number of attributes. Following recent results of Camenisch and Groß (CCS 2008), the proof simultaneously convinces the verifier that certified attributes satisfy a certain predicate. Our construction relies on a new kind of P-signature, termed block-wise P-signature, that allows a user to obtain a signature on a committed vector of messages and makes it possible to generate a short witness that serves as a proof that the signed vector satisfies the predicate. A non-interactive anonymous credential is obtained by combining our block-wise P-signature scheme with the Groth-Sahai proof system. It allows efficiently proving possession of a credential while simultaneously demonstrating that underlying attributes satisfy a predicate corresponding to the evaluation of inner products (and therefore disjunctions or polynomial evaluations). The security of our scheme is proved in the standard model under noninteractive assumptions.

Introduction

Introduced by Chaum [START_REF] Chaum | Security without identification: Transaction systems to make big brother obsolete[END_REF] and extensively studied in the last two decades (e.g. [17-19, 4, 3] and references therein) anonymous credential systems enable users to authenticate themselves in a privacy-preserving manner. In such a protocol, a user can prove that an organization has supplied him with a certificate in such

The work of this author was supported by the French ANR-07-TLCOM-04-COPRIM Project. This author acknowledges the Belgian Fund for Scientific Research for his "Chargé de recherches" fellowship and the BCRYPT Interuniversity Attraction Pole. The work of this author was supported by the French ANR-07-TCOM-013-04 PACE Project and by the European Commission through the ICT Program under Contract ICT-2007-216676 ECRYPT II.

a way that the request for a certificate cannot be linked to any of its proofs of possession and multiple proofs involving the same credential cannot be linked to each other. In many realistic applications, it is desirable to augment digital credentials with a number of user attributes (such as their citizenship, their birth date, their obtained degrees, . . . ) while allowing users to selectively disclose some of their attributes or efficiently prove properties about them without disclosing any other information. This problem was addressed by Camenisch and Groß [START_REF] Camenisch | Efficient Attributes for Anonymous Credentials[END_REF] who showed how to conveniently extend the Camenisch-Lysyanskaya construction [START_REF] Camenisch | An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation[END_REF][START_REF]A Signature Scheme with Efficient Protocols[END_REF] into an anonymous credential system with efficient attributes. In this paper, we consider similar problems in the context of non-interactive anonymous credentials in the standard model, as formalized in [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF].

Anonymous credential systems usually combine two essential components. The first one is a protocol allowing a user to obtain a signature from an organization on a committed value (which is typically the user's private key) by sending a commitment to the signer and eventually obtaining a signature on the message without leaking useful information on the latter. The second component is a proof of knowledge of a signature on a committed value. Namely, the prover holds a pair (m, σ), reveals a commitment c to m and demonstrates his possession of σ as a valid signature on m.

Prior Work. Camenisch and Lysyanskaya [START_REF] Camenisch | An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation[END_REF][START_REF]A Signature Scheme with Efficient Protocols[END_REF] used groups of hidden order and Fujisaki-Okamoto commitments [START_REF] Fujisaki | Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations[END_REF] to build the first practical realizations 10 years ago. Their approach was subsequently extended to groups of public order using bilinear maps [START_REF]Signature Schemes and Anonymous Credentials from Bilinear Maps[END_REF][START_REF] Akagi | An Efficient Anonymous Credential System[END_REF].

Until recently, all anonymous credential systems required users to engage in an interactive conversation with the verifier to convince him of their possession of a credential. While interaction can be removed using the Fiat-Shamir paradigm [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] and the random oracle model [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF], this methodology is limited to only give heuristic arguments in terms of security [START_REF] Goldwasser | On the (In)security of the Fiat-Shamir Paradigm[END_REF]. This motivated Belenkiy, Chase, Kohlweiss and Lysyanskaya [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF] to design non-interactive 1 anonymous credentials in the standard model -assuming a common reference string -using an underlying primitive named P-signature (as a shorthand for signatures with efficient Protocols). Their results were extended by [START_REF]Compact E-Cash and Simulatable VRFs Revisited[END_REF] (and, more recently, in [START_REF] Fuchsbauer | Commuting Signatures and Verifiable Encryption and an Application to Non-Interactively Delegatable Credentials[END_REF]) into non-interactive anonymous credential schemes supporting credential delegation.

Credentials Supporting Efficient Attributes. Users holding a number of certified attributes may be willing to selectively disclose a restricted number of their attributes while preserving their privacy and the secrecy of their other attributes. A natural approach is to extend classical anonymous credentials such as [START_REF] Camenisch | An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation[END_REF][START_REF]Signature Schemes and Anonymous Credentials from Bilinear Maps[END_REF] using generalizations of the Pedersen commitment [START_REF] Pedersen | Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[END_REF] allowing to commit to n attributes at once in groups of hidden order. However, disclosing a single specific attribute entails to commit to n -1 attributes so as to prove that one attribute matches the disclosed value and committed attributes are the remaining certified ones. The drawback of this technique is that each proof has linear size in the overall number of attributes.

To address this concern, Camenisch and Groß [START_REF] Camenisch | Efficient Attributes for Anonymous Credentials[END_REF] suggested a completely different technique consisting in encoding attributes as prime numbers. Basically, users first obtain a signature on two committed messages: the first one is the user's private key and the second one consists of the product of all users' attributes. Later on, when the user wants to prove his ownership of a credential containing a certain attribute, he just has to prove that this attribute divides the second committed message. Camenisch and Groß also showed how users can prove that they hold an attribute appearing in some public attribute list and how to handle negated statements (namely, prove that a certain attribute is not contained in their attribute set). They also showed how to extend their techniques and prove the conjunction or the disjunction of simple such atomic statements. Unfortunately, their techniques cannot be applied in the setting of non-interactive anonymous credentials as they inherently rely on groups of hidden order, which makes them hardly compatible with the Groth-Sahai proof systems [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] used in [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF][START_REF]Compact E-Cash and Simulatable VRFs Revisited[END_REF]. It turns out that efficiently handling attributes in this context requires new techniques to be worked out.

In [START_REF] Shahandashti | Threshold Attribute-Based Signatures and Their Application to Anonymous Credential Systems[END_REF], Shahandashti and Safavi-Naini used threshold attribute-based signatures [START_REF] Maji | Attribute-based signatures[END_REF] to construct attribute-based anonymous credentials where users can prove threshold predicates (i.e., the ownership of t-out-of-n public attributes). However, their construction requires interaction and is not meant to provide compact proofs, which is the focus of this paper.

Our Contribution. This paper presents an anonymous credential scheme allowing to non-interactively prove the possession of a credential associated with attributes that satisfy a given predicate without leaking any further information. To this end, we extend the approach of [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF] by introducing a new kind of P-signature termed block-wise P-signature. In a nutshell, such a primitive is a P-signature allowing a user to obtain a signature on a committed vector of messages (similarly to the multi-block P-signature of [START_REF]Compact E-Cash and Simulatable VRFs Revisited[END_REF]). Unlike [START_REF]Compact E-Cash and Simulatable VRFs Revisited[END_REF] however, our P-signature makes it possible for the user to generate a short NIZK argument (i.e., the size of which does not depend on the vector size) that serves as evidence that the signed vector satisfies a certain predicate.

Inspired by the work of Katz, Sahai, Waters [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF], we present a block-wise P-signature for predicates corresponding to the zero or non-zero evaluation of inner products (and therefore disjunctions or polynomial evaluations). By combining our block-wise P-signature with the Groth-Sahai methodology [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] as in [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], we readily obtain an efficient non-interactive anonymous credential supporting efficient attributes. By appropriately using the inner product with suitable attribute encodings, we notably obtain (1) an efficient way for users to prove that specific attributes appear in their attribute set; (2) a method for concisely proving the inclusion of one of their attributes in a public list; (3) short proofs that the certified attribute set contains a certain (exact or inexact) threshold of binary attributes (in a similar way, we can prove that a subset of the certified set is at most t binary attributes away from some public attribute set). Using a very small amount of interaction (namely, verifiers just have to send a challenge consisting of a short random value in Z p , where p is the group order), we can also handle conjunctions of atomic conditions and even more complex formulas such as CNF or DNF in two rounds. The non-interactivity property is unfortunately lost when we want to deal with CNF/DNF formulas but our solution still decreases the number of rounds w.r.t. traditional interactive constructions. Indeed, at least 3 rounds are needed in interactive proofs using Σ protocols.

The security of our scheme is proved in the standard model under noninteractive assumptions. Although our scheme does not perform as well as the Camenisch-Groß system (notably because, unlike [START_REF] Camenisch | Efficient Attributes for Anonymous Credentials[END_REF], we cannot prevent the public key size from depending on the number n of attributes), this yields the first result on non-interactive anonymous credentials with efficient attributes in the standard model. Like [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF][START_REF]Compact E-Cash and Simulatable VRFs Revisited[END_REF], we rely on a common reference string and only need interaction in the protocol allowing users to obtain their credentials (except for predicates involving conjunctions).

Organization. In section 2, we first give formal definitions of block-wise Funforgeable signatures (similarly to [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], we can only prove a relaxed form of unforgeability which suffices in this context) and block-wise P -signatures. Our realization for inner product relations is described in section 3. Its application to the realization of anonymous credentials with efficient attributes is detailed in the full version of the paper, where we also discuss the efficiency of the scheme and the kind of predicates that can be expressed using inner products.

Background and Definitions

Notations. We say that a function ν : N → [0, 1[ is negligible if for, any polynomial p(.), we have ν(λ) < |1/p(λ)| for any sufficiently large λ ∈ N. If A(x) B(y) denotes an interactive protocol between A and B on input x and y, respectively, and if participant A (resp. B) outputs a bit b ∈ {0, 1} after the execution of the protocol, we write b ⇐ A(x) B(y) (resp. A(x) B(y) ⇒ b).

Bilinear Maps and Complexity Assumptions

We consider bilinear groups (G, G T ) of prime order p with a mapping e : G×G → G T such that: (1) e(g a , h b ) = e(g, h) ab for any (g, h)

∈ G × G and a, b ∈ Z; (2) e(g, h) = 1 G T whenever g, h = 1 G . Definition 1 ([9]
). In a group G of prime order p, the Decision Linear Problem (DLIN) is to distinguish the distributions (g, g a , g b , g ac , g bd , g c+d ) and (g, g a , g b , g ac , g bd , g z ), with a, b, c, d, z R ← Z p . The Decision Linear Assumption is the intractability of DLIN for any PPT distinguisher D.

This problem is to decide if three vectors g 1 = (g a , 1, g), g 2 = (1, g b , g) and g 3 = (g ac , g bd , g z ) are linearly dependent (i.e., if z = c + d).

Like several previous P-signatures, our scheme uses the Hidden Strong Diffie-Hellman assumption [START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF] that strengthens a "q-type" assumption from [START_REF] Boneh | Short signatures without random oracles[END_REF].

Definition 2 ( [START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF]). The q-Hidden Strong Diffie-Hellman problem (q-HSDH) consists in, given (g, u, g ω ) ∈ G 3 and a set of q tuples (g 1/(ω+ci) , g ci , u ci ) with c 1 , . . . , c q R ← Z * p , finding (g 1/(ω+c) , g c , u c ) such that c = c i for i = 1, . . . , q. We also use the following problem, which is not easier than the problem, used in [START_REF] Kunz-Jacques | About the security of MTI/C0 and MQV[END_REF], of finding a pair (g µ , g µab ) ∈ (G\{1 G }) 2 given (g, g a , g b ) ∈ G 3 . Definition 3 ([32]). The Flexible Diffie-Hellman problem (FlexDH) in G is, given (g, g a , g b ) ∈ G 3 , where a, b R ← Z * p , to find a triple (g µ , g µa , g µab ) such that µ = 0. The paper will make use of two other problems. The first one was introducedin a potentially easier variant -in [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF].

Definition 4 ( [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF]). Let G be a group of prime order p. The n-Diffie-Hellman Exponent (n-DHE) problem is, given (g, g 1 , . . . , g n , g n+2 , . . . , g 2n ) ∈ G 2n such that g i = g (α i ) for each i ∈ [1, 2n]\{n + 1} and where α R ← Z * p , to compute the missing element g n+1 = g (α n+1 ) .

We finally need an assumption that strengthens the n-DHE assumption in the same way as the FlexDH assumption is a strengthening of the Diffie-Hellman assumption.

Definition 5. Let G be a group of prime order p. The Flexible n-Diffie-Hellman Exponent (n-FlexDHE) problem is, given (g, g 1 , . . . , g n , g n+2 , . . . , g 2n ) in G 2n such that g i = g (α i ) for each i ∈ [1, 2n]\{n + 1} and where α R ← Z * p , to compute a non-trivial triple (g µ , g µ n+1 , g µ 2n ) ∈ (G\{1 G }) 3 , for some µ ∈ Z * p and where g n+1 = g (α n+1 ) .

Evidence of the generic intractability of the n-FlexDHE assumption is provided in the full version of the paper.

Commitments to Vectors

We consider perfectly hiding commitments (VecCom, VecOpen) allowing to commit to vectors. In the following, we denote by V = VecCom( m; r) the result of committing to m = (m 1 , . . . , m n ) ∈ Z n p using randomness r R ← Z p . In addition, we require that commitments be openable in a coordinate-wise manner and call W = VecOpen( m, r, i) the opening of V in position i ∈ [1, n]. Such a pairingbased Pedersen-like commitment [START_REF] Pedersen | Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[END_REF], based on ideas from [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF][START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF], was described in [START_REF] Libert | Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs[END_REF]. The commitment key is (g, g 1 , . . . , g n , g n+2 , . . . , g 2n ) ∈ G 2n where

g i = g (α i ) for each i. To commit to a vector m = (m 1 , . . . , m n ), the committer picks r R ← Z p and computes V = g r • n j=1 g mj n+1-j . Thanks to the specific choice of {g i } i∈[1,2n]\{n+1} , W i = g r i • n j=1,j =i g mj n+1-j+i serves as evidence that m i is the i-th component of m as it satisfies the relation e(g i , V ) = e(g, W i ) • e(g 1 , g n ) mi .
The opening W i = VecOpen(V, m, r, i) at position i is easily seen not to reveal anything about other components of m. Moreover, the infeasibility of opening a commitment to two distinct messages for some coordinate i ∈ [1, n] relies on the n-DHE assumption.

Block-wise F-Unforgeable Signatures and P-Signatures

We begin by defining block-wise F-unforgeable signatures. As introduced in [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], F-unforgeability refers to the infeasibility for the adversary to craft a valid signature on some message m ∈ Z p while only outputting F (m), for some injective function F , instead of m itself. The need for such a relaxation stems from the limited extractability of Groth-Sahai proofs: in a nutshell, only g m is efficiently extractable from a commitment to m ∈ Z p using the trapdoor of the CRS.

For reasons that will become apparent later on, block-wise F-unforgeable signatures will be associated with two families of relations that we call R 1 and R 2 , respectively. These two families are not explicitly used in the following definition but they are handy when it comes to formalize security properties. Definition 6. Let D be a domain and let R 1 and R 2 be families of efficiently computable relations such that each

R ∈ R 1 ∪ R 2 is of the form R : [0, n] × D n × D n → {0, 1} for some n ∈ N. A block-wise signature for (R 1 , R 2 , D) con-
sists of a tuple Σ = (Setup, SigSetup, Sign, Verify, Witness-Gen, Witness-Verify) of algorithms with the following specifications.

Setup(λ): takes as input a security parameter λ and outputs a set of public parameters params. SigSetup(λ, n): takes as input a security parameter λ ∈ N and an integer n ∈ poly(λ) denoting the length of message vectors to be signed. It outputs a key pair (pk, sk). Sign(sk, m): is a (possibly randomized) algorithm that takes as input a private key sk and a vector m = (m 1 , . . . , m n ) of messages where m i ∈ D for i = 1 to n. It outputs a signature σ on m. Verify(pk, m, σ): is a deterministic algorithm that takes as input a public key pk, a signature σ and a message vector m = (m 1 , . . . , m n ). It outputs 1 if σ is deemed valid for m or 0 otherwise. Witness-Gen(pk, R, i, m, X, σ): takes as input a public key pk,

a relation R ∈ R 1 ∪ R 2 , an integer i ∈ [0, n], two distinct vectors m = (m 1 , . . . , m n ) ∈ D n and X = (x 1 , . . . , x n ) ∈ D n , and a signature σ. If Verify(pk, m, σ) = 0 or R(i, m, X) = 0, it outputs ⊥. Otherwise, it returns a witness W proving that σ is a signature on some m ∈ D n s.t. R(i, m, X) = 1. Witness-Verify(pk, R, i, X, W, σ): is a deterministic algorithm that takes in a public key pk, a relation R ∈ R 1 ∪R 2 , an integer i ∈ [0, n], a vector X ∈ D n , a witness W and a signature σ. It outputs 1 if W is deemed as convincing evidence that σ is a valid signature on some vector m = (m 1 , . . . , m n ) ∈ D n such that R(i, m, X) = 1.
Except Setup, these algorithms all implicitly take public parameters params as additional inputs. To lighten notations, we omit to explicitly write them.

The following security definitions consider two kinds of forger. The first one -which corresponds to case (i) in the definition -refers to attacks where the adversary outputs a new signature that was not legally obtained by invoking the signing oracle. The second one -captured by case (ii) -relates to forgeries where the adversary re-uses a signature (say σ j for some j ∈ {1, . . . , q}) that was produced by the signing oracle but manages to prove a property that is not satisfied by the signed vector m j .

In case (ii), we need to consider two families of relations. The first one is called R 1 and includes relations R 1 for which the adversary illegitimately proves that R 1 (i, m j , X ) = 1 and only outputs F ( X ) = (F (x 1 ), . . . , F (x n )). The second relation family R 2 comprises relations R 2 for which the adversary tricks the verifier into believing that R 2 (i, m j , X ) = 1 and explicitly outputs X = (x 1 , . . . , x n ) instead of F ( X ). We cannot consider a single relation family unifying both R 1 and R 2 because, for technical reasons, our security proof ceases to work if the adversary only outputs F ( X ) in the case of relations R 2 ∈ R 2 (as explained in the full version of the paper). At the same time, we also need relations R 1 ∈ R 1 because of the limited extractability properties of Groth-Sahai proofs.

In the notations of Definition 7, Υ ⊂ {1, . . . , n} denotes the smallest subset such that values {F (x t )} t∈Υ make it possible to verify that

X = (x 1 , . . . , x n ) satisfies R 1 (i, m, X) = 1. Definition 7. Let R 1 , R 2 be families of relations over [0, n] × D n × D n for some domain D. A block-wise signature scheme Σ is said to be (F, R 1 , R 2 )-
unforgeable for some efficiently computable injective function F (.), if any PPT adversary has negligible advantage in the following game:

1. The challenger runs SigSetup(λ, n), obtains (pk, sk) and sends pk to A. 2. Adversary A adaptively queries a signing oracle on up to q ∈ poly(λ) occasions. At each query j ∈ [1, q], A chooses a vector m = (m 1 , . . . , m n ) and obtains σ j = Sign(sk, m). 3. Eventually, A outputs a tuple (Pred , W , σ ) consisting of a predicate Pred , a witness W and a signature σ . The predicate Pred consists of a triple which is either of the form (R 1 , i, {F (x t )} t∈Υ ), for some subset Υ ⊂ {1, . . . , n} (i) σ was not the output of any signing query;

such that i ∈ Υ , or (R 2 , i, X ) where i ∈ [0, n] is an index, R 1 ∈ R 1 and R 2 ∈ R 1 ∪ R 2
(ii) σ = σ j , for some query j ∈ [1, q], but the queried m j = (m j,1 , . . . , m j,n )

was such that R 1 (i, m j , X ) = 0 (resp. R 2 (i, m j , X ) = 0) while the predicate Pred is of the form (R 1 , i, {F (x t )} t∈Υ ) (resp. (R 2 , i, X )
). The advantage of adversary A is its probability of being successful, taken over all random coins.

From a block-wise F-unforgeable signature, a full-fledged block-wise P-signature is obtained as specified by Definition 8. Definition 8. A block-wise P-signature combines a (F, R 1 , R 2 )-unforgeable blockwise signature with a vector commitment (VecCom, VecOpen), a perfectly binding commitment (Com, Open) and:

1

. An algorithm SigProve 1 pk, R 1 , i, Υ, σ, m = (m 1 , . . . , m n ), X = (x 1 , . . . , x n )
that, for some relation R 1 ∈ R 1 and some subset Υ ⊂ {1, . . . , n} such that i ∈ Υ , generates commitments {C xt } t∈Υ , C W , C σ and a NIZK proof

π ← NIZPK {x t in C xt } t∈Υ , W in C W , σ in C σ | {(W, {F (x t )} t∈Υ , σ) : ∃ m s.t. Verify(pk, m, σ) = 1 ∧ Witness-Verify(pk, R 1 , i, X, W, σ) = 1} ,
and the corresponding VerifyProof

1 (pk, R 1 , i, π, C σ , C W , {C xt } t∈Υ ) algorithm.
2. An algorithm SigProve 2 (pk, R, i, σ, m, X) that, for some relation

R ∈ R 1 ∪ R 2 , generates commitments C W , C σ and a proof π ← NIZPK W in C W , σ in C σ | {(W, σ) : ∃ m s.t. Verify(pk, m, σ) = 1 ∧ Witness-Verify(pk, R, i, X, W, σ) = 1}
with its corresponding VerifyProof 2 (pk, R, i, π, C σ , C W , X) algorithm.

3. A NIZK proof that two perfectly binding commitments open to the same value, i.e., an algorithm EqComProve outputting a proof of membership for the language

L = {(C, D) s.t. ∃ (x, y), (open x , open y ) | C = Com(x, open x ) ∧ D = Com(y, open y ) ∧ x = y}. 4. SigIssue sk, V , (m n1+1 , . . . , m n ) SigObtain(pk, m |n 1 , open m |n 1
) is an interactive protocol allowing a user to obtain a signature σ on the partially committed vector m = (m 1 , . . . , m n1 , m n1+1 , . . . , m n ) without letting the signer -whose input consists of V = VecCom( m |n 1 , r ), for some r , and an integer n 1 ∈ [1, n], and public messages (m n1+1 , . . . , m n ) -learn anything about m |n 1 = (m 1 , . . . , m n1 ).

In this definition, Υ ⊂ {1, . . . , n} is the smallest subset such that commitments {C xt } t∈Υ allow verifying the proof that the underlying vector X satisfies R 1 (i, m, X) = 1.

Unforgeability of P-signatures. To define the unforgeability of block-wise P-signatures, we shall assume that SigIssue SigObtain starts with the user U committing to a vector (m 1 , . . . , m n1 ) and interactively proving to the issuer his knowledge of an opening of the commitment. We require the existence of a knowledge extractor E A SigObtain that can extract the committed vector (m 1 , . . . , m n1 ) by rewinding the prover A. Since (VecCom, VecOpen) is a perfectly hiding commitment, this will be necessary to formalize the unforgeability of our P-signatures. We note that a similar approach was taken in [START_REF] Camenisch | Compact E-Cash[END_REF] to define specific security properties of e-cash systems. for some integer n ∈ poly(λ), and hands pk to A. 2. On up to q ∈ poly(λ) occasions, A triggers an execution of SigIssue SigObtain and acts as a user interacting with the SigIssue-executing challenger. At each such execution j ∈ [1, q], the challenger runs E A SigObtain so as to extract A's vector m j = (m j,1 , . . . , m j,n ) (or, more precisely, the restriction (m j,1 , . . . , m j,n1 ) to its first n 1 coordinates, for some n 1 ∈ [1, n]) and bookkeeps it. We denote by σ j the signature obtained by A at the end of the j-th execution of SigObtain. 3. A outputs commitments C σ , C W , a proof π and a statement claim consisting of a triple which is either of the form (R 1 , i,

Definition 9. A block-wise P-signature Σ is (F, R 1 , R 2 )-unforgeable, for re- lation families R 1 , R 2 ,
{C xt } t∈Υ ) or (R 2 , i, X), for some integer i ∈ [0, n], some relations R 1 ∈ R 1 or R 2 ∈ R 1 ∪ R 2 , some vector X = (x 1 , . . . , x n ) ∈ D n
or some commitments {C xt } t∈Υ -for some subset Υ ⊂ {1, . . . , n} -to elements x t ∈ D. The adversary is successful if: a. Exactly one of the following conditions is satisfied.

1. claim = (R 1 , i, {C xt } t∈Υ ) and VerifyProof 1 (pk, R 1 , i, π, C σ , C W , {C xt } t∈Υ ) = 1. 2. claim = (R 2 , i, X) and VerifyProof 2 (pk, R 2 , i, π, C σ , C W , X) = 1.
b. If we define Pred to be (R, i, {Extract(C xt )} t∈Υ ) in situation 1 and simply claim in situation 2, the triple Pred, Extract(C W ), Extract(C σ ) forms a successful forgery in the game of Definition 7 where the vectors m 1 , . . . , m q are those queried for signature.

The advantage of A is its success probability, taken over all coin tosses.

Belenkiy et al. [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF] formalized other security notions named signer privacy, user privacy and zero-knowledge that P-signatures ought to satisfy (formal definitions are given in the full version of the paper).

Signer Privacy. As formalized in [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], this notion captures that, during its interaction with the honest issuer, an adversary acting as a malicious user should not gain any side information beyond the obtained signature on a vector m = (

m |n 1 |(m n1+1 , . . . , m n )) ∈ D n .
More precisely, there must exist an efficient simulator SimIssue such that no PPT adversary A can tell whether it is running SigIssue SigObtain in interaction with a real issuer or if it is interacting with SimIssue that only has access to a signing oracle. As insisted in [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF], SimIssue is allowed to rewind A if necessary.

User Privacy. User privacy is also defined following [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF]. It requires that any malicious signer interacting with an honest user be unable to learn anything about the user's private messages m |n 1 ∈ D n1 . As previously, there must exist an efficient simulator SimObtain -which is allowed to rewind the adversary A -such that a dishonest signer A cannot distinguish a conversation with a real user from an interaction with SimObtain.

Zero Knowledge. To explain the zero-knowledge property, we introduce a simulator Sim = (SimSetup, SimSigProve 1 , SimSigProve 2 , SimEqComProve) that implements P-signature algorithms for generating parameters, proving statements involving some relation family R and proving the equality of commitment openings without using any secret.

If for all outputs (params s , τ ) of SimSetup, it holds that Com(params s , •) is now perfectly hiding, if params s are computationally indistinguishable from those produced by Setup, and if any PPT adversary cannot tell whether it is interacting with real algorithms (SigProve 1 , SigProve 2 , EqComProve) or simulators (SimSigProve 1 , SimSigProve 2 , SimEqComProve), the scheme is said zeroknowledge and it is guaranteed not to leak useful information about secret values.

Groth-Sahai Proofs

In the following notation, for equal-dimension vectors A and B containing exponents or group elements, A B stands for their component-wise product.

To simplify the description, our scheme uses Groth-Sahai proofs based on the DLIN assumption although instantiations based on the symmetric external Diffie-Hellman assumption are also possible. In the DLIN setting, the Groth-Sahai (GS) proof systems [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] use a common reference string comprising vectors

f 1 , f 2 , f 3 ∈ G 3 , where f 1 = (f 1 , 1, g), f 2 = (1, f 2 , g) for some f 1 , f 2 , g ∈ G. To commit to X ∈ G, one sets C = (1, 1, X) f 1 r f 2 s f 3 t with r, s, t R ← Z p . When
proofs should be perfectly sound, f 3 is set as

f 3 = f 1 ξ1 f 2 ξ2 with ξ 1 , ξ 2 R ← Z * p . Commitments C = (f r+ξ1t 1 , f s+ξ2t 2 , X • g r+s+t(ξ1+ξ2
) ) are then Boneh-Boyen-Shacham (BBS) ciphertexts [START_REF] Boneh | Short Group Signatures[END_REF] that can be decrypted using α 1 = log g (f 1 ), α 2 = log g (f 2 ). In the perfect witness indistinguishability (WI) setting, defin-

ing f 3 = f 1 ξ1 f 2 ξ2
(1, 1, g) -1 gives linearly independent ( f 1 , f 2 , f 3 ) and C is a perfectly hiding commitment. Under the DLIN assumption, the two settings are indistinguishable. In either case, the commitment is denoted by C = GSCom(X, open X ) and open X = (r, s, t) is its opening.

To commit to an exponent x ∈ Z p , one computes

C = ϕ x f 1 r f 2 s
, with r, s R ← Z * p , using a CRS comprising vectors ϕ, f 1 , f 2 . The commitment and its opening are denoted by C = GSCom(x, open x ) and open x = (r, s), respectively. In the soundness setting ϕ, f 1 , f 2 are linearly independent vectors (typically, one

chooses ϕ = f 3 (1, 1, g) where f 3 = f 1 ξ1 f 2 ξ2
) whereas, in the WI setting,

choosing ϕ = f 1 ξ1 f 2 ξ2
gives a perfectly hiding commitment since C is always a BBS encryption of 1 G . On a perfectly sound CRS (where

f 3 = f 1 ξ1 f 2 ξ2 and ϕ = f 3 (1, 1, g))
, commitments to exponents are not fully extractable since the trapdoor (α 1 , α 2 ) only allows recovering

g x from C = ϕ x f 1 r f 2 s
. In order to commit to x ∈ Z p , we will sometimes commit to the group element g x . The result of this process will be denoted by

C = GSCom (x, open x ) = GSCom(g x , open x )
with open x = (r, s, t).

To prove that committed variables satisfy a set of relations, the Groth-Sahai techniques require one commitment per variable and one proof element (made of a constant number of group elements) per relation. Such proofs are available for pairing-product relations, which are of the type

n i=1 e(A i , X i ) • n i=1 • n j=1 e(X i , X j ) aij = t T , for variables X 1 , . . . , X n ∈ G and constants t T ∈ G T , A 1 , . . . , A n ∈ G, a ij ∈ G, for i, j ∈ [1, n]. Efficient proofs also exist for multi-exponentiation equations m i=1 A yi i • n j=1 X bj j • m i=1 • n j=1 X yiγij j = T, for variables X 1 , . . . , X n ∈ G, y 1 , . . . , y m ∈ Z p and constants T, A 1 , . . . , A m ∈ G, b 1 , . . . , b n ∈ Z p and γ ij ∈ G, for i ∈ [1, m], j ∈ [1, n].
Multi-exponentiation equations admit zero-knowledge proofs at no additional cost. On a simulated CRS (prepared for the WI setting), the trapdoor (ξ 1 , ξ 2 ) makes it is possible to simulate proofs without knowing witnesses and simulated proofs are perfectly indistinguishable from real proofs. As for pairingproduct equations, NIZK proofs are often possible (this is typically the case when the target element t T has the special form t T = t i=1 e(S i , T i ), for constants {(S i , T i )} t i=1 and some t ∈ N) but usually come at some expense. From an efficiency standpoint, quadratic pairing product equations cost 9 elements to prove whereas linear ones (when a ij = 0 for all i, j) take 3 group elements. Linear multi-exponentiation equations of the type m i=1 A yi i = T demand 2 group elements.

A Construction for Inner Product Relations

As noted in [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF], many predicates can be expressed in terms of the inner product of two vectors of attributes. In this section, we describe a P-signature scheme for families (R 1 , R 2 ) where R 1 encompasses (in)-equality relations and R 2 relates to inner products. Namely, we set R 1 = {R EQ , R ¬EQ } and R 2 = {R IP , R ¬IP }, which are specified as follows. We let D = Z p , for some prime p and, for vectors m ∈ Z n p , X ∈ Z n p , the relations R IP and R ¬IP are only defined for i = 0 in such a way that R IP (0, m, X) = 1 (resp. R ¬IP (0, m, X) = 1) if and only if m • X = 0 (resp. m • X = 0). As for R 1 , we define relations R EQ and R ¬EQ for i ∈ [1, n] and so that R EQ (i, m, X) = 1 (resp. R ¬EQ (i, m, X) = 1) if and only if m i = x i (resp.

m i = x i ).
The construction is based on the commitment scheme of section 2.2 and a signature scheme suggested in [START_REF] Cathalo | Group Encryption: Non-Interactive Realization in the Standard Model[END_REF] to sign group elements. The intuition is to sign a commitment to a vector m using a signature scheme for group elements such as [START_REF] Cathalo | Group Encryption: Non-Interactive Realization in the Standard Model[END_REF][START_REF] Fuchsbauer | Automorphic Signatures in Bilinear Groups and an Application to Round-Optimal Blind Signatures[END_REF][START_REF] Abe | Structure-Preserving Signatures and Commitments to Group Elements[END_REF]. Here, a lightweight version of the scheme can be used since, in the proof, the simulator knows the discrete logarithms of the group elements that are signed (hence, there is no need to combine the scheme with a trapdoor commitment to group elements as in [START_REF] Cathalo | Group Encryption: Non-Interactive Realization in the Standard Model[END_REF]). In this simplified version, the signer holds a public key comprising (Ω = g ω , A = g γ , u, U 0 , U 1 = g β1 ) ∈ G 5 , for private elements (ω, γ, β 1 ). To sign a vector m, the signer first computes a commitment V to m, chooses c R ← Z p and computes σ 1 = (g γ ) 1/(ω+c) , σ 2 = g c , σ 3 = u c , σ 4 = (U 0 • V β1 ) c , σ 5 = V c and also sets σ 6 = V as part of the signature.

The construction handles inner products using the properties of the commitment scheme recalled in section 2.2. More precisely, we use the property that this scheme allows the committer to generate a short non-interactive argument allowing to convince the verifier that the committed vector m is orthogonal to a public vector X = (x 1 , . . . , x n ) without revealing anything else. Concretely, given a commitment

C = g r • n j=1 g mj n+1-j to m = (m 1 , . . . , m n ), for each i ∈ [1, n],
we know that the witness

W i = g r i • n j=1,j =i g mj n+1-j+i satisfies e(g i , C) = e(g 1 , g n ) mi • e(g, W i ), (1)
For each i, if we raise both members of (1) to the power x i and multiply the resulting n equations altogether, we find

e n i=1 g xi i , C = e(g 1 , g n ) m• X • e g, n i=1 W xi i , (2)
which implies e Likewise, the committer can also convince the verifier that m • X = 0 by proving knowledge of group elements

W = n i=1 W xi i , W 1 = g m• X 1 ∈ G such that e n i=1 g xi i , C = e(W 1 , g n ) • e(g, W ). (3)
To convince the verifier that W 1 = 1 G , the prover demonstrates knowledge of another group element W 0 = g 1/ m• X for which e(W 0 , W 1 ) = e(g, g 1 ). We would like to argue that a malicious committer cannot open a commitment C to a vector m such that m • X = 0 and also produce (W, W 0 , W 1 ) ∈ G such that the equalities e(W 0 , W 1 ) = e(g, g 1 ) and (3) are both satisfied. Unfortunately, this is not true since a cheating prover can commit to m = 0 (which is orthogonal to everything). Since the commitment C = g r and the value W =

(W 0 , W 1 , W ) = g 1/µ
1 , g µ , W/g µ n , with µ R ← Z p , which satisfies the equalities e(W 0 , W 1 ) = e(g, g 1 ) and e( n i=1 g xi i , C) = e(W 1 , g n ) • e(g, W ). To address this problem, we require the prover to additionally reveal the pair (W 2 , W 3 ) = (g m• X , g m• X 2n ) when stating that m • X = 0. The extra checks e(W 1 , g) = e(g 1 , W 2 ) and e(W 1 , g 2n ) = e(g 1 , W 3 ) then suffice to convince the verifier. Under the n-FlexDHE assumption, we can show (as detailed in the full version of the paper) that the prover cannot generate (W 0 , W 1 , W 2 , W 3 , W ) and subsequently open the commitment to a vector m that contradicts the assertion.

In details, the F-unforgeable block-wise signature scheme is as follows.

Setup(λ): chooses bilinear groups (G, G T ) with a generator g R ← G. It generates a perfectly sound Groth-Sahai CRS f = ( f 1 , f 2 , f 3 ). Public parameters con- sist of params := (G, G T ), g, f . SigSetup(λ, n): picks γ, ω, α, β 1 R ← Z p , u, U 0 R ← G at random and computes Ω = g ω , A = g γ , U 1 = g β1 as well as g i = g (α i ) for each i ∈ [1, n] ∪ [n + 2, 2n].
The private key is sk = (γ, ω, β 1 ) and the corresponding public key is defined to be pk

= u, Ω = g ω , A = g γ , U 0 , U 1 , {g i } i∈[1,2n]\{n+1} .
Sign(sk, m): to sign m = (m 1 , . . . , m n ), conduct the following steps.

1. Pick r R ← Z p and compute V = g r • n j=1 g mj n+1-j = g m1 n • • • g mn 1 • g r . 2. Choose c R ← Z p and compute σ 1 = g γ/(ω+c) , σ 2 = g c , σ 3 = u c , σ 4 = (U 0 • V β1 ) c , σ 5 = V c , σ 6 = V
and output σ = (σ 1 , σ 2 , σ 3 , σ 4 , σ 5 , σ 6 , r).

Verify(pk, m, σ): parse σ as (σ 1 , σ 2 , σ 3 , σ 4 , σ 5 , σ 6 , r) and m as (m 1 , . . . , m n ).

1. Return 0 if the following equalities do not hold

e(A, g) = e(σ 1 , Ω • σ 2 ), e(u, σ 2 ) = e(σ 3 , g), (4)
e(g, σ 4 ) = e(U 0 , σ 2 ) • e(U 1 , σ 5 ), e(g, σ 5 ) = e(σ 6 , σ 2 ). ( 5)

2. Return 1 if σ 6 = g r • n j=1 g mj n+1-j and 0 otherwise. Witness-Gen(pk, R, i, m, X, σ): parse σ as (σ 1 , σ 2 , σ 3 , σ 4 , σ 5 , σ 6 , r). Parse m and X as (m 1 , . . . , m n ) and (x 1 , . . . , x n ), respectively. Return ⊥ if it turns out that Verify(pk, m, σ) = 0. Otherwise,

a. If R = R EQ (and i ∈ [1, n]), return ⊥ if m i = x i .
Otherwise, compute and output the witness

W = g r i • n j=1,j =i g mj n+1-j+i . b. If R = R ¬EQ (and i ∈ [1, n]), return ⊥ if m i = x i . Otherwise, compute W 0 = g 1/(mi-xi) , W 1 = g mi-xi 1 , W 2 = g mi-xi , W 3 = g mi-xi
= (W 0 , W 1 , W 2 , W 3 , W 4 ). c. If R = R IP (and i = 0), return ⊥ if m • X = 0. Otherwise, compute W i = g r i •
n j=1,j =i g mj n+1-j+i for i = 1 to n. Then, compute and output the witness

W = n i=1 W xi i . d. If R = R ¬IP (and i = 0), return ⊥ if m • X = 0. Otherwise, compute W 0 = g 1/( m• X) , W 1 = g m• X 1 , W 2 = g m• X , W 3 = g m• X 2n . For i = 1 to n, compute W 4,i = g r i • n j=1,j =i g mj n+1-j+i and finally set W 4 = n i=1 W xi 4,i . Return the witness W = (W 0 , W 1 , W 2 , W 3 , W 4 ).
Witness-Verify(pk, R, i, X, W, σ): parse σ as (σ 1 , σ 2 , σ 3 , σ 4 , σ 5 , σ 6 , r) and X as (x 1 , . . . , x n ). Return 0 if equations ( 4)-( 5 ) and e(W 0 , W 1 ) = e(g, g 1 ), e(W 1 , g) = e(g 1 , W 2 ),

e(W 1 , g 2n ) = e(g 1 , W 3 ).

The correctness of algorithms Sign and Verify is almost straightforward and that of Witness-Gen and Witness-Verify follows from the properties of the commitment scheme in section 2.2.

P-Signature Protocols. To obtain a complete P-signature, the scheme is augmented with algorithms SigProve i , for i ∈ {1, 2}, and EqComProve.

SigProve 1 (pk, R, i, Υ = {i}, σ, m, X): parse σ as (σ 1 , σ 2 , σ 3 , σ 4 , σ 5 , σ 6 , r), m as (m 1 , . . . , m n ) and X as (x 1 , . . . , x n ). Then, compute Groth-Sahai commitments { C xt,j = GSCom(X t,j , open xt,j )} t∈Υ,j∈{1,2,3} to the variables

{(X t,1 , X t,2 , X t,3 ) = (g xt 1 , g xt , g xt 2n )} t∈Υ .
For j = 1 to 6, compute C σj = GSCom(σ j , open σj ) and generate a NIZK proof that committed variables {σ j } 6 j=1 satisfy (4)-( 5). This requires to introduce auxiliary variables σ 7 ∈ G, θ 1 ∈ Z p with their own commitments

e(g, σ 4 ) = e(U 0 , σ 2 ) • e(U 1 , σ 5 ), e(g, σ 5 ) = e(σ 6 , σ 2 ), ( 9)

θ 1 = 1, e(A/σ 7 , g θ1 ) = 1 G T (10)
Let π σ be the proof for ( 8)- [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF]. Then, the algorithm considers two cases.

-

If R = R EQ , let C W = GSCom(W, open W ),
where the witness W is obtained as W = Witness-Gen(pk, R EQ , i, m, X, σ). Generate proofs π xi , {π Xt,j } t∈Υ,j=1,2 that committed variables σ 6 , W and X i,1 satisfy e(g i , σ 6 ) = e(X i,1 , g n ) • e(g, W ), [START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF] e(X i,2 , g 1 ) = e(X i,1 , g), e(X i,2 , g 2n ) = e(X i,3 , g).

The final proof is

π = { C xt,j } t∈Υ,j∈{1,2,3} , { C σj } 7 j=1 , C W , C θ1 , π σ , π xi , {π Xt,j } t∈Υ,j=1 ,2 .
-If R = R ¬EQ , generate commitments {C Wj } 4 j=0 to the components of the witness (W 0 , W 1 , W 2 , W 3 , W 4 ) ← Witness-Gen(pk, R ¬EQ , i, m, X, σ). Generate proofs π xi , π W for relations [START_REF] Camenisch | A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks[END_REF] and ( 14)

e(g i , σ 6 ) • e(X i,1 , g n ) -1 = e(W 1 , g n ) • e(g, W 4 ) (13)
e(W 0 , W 1 ) = e(g, g 1 ) ( 14)

e(W 1 , g) = e(g 1 , W 2 )
e(W 1 , g 2n ) = e(g 1 , W 3 ), and proofs {π Xt,j } t∈Υ,j=1,2 that {(X t,1 , X t,2 , X t,3 )} t∈Υ satisfy [START_REF] Camenisch | Efficient Protocols for Set Membership and Range Proofs[END_REF]. The final proof consists of

π = { C xt,j } t∈Υ,j∈{1,2,3} { C σj } 7 j=1 , { C Wi } 4 j=0 , C θ1 , π σ , π xi , π W , {π Xt,j } t∈Υ,j=1,2 .
SigProve 2 (pk, R, i, σ, m, X): parse σ and m as previously and X as (x 1 , . . . , x n ). For i = 1 to 6, compute commitments

C σi = GSCom(σ i , open σi ). Using extra variables σ 7 ∈ G, θ 1 ∈ Z p and their commitments C σ7 = GSCom(σ 7 , open σ7 ), C θ1 = GSCom(θ 1 , open θ1
), generate a NIZK proof that {σ i } 6 i=1 satisfy (4)-( 5). We call π σ the proof for ( 8)- [START_REF] Boneh | Collusion-Resistant Broadcast Encryption with Short Ciphertexts and Private Keys[END_REF]. Then, consider the two following cases.

-

If R = R IP , set C W = GSCom(W, open W ),
where the witness W is computed as W = Witness-Gen(pk, R IP , 0, m, X, σ). Then, generate a proof π X that W and σ 6 satisfy e(

The NIZK proof is π

= { C σj } 7 j=1 , C W , C θ1 , π σ , π X .
-If R = R ¬IP , define the auxiliary variable Θ = g ∈ G and generate

C Θ = GSCom(Θ, open Θ ), { C Wj = GSCom(W j , open Wj )} 4 j=0
, where {W j } 4 j=0 ← Witness-Gen(pk, R ¬IP , 0, m, X, σ). Then, generate a proof π NOT X that Θ and {W i } 4

i=0 satisfy e(W 0 , W 1 ) = e(Θ, g 1 ), e(W 1 , g) = e(g 1 , W 2 ), ( 16)

e(W 1 , g 2n ) = e(g 1 , W 3 ), e(Θ/g, g θ1 ) = 1 G T . (17) e
( n j=1 g xj j , σ 6 ) = e(g, W 4 ) • e(W 1 , g n ). (18)
The NIZK proof consists of π

= { C σj } 7 j=1 , { C Wj } 4 j=0 , C θ1 , π σ , π NOT X . -If R = R EQ (and i ∈ [1, n]), generate C W = GSCom(W, open W ) for the witness W ← Witness-Gen(pk, R EQ , i, m, X, σ), introduces a commit- ment C Xi = GSCom(X i , open Xi ) to the auxiliary variable X i = g xi 1 and compute proofs π W and π xi that e(g i , σ 6 ) = e(X i , g n ) • e(g, W ) e(X i /g xi 1 , g θ1 ) = 1 G T (19)
The proof is π

= { C σj } 7 j=1 , C W , C Xi , C θ1 , π σ , π W , π xi . -If R = R ¬EQ (and thus i ∈ [1, n]), compute Groth-Sahai commitments { C Wj = GSCom(W j , open Wj )} 4 j=0
to the components of the witness {W j } 4 j=0 ← Witness-Gen(pk, R ¬EQ , i, m, X, σ). Then, introduce a commitment C Xi = GSCom(X i , open Xi ) to the auxiliary variable X i = g xi 1 and generate proofs (π Xi,W , {π Wj } 3 j=1 , π Xi , π Θ ) for

e(g i , σ 6 ) • e(X i , g n ) -1 = e(W 1 , g n ) • e(g, W ), (20)
e(W 0 , W 1 ) = e(Θ, g 1 ),

(W 1 , g) = e(g 1 , W 2 ), e(W 1 , g 2n ) = e(g 1 , W 3 ), e(X i /g xi 1 , g θ1 ) = e(Θ/g, g θ1 ) = 1 G T ( (21) e
) 22
The proof is

π = { C σj } 7 j=1 , { C Wj } 4 j=0 , C Xi , C θ1 , π σ , π Xi,W , {π Wj } 3 j=1 , π Xi , π Θ . SigIssue sk, V , (m n1+1 , . . . , m n ) SigObtain(pk, m |n 1 , open m |n 1
): the user U and the issuer interact with each other in the following way.

The issuer sets

V = V • n j=n1+1 g mj n+1-j . Then, it randomly chooses c, r R ← Z p , computes σ 1 = g γ/(ω+c) , σ 2 = g c , σ 3 = u c and σ 4 = U 0 • (V • g r ) β1 c , σ 5 = (V • g r ) c , σ 6 = V • g r
and returns σ = (σ 1 , σ 2 , σ 3 , σ 4 , σ 5 , σ 6 ) and r .

3. U outputs σ = (σ 1 , σ 2 , σ 3 , σ 4 , σ 5 , σ 6 , r), where r = r + r .

The algorithm EqComProve is standard:

given two distinct Groth-Sahai com- mitments C X = GSCom(X, open X ) and C Y = GSCom(Y, open Y ) such that X = Y ∈ G, the NIZK proof can be a proof that C X C Y -1 is a com- mitment that opens to 1 G . If we write f 1 = (f 1 , 1, g), f 2 = (1, f 2 , g) and f 3 = (f 31 , f 32 , f 33 ), this amounts to proving the existence of (ρ 1 , ρ 2 , ρ 3 ) ∈ Z 3 p such that C X C Y -1 = (f ρ1 1 •f ρ3 31 , f ρ2 2 •f ρ3 32 , g ρ1+ρ2 •f ρ3 33
). On a simulated CRS, this relation can always be proved in NIZK since it is a linear multi-exponentiation equation.

Efficiency. From an efficiency standpoint, the outputs of SigProve 1 consist of 80 elements of G for R EQ and 101 group elements for R ¬EQ . Each proof produced by SigProve 2 requires less than 80 group elements for relations R EQ and R IP and at most 107 elements in the case of R ¬EQ and R ¬IP .

When these proofs are combined to prove the ownership of a credential, they result in non-interactive proofs demanding about 2 kB at the 80-bit security level. A detailed efficiency analysis is provided in the full version of the paper.

We leave it as an open problem to eliminate the dependency on n in the public key size (as was done in [START_REF] Camenisch | Efficient Attributes for Anonymous Credentials[END_REF]) without using interaction or random oracles.

Security. The security of the scheme relies on the assumptions described at the beginning of section 2. The proofs of the following theorems are given in the full version of the paper.

Theorem 1. If the HSDH, FlexDH and n-FlexDHE assumptions hold in G, the above block-wise P-signature scheme is (F, R 1 , R 2 )-unforgeable w.r.t. the injective function F (m) = (g m 1 , g m , g m 2n ) and the relations families R 1 = {R EQ , R ¬EQ }, R 2 = {R IP , R ¬IP }.

Theorem 2. The block-wise P-signature provides signer and user privacy if the underlying WI proof of knowledge is secure.

Theorem 3. The block-wise P-signature is zero-knowledge if the DLIN assumption holds in G.

Non-Interactive Anonymous Credentials with Efficient Attributes

In the full version of the paper, we provide the complete details about how block-wise P-signatures for these relation families can be generically turned into non-interactive anonymous credentials with efficient attributes. Proper security definitions for these are given in the full paper, where we prove the security of the generic construction in the same way as in [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF]. In a nutshell, the construction appeals to SigProve 1 to prove that the first component of the user's certified vector m is the same value (i.e., his private key sk U ) as the one contained in the user's pseudonym. Then, SigProve 2 is used to convince the verifier that the certified vector X satisfies m • X = 0. The construction is presented without optimizations for the sake of generality. Its optimized variant provides proofs of about 2 kB.

In the full version, we describe in details the predicates that can be expressed using inner product relations and suitable attribute encodings (already used in [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF]). For example, when m contains the coefficients a polynomial whose roots are the user's attributes, the inclusion (or the non-inclusion) of some attribute ω ∈ Z p can be selectively demonstrated by setting the coordinates of X as (1, ω, . . . , ω n-1 ). A similar technique can be used to prove that some certified attribute ω (this time encoded as a sub-vector (1, ω, . . . , ω n-1 ) of m) lies in a public list (or not) by proving its orthogonality to some X that contains the coefficients of a polynomial.

Using more complex attribute encodings, inner products can also handle disjunctions of a small (e.g., logarithmic in λ) number of atomic conditions. If we assume only two rounds of interaction, conjunctions can also be dealt with: the verifier just has to send a short random challenge in Z p which is used to randomize the vector X in such a way that the condition m• X = 0 guarantees the validity of assertions (m 1 = x 1 )∧. . .∧(m n = x n ) with overwhelming probability. Although the need for interaction seems at odds with the original motivation of P-signatures, we still gain something since only two rounds are necessary.

Finally, as already noted in [START_REF] Katz | Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products[END_REF], inner products also provide a method to prove exact threshold statements about sets of binary attributes. For example, if m and X encode two sets of binary attributes (such as "gender", "graduated", etc.) X and S, the prover can convince the verifier that |S ∩ X| = t. In addition, by combining the same technique with set membership proofs [START_REF] Camenisch | Efficient Protocols for Set Membership and Range Proofs[END_REF], statements about inexact thresholds |S ∩ X| ≤ t can also be proved as detailed in the full version.

  are relations and X = (x 1 , . . . , x n ) ∈ D n is a vector. The adversary wins if: (a) Witness-Verify(pk, R, i, X , W , σ ) = 1. (b) It holds that either:

  if there are efficient algorithms (ExtractSetup, Extract) s.t. (i) the output distributions of Setup and ExtractSetup are statistically close; (ii) any PPT algorithm A has negligible advantage in the following game:1. The challenger runs params ← ExtractSetup(λ) and (sk, pk) ← SigSetup(λ, n),

  X = 0. As it turns out, a single group element W = n i=1 W xi i suffices to convince the verifier that m • X = 0. It can be showed (as in detailed in the full version of the paper) that, after the commitment phase, if the committer is able to produce a witness W satisfying e n i=1 g xi i , C = e g, W and subsequently open the commitment C to a vector m such that m • X = 0, the n-DHE assumption can be broken.

  i , C) = e(g, W ), the prover can fool the verifier by revealing

  . Return the witness consisting of the tuple W

C

  σ7 = GSCom(σ 7 , open σ7 ), C θ1 = GSCom(θ 1 , open θ1 ) and to prove that e(σ 7 , g) = e(σ 1 , Ω • σ 2 ), e(u, σ 2 ) = e(σ 3 , g),

  [START_REF] Bellare | Random oracles are practical: A paradigm for designing efficient protocols[END_REF] ) = e(g, W ).

1 .

 1 U commits to m |n 1 = (m 1 , . . . , m n1 ) and computes V = g r • n1 j=1 g mj n+1-j , where r R ← Z p , retains open m |n 1 = (m 1 , . . . , m n1 , r ) and provides the issuer with an interactive WI proof of knowledge of (m 1 , . . . , m n1 , r ) such that V = g r •

  ) are not satisfied. Otherwise, two cases are distinguished.a. If R = R EQ (and i ∈ [1, n]), return 1 iff e(g i , σ 6 ) = e(g 1 , g n ) xi • e(g, W ). b. If R = R ¬EQ (and i ∈ [1, n]), parse W as (W 0 , W 1 , W 2 , W 3 , W 4 ) ∈ G 5and return ⊥ if it does not parse properly. Otherwise, return 1 if and only if e g i , σ6 • g -xi n+1-i = e(W 1 , g n ) • e(g, W 4 ) and 2 e(W 0 , W 1 ) = e(g, g 1 ), e(W 1 , g) = e(g 1 , W 2 ),(6)e(W 1 , g 2n ) = e(g 1 , W 3 ).c. If R = R IP (and i = 0), parse the witness W as a group element W ∈ G and return 1 if and only if e(g, W ) = e ¬IP (and i = 0), parse W as (W 0 , W 1 , W 2 , W 3 , W 4 ) ∈ G 5 and return ⊥ if it does not parse properly. Return 1 if and only if e n i=1 g xi i , σ 6 = e(W 1 , g n ) • e(g, W 4

	n i=1 g xi i , σ 6 .
	d. If R = R

The protocol for obtaining a signature on a committed message still demands interaction but the proving phase, which is usually more frequently executed, consists of one message from the prover to the verifier.

Looking ahead, W0 will be useful to convince the verifier (via the first relation of[START_REF] Blazy | Batch Groth-Sahai[END_REF]) that W1 = 1 G when (W1, W2, W3, W4) will appear in committed form within Groth-Sahai proofs produced by SigProve 2 . Although W0 is not strictly necessary in Witness-Verify in the cases R = R ¬IP and R = R ¬EQ (since the algorithm can directly check that W1 = 1 G ), we included it among the outputs of Witness-Gen for ease of explanation.