Benoît Libert

Damien Vergnaud

Group Signatures with Verifier-Local Revocation and Backward Unlinkability in the Standard Model

Keywords: Group signatures, verifier-local revocation, bilinear maps, backward unlinkability, standard model

Group signatures allow users to anonymously sign messages in the name of a group. Membership revocation has always been a critical issue in such systems. In 2004, Boneh and Shacham formalized the concept of group signatures with verifier-local revocation where revocation messages are only sent to signature verifiers (as opposed to both signers and verifiers). This paper presents an efficient verifier-local revocation group signature (VLR-GS) providing backward unlinkability (i.e. previously issued signatures remain anonymous even after the signer's revocation) with a security proof in the standard model (i.e. without resorting to the random oracle heuristic).

Introduction

The group signature primitive, as introduced by Chaum and van Heyst in 1991 [START_REF] Chaum | Group Signatures[END_REF], allows members of a group to sign messages, while hiding their identity within a population group members administered by a group manager. At the same time, it must be possible for a tracing authority holding some trapdoor information to "open" signatures and find out which group members are their originator. A major issue in group signatures is the revocation of users whose membership should be cancelled: disabling the signing capability of misbehaving members (or honest users who intentionally leave the group) without affecting remaining members happens to be a highly non-trivial problem. In 2004, Boneh and Shacham [START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF] formalized the concept of group signatures with verifier-local revocation where revocation messages are only sent to signature verifiers (as opposed to both signers and verifiers). This paper describes the first efficient verifier-local revocation group signature scheme providing backward unlinkability (i.e., previously issued signatures remain anonymous even after the signer's revocation) whose proof of security does not hinge upon the random oracle heuristic.

Related Work

Group signatures. Many group signatures were proposed in the nineties, the first provably coalition-resistant proposal being the famous ACJT scheme [START_REF] Ateniese | A Practical and Provably Secure Coalition-Resistant Group Signature Scheme[END_REF] proposed by Ateniese, Camenisch, Joye and Tsudik in 2000. The last few years saw the appearance of new constructions using bilinear maps [START_REF] Boneh | Short Group Signatures[END_REF][START_REF] Nguyen | Efficient and Provably Secure Trapdoor-Free Group Signature Schemes from Bilinear Pairings[END_REF][START_REF] Furukawa | An Efficient Group Signature Scheme from Bilinear Maps[END_REF][START_REF] Delerablée | Dynamic Fully Anonymous Short Group Signatures[END_REF]. Among these, the Boneh-Boyen-Shacham scheme [START_REF] Boneh | Short Group Signatures[END_REF] was the first one to offer signatures shorter than 200 bytes using the Strong Diffie-Hellman assumption [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF]. Its security was analyzed using random oracles [START_REF] Bellare | Random Oracles are Practical: A Paradigm for Designing Efficient Protocols[END_REF] in the model of Bellare, Micciancio and Warinschi [START_REF] Bellare | Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions[END_REF] (BMW) which captures all the requirements of group signatures in three welldefined properties.

The BMW model, which assumes static groups where no new member can be introduced after the setup phase, was independently extended by Kiayias and Yung [START_REF] Kiayias | Group Signatures: Provable Security, Efficient Constructions and Anonymity from Trapdoor-Holders[END_REF] and Bellare-Shi-Zhang [START_REF] Bellare | Foundations of Group Signatures: The Case of Dynamic Groups[END_REF] to a dynamic setting. In these models (that are very close to each other), efficient pairing-based schemes were put forth by Nguyen and Safavi-Naini [START_REF] Nguyen | Efficient and Provably Secure Trapdoor-Free Group Signature Schemes from Bilinear Pairings[END_REF], Furukawa and Imai [START_REF] Furukawa | An Efficient Group Signature Scheme from Bilinear Maps[END_REF] and, later on, by Delerablée and Pointcheval [START_REF] Delerablée | Dynamic Fully Anonymous Short Group Signatures[END_REF]. In dynamically growing groups, Ateniese et al. [START_REF] Ateniese | Practical Group Signatures without Random Oracles[END_REF] also proposed a construction without random oracles offering a competitive efficiency at the expense of a security resting on interactive assumptions that are not efficiently falsifiable [START_REF] Naor | On Cryptographic Assumptions and Challenges[END_REF]. Another standard model proposal was put forth (and subsequently improved [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF]) by Boyen-Waters [START_REF] Boyen | Compact Group Signatures Without Random Oracles[END_REF] in the static model from [START_REF] Bellare | Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions[END_REF] under more classical assumptions. Groth [START_REF] Groth | Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures[END_REF] described a scheme with constant-size signatures without random oracles in the dynamic model [START_REF] Bellare | Foundations of Group Signatures: The Case of Dynamic Groups[END_REF] but signatures were still too long for practical use. Later on, Groth showed [START_REF]Fully Anonymous Group Signatures Without Random Oracles[END_REF] a fairly practical random-oracle-free group signature with signature length smaller than 2 kB and full anonymity (i.e., anonymity in a model where the adversary is allowed to open anonymous signatures at will) in the model of [START_REF] Bellare | Foundations of Group Signatures: The Case of Dynamic Groups[END_REF].

Verifier-local revocation. Membership revocation has always been a critical issue in group signatures. The simplest solution is to generate a new group public key and provide unrevoked signers with a new signing key, which implies the group master to send a secret message to each individual signer as well as to broadcast a public message to verifiers. In some settings, it may not be convenient to send a new secret to signers after their inclusion in the group. In verifierlocal revocation group signatures (VLR-GS), originally suggested in [START_REF] Chaum | An Efficient Protocol for Anonymously Providing Assurance of the Container of the Private Key[END_REF] and formalized in [START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF], revocation messages are only sent to verifiers (making the group public key and the signing procedure independent of which and how many members were excluded). The group manager maintains a (periodically updated) revocation list (RL) which is used by all verifiers to perform the revocation test and make sure that signatures were not produced by a revoked member.

The RL contains a token for each revoked user. The verification algorithm accepts all signatures issued by unrevoked users and reveals no information about which unrevoked user issued the signature. However, if a user is revoked, his signatures are no longer accepted. It follows that signatures from a revoked member become linkable: to test that two signatures emanate from the same revoked user, one can simply verify signatures once using the RL before the alleged signer's revocation and once using the post-revocation RL. As a result, users who deliberately leave the group inevitably lose their privacy.

The property of backward unlinkability, first introduced in [START_REF] Song | Practical Forward Secure Group Signature Schemes[END_REF] in the context of key-evolving group signatures, ensures that signatures that were generated by a revoked member before his revocation remain anonymous and unlinkable. This property is useful when members who voluntarily leave the group wish to retain a certain level of privacy. When users' private keys get stolen, preserving the anonymity of their prior signatures is also definitely desirable.

Boneh and Shacham [START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF] proposed a VLR group signature using bilinear maps in a model inspired from [START_REF] Bellare | Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions[END_REF]. In [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF], Nakanishi and Funabiki extended Boneh-Shacham group signatures and devised a scheme providing backward unlinkability. They proved the anonymity of their construction under the Decision Bilinear Diffie-Hellman assumption [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF]. In [START_REF]A Short Verifier-Local Revocation Group Signature Scheme with Backward Unlinkability[END_REF], the same authors suggested another backward-unlinkable scheme with shorter signatures. Other pairing-based VLR-GS constructions were put forth in [START_REF] Zhou | A Shorter Group Signature with Verifier-Location Revocation and Backward Unlinkability[END_REF][START_REF]Shorter Verifier-Local Revocation Group Signatures from Bilinear Maps[END_REF] Traceable signatures [START_REF] Kiayias | Traceable Signatures[END_REF], that also have pairing-based realizations [START_REF] Nguyen | Efficient and Provably Secure Trapdoor-Free Group Signature Schemes from Bilinear Pairings[END_REF][START_REF] Choi | Short Traceable Signatures Based on Bilinear Pairings[END_REF], can be seen as extensions of VLR-GS schemes as they also admit an implicit tracing mechanism. They provide additional useful properties such as the ability for signers to claim (and prove) the authorship of anonymously generated signatures or the ability for the group manager to reveal a trapdoor allowing to publicly trace all signatures created by a given user. This primitive was recently implemented in the standard model [START_REF] Libert | Efficient Traceable Signatures in the Standard Model[END_REF]. However, it currently does not provide a way to trace users' signatures per period: once the tracing trapdoor of some group member is revealed, all signatures created by that member become linkable. In some situations, it may be desirable to obtain a fine-grained traceability and only trace signatures that were issued in specific periods. The problem of VLR-GS schemes with backward unlinkability can be seen as the one of tracing some user's signatures from a given period onwards while preserving the anonymity and the unlinkability of that user's signatures for earlier periods. The solution described in this paper readily extends to retain the anonymity of signatures produced during past and future periods.

Contribution of the paper.

All known constructions of group signatures with verifier local revocation (with or without backward unlinkability) make use of the Fiat-Shamir paradigm [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF] and thus rely on the random oracle methodology [START_REF] Bellare | Random Oracles are Practical: A Paradigm for Designing Efficient Protocols[END_REF], which is known not to provide more than heuristic arguments in terms of security. Failures of the random oracle model were indeed reported in several papers such as [START_REF] Canetti | The Random Oracle Methodology, Revisited[END_REF][START_REF] Goldwasser | On the (In)security of the Fiat-Shamir Paradigm[END_REF]. When first analyzed in the random oracle model, cryptographic primitives thus deserve further efforts towards securely instantiating them without appealing to the random oracle idealization.

The contribution of this paper is to describe a new VLR-GS scheme with backward unlinkability in the standard model. Recently, Groth and Sahai [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF] described powerful non-interactive proof systems allowing to prove that a number of committed variables satisfy certain algebraic relations. Their techniques notably proved useful to design standard model group signatures featuring constant signature size [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF][START_REF] Groth | Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures[END_REF][START_REF]Fully Anonymous Group Signatures Without Random Oracles[END_REF].

Extending the aforementioned constructions to obtain VLR-GS schemes with backward unlinkability is not straightforward. The approach used in [START_REF]A Short Verifier-Local Revocation Group Signature Scheme with Backward Unlinkability[END_REF], which can be traced back to Boneh-Shacham [START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF], inherently requires to use programmable random oracles, the behavior of which currently seems impossible to emulate in the standard model (even with the techniques developed in [START_REF] Hofheinz | Programmable Hash Functions and Their Applications[END_REF]). Another approach used in [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF] looks more promising as it permits traceability with backward unlinkablity without introducing additional random oracles. This technique, however, does not interact with the Groth-Sahai toolbox in a straightforward manner as it typically requires non-interactive zero-knowledge (NIZK) proofs for what Groth and Sahai called pairing product equations. The problem that we face is that proving the required anonymity property of VLR-GS schemes entails to simulate a NIZK proof for such a pairing-product equation at some step of the reduction. As pointed out in [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF], such non-interactive proofs are only known to be simulatable in NIZK under specific circumstances that are not met if we try to directly apply the technique of [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF].

To address the above technical difficulty, we use the same revocation mechanism as [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF] but use a slightly stronger (but still falsifiable [START_REF] Naor | On Cryptographic Assumptions and Challenges[END_REF]) assumption in the proof of anonymity: while Nakanishi and Funabiki rely the Decision Bilinear Diffie-Hellman assumption, we rest on the hardness of the so-called Decision Tripartite Diffie-Hellman problem, which is to distinguish g abc from random given (g, g a , g b , g c ). Our contribution can be summarized as showing that the implicit tracing mechanism of [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF] can be safely applied to the Boyen-Waters group signature [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF] to make it backward-unlinkably revocable. This property comes at the expense of a quite moderate increase of signature sizes w.r.t. [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF]. The main price to pay is actually to use a slightly stronger assumption than in [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF] in the security proof.

Preliminaries

Verifier-Local Revocation Group Signatures

This section presents the model of VLR group signatures with backward unlinkability proposed in [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF] which extends the Boneh-Shacham model [START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF] of VLR group signatures. Verify(gpk, j, RL j , σ, M ): is a deterministic algorithm taking as input gpk, the period number j, a set of revocation tokens RL j for period j, a signature σ, and the message M . It outputs either "valid" or "invalid". The former output indicates that σ is a correct signature on M at interval j w.r.t. gpk, and that the signer is not revoked at interval j.

For all (gpk, gsk, grt) = Keygen(λ, N, T ), all j ∈ {1, . . . , T }, all RL j , all i ∈ {1, . . . , N } and any message M ∈ {0, 1} * , it is required that if grt[i][j] / ∈ RL j then:

Verify(gpk, j, RL j , Sign(gpk, gsk[i], j, M ), M ) = "valid".

Remark 1. As mentioned in [START_REF] Boneh | Group Signatures with Verifier-Local Revocation[END_REF], any such group signature scheme has an associated implicit tracing algorithm that allows tracing a signature to the group member who generated it using the vector grt as the tracing key: on input a valid message-signature pair (M, σ) for period j, the opener can determine which user was the author of σ by successively executing the verification algorithm on (M, σ) using the vector of revocation tokens (i.e., with RL j = {grt[i][j]} i∈{1,...,N } ) and outputting the first index i ∈ {1, . . . , N } for which the verification algorithm returns "invalid" whereas verifying the same pair (M, σ) with RL j = ∅ yields the answer "valid".

From a security standpoint, VLR group signatures with backward unlinkability should satisfy the following properties: Definition 2. A VLR-GS with backward unlinkability has the traceability property if no probabilistic polynomial time (PPT) adversary A has non-negligible advantage in the following game.

1. The challenger C runs the setup algorithm to produce a group public key gpk, a group master secret gsk and a vector grt of revocation tokens. It also defines a set of corrupt users U which is initially empty. The adversary A is provided with gpk and grt while C keeps gsk to itself.

A can make a number of invocations to the following oracles:

Signing oracle: on input of a message M , an index i ∈ {1, . . . , N } and a period number j, this oracle responds with a signature σ generated on behalf of member i for period j. Corruption oracle: given an index i ∈ {1, . . . , N }, this oracle reveals the private key gsk [i] of member i which is included in the set U .

3.

A eventually comes up with a signature σ on a message M , a period number j and a set of revocation tokens RL j .

The adversary A is declared successful if -Verify(gpk, j , RL j , σ , M ) = "valid".

-The execution of the implicit tracing algorithm on input of the vector of revocation tokens (grt [START_REF] Ateniese | Practical Group Signatures without Random Oracles[END_REF][j ], . . . , grt[N ][j ]), ends up in one of the following ways:

• σ traces to a member outside the coalition U \RL j that did not sign M during period j • the tracing fails.

A's advantage in breaking traceability is measured as

Adv trace A (k) := Pr[A is successful],
where the probability is taken over the coin tosses of A and the challenger.

This definition slightly weakens the original one [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF] that captures the strong unforgeability requirement (i.e., the message-signature pair (M , σ ) must be different from that of any signing query during period j ). Due to the use of publicly randomizable non-interactive witness indistinguishable proofs, we need to settle for the usual flavor of unforgeability according to which the message M must not have been queried for signature during the target period j . Definition 3. A VLR-GS with backward unlinkability provides BU-anonymity if no PPT adversary A has non-negligible advantage in the following game.

1. The challenger C runs Keygen(λ, n, T ) to produce a group public key gpk, a master secret gsk and a vector grt of revocation tokens. The adversary A is given gpk but is denied access to grt and gsk. 2. At the beginning of each period, C increments a counter j and notifies A about it. During the current time interval j, A can adaptively invoke the following oracles:

Signing oracle: on input of a message M and an index i ∈ {1, . . . , n}, this oracle outputs a signature σ generated for member i and period j. Corruption oracle: for an adversarially-chosen i ∈ {1, . . . , n}, this oracle reveals member i's private key gsk[i]. Revocation oracle: given i ∈ {1, . . . , n}, this oracle outputs member i's revocation token for the current period j.

3. At some period j ∈ {1, . . . , T }, A comes up with a message M and two distinct user indices i 0 , i 1 ∈ {1, . . . , n} such that neither i 0 or i 1 has been corrupt. Moreover, they cannot have been revoked before or during period j . At this stage, C flips a fair coin d R ← {0, 1} and generates a signature σ on M on behalf of user i d which is sent as a challenge to A. 4. A is granted further oracle accesses as in phase 2. Of course, she may not query the private key of members i 0 , i 1 at any time. On the other hand, she may obtain their revocation tokens for time intervals after j . 5. Eventually, A outputs d ∈ {0, 1} and wins if d = d .

The advantage of A in breaking BU-anonymity is defined as Adv bu-anon

A (k) := |Pr[d = d ] -1/2|
, where the probability is taken over all coin tosses.

Bilinear Maps and Complexity Assumptions

Bilinear groups. Groups (G, G T ) of prime order p are called bilinear groups if there is an efficiently computable 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 .
In such groups, we will need three non-interactive (and thus falsifiable [START_REF] Naor | On Cryptographic Assumptions and Challenges[END_REF]) complexity assumptions.

Definition 4. In a group G = g of prime order p > 2 λ , 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 R ← Z * p , z R ← Z * p . The Decision Linear Assumption posits that, for any PPT distinguisher D,

Adv DLIN G,D (λ) = |Pr[D(g, g a , g b , g ac , g bd , g c+d ) = 1|a, b, c, d R ← Z * p ] -Pr[D(g, g a , g b , g ac , g bd , g z ) = 1|a, b, c, d R ← Z * p , z R ← Z * p ]| ∈ negl(λ).
This problem amounts to deciding whether vectors g 1 = (g a , 1, g), g 2 = (1, g b , g) and g 3 are linearly dependent or not. It has been used [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF] to construct efficient non-interactive proof systems.

We also rely on a variant, introduced by Boyen and Waters [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF], of the Strong Diffie-Hellman assumption [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF].

Definition 5 ([11]). In a group G of prime order p, the -Hidden Strong Diffie-Hellman problem ( -HSDH) is, given elements (g, Ω = g ω , u) R ← G 3 and distinct triples (g 1/(ω+s i ) , g s i , u s i ) with s 1 , . . . , s R ← Z * p , to find another triple (g 1/(ω+s) , g s , u s ) such that s = s i for i ∈ {1, . . . , }. We also rely on the following intractability assumption suggested for the first time in [8, Section 8]. Definition 6. In a prime order group G, the Decision Tripartite Diffie-Hellman Assumption (DTDH) is the infeasibility of deciding if η = g abc on input of (g, g a , g b , g c , η), where a, b, c R ← Z * p . The advantage function Adv DTDH G,D (λ) of any PPT distinguisher D is defined analogously to the DLIN case.

The above assumption is a bit stronger than the widely accepted Decision Bilinear Diffie-Hellman assumption according to which the distributions {(g, g a , g b , g c , e(g, g) abc )|a, b, c, R ← Z p } and {(g, g a , g b , g c , e(g, g) z )|a, b, c, z R ← Z p } are computationally indistinguishable. Yet, the DTDH problem is still believed to be hard in groups with a bilinear map where the DDH problem is easy.

Groth-Sahai Proof Systems

In the following notations, for equal-dimension vectors or matrices A and B containing group elements, A B stands for their entry-wise product (i.e. it denotes their Hadamard product). When based on the DLIN assumption, 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 g 1 , g 2 , g 3 ∈ G 3 , where

g 1 = (g 1 , 1, g), g 2 = (1, g 2 , g) for some g 1 , g 2 ∈ G. To commit to group elements X ∈ G, one sets C = (1, 1, X) g 1 r g 2 s g 3 t with r, s, t R ← Z * p .
When the proof system is configured to give perfectly sound proofs, g 3 is chosen as

g 3 = g 1 ξ 1 g 2 ξ 2 with ξ 1 , ξ 2 R ← Z * p . Commitments C = (g r+ξ 1 t 1 , g s+ξ 2 t 2 , X • g r+s+t(ξ 1 +ξ 2 )
) are then Boneh-Boyen-Shacham (BonehBoyenShacham2004) ciphertexts that can be decrypted using α 1 = log g (g 1 ), α 2 = log g (g 2 ). In the witness indistinguishability (WI) setting, vectors g 1 , g 2 , g 3 are linearly independent and C is a perfectly hiding commitment. Under the DLIN assumption, the two kinds of CRS are computationally indistinguishable.

To commit to a scalar x ∈ Z p , one computes C = ϕ x g 1 r g 2 s , with r, s R ← Z * p , using a CRS comprising vectors ϕ, g 1 , g 2 . In the soundness setting ϕ, g 1 , g 2 are linearly independent (typically

ϕ = g 3 (1, 1, g) where ϕ = g 1 ξ 1 g 2 ξ 2 ) whereas, in the WI setting, choosing ϕ = g 1 ξ 1 g 2 ξ 2
gives a perfectly hiding commitment since C is always a BonehBoyenShacham2004 encryption of 1 G .

To prove that committed variables satisfy a set of relations, the GS techniques replace variables by commitments in each relation. The whole proof consists of one commitment per variable and one proof element (made of a constant number of group elements) per relation.

Such proofs are easily obtained 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 ) a ij = t T , (1)
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 y i i • n j=1 X b j j • m i=1 • n j=1 X y i γ ij j = T, (2)
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}.

In both cases, proofs for quadratic equations cost 9 group elements. Linear pairing-product equations (when a ij = 0 for all i, j) take 3 group elements each. Linear multi-exponentiation equations of the type n j=1 X b j j = T (resp. m i=1 A y i i = T ) demand 3 (resp. 2) group elements. Multi-exponentiation equations admit zero-knowledge proofs at no additional cost. On a simulated CRS (prepared for the WI setting), a trapdoor makes it is possible to simulate proofs without knowing witnesses and simulated proofs are identically distributed to real proofs.

On the other hand, pairing-product equations are not known to always have zero-knowledge proofs. Proving relations of the type (1) in NIZK usually comes at some expense since auxiliary variables have to be introduced and proof sizes are not necessarily independent of the number of variables. If t T = 1 G T in relation [START_REF] Ateniese | Practical Group Signatures without Random Oracles[END_REF], the NIZK simulator can always use

X 1 = • • • = X n = 1 G as witnesses. If t T equals n
j=1 e(g j , h j ) for known group elements g 1 , . . . , g n , h 1 , . . . , h n ∈ G, the simulator can prove that

n i=1 e(A i , X i ) • n i=1 • n j=1 e(X i , X j ) a ij = n j=1 e(g j , Y j ) (3)
and that introduced variables Y 1 , . . . , Y n satisfy the linear equations Y j = h j for j ∈ {1, . . . , n }.

Since linear equations are known to have NIZK proofs and the proof of relation (3) can be simulated using witnesses

X 1 = • • • = X n = Y 1 = • • • = Y n = 1 G .
When t T is an arbitrary element of G T , pairing-product equations are currently not known to have NIZK proofs at all.

A Scheme in the Standard Model

Description of the scheme

In notations hereafter, it will be useful to define the coordinate-wise pairing E :

G × G 3 → G 3
T such that, for any h ∈ G and any vector g = (g 1 , g 2 , g 3 ) ∈ G 3 , E h, g = e(h, g 1 ), e(h, g 2 ), e(h, g 3 ) .

As in [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF], we will also make use of a symmetric bilinear map F : G 3 × G 3 → G T defined in such a way that, for any vectors

X = (X 1 , X 2 , X 3 ) ∈ G 3 and Y = (Y 1 , Y 2 , Y 3 ) ∈ G 3 , we have F ( X, Y ) = F ( X, Y ) 1/2 • F ( Y , X) 1/2
, where F :

G 3 × G 3 → G 9
T is a non-commutative bilinear mapping that sends ( X, Y ) onto the matrix F ( X, Y ) of entry-wise pairings (i.e., containing e(X i , Y j ) in its entry (i, j)).

Also, for any z ∈ G T , ι T (z) denotes the 3 × 3 matrix containing z in position (3, 3) and 1 everywhere else. For group elements X ∈ G, the notation ι(X) will denote the vector (1, 1, X) ∈ G 3 .

The group manager holds a public key (g, Ω = g ω , A = e(g, g) α , u), where (α, γ) is the private key. As in the Boyen-Waters construction [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF], group members' private keys consist of triples (K 1 , K 2 , K 3 ) = (g α ) 1/(ω+s i ) , g s i , u s i , where s i uniquely identifies the group member. Messages can be signed by creating tuples (S 1 , S 2 , S 3 , S 4 ) = (K 1 , K 2 , K 3 • F (m) r , g r ), where r is a random exponent and F : {0, 1} * → G is a Waters-like hash function [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF].

The revocation mechanism of [START_REF] Nakanishi | Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps[END_REF] consists in introducing a vector (h 1 , . . . , h T ) of group elements, where T is the number of time periods, that allow to form revocation tokens for each user: the revocation token of user i for period j is obtained as grt

[i][j] = h s i j .
When user i must be revoked at stage j, the group manager can simply add grt[i][j] to the revocation list RL j of period j. When user i signs a message during stage j, he is required to include a pair (T 1 , T 2 ) = g δ , e(h j , g s i ) δ in the signature and append a proof that (g, T 1 = g δ , K 2 = g s i , h j , T 2 ) satisfy the forementioned relation and that T 2 is indeed the "Bilinear Diffie-Hellman value" e(h j , g s i ) δ associated with (g, T 1 , K 2 , h j ).

Keygen(λ, N, T ): for security parameters λ and n ∈ poly(λ), choose bilinear groups (G, G T ) of order p > 2 λ , with g, h 1 , . . . , h

T , u R ← G. Select α, ω R ← Z * p and set A = e(g, g) α , Ω = g ω . Select v = (v 0 , v 1 , . . . , v n ) R ← G n+1 . Choose vectors g = ( g 1 , g 2 , g 3 ) such that g 1 = (g 1 , 1, g) ∈ G 3 , g 2 = (1, g 2 , g) ∈ G 3 , and g 3 = g 1 ξ 1 • g 2 ξ 2 , with g 1 = g α 1 , g 2 = g α 2 and α 1 , α 2 R ← Z * p , ξ 1 , ξ 2 R ← Z p .
Finally, select a collision-resistant hash function H : {0, 1} * → {0, 1} n . The group public key is defined to be gpk := g, h 1 , . . . , h T , A = e(g, g) α , Ω = g ω , u, v, g, H while the group manager's private key is α, ω, α 1 , α 2 . User i is assigned the group signing key gsk[i] = (K 1 , K 2 , K 3 ) = (g α ) 1 ω+s i , g s i , u s i and his revocation token for period j ∈ {1, . . . , T } is defined as grt

[i][j] := h s i j . Sign(gpk, gsk[i], j, M ): given gsk[i] = (K 1 , K 2 , K 3 ) = (g α )
1 ω+s i , g s i , u s i , to sign a message M during period j, the signer U i first computes a hash value m = m 1 . . . m n = H(j||M ) ∈ {0, 1} n and conducts the following steps.

Choose δ, r R

← Z * p and first compute

T 1 = g δ T 2 = e(h j , K 2 ) δ (4)
as well as

θ 1 = K 1 = (g α ) 1/(ω+s i ) (5)
θ 2 = K 2 = g s i (6) θ 3 = K 3 • F (m) r = u s i • F (m) r (7)
θ 4 = g r (8
)

θ 5 = h δ j , (9)
where

F (m) = v 0 • n k=1 v m k k .
2. Commit to group elements θ , for ∈ {1, . . . , 5}. For ∈ {1, . . . , 5}, choose r , s , t R ← Z * p and set σ

= (1, 1, θ ) • g 1 r • g 2 s • g 3 t .
3. Give NIWI proofs that committed variables θ 1 , . . . , θ 4 satisfy

e(θ 1 , Ω • θ 2 ) = A (10) e(θ 3 , g) = e(u, θ 2 ) • e(F (m), θ 4 ) (11)
Relation ( 10) is a quadratic pairing product equation (in the Groth-Sahai terminology) over variables θ 1 , θ 2 . Such a relation requires a proof consisting of 9 group elements that we denote by π 1 = ( π 1,1 , π 1,2 , π 1,3 ). Relation ( 11) is a linear pairing product equation over the variables θ 2 , θ 3 , θ 4 . The corresponding proof, that we denote by π 2 = (π 2,1 , π 2,2 , π 2,3 ) ∈ G 3 , consists of 3 group elements. 5. Give NIZK proofs that committed variables θ 2 and θ 5 satisfy

T 2 = e(θ 2 , θ 5 ) (12)
e(h j , T 1 ) = e(g, θ 5 )

These are two linear pairing product equations over the variables θ 2 and θ 5 and proving them in NIZK requires to introduce an auxiliary variable θ 6 . Proving ( 13) is achieved by proving in NIZK that e(θ 6 , T 1 ) = e(g, θ 5 ) and θ 6 = h j . The proof for (13) thus comprises an auxiliary commitment σ 6 = ι(h j ) g 1 r 6

g 2 s 6 g 3 t 6 to θ 6 = h j and proofs that relations e(θ 6 , T 1 ) = e(g, θ 5 ) ( 14)

e(θ 6 , g) = e(h j , g) (15)
are simultaneously satisfied. These relations are all pairing-product equations. Relation ( 12) is quadratic and costs 9 group elements to prove. We will call this proofs π 3 = ( π 3,1 , π 3,2 , π 3,3 ). Relations ( 14)-( 15) are linear and only require 3 group elements each.

The corresponding proofs are denoted by π 4 = (π 4,1 , π 4,2 , π 4,3 ) and π 5 = (π 5,1 , π 5,2 , π 5,3 ).

The signature consists of σ = (T 1 , T 2 , σ 1 , . . . , σ 6 , π 1 , π 2 , π 3 , π 4 , π 5 ).

Verify(j, M, σ, gpk, RL j ): parse σ as (T 1 , T 2 , σ 1 , . . . , σ 6 , π 1 , π 2 , π 3 , π 4 , π 5 ) and return "valid" if and only if all proof are valid and σ passes the revocation test:

1. We abstracted away the construction of proof elements π 1 , π 2 , π 3 , π 4 , π 5 for clarity. To explain to proof of anonymity, it will be useful to outline what verification equations look like: namely, π 1 , π 2 , π 3 , π 4 , π 5 must satisfy

1) F σ 1 , ι(Ω) • σ 2 = ι T A F g 1 , π 1,1 F g 2 , π 1,2 ) F ( g 3 , π 1,3 2) E g, σ 3 = E u, σ 2 E F (m), σ 4 E π 2,1 , g 1 E π 2,2 , g 2 E π 2,3 , g 3 3) F σ 2 , σ 5 = F (ι(T 2 )) F π 3,1 , g 1 F π 3,2 , g 2 F π 3,3 , g 3 4) E T 1 , σ 6 = E ι(g), σ 5 E π 4,1 , g 1 E π 4,2 , g 2 E π 4,3 , g 3 5) E g, σ 6 = E h j , ι(g) E π 5,1 , g 1 E π 5,2 , g 2 E π 5,3 , g 3 2.
The signer must not be revoked at period j: for all B ij = h s i j ∈ RL j ,

T 2 = e(B ij , T 1 ) (16)
As in all VLR-GS schemes, there is an implicit tracing algorithm that can determine which group member created a valid signature using the vector of revocation tokens (and the revocation test ( 16)) which acts as a tracing key. We observe that, if necessary, the group manager is able to explicitly open the signature in O(1) time by performing a BonehBoyenShacham2004-decryption of σ 2 using the trapdoor information α 1 , α 2 .

As far as efficiency goes, signatures consist of 46 elements of G and 1 element of G T . If we consider an implementation using symmetric pairings with a 256-bit group order and also assume that elements of G T have a 1024-bit representation (with symmetric pairings and supersingular curves, such pairing-values can even be compressed to the third of their length as suggested in [START_REF] Scott | Compressed Pairings[END_REF]), we obtain signatures of about 1.56 kB.

Security

When proving the BU-anonymity property, it seems natural to use a sequence of games starting with the real attack game and ending with a game where T 2 is replaced by a random element of G T so as to leave no advantage to the adversary while avoiding to affect the adversary's view provided the Decision Bilinear Diffie-Hellman (DBDH) assumption holds. The problem becomes to simulate (using a fake common reference string) the NIZK proof that (g, T 1 , h j , K 2 , T 2 ) forms a bilinear Diffie-Hellman tuple. Since T 2 is a given element of G T in the proof, there is apparently no way to simulate the proof for relation [START_REF]Advances in Cryptology -Eurocrypt 2004, International Conference on the Theory and Applications of Cryptographic Techniques[END_REF].

As a natural workaround to this problem, we use the Decision Tripartite Diffie-Hellman assumption instead of the DBDH assumption in the last transition of the sequence of games.

Theorem 1 (BU-anonymity). The scheme satisfies the backward unlinkable anonymity assuming that the Decision Linear problem and the Decision Tripartite Diffie-Hellman problem are both hard in G. More precisely, we have

Adv bu-anon A (λ) ≤ T • N • 2 • Adv DLIN G (λ) + Adv DTDH G (λ) ( 17
)
where N is the maximal number of users and T is the number of time periods.

Proof. The proof is a sequence of games organized in such a way that even an unbounded adversary has no advantage in the final game while the first one is the real attack game as captured by definition 3. Throughout the sequence, we call S i the event that the adversary wins and her advantage is

Adv i = |Pr[S i ] -1/2|.
Game 1: the challenger B sets up the scheme by choosing random exponents

ω, α, α 1 , α 2 , ξ 1 , ξ 2 R ← Z * p
and setting g ω and A = e(g, g) α . It also sets u = g γ for a randomly chosen γ R ← Z * p and picks h 1 , . . . , h T ∈ G as well as vectors v ∈ G n+1 , and defines

g 1 = (g 1 = g α 1 , 1, g), g 2 = (1, g 2 = g α 2 , g), g 3 = g 1 ξ 1 g 2 ξ 2 .
Using ω, α, it generates users' private keys and answers all queries as in the real game. At the challenge phase, the adversary chooses two unrevoked and uncorrupted users i 0 , i 1 and is given a challenge signature σ on behalf of signer i d . Eventually, she outputs a guess d ∈ {0, 1} and her advantage is Adv 1 = |Pr[S 1 ] -1/2|, where S 1 denotes the event that d = d .

Game 2: we modify the simulation and let the simulator B pick two indices i ∈ {1, . . . , N }, j R ← {1, . . . , T } at the outset of the simulation. In the challenge phase, B aborts if A's chosen pair (i 0 , i 1 ) does not contain i or if A does not choose to be challenged for period j . It also fails if i is ever queried for corruption or if it is queried for revocation before or during period j . Assuming that B is lucky when drawing i , j (which is the case with probability (2/N ) • (1/T ) since i and j are independent of A's view), the introduced failure event does not occur. We can write Adv 2 = 2 • Adv 1 /(N T ).

Game 3: we introduce a new rule that causes B to abort. At the challenge step, we have i ∈ {i 0 , i 1 } unless the failure event of Game 2 occurs. The new rule is the following: when B flips d R ← {0, 1}, it aborts if i d = i . With probability 1/2, this rule does not apply and we have Adv

3 = 1/2 • Adv 2 .
Game 4: we modify the setup phase and consider group elements Z 1 = g z 1 , Z 2 = g z 2 that are used to generate the public key gpk and users' private keys. Namely, for j ∈ {1, . . . , T }\{j }, B chooses µ j R ← Z * p and defines h j = g µ j whereas it sets

h j = Z 2 . Also, B chooses ν R ← Z * p and sets A = e(g, Z 1 • g ω ) ν (so that α is implicitly fixed as α = ν(z 1 + ω)). Private keys of users i = i are calculated as (K 1 , K 2 , K 3 ) = (Z 1 • g ω ) ν/(ω+s i ) , g s i , u s i , for a random s i R ← Z *
p and using ω. Since B knows s i for each i = i , it can compute revocation tokens B ij = h s i j for users i = i in any period.

The group signing key of the expected target user i is set as the triple (K 1 , K 2 , K 3 ) = (g ν , Z 1 , Z γ 1 ), which implicitly defines s i = z 1 = log g (Z 1 ). We note that, for periods j = j , the revocation tokens h s i j are also computable as Z µ j 2 . On the other hand, the token h

s i j = g z 1 z 2 is not computable from Z 1 , Z 2 .
However, unless the abortion rule of Game 2 occurs, A does not query it. Although B does not explicitly use z 1 = log g (Z 1 ) and z 2 = log g (Z 2 ), it still knows all users' private keys and it can use them to answer signing queries according to the specification of the signing algorithm. It comes that A's view is not altered by these changes and we have Pr

[S 4 ] = Pr[S 3 ].
Game 5: we bring a new change to the setup phase and generate the CRS ( g 1 , g 2 , g 3 ) by setting

g 3 = g 1 ξ 1 g 2 ξ 2 ι(g) -1 instead of g 3 = g 1 ξ 1 g 2 ξ 2 .
We note that vectors g 1 , g 3 , g 3 are now linearly independent. Any noticeable change in the adversary's behavior is easily seen 1 to imply a statistical test for the Decision Linear problem so that we can write

|Pr[S 5 ] -Pr[S 4 ]| = 2 • Adv DLIN (B).
Game 6: we modify the generation of the challenge signature and use the trapdoor (ξ 1 , ξ 2 ) of the CRS to simulate NIZK proofs. We suppose that B knows values (Z 1 , Z 2 , Z 3 ) = (g z 1 , g z 2 , g z 3 ) and η = g z 1 z 2 z 3 . Elements Z 1 and Z 2 are used to define the group public key as in Game 4 whereas Z 3 will be used to create the challenge signature on behalf of user i for period j . To this end, B first implicitly defines δ = z 3 by setting

T 1 = Z 3 T 2 = e(g, η).
Elements θ 1 , . . . , θ 4 are committed to as specified by the scheme and π 1 , π 2 are calculated accordingly. This time however, σ 5 is calculated as a commitment to 1 G : namely, σ 5 = g 1 r 5 g 2 s 5 g 3 t 5 , where r 5 , s 5 , t 5

R ← Z * p . Then, B generates a proof π 3 = ( π 3,1 , π 3,2 , π 3,3 ) satisfying F σ 2 , σ 5 = F ι(g), ι(η) F π 3,1 , g 1 F π 3,2 , g 2 F π 3,3 , g 3 . (18)
Such an assignment can be obtained as

π 3,1 = σ 2 r 5 ι(η) -ξ 1 π 3,2 = σ 2 s 5 ι(η) -ξ 2 π 3,3 = ι(η) σ 2 t 5 .
We note that the value θ 5 = h δ j = g z 2 z 3 is not used by B. To simulate the proof π 3 that T 2 = e(θ 2 , θ 5 ) without knowing θ 5 , the simulator takes advantage of the fact that T 2 = e(g, η)

1 Indeed, Pr[B(g1, g2, g ξ 1 1 , g ξ 2 2 , g ξ 1 +ξ 2 ) = 1] and Pr[B(g1, g2, g ξ 1 1 , g ξ 2 2 , g ξ 1 +ξ 2 -1 ) = 1] are both within distance Adv DLIN (B) from Pr[B(g1, g2, g ξ 1 1 , g ξ 2 2 , g z ) = 1]
, where z is random.

for known g, η ∈ G (and simulating such a proof would not have been possible if T 2 had been a given element of G T ). To simulate proofs π 4 = (π 4,1 , π 4,2 , π 4,3 ), π 5 = (π 5,1 , π 5,2 , π 5,3 ) that relations ( 14)-( 15) are both satisfied, B generates π 4 as if it were a real proof using the variable assignment θ 5 = θ 6 = 1 G that obviously satisfies e(θ 6 , T 1 ) = e(g, θ 5 ) (and

σ 6 = g 1 r 6 g 2 s 6 g 3 t 6
is thus computed as a commitment to 1 G ). As for π 5 , the assignment

π 5,1 = g r 6 • h -ξ 1 j π 5,2 = g s 6 • h -ξ 2 j π 5,3 = g t 6 • h j .
is easily seen to satisfy the last verification equation

E g, σ 6 = E h j , ι(g) E π 5,1 , g 1 E π 5,2 , g 2 E π 5,3 , g 3 since g 3 = g 1 ξ 1 g 2 ξ 2 ι(g) -1
. Simulated proofs π 4 , π 5 are then randomized as explained in [START_REF] Groth | Efficient Non-interactive Proof Systems for Bilinear Groups[END_REF] to be uniform in the space of valid proofs and achieve perfect witness indistinguishability. Simulated proofs are perfectly indistinguishable from real proofs and Pr[S 6 ] = Pr[S 5 ].

Game 7: is identical to Game 6 but we replace η (that was equal to g z 1 z 2 z 3 in Game 6) by a random group element. It is clear that, under the DTDH assumption, this change does not significantly alter A's view. We thus have |Pr[S 7 ] -Pr[S 6 ]| ≤ Adv DTDH G,B (λ). In Game 7, it is easy to see that Pr[S 7 ] = 1/2. Elements T 1 and T 2 are indeed completely independent of s i = z 1 (and thus of i ). Moreover, in the WI setting, all commitments σ 1 , . . . , σ 5 are perfectly hiding and proofs π 1 , . . . , π 5 reveal no information on underlying witnesses.

When gathering probabilities, we obtain the upper bound (17) on A's advantage in Game 1.

Theorem 2 (Traceability). The scheme satisfies the full non-traceability assuming that the N -Hidden Strong Diffie-Hellman problem is hard in G. More precisely, we have

Adv trace A (λ) ≤ 4 • n • N • q s • 1 - (N -1) p -1 • Adv N -HSDH (λ) + Adv CR (n) ( 19
)
where N is maximum of the number of the adversary signature queries and the maximal number of users and T is the number of time periods.

Proof. The proof is very similar to the proof of full traceability in the Boyen-Waters [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF] group signature. One difference is that [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF] reduces the full traceability property of their scheme to the unforgeability of a 2-level hierarchical signature [START_REF] Kiltz | Append-Only Signatures[END_REF]. To prove this result, Boyen and Waters restricted the message space (where the element s i , that uniquely identifies the group member is the group signature, must be chosen) to a relatively small interval at the first level.

In our proof of anonymity, we need elements s i to be uniformly chosen in Z * p . Therefore, we cannot directly link the security of our scheme to that of the 2-level hierarchical signature of [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF] and a direct proof is needed (but it is simply obtained using the techniques from [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF]). Namely, two kinds of forgeries must be considered as in [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF]:

-Type I forgeries are those for which the implicit tracing algorithm fails to identify the signer using the vector of revocation tokens for the relevant period j . -Type II forgeries are those for which the implicit tracing algorithm incriminates a user outside the coalition and that was not requested to sign the message M during period j .

The two kinds of adversaries are handled separately in lemmas 1 and 2.

To conclude the proof, we consider an algorithm B that guesses the kind of forgery that A will come up with. Then, B runs the appropriate HSDH solver among those described in previous lemmas. If the guess is correct, B solves the HSDH problem with the success probability given in the lemmas. Since this guess is correct with probability 1/2, we obtain the claimed security bound.

Lemma 1. If N is the maximal number of users, any Type I forger A has no advantage than Adv Type-I A (λ) ≤ Adv N -HSDH (λ).

Proof. The proof is close to the one of lemma A.1 in [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF]. The simulator B is given a N -HSDH instance consisting of elements (g, Ω = g ω , u) and triples {(A i , B i , C i ) = (g 1/(ω+s i ) , g s i , u s i )} i=1,...,N . The simulator picks α, β 0 , . . . , β n R ← Z * p and sets v i = g β i , for i = 0, . . . , n. Vectors g 1 , g 2 , g 3 are chosen as g 1 = (g 1 = g α 1 , 1, g), g 2 = (1, g 2 = g α 2 , g) and

g 3 = g 1 ξ 1 g 2 ξ 2 , for randomly chosen α 1 , α 2 , ξ 1 , ξ 2 R ← Z *
p , in such a way that the CRS g = ( g 1 , g 2 , g 3 ) provides perfectly sound proofs for which B retains the extraction trapdoor (α 1 = log g (g 1 ), α 2 = log g (g 2 )). Finally, B generates (h 1 , . . . , h T ) ∈ G T as h j = g ζ j , for j = 1, . . . , T , with ζ 1 , . . . , ζ T R ← Z * p . Then, B starts interacting with the Type I adversary A who is given the group public key gpk := (g, A = e(g, g) α , h 1 , . . . , h T , Ω, u, v, g) and the vector of revocation tokens grt, which B generates as

grt[i][j] = h s i j = B ζ j
i . The simulation proceeds as follows: -when A decides to corrupt user i ∈ {1, . . . , N }, B returns the HDSH triple (A i , B i , C i ).

-when A queries a signature from user i ∈ {1, . . . , N } for a message M , B uses the private key (K 1 , K 2 , K 3 ) = (A i , B i , C i ), to generate the signature by following the specification of the signing algorithm.

When A outputs her forgery (M , j , σ ), B uses elements α 1 , α 2 to decrypt σ i , for indices i ∈ {1, . . . , 5}, and obtain θ 1 = (g α ) 1/(ω+s ) , θ 2 = g s as well as

θ 3 = u s • (v 0 • n k=1 v m k k ) r and θ 4 = g r . From these values, B can extract u s since it knows the discrete logarithm log g (v 0 • n k=1 v m k k ) = β 0 + n k=1 m k β k , where m 1 . . . m n = H(j ||M ) ∈ {0, 1} n .
Since σ is a Type I forgery, the implicit tracing algorithm must fail to identify one of the group members {1, . . . , N }. The perfect soundness of the proof system implies that s ∈ {s 1 , . . . , s N } and (θ 1 1/α , θ 2 , u s ) is necessarily an acceptable solution.

Lemma 2. The scheme is secure against Type II forgeries under the (N -1)-HSDH assumption. The advantage of any Type II adversary A is at most

Adv Type-II A (λ, n) ≤ 2 • n • N • q s • 1 - (N -1) p -1 • Adv (N -1)-HSDH (λ) + Adv CR (n)
where N and q s stand for the number of users and the number of signing queries, respectively, and the last term accounts for the probability of breaking the collision-resistance of H.

Proof. The proof is based on lemma A.2 in [START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF]. Namely, the simulator B receives a (N -1)-HSDH input comprising (g, Ω = g ω , u) and a set of triples

{(A i , B i , C i ) = (g 1/(ω+s i ) , g s i , u s i )} i=1,...,N -1 .
To prepare the public key gpk, the simulator B picks a random index ν R ← {0, . . . , n}, as well as ρ 0 , . . . , ρ n R ← Z * p and integers β 0 , . . . ,

β n R ← {0, . . . , 2q s -1}. It sets v 0 = u β 0 -2νqs • g ρ 0 , v i = u β i • g ρ i for i = 1, . . . , n. It also defines h 1 , . . . , h T by setting h j = g ζ j , with ζ j R ← Z *
p , for j = 1, . . . , T . It finally chooses vectors g as specified by the setup algorithm to obtain perfectly sound proofs.

Before starting its interaction with the Type II forger A, B initializes a counters ctr ← 0 and chooses an index i R ← {1, . . . , N } as a guess for the honest user on behalf of which A will attempt to generate a forgery. The simulation proceeds by handling A's queries in the following way.

Queries: at the first time that user i ∈ {1, . . . , N } is involved in a signing query or a corruption query, B does the following:

-if the query is a corruption query, B halts and declares failure if i = i as it necessarily guessed the wrong user i . Otherwise, it increments ctr and returns the triple (A ctr , B ctr , C ctr ) as a private key for user (K 1 , K 2 , K 3 ).

-if the query is a signing query for period j ∈ {1, . . . , T },

-if i = i B increments ctr and answers the query by running the signing algorithm using the private key (K

1 , K 2 , K 3 ) = (A ctr , B ctr , C ctr ). -if i = i , B chooses t R
← Z * p at random and implicitly defines a triple (K 1 , K 2 , K 3 ) = (g 1/t , g t •Ω -1 , * ), where * is a placeholder for an unknown group element (note that this implicitly defines s

* = t -ω). Then, B computes m 1 . . . m n = H(j||M ) ∈ {0, 1} n . At this stage, it is convenient to write F (m 1 . . . m n ) = v 0 • n k=1 v m k k as F (m 1 . . . m n ) = u J • g K where J = β 0 -2νq s + n j=1 β j m j , K = ρ 0 + n j=1 ρ j m j . If J = 0, B aborts. Otherwise, it can pick r R ← Z *
p and compute a pair

θ 3 = u t • F (m 1 . . . m n ) r • Ω K J , θ 4 = g r • Ω 1 J ,
which can be re-written as (θ 4 = u t -ω • F (m 1 . . . m n ) r, θ 5 = g r) if we define r = r + ω/J(m). This pair then allows generating a suitably anonymized signature. In particular, since B knows

θ 2 = K 2 = g t • Ω -1 , it is able to compute T 2 = e(h j , K 2 ) δ and T 1 = g δ for a random δ R ← Z * p .
When subsequent queries involve the same user i, B responds as follows (we assume that corruption queries are distinct):

-For corruption queries on users i ∈ {1, . . . , N } that were previously involved in signing queries, B aborts if i = i . Otherwise, it knows the private key (K 1 , K 2 , K 3 ) (that was used to answer signing queries) and hands it to A. -For signing queries, B uses the same values as in the first query involving the user i ∈ {1, . . . , N }. If i = i , B uses the same triple (A ctr , B ctr , C ctr ). In the case i = i , B re-uses the pair (K 1 , K 2 ) = (g 1/t , g t • Ω -1 ) and proceeds as in the first query involving i (but uses a fresh random exponent r).

Forgery: the game ends with the adversary outputting message M together with a type II forgery σ = (T 1 , T 2 , σ 1 , . . . , σ 6 , π 1 , . . . , π 5 ) for some period j ∈ {1, . . . , T }. By assumption, the implicit tracing algorithm must point to some user who did not sign M at period j . Then, B halts and declares failure if σ does not trace to user i . Since the chosen index i was independent of A's view, with probability 1/N , B's guess turns out to be correct. Then, the perfect soundness of the proof system implies that σ 2 is a BonehBoyenShacham2004 encryption of K 2 . Then, B computes m = m 1 . . . m n = H(j ||M ). If user i signed a message M at period j such that (j, M ) = (j , M ) but H(j||M ) = H(j ||M ), A was necessarily able to generate a collision on H. Otherwise, the perfect soundness of the proof system implies that σ 3 and σ 4 decrypt into θ 3 = u t -ω F (m ) r θ 4 = g r for some r ∈ Z * p and where F (m ) = v 0 • n k=1 v m k k = u J • g K and s = t i -ω. Then, B aborts if J(m ) = β 0 + n j=1 β j m j -2νq s = 0. Otherwise, B can compute u s * and thereby obtains a full tuple g 1/(ω+s ) , g s , u s where s = t -ω differs from s 1 , . . . , s N -1 with probability at least 1 -(N -1)/p (since the value t was chosen at random).

B's probability not to abort throughout the simulation can assessed as in [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF][START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF]. More precisely, one can show that J = 0 in all signing queries with probability greater than 1/2. Conditionally on the event that B does not abort before the forgery stage, the probability to have J = 0 is then shown to be at least 1/(2nq s ) (see [START_REF] Waters | Efficient Identity-Based Encryption Without Random Oracles[END_REF][START_REF]Full-Domain Subgroup Hiding and Constant-Size Group Signatures[END_REF] for details).

A Variant with Shorter Group Public Keys

As described in this section, the scheme suffers from a group public key of size O(T ), which makes it impractical when the number of time periods is very large. In the random oracle model h 1 , . . . , h T could be derived from a random oracle. However, avoiding the dependency on T in the group public key size is also possible without resorting to random oracles. This can be achieved using the techniques introduced in [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF] in the context of identity-based encryption.

The vector (h 1 , . . . , h T ) is replaced by a triple (h, h 0 , h 1 ) ∈ G 3 and the revocation token of user i at period j ∈ {1, . . . , T } is defined to be the pair (B ij1 , B ij2 ) = (h s i •F (j) ρ , g ρ ), where ρ R ← Z * p and F (j) = h 0 • h j 1 is the selectively-secure identity-hashing function of Boneh and Boyen [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF]. Since the revocation token (B ij1 , B ij2 ) satisfies the relation e(B ij1 , g) = e(h, g s i ) • e(F (j), B ij2 ), we have e(B ij1 , g δ ) = e(h, g s i ) δ • e(F (j) δ , B ij2 ) for any δ ∈ Z * p . Therefore, in each signature σ, the pair (T 1 , T 2 ) is superseded by a triple (T 1 , T 2 , T 3 ) = (g δ , F (j) δ , e(h, K 2 ) δ ) (so that the verifier needs the check that e(T 1 , F (j)) = e(g, T 2 )) whereas σ 5 becomes a commitment to θ 5 = h δ and the NIZK proof for relation [START_REF] Canetti | The Random Oracle Methodology, Revisited[END_REF] is replaced by a proof that e(h, T 1 ) = e(g, θ 5 ). At step 2 of the verification algorithm, the revocation test then consists in testing whether e(T 1 , B ij1 ) = T 3 • e(T 2 , B ij2 ) for revocation tokens {(B ij1 , B ij2 )} i∈RL j . Using the technique of [START_REF] Boneh | Short Signatures Without Random Oracles[END_REF] to generate tokens for periods j ∈ {1, . . . , T }\{j }, it can be checked that everything goes through in the proof of anonymity.

Conclusion

We described a simple way to provide Boyen-Waters group signatures with an efficient verifier local revocation mechanism with backward unlinkability.

The scheme can be easily extended so as to provide exculpability (and prevent the group manager from signing on behalf of users) using a dynamic joining protocol such as the one of [START_REF] Libert | Efficient Traceable Signatures in the Standard Model[END_REF]. It would be interesting to turn the scheme into a traceable signature [START_REF] Kiayias | Traceable Signatures[END_REF] supporting fine-grained (i.e. per period) user tracing while leaving users the ability to claim their signatures.

The first author acknowledges the Belgian National Fund for Scientific Research (F.R.S.-F.N.R.S.) for their financial support and the BCRYPT Interuniversity Attraction Pole. The second author is supported by the European Commission through the ICT Program under Contract ICT-2007-216676 ECRYPT II and by the French Agence Nationale de la Recherche through the ANR 07-TCOM-013-04 PACE Project.


Sébastien Canard

Cécile Delerablée

Aline Gouget

Emeline Hufschmitt

Fabien Laguillaumie

Hervé Sibert

Jacques Traoré

Damien Vergnaud

Fair E-cash: Be Compact, Spend Faster ⋆

Keywords: Fair e-cash, privacy-preserving, batch RSA, blind signature

We present the first fair e-cash system with a compact wallet that enables users to spend efficiently k coins while only sending to the merchant O(λ log k) bits, where λ is a security parameter. The best previously known schemes require to transmit data of size at least linear in the number of spent coins. This result is achieved thanks to a new way to use the Batch RSA technique and a tree-based representation of the wallet. Moreover, we give a variant of our scheme with a less compact wallet but where the computational complexity of the spend operation does not depend on the number of spent coins, instead of being linear at best in existing systems.

Introduction

Electronic cash systems allow users to withdraw electronic coins from a bank, and then to pay merchants using these coins preferably in an off-line manner, i.e. with no need to communicate with the bank or a trusted party during the payment. Finally, the merchant deposits the coins he has received to the bank.

An e-cash system should provide user anonymity against both the bank and the merchant during a purchase in order to emulate the perceived anonymity of regular cash. However, it seems that the necessity to fight against money laundering encourages the design of fair e-cash systems where a trusted party can, at any time when it's needed, revoke the anonymity of users. We thus focus on the design of fair e-cash systems. In order to reach the privacy target while being reasonably practical, it is necessary to focus on the efficiency of the most repeated protocol, namely the spending one between the user and the merchant. It should also be possible to withdraw or spend several coins more efficiently than repeating a single withdrawal or spending protocol. At last, we must pay attention to the compactness of the data that are exchanged in all protocols.

Related Works. The compact e-cash system [START_REF] Camenisch | Advances in Cryptology -Crypto 2005[END_REF] has recently aroused a new interest in e-cash by proposing the first e-cash system permitting a user to efficiently withdraw a wallet with 2 L coins such that the space required to store these coins, and the complexity of the withdrawal protocol, are proportional to L rather than to 2 L . Another possibility of efficient withdrawal is also given in [START_REF] Au | Practical Anonymous Divisible E-Cash from Bounded Accumulators[END_REF]. These schemes fulfill all security properties usually required in the non-fair setting but do not consider the efficiency of the spending phase. One solution to improve it is to manage a wallet that contains coins with several monetary values [START_REF] Canard | A Handy Multi-coupon System[END_REF]. The main drawback of this solution is that the user must choose during the withdrawal protocol how many coins he wants for each monetary value. In [START_REF] Au | Compact E-Cash from Bounded Accumulator[END_REF], the initial compact e-cash scheme is modified to improve the spending phase; however, the overall cost is still linear in the number of spent coins and, again, the paper only consider non-fair e-cash. Consequently, there exists no privacy-preserving fair e-cash system allowing the user to both (i) withdraw compact wallets and (ii) spend several coins while the transmitted data size is less than linear in the number of spent coins.

Our Contributions. This paper presents a fair e-cash system with a compact wallet that allows users to spend efficiently k coins while sending to the merchant only O(λ log k) bits, with λ a security parameter, while preserving the privacy of the users. Our proposal makes use of two main cryptographic building blocks: blind signatures [START_REF] Chaum | Blind Signatures for Untraceable Payments[END_REF] and batch cryptography [START_REF] Fiat | Batch RSA[END_REF]. The concept of blind signature is the essence of many e-cash systems [START_REF] Chaum | Untraceable Electronic Cash[END_REF][START_REF] Brands | Untraceable Off-line Cash in Wallets with Observers (Extended Abstract)[END_REF][START_REF] Traoré | Group Signatures and Their Relevance to Privacy-Protecting Off-Line Electronic Cash Systems[END_REF]. However, many of these suffer from a lack of efficiency since they usually use the cut-and-choose method in order to identify double-spenders [START_REF] Chaum | Untraceable Electronic Cash[END_REF]. The Batch RSA method makes it possible to efficiently obtain multiple RSA signatures of multiple messages. Batch cryptography has been used to build several e-cash systems, in order to get additional properties [START_REF] Ferguson | Single Term Off-Line Coins[END_REF][START_REF] Brands | Distance-Bounding Protocols (Extended Abstract)[END_REF], to decrease the amount of processing done by the merchant [START_REF] Pavlovski | Detachable Electronic Coins[END_REF], or to improve the efficiency of the withdrawal process at the cost of the linkability of coins withdrawn together [START_REF] Boyd | Efficient Electronic Cash Using Batch Signatures[END_REF].

To the best of our knowledge, our proposal is the most efficient (fair) e-cash system in terms of wallet storage size, computational complexity of spending and spending transfer size, which is strongly unforgeable. Note that the level of anonymity achieved by our scheme is strong but it is not perfect. Indeed it is strong because it is impossible to link (i) a withdrawal protocol with a user identity, (ii) a spending protocol to a withdrawal protocol, and (iii) two spending protocols but only under specific constraints. The anonymity property achieved by our scheme cannot be perfect since some information related to the coin number (with respect to the wallet) leaks during the spending phase.

Security Model

Algorithms

A fair e-cash system involves four kinds of players: a user U, a bank B, a merchant M and a judge J . Each user is able to withdraw a wallet with ℓ coins. Such wallet consists of an identifier and a proof of validity. A fair e-cash scheme is defined by the following algorithms, where λ is a security parameter.

-ParamGen(1 λ ) is a probabilistic algorithm that outputs the parameters of the system params.

In the sequel, all algorithms take as input 1 λ and params. -JKeyGen(), BKeyGen() and UKeyGen() are key generation algorithms for J , B and U, respectively. The key pairs are denoted by (sk J , pk J ), (sk B , pk B ), and (sk U , pk U ). Note that UKeyGen() also provides the keys of merchants that can be seen as users in e-cash systems. -Register(J (sk J , pk U ), U(sk U , pk J )) is an interactive protocol whose outcome is a notification decision of J together with a certificate of validity of U's public key which guarantee that U knows his secret key. -Withdraw(U(pk B , sk U , ℓ), B(pk U , sk B )) is an interactive protocol that allows U to withdraw a wallet W of ℓ coins. The output of U is a wallet W , i.e. an identifier I and a proof of validity Π, or an error message ⊥. The output of B is its view V Withdraw B of the protocol. -Spend(U(W, pk M , pk B , k), M(sk M , pk B )) is an interactive protocol enabling U to spend k coins. M outputs the serial numbers S 0 , • • • , S k-1 and a proof of validity π. U's output is an updated wallet W ′ or an error message ⊥.

-Deposit(M(sk M , (S 0 , . . . , S k-1 ), π, pk B ), B(pk M , sk B )) is an interactive protocol allowing M to deposit the coins, i.e. S 0 , . . . , S k-1 and π. B adds the coins to the list of spent coins or outputs an error message ⊥. -Identify(S, π 1 , π 2 , sk J ) is an algorithm executed by J which outputs a proof Π G and either a registered public key pk U or ⊥. -VerifyGuilt(S, pk U , Π G , pk J ) is an algorithm allowing to publicly verify the proof Π G that the Identify has been done correctly.

Security Properties

We informally describe the security statements of a fair e-cash scheme.

Unforgeability. From the bank point of view, what matters is that no coalition of users can ever spend more coins than they have withdrawn:

let A be an adversary that has access to the public key pk B of the system; -A, playing a user, executes in a concurrent manner Withdraw and Deposit protocols with the bank. A can legitimately withdraw f wallets; we denote by w f the number of coins withdrawn during these executions. -the adversary A wins the game if, at any time, the honest bank accepts more than w f coins (without detecting a double-spending). We require that no PPT adversary succeeds in this game with non-negligible probability. Anonymity. From the user privacy point of view, the bank, even when cooperating with malicious users and merchants, should not learn anything about a user's spending other than from the environment. We capture a weaker notion of anonymity by assuming that the targeted users withdraw and spend the same number of coins (see discussion in Section 5.2):

let A be an adversary that has access to the secret key sk B of the bank; -A executes Withdraw (as the bank) and Spend (as the merchant) protocols any number of times. A can also corrupt players; -at any time of the game, A chooses two honest users U 0 and U 1 such that both U 0 and U 1 has withdrawn and spent the same number of coins. Then, a bit b ∈ {0, 1} is chosen and a Spend protocol is played between U b and A. At the same time, we assume that Ub also plays a Spend protocol that is not observed by A. Next, A can again executes Withdraw (as the bank) and Spend (as the merchant) protocols; -the adversary A finally outputs a bit b ′ . We require that for any PPT adversary, the probability that b ′ = b differs significantly from 1/2 is negligible. Identification of double-spenders. From the bank's point of view, no collection of users should be able to double-spend a coin without revealing one of their identities:

let A be a an adversary that has access to pk B ; -A executes, as a user, Withdraw and Spend protocols as many time as it wishes; -A wins the game if, at any time, the bank outputs ⊥ while the merchant executes the Deposit protocol and Identify outputs ⊥. We require that no PPT adversary succeeds with non-negligible probability. Exculpability. The bank, even cooperating with malicious users, cannot falsely accuse honest users from having double-spent a coin, and only users who double-spent a coin can be convicted:

let A be an adversary that has access to both the secret key sk B of the bank and the one sk J of the judge;

the adversary A can create as many users as he wants and corrupt some of them. All along the game, A plays the bank side of the Withdraw and Deposit protocols, A can play either the role of the user (as a corrupted user) or the role of the merchant during Spend protocols; -the adversary A wins the game if, at any time, the Identify algorithm outputs the public key of an honest user together with a valid proof Π G . We require that no PPT adversary succeeds with non-negligible probability.

Useful Tools, Notations and Conventions

In the sequel, λ is the general security parameter. In a withdrawal protocol, the user withdraws ℓ ≤ K = 2 L coins from the bank, and every coin is labeled with a serial number S j , 0 ≤ j < ℓ. In a spending protocol, the number of remaining coins in the wallet before spending and the number of coins to be spent is denoted by K ′ and k, respectively.

Batch RSA Method

The Batch RSA method [START_REF] Fiat | Batch RSA[END_REF] makes it possible, for a given RSA modulus, to efficiently obtain multiple RSA signatures whose public exponents are coprime pairwise.

Let n be an RSA modulus for which the factorization is only known by the signer. Let e 0 , . . . , e ℓ-1 be ℓ exponents, coprime both pairwise and with φ(n), with ℓ ≤ K = 2 L . As the efficiency of the Batch RSA depends on the size of these exponents, a generic suitable choice is the ℓ first odd prime numbers. Let E = ℓ-1 i=0 e i . Given messages S 0 , S 1 , . . . , S ℓ-1 , it is possible to generate the ℓ roots S

1/e 0 0 (mod n), . . . , S 1/e ℓ-1 ℓ-1 (mod n) in O(log K log E + log n) modular multiplications and O(K) divisions.
We sketch the steps of the Batch RSA description and complexity proof described in [START_REF] Fiat | Batch RSA[END_REF]:

-(B1) compute the product M = ℓ-1 i=0 S E/e i i
along a binary tree as shown in Figure 1 for the case ℓ = 5. Every complete binary tree with ℓ leaves is suitable. However, for efficiency purpose, we suppose the height of the tree is O(log K) = O(L). Each node in the tree

contains a value M [i 1 ...i 2 ] = i 2 i=i 1 S E [i 1 ...i 2 ] /e i i with E [i 1 ...i 2 ] = i 2 i=i 1 e i .
In order to compute this tree, the number of operations is O(log

K log E + log n) multiplications; -(B2) compute the batch signature M 1/E = ℓ-1 i=0 S 1/e i i
, as a usual RSA signature with public exponent E; -(B3) decompose M 1/E in order to obtain the values S 1/e i i . In this step, the binary tree built at the first step is parsed down, and at each node of the tree the value M

1/E [i 1 ...i 2 ] [i 1 ...i 2 ] = i 2 i=i 1 S 1/e i i
is computed and broken into two factors (one for each son) by using the Chinese remainder theorem and the values computed in (B1). The cost of this last step is O(K) modular divisions and O(log E log K) operations.

Use of Batch RSA in our proposal. The messages signed using Batch RSA are the serial numbers of coins. For efficiency purpose, the Batch RSA exponents e i are the K first prime numbers. Therefore, we have log E = V(e K-1 ), where V is the Chebyshev function 1 . This yields log E ∼ K ln K.

During the withdrawal, the user has to perform steps (B1) and (B2) (see Section 3.2) in order to receive an aggregated signature on all the serial numbers that he has chosen. The aggregated value M 1/E represents his wallet. One novel aspect of our scheme is that it is never necessary to fully decompose the aggregated signature into all the signatures of spent coins during the spending phase. Indeed, at each spending, the current aggregated signature is split into two parts following a single node operation from step (B3), the first part being the aggregated signature of the coins to be spent, and the second part being the new wallet signature representing the remaining coins. Suppose that a user still owns an aggregated signature M

M = 5 i=1 S E e i i S 1 S 2 e 2 e 1 S e2 1 S e1 2 S e2e3 1 S e1e3 2 S e1e2
1/E ′ F = i∈F S 1/e i i
, with F ⊂ {0, . . . , ℓ -1} and E ′ = i∈F e i . This user wants to spend a subset F 1 of the coins in F . Let F 2 = F \ F 1 . In order to compute the aggregated signature M

1/E ′ 1 F 1 = i∈F 1 S 1/e i i
, the user creates two binary trees, corresponding to the subsets F 1 and F 2 , respectively, and connects them at the root of a new binary tree. Then, the user computes the resulting tree as in step (B1) above in order to obtain the two factors M F 1 and M F 2 . The cost is O(log #F log E ′ + log n). Using the values computed for the roots of each subset F i , the user can now retrieve the aggregated signature to be spent and the remainder as another aggregated signature. The cost of this operation is 2 modular divisions and O(log E ′ ) multiplications. An example is shown in Figure 2.

This technique allows a user to carry a very small amount of data and to transfer reduced signature data. Indeed, in this case, only the non-spent interval and the remaining aggregated signature must be stored in the wallet, while a single aggregated signature is sent to the merchant. There are several trade-offs related to how we use the Batch RSA signatures. We detail them in Section 6.

RSA Blind Signature Scheme

A blind signature [START_REF] Chaum | Blind Signatures for Untraceable Payments[END_REF] is a protocol between a user and a signer where the user gets a signature from the signer in a way that the signer does not know the content of the message he is signing. Furthermore, the signer cannot link afterward his views of the protocol to the resulting signatures.

A common blind signature is the RSA blind signature scheme from Chaum [START_REF] Chaum | Blind Signatures for Untraceable Payments[END_REF][START_REF]Blind Signature System[END_REF]. This three-move blind signature scheme is defined by a set of five algorithms BS=(KeyGen, Blind, Sign, UnBlind, Verif), where Blind corresponds to the computation of M = r e .H(M ) (mod n) where r is a secret random value, M is the message to be blindly signed and H is a one-way

M 1 E [1...4] [1...4] = 4 i=1 S e 1 e 2 e 3 e 4 e i i S 1 e 1 1 M 1 E [2...4] [2...4] = S 1 e 2 2 S 1 e 3 3 S 1 e 4 4 S 1 S 2 S 3 S 4 S e4 3 S e3 4 M [2...4] = S e3e4 2 S e4e2 3 S e3e2 4
Fig. 2. Binary tree built to spend coins 2, 3, 4 from a wallet with 4 remaining coins collision-resistant hash function, while Unblind consists in computing σ = σ/r (mod n), where σ is a classical RSA signature on the message M . Thus, it is obvious that σ is also a classical RSA signature of the message M .

Use of the RSA blind signature scheme in our proposal. Our scheme relies on blind RSA signatures using the Batch RSA technique, for which we choose a modulus n, where log n is polynomial in λ. The messages signed using the RSA blind signature are serial numbers of coins. During step (B2), the batch signature is replaced by a blind signature process. Thus, for M = ℓ-1 i=0 H(S i ) E/e i , instead of simply computing the message M 1/E = ℓ-1 i=0 H(S i ) 1/e i , the signer obtains from the user M = r E M (mod n) and computes σ = M 1/E = r ℓ-1 i=0 H(S i ) 1/e i (mod n). The user finally computes, as for the traditional RSA blind signature scheme, σ = σ/r (mod n), which corresponds to ℓ-1 i=0 H(S i ) 1/e i , as desired.

Signature of Knowledge

Zero-knowledge proofs of knowledge (ZKPK) are interactive protocols between a verifier and a prover allowing a prover to assure the verifier his knowledge of a secret, without any leakage of it.

In the following, we use proofs of knowledge of a discrete logarithm [START_REF] Schnorr | Efficient signature generation by smart cards[END_REF][START_REF] Girault | On the Fly Authentication and Signature Schemes Based on Groups of Unknown Order[END_REF], of a representation, proof of equality of two known representations in the same or in different groups [START_REF] Boudot | Efficient Publicly Verifiable Secret Sharing Schemes with Fast or Delayed Recovery[END_REF]. In the following, we denote by P K(α 1 , . . . , α q : R(α 1 , . . . , α q )) a proof of knowledge of the secrets α 1 , . . . , α q verifying the relation R. Note that the combination of these proofs and the underlying security have been studied in [START_REF] Kiayias | Traceable Signatures[END_REF][START_REF] Canard | Complex Zero-Knowledge Proofs of Knowledge Are Easy to Use[END_REF] and refined in [START_REF] Camenisch | On the Portability of Generalized Schnorr Proofs[END_REF]. These interactive proofs can also be used non interactively (a.k.a. signatures of knowledge) by using the Fiat-Shamir heuristic [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF].

3.4 Camenisch-Lysyanskaya Type Signature Schemes.

Camenisch and Lysyanskaya have proposed in [START_REF] Camenisch | A Signature Scheme with Efficient Protocols[END_REF] various signature schemes which include new features. These signatures, called CL signatures for short, are based on Pedersen's commitment scheme which allows a user to commit some values without revealing them. CL signatures should satisfy the unforgeability property and have the following protocols.

-KeyGen: a key generation algorithm which outputs a key pair (sk, pk).

-Sign: an efficient protocol between a user and a signer that permits the user to obtain from the signer a signature Σ of some commitment C = Commit(x 1 , . . . , x k ) such that (x 1 , . . . , x k ) are unknown from the signer. The latter uses the CLSign algorithm on input C and the user obtains a signature Σ on the messages (x 1 , . . . , x k ), such that Verif(Σ, (x 1 , . . . , x k )) = 1. -ZKPK: an efficient ZKPK of a signature of some values that are moreover (may be independently) committed. -Verif: a procedure verifying the signature Σ on the messages (x 1 , . . . , x k ).

One possible choice is to take the construction from [START_REF] Camenisch | A Signature Scheme with Efficient Protocols[END_REF], which is secure under the flexible RSA assumption (a.k.a. strong RSA assumption), and where the signature on values (x 0 , . . . , x k ) is (A, e, s)

such that A e = a 0 a x 1 1 • • • a x k k b s
, where the a i 's and b are public.

Compact spending

In this section, we first give a high level description of our proposal before describing the procedure and protocols of our scheme.

Overview of our scheme

In e-cash systems, a withdrawal protocol allows a user to get from the bank, a wallet of coins that can be represented by a set of serial numbers and a signature of the bank that will allow him to prove the validity of the coins. The spending protocol of a fair e-cash system usually includes the generation of ℓ valid serial numbers S 0 , . . . , S ℓ-1 (to allow the detection of doublespending by the bank during the deposit protocol), a verifiable encryption of the spender public key, and a proof of validity of the S i 's and of the encryption of the user public key without revealing any information about his identity.

Serial numbers. As we have seen, the Batch RSA technique can be used to obtain compact spendings by aggregating signatures. However, the transmission of the serial numbers also has to get more compact in order to decrease the overall spending complexity. In order to compact data related to serial numbers, we use a tree with a derivation mechanism from the root to the leaves which represent the serial numbers of the coins. In our scheme, the maximal number of coins that can be withdrawn during a protocol is a fixed parameter of the system K = 2 L . Each wallet of monetary value ℓ ≤ K = 2 L withdrawn from the bank is mapped to a binary tree of L+ 1 levels2 . The tree root is assigned a compact serial number S 0,0 . For every level i, 0 ≤ i < L, the 2 i nodes are assigned each a compact serial number denoted by S i,j with 0 ≤ j < 2 i . The values S L,j with 0 ≤ j < 2 L related to the leaves of the tree are called the serial numbers of the purse and denoted S j . The derivation is illustrated by Figure 3 and it works as follows: the descendants from a node S i,j are given by a public function F(•, •) that, on input a compact serial number S i,j and a bit b ∈ {0, 1} to indicate left or right, outputs the (compact) serial number S i+1,2j+b of the left or right descendant of S i,j in the tree. Thus, from the tree root S 0,0 , it is possible to compute all the serial numbers S i,j , 0 ≤ i ≤ L, 0 ≤ j < 2 i . The idea used to obtain compact spendings with serial numbers is that it is possible to send the serial number of a node S i,j instead of the serial numbers of all the leaves that come from him. Conversely, once a node S i,j is revealed, none of its descendants or ascendants can be spent, and no node can be spent more than once. This rule is necessary to protect against over-spending. It must also be impossible to compute a serial number without the knowledge of one of its ascendants. Finally, for security reasons, function F must be collision-free. Withdrawal. During the withdrawal protocol, the user chooses a number ℓ ≤ K = 2 L of coins to withdraw. For every j, 0 ≤ j ≤ ℓ-1, the serial number S j is the message related to the exponent e j (see Section 3.1). The user computes the ℓ serial numbers S 0 , . . . , S ℓ-1 from a compact serial number S 0,0 = s, where s is a random value known only by the user but computed jointly by the bank and the user, so as to prevent an attack where two users use the same compact serial number. The user at last obtains from the bank both a blind Batch RSA signature on the serial numbers S 0 , . . . , S ℓ-1 with exponents e 0 , . . . , e ℓ-1 and a CL signature on s and her identity u.

F (•, 0) S 0,0 S 2,0 S 3,0 = S 0 S 3,1 = S 1 F (•, 1) F (•, 0) S 1,1 S 2,1 S 2,2 S 3,2 = S 2 S 3,3 = S 3 S 3,4 = S 4 F (•, 0) F (•, 0) F (•, 1) S 1,0 F (•, 1) F (•, 0) F (•, 0) F (•, 1)
Spending. When a user wants to spend k coins, she does not need to send k serial numbers and k proofs of validity but only one batch signature (see Section 3.1) and O(λ log(k)) nits corresponding to "compact serial numbers", assuming that the user spends the coins by increasing (or decreasing) exponents. As the size of the remaining values transmitted during spending is at most O(λ log k) bits, this is also the overall size of the data transmitted during the spending protocol.

Finally, the merchant can verify the correctness of the serial numbers (w.r.t. the bank) using a ZKPK of the CL signature on the values s and u done by the user, following a technique given in [START_REF] Traoré | Group Signatures and Their Relevance to Privacy-Protecting Off-Line Electronic Cash Systems[END_REF] which permits us not to prove that the spent serial numbers are indeed generated from the value s signed by the bank.

Setup Procedure

The ParamGen procedure first sets 2 L = K as the maximum number of coins in a wallet and e 0 , . . . , e K-1 as K distinct small prime numbers. For all i ∈ [1, K], E i = i-1 j=0 e j . Next Enc J (•) is an encryption function of the judge's IND-CPA public key cryptosystem (e.g. the El Gamal encryption scheme), H(•) and F(•, •) are two one-way collision resistant (hash) functions, g is a generator of a cyclic group G of prime or unknown order (the structure of the group depends on the chosen CL signature scheme). Next, the bank B (resp. the judge J ) executes the BKeyGen (resp. JKeyGen) procedure by executing the KeyGen algorithms of the CL and blind signature schemes (resp. of the encryption scheme).

During the UKeyGen procedure, each user U is finally associated to a long-term private key sk U = u and a corresponding public key pk U = g u , where g is a public parameter.

Withdrawal Protocol

Let U be a user who wants to withdraw ℓ (with 0 < ℓ ≤ K) coins to the bank B. The protocol between U and B is described in Figure 4. Note that B can compute the commitment C on u, s = s ′ + s ′′ and w using only C ′ and s ′′ and without needing to know s ′ and thus s. Next, the computation of E ℓ and the serial numbers S 0 , . . . , S ℓ-1 is done using the tree structure we described above with F as function and S 0,0 = s as the tree root (see Sections 3.1 and 4.1 for details). The user U now possesses a wallet determined by the set (s, u, w, Σ, σ).

M = r E ℓ M (mod n) Σ = CLSign(C) C = Commit(s = s ′ + s ′′ , u, w) σ = M 1/E ℓ (mod n) V Withdraw B = (C, pk U , U, s ′′ , Σ, E ℓ , M , σ) Verify U C ′ , U, pk U σ s ′′ , Σ M , E ℓ Verif(Σ, (s = s ′ + s ′′ , u, w)) ? = 1 U B C ′ = Commit(s ′ , u, w)
Choose s ′ , w at random

U = P K(α, β, γ : pk U = g α ∧ C ′ = Commit(β, α, γ)) σ = σ/r (mod n) W = (s, u, w, Σ, σ)
Choose r at random

M = H(S 0 ) E ℓ /e 0 • • • H(S ℓ-1 ) E ℓ /e ℓ-1
Compute E ℓ and S 0 , • • • , S ℓ-1 using F and S 0,0 = s Choose s ′′ at random

The Spend Protocol

Assume that a user U owns a wallet (s, u, w, Σ, σ) and wants to spend k coins to a merchant M. The spend protocol works as follows:

1. M sends some public information info concerning the transaction (typically the time and date of the ongoing transaction); 2. U knows the smallest i such that S i , • • • , S i+k-1 are unspent serial numbers; 3. U does not need to compute the values of the serial numbers S i , • • • , S i+k-1 . Indeed, she only needs to compute the smallest number of master serial numbers necessary to allow the computation by the merchant of S i , • • • , S i+k-1 . In the worst case, we need 2⌊log k⌋ values S i 1 ,j 1 , . . . , S in,jn , 0 ≤ i 1 , . . . , i n and 0

≤ j 1 ≤ 2 i 1 -1, . . . , 0 ≤ j n ≤ 2 in -1.
U sends to the merchant S i 1 ,j 1 , . . . , S in,jn and the index value i; 4. using the batch RSA signature described in Section 3.1, U computes the batch signature

σ [i,i+k-1] on S i , • • • , S i+k-1 (further denoted σ k ); 5. U computes R = H(info||pk M ||σ k )
which is used as a freshness indicator; 6. next U computes two values C 1 = Enc J (pk U ) and C 2 = Enc J (s); 7. U produces a signature of knowledge Π which proves that:

-C 1 and C 2 are well-formed, that is C 1 is an encryption of pk U = g u and C 2 is an encryption of s under the judge's public key encryption scheme, without revealing pk U nor s; -U knows a CL bank's signature Σ on u, s and w without revealing u, s, w nor σ.

She uses c = H(S i 1 ,j 1 . . . S in,jn σ k R C 1 C 2 ) as a challenge; 8. at the end, the user has sent (i, S i 1 ,j 1 , . . . , S in,jn , σ k , C 1 , C 2 , Π, R); 9. the merchant M computes S i , • • • , S i+k-1 from S i 1 ,j 1 , . . . , S in,jn and checks the validity of the coin by verifying the validity of σ k and Π;

Deposit Protocol

During this step, a merchant M sends to the bank B the values (i, S i , . . .

, S i+k-1 , σ k , C 1 , C 2 , Π, R).
The bank checks the validity of the spending by verifying the batch signature σ k on the values S i , . . . , S i+k-1 using the index i, and the validity of the proof Π using R, C 1 and C 2 . If the spending is valid, the bank checks whether at least one of the serial numbers S ∈ {S i , . . . , S i+k-1 } is already in its database. If not, B adds them into the database. Otherwise, the bank verifies the freshness of the spending using the value R. If it is fresh, the bank asks the judge to execute the identification of double spender procedure. Otherwise, the merchant is a cheater and the bank rejects the deposit.

Identification of Double Spender and Verification of Guilt

In this procedure, the bank sends to the judge two spendings (i, S i , . . .

, S i+k-1 , σ k , C 1 , C 2 , Π, R) and (i ′ , S ′ i ′ , . . . , S ′ i ′ +k ′ -1 , σ ′ k ′ , C ′ 1 , C ′ 2 , Π ′ , R ′ ) such that there exists i 0 and i ′ 0 with i ≤ i 0 ≤ i + k -1 and i ′ ≤ i ′ 0 ≤ i ′ + k ′ -1 with S i 0 = S ′ i ′ 0 = S.
This latter verifies the validity of both spendings, decrypts C 2 and C ′ 2 to retrieve s and s ′ , and next decrypts C 1 and/or C ′ 1 if necessary.

-If S cannot be computed from s (resp. s ′ ), then the judge decrypts C 1 (resp. C ′ 1 ) and concludes that pk U (resp. pk U ′ ) is guilty.

-Else, with high probability s = s ′ (since H and F are collision-free) and pk U = pk U ′ (since it is unlikely that two different users obtain the same wallet secret s in the withdrawal phase and since F is collision-free). Thus, the judge concludes that pk U = pk U ′ is guilty. Note that if the case s = s ′ and pk U = pk U ′ happens, that means that user U has proven the knowledge of a bank's signature on the values (s, u) and user U ′ has proven the knowledge of a bank's signature on the values (s, u ′ ). In this case, the two spendings are valid and the judge sends back a false alarm message since there is no double-spending. -At the end, the judge produces a proof Π G that the public key of the guilty user has been correctly decrypted. The proof consists of the values (s and pk U ) related to the cheater and of a ZKPK that the secret key sk J embedded in pk J has correctly been used to decrypt s and pk U .

The verification of guilt consists in verifying the judge's proof Π G on pk U and s.

Security Analysis

In this section, we give the security arguments for our construction. We first detailed the security assumptions we use and next give the security theorem; security proofs are not included in the paper due to space restrictions.

Security Assumptions

One-More Unforgeability. In 2001, Bellare et al. [START_REF] Bellare | The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme[END_REF] introduced the notion of one-more one-way function, and showed how it leads to a proof of security of Chaum's RSA-based blind signature scheme [START_REF]Blind Signature System[END_REF] in the random oracle model. We now introduce a variant of the one-more RSA problem in order to prove the security of the Batch variant of Chaum's blind signatures. The one-more flexible (or strong) RSA-problem is defined by the following game for an algorithm A.

the adversary A gets an RSA modulus n and a public exponent E made of the product of ℓ prime numbers E = e 0 . . . e ℓ-1 ; -it is given access to an inversion oracle that given y ∈ Z * n returns x ∈ Z * n such that x E = y mod N ; -it is given access to a challenge oracle that returns ℓ random challenges point from Z * n ; -eventually, A wins the game if it succeeds in inverting q • ℓ + 1 points output by the challenge oracle using less than q queries to the inversion oracle 3 .

The strong one-more RSA assumption states that no probabilistic polynomial-time algorithm A may win the previous game with non-negligible probability. Following, Bellare et al.'s technique from [START_REF] Bellare | The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme[END_REF], it is readily seen that in the random oracle model, the Batch-RSA blind signature scheme is one-more unforgeable under the strong onemore RSA assumption: Lemma 1. If the one-more flexible RSA problem is hard, then the Batch-RSA blind signature scheme is polynomially-secure against one-more forgery in the random oracle model. Proof. It is almost identical to the one of [START_REF] Bellare | The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme[END_REF]Theorem 16].

⊓ ⊔

Strong Blindness Property. In the security proof of our e-cash system, we need a Strong Blindness property for this Batch-RSA blind signature scheme. More precisely, we have the following experiment:

let A be a PPT Turing Machine having access to the signer's key pair and being able to participate to the blind process from the signer's point of view, obtain resulting message/signature (M, σ) and obtain chosen partial pairs message/signature, that is all S i ∈ F and the signature i∈F H(S i ) 1/e i for any F ⊂ {0, • • • , ℓ -1} of the adversary's choice (see Section 3.1 for details); -at any time of the game, the adversary outputs two transcripts I 0 and I 1 of a blind signature process (from the signer's point of view) and a challenge F ⊂ {0, • • • , ℓ -1}. The challenger next chooses at random a bit b ∈ {0, 1} and outputs the messages and the signature corresponding to the transcript I b and the set F ; -the adversary finally outputs a bit b ′ .

The Strong Blindness property says that the probability that b ′ = b differs significantly from 1/2 is negligible.

Lemma 2. The Batch-RSA Blind signature scheme unconditionally verifies the Strong Blindness property.

Proof. Straightforward as the proof is similar to the security proof of the initial RSA blind signature scheme, which is unconditionally blind.

⊓ ⊔

Unforgeability of signature of knowledge. In our construction, we use the Fiat-Shamir heuristic to make non-interactive traditional interactive zero-knowledge proofs of knowledge.

In [START_REF] Seberry | Security Arguments for Digital Signatures and Blind Signatures[END_REF], Pointcheval and Stern prove that this transformation is secure in the random oracle model.

Camenisch-Lysyanskaya type signature schemes. We need the CL type signature scheme to be unforgeable, saying that even if an adversary has oracle access to the signing algorithm which provides signatures on messages of the adversary's choice, the adversary cannot create a valid signature on a message not explicitly queried. If we choose the CL signature scheme in [START_REF] Camenisch | A Signature Scheme with Efficient Protocols[END_REF], we need to assume that the flexible RSA problem is hard.

The One-more discrete logarithm assumption. The one-more discrete logarithm problem [START_REF] Bellare | The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme[END_REF] is the following one. Given l + 1 values and having access to a discrete logarithm oracle at most l times, find the discrete logarithm of all these values.

Security Statement

Theorem 1. Our e-cash system is a secure fair e-cash system:

unforgeability under the one-more unforgeability of the Batch-RSA blind signature scheme and the non-malleability of the signature of knowledge, in the random oracle model; -anonymity under the strong blindness of the Batch-RSA blind signature scheme and the indistinguishability of the encryption scheme, in the random oracle model; -identification of double-spenders under the unforgeability of the CL signature scheme, in the random oracle model; -exculpability under the one-more discrete logarithm assumption, in the random oracle model. Note that our construction does not provide a perfect anonymity property since it is possible to know which leaves in the serial number binary tree are used during the spending. For example, if two spendings are from the same part of the tree, everyone can conclude that the spendings are from different wallets.

Efficiency Considerations

In order to simplify the complexity statements, we consider ℓ = K, so that the exponents used for a wallet are the first K = 2 L prime numbers; we have log E ∼ K ln K. The coins are spent following the decreasing order of exponents. We denote by E ′ the product of exponents corresponding to the number K ′ of coins remaining in the wallet. As seen in Section 4, the data transfer size is always at least O(λ log k).

Using Batch RSA as described in Section 3.1 as our default variant (V 0) for the scheme yields the following efficiency trade-off: only the highest remaining exponent and one aggregated signature have to be stored in the wallet, with storage size O(log n). During the spending phase, a binary tree has to be rebuilt, requiring O(log K ′ log E ′ ) = O(K ′ log 2 K ′ +log n) multiplications, and the current signature has to be broken up in two pieces, which costs O(1) modular divisions plus O(log E ′ ) = O(K ′ log K ′ ) modular multiplications. At last, a single aggregated signature is sent to the merchant, together with the number of coins and the biggest exponent, thus requiring transfer of O(log n) bits. As this variant is targeted at reduced storage, it is relevant to store also the root serial number only and compute the needed serial numbers at each spending, thus minimizing the storage cost.

Instead of reducing the storage cost, we can also manage the Batch RSA tree similarly to the tree of serial numbers. This yields variant (V 1): we store the initial withdrawal binary tree so that, during the spending, the user sends the aggregated signatures corresponding to the nodes of the tree closest to the root and such that all the corresponding leaves are in the spending set. The whole binary tree is stored, hence the initial storage size is O(K log n). During the spending phase, the user needs to send at most 2⌊log 2 (k + 1)⌋ aggregated signatures corresponding to tree nodes to the merchant, hence a data transfer of size O(log n log k). The computational cost for the user is the cost of retrieving the aggregated signatures corresponding to the nodes spent and to their remaining counterparts. At most, this requires O(log K) signature breakups (in case single coins must be retrieved), each of which costs O(1) modular divisions plus at most (for nodes closest to the tree root) O(log E ′ ) = O(K ′ log K ′ ) modular multiplications. However, these values can be pre-computed off-line after the withdrawal of the wallet, and stored in the tree, thus achieving a O(1) on-line computational cost. This variant aims at reducing computations during spending, so it is relevant to store also the whole serial number tree in order to retrieve the needed serial numbers at each spending in O(1).

The relative storage, spending computational complexity and data transfer size of our schemes are summed up in Table 1; M and D are the respective costs of exponentiation, multiplication and division modulo n, F is the cost of derivation with function F, λ is a security parameter, K is the number of withdrawn coins, k the number of spent coins and K ′ the number of remaining coins in the wallet after spending. They take into account the complexities related to the serial numbers mentioned in Section 4, which provides the overall picture as the proof Π and the remaining data only have a constant complexity. Table 1. Efficiency trade-offs.

3 e 3 e 4 e 5 e 1 e 2 S 3 S 4 e 5 e 4 S 5 S e5 4 S e4 5 e 1 e 2 e 3 Fig. 1 .

 3352345531 Fig. 1. Withdrawal binary tree for the computation of M

Fig. 3 .

 3 Fig. 3. Serial number binary tree for ℓ = 5 and K = 2 3

Fig. 4 .

 4 Fig. 4. Withdrawal Protocol

  O(λ + log n) O(K(λ + log n)) Computational complexity O(K ′ log 2 K ′ + log n)M O(1) of spending +O(1)D + O(log k)F Spending transfer size O(λ log k + log n) O((λ + log n) log k)

We recall that the Chebyshev function is V(x) = p≤x prime log(p).

The user may withdraw less than 2 L coins, but still has to work with a tree of depth L + 1, because the number of derivations to get the serial number of a coin must be the same for all users in order to prevent linking.

Using q times the inversion oracle and the batch RSA technique given in Section 3.1, the adversary can easily invert q • ℓ points.

⋆ This work has been financially supported by the French Agence Nationale de la Recherche and the TES Cluster under the PACE project while 2nd author was working at Orange Labs and 4th author at ENS.