Georg Fuchsbauer

David Pointcheval

Damien Vergnaud

Transferable Constant-Size Fair E-Cash

We propose an efficient blind certification protocol with interesting properties. It falls in the Groth-Sahai framework for witness-indistinguishable proofs, thus extended to a certified signature it immediately yields non-frameable group signatures. We use blind certification to build an efficient (offline) e-cash system that guarantees user anonymity and transferability of coins without increasing their size. As required for fair e-cash, in case of fraud, anonymity can be revoked by an authority, which is also crucial to deter from double spending.

Introduction

Motivation

The issue of anonymity in electronic transactions was introduced for e-cash and e-mail in the early 1980's by Chaum, with the famous primitive of blind signatures [START_REF] Chaum | Blind signatures for untraceable payments[END_REF][START_REF] Chaum | Blind signature system[END_REF]: a signer accepts to sign a message, without knowing the message itself, and without being able to later link a message-signature pair to the transaction it originated from. In e-cash systems, the message is a serial number to make a coin unique. The main security property is resistance to "one-more forgeries" [START_REF] Pointcheval | Security arguments for digital signatures and blind signatures[END_REF], which guarantees the signer that after t transactions a user cannot have more than t valid signatures.

Blind signatures have thereafter been widely used for many variants of e-cash systems; in particular fair blind signatures [START_REF] Stadler | Fair blind signatures[END_REF], which allow to provide revocable anonymity. They deter from abuse since in such a case the signer can ask an authority to reveal the identity of the defrauder. In order to allow the signer to control some part of the message to be signed, partially blind signatures [START_REF] Abe | Provably secure partially blind signatures[END_REF] have been proposed.

Another primitive providing anonymity are group signatures [START_REF] Chaum | Group signatures[END_REF], enabling a user to sign as a member of a group without leaking any more information about his identity. The strong security model in [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF] considers dynamic groups in which the group manager is not fully trusted: one thus requires that the latter cannot frame honest users.

For e-cash systems, the classical scenario is between a bank, a user and a merchant/shop: the user withdraws money from the bank and can then spend it in a shop. The latter deposits it at the bank to get its account credited. Literature tries to improve the withdrawal and the spending processes, e.g. with divisible e-cash [START_REF] Eng | Single-term divisible electronic coins[END_REF][START_REF] Canard | Divisible e-cash systems can be truly anonymous[END_REF]. However, for many applications, such as e-tickets or coupons [START_REF] Nakanishi | Unlinkable electronic coupon protocol with anonymity control[END_REF], transferability [OO90,OO92,CG08] is a more desirable property. It is known that the size of coins grows linearly in the number of transfers [START_REF] Chaum | Transferred cash grows in size[END_REF]-a drawback we will avoid in our construction by modifying the model (cf. Sect. 1.3).

Classical e-cash requires that as long as a user does not spend a coin twice (double spending), she remains anonymous. Von Solms and Naccache [START_REF] Sebastiaan | On blind signatures and perfect crimes[END_REF] pointed out that perfect anonymity enables perfect crimes, and thus suggested fair e-cash, where an authority can trace coins that were acquired illegally. Necessity to fight money laundering also encourages the design of fair e-cash systems enabling a trusted party to revoke the anonymity of users, whenever needed.

Contributions

Our first result is the definition and efficient pairing-based instantiation of a new primitive, which we call partially-blind certification. A protocol allows an issuer to interactively issue a certificate to a user, of which parts are then only known to the user and cannot be associated to a particular protocol execution by the issuer. The certificates are unforgeable in that from q runs of the protocol with the issuer cannot be derived more than q valid certificates. We then give two applications of the primitive:

-In order to achieve anonymity and unlinkability in group signatures, a common approach is the following: Using a signing key provided by the group manager, a user produces a signature, encrypts it and adds a proof of its validity. For this method to work efficiently in the standard model, these signing keys have to be constructed carefully. In [START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF] for example, it is the group manager that constructs the entire signing key-which means that he can impersonate (frame) users.

Groth [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF] achieves non-frameability by using certified signatures (defined in [START_REF] Boldyreva | A closer look at PKI: Security and efficiency[END_REF]): The user chooses a verification key which is signed by the issuer. A signature produced with the corresponding signing key together with the verification key and the issuer's signature on it can then be verified under the issuer's key. Security of Groth's instantiation however relies on an unnatural assumption.

We avoid this by observing the following: it is not necessary that the user choose the verification key, as long as she can be sure that the private key contains enough entropy. Since the blind component of our instantiation of our primitive can serve as signing key, our construction applies immediately to build non-frameable group signatures (see Sect. 4). -Second, in e-cash, the serial number of a coin needs to contain enough entropy to avoid collisions, but again the user need not control it entirely. Partially-blind certificates are applicable here too.

Transferable Anonymous Constant-Size Fair E-Cash

The instantiation we give of our new primitive allows it to be combined with the results of Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], which is crucial to our main contribution: an efficient standard-model anonymous fair e-cash system in the classical three-party scenario with the following novel features: First, coins are transferable while remaining constant in size. We circumvent the impossibility results by introducing a new method to trace double spenders: the users keep receipts when receiving coins instead of storing all information about transfers inside the coin. The amount of data a user has to deal with is thus proportional to the number of coins he received, rather than the path a coin took until reaching him.

Second, partial blindness of our certificates provides the strongest possible notion of anonymity: a user remains anonymous even w.r.t. an entity issuing coins and able to detect double spendings.1 Moreover, coins are unlinkable to anyone except the authority and the double-spending detector. We give an overview of our model before getting back to its security properties.

-The participants of the system are the following: the system manager (that registers users within the system), the bank (issuing coins), users (that withdraw, transfer or spend coins), merchants to which coins are spent, the double-spending detector, and a trusted authority, called tracer, that can trace coins, revoke anonymity and identify double-spenders. -In order to get a coin, a user runs a withdrawal protocol with the bank, after which he holds a coin and a receipt to be kept even after transferring or spending the coin (to defend himself against wrongful accusation of double-spending).2

-Another protocol enables users to transfer coins to other users who, besides the coin, also get a receipt, which they keep too. -To spend the coin, the user interacts with a merchant. The latter will deposit the coin at the bank who invokes the double-spending detector to check if it has already been spent. If it is the case, the tracer is invoked to reveal the double spender. He does so by tracing back the two instances of the coin by asking the receipts from the users that transferred the coins until identifying the double spender.

Note that the tracing authority identifies innocent users that merely transferred a coin that has been used fraudulently before. However, this does not weaken anonymity, which does not hold against the tracer anyway and since identities are not revealed to anyone else. Moreover, this can be proved to be unavoidable in order to achieve constant-size transferable coins. An inevitable shortcoming of our model is that a user who loses a receipt can be accused of double spending, since he cannot prove legal acquisition of the coin if he transferred it. The system satisfies the following security notions:

-Any user who spends a coin twice is detected.

-As long as a user keeps all his receipts, he cannot be wrongfully accused of double spending, even if everyone else colludes against him. -A user is anonymous even against collusions of the manager, the bank, the double-spending detector, merchants, and other users. -Transfers of coins are unlinkably anonymous to collusions possibly comprising the manager, the bank, merchants, and other users. (The double-spending detector must necessarily be able to link two spendings of the same coin.)

Our construction is secure in the standard security model (i.e., without relying on the random oracle idealization [BR93])3 and its security is based on a new (though natural) assumption that holds in the generic group model [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF].

Organization of the Paper

In the next section, we state the employed assumptions. In Sect. 3, we describe our new Partially-Blind Certification primitive, and apply it to group signatures in Sect. 4. In Sect. 5, we extend some techniques of Groth-Sahai, recapitulating re-randomization of commitments and introducing proofs for relations of values committed under different keys. In Sect. 6, we combine everything to construct our e-cash system.

Assumptions

We present the assumptions on bilinear groups on which our security results build. A bilinear group is a tuple (p, G, G T , e, G) where (G, +) and (G T , •) are two cyclic groups of order p, G is a generator of G, and

e : G × G → G T is a non-degenerate bilinear map, i.e., ∀ U, V ∈ G ∀ a, b ∈ Z : e(aU, bV ) = e(U, V ) ab , and e(G, G) is a generator of G T .
The first two of the following assumptions are classical [START_REF] Diffie | New directions in cryptography[END_REF][START_REF] Boneh | Short group signatures[END_REF]. The third is a simple extension of the Hidden Strong Diffie-Hellman Problem proposed by Boyen and Waters in [START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF].

Definition 1. The Computational Diffie-Hellman (CDH) Assumption states that the following problem is intractable4 : given (G, αG, βG) ∈ G 3 , for α, β ∈ Z p , output αβG.

Definition 2. The Decisional Linear (DLIN) Assumption states that the following problem is intractable: given (U, V, G, αU, βV, γG) ∈ G 6 , decide whether γ = α + β or not.

Definition 3. The q-Double Hidden Strong Diffie-Hellman (DHSDH) Assumption states that the following problem is intractable: given (G, H, K, Γ = γG) ∈ G 4 and q -1 tuples

X i = x i G, X ′ i = x i H, Y i = y i G, Y ′ i = y i H, A i = 1 γ+x i (K + y i G) with x i , y i ← Z * p for 1 ≤ i ≤ q -1, output a new tuple X = xG, X ′ = xH, Y = yG, Y ′ = yH, A = 1 γ+x (K + yG) .
Note that a tuple (X, X ′ , Y, Y ′ , A) has the above format if and only if it satisfies

e(X, H) = e(G, X ′ ) e(Y, H) = e(G, Y ′ ) e(A, Γ + X) = e(K + Y, G)
Remark 4. Boneh and Boyen [START_REF] Boneh | Short signatures without random oracles[END_REF] introduced the Strong Diffie-Hellman (SDH) assumption in bilinear groups stating that given a (q+1)-tuple (G, γG, γ 2 G, . . . , γ q G) ∈ G q+1 for a random γ ← Z * p , it is infeasible to output a pair (x, 1 γ+x G) ∈ Z p × G. Hardness of SDH implies hardness of the following two problems (the first implication is proved in [START_REF] Boneh | Short signatures without random oracles[END_REF], the second in Appendix B):

(I) Given G, γG ∈ G and q -1 distinct pairs (x i , 1 γ+x i G) ∈ Z p × G, output a new pair (x, 1 γ+x G) ∈ Z p × G.
(II) Given G, K, γG ∈ G and q -1 distinct triples x i , y i ,

1 γ+x i (K + y i G) ∈ Z 2 p × G, output a new triple x, y, 1 γ+x (K + yG) ∈ Z 2 p × G.
The Hidden SDH problem defined in [START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF] is a variant of Problem (I), where instead of giving the x i 's explicitly, they are given as (x i G, x i H). Similarly, the goal is to output a new triple (xG, xH, 1 γ+x G). Now the Double Hidden SDH assumption (Definition 3) transforms Problem (II) the same way: instead of being given explicitly, x i and y i are given as (x i G, x i H, y i G, y i H). See Appendix A for a discussion on the various assumptions derived from SDH and their relations.

3 Partially-Blind Certification 3.1 Model Definition 5. A partially-blind certification scheme (Setup, Sign, User, Verif) is a 4-tuple of (interactive) probabilistic polynomial-time Turing machines (PPTs) such that:

-Setup is a PPT that takes as input an integer k and outputs a pair (pk, sk) of public (resp. secret) key. We call k the security parameter. -Sign and User are interactive PPTs such that User takes as inputs a public key pk and Sign takes as input the matching secret key sk. Sign and User engage in the certificate-issuing protocol and when they stop, Sign outputs completed or not-completed while User outputs a pair of bit strings (σ, τ ) or ⊥. -Verif is a deterministic polynomial-time Turing machine that on input a public key pk and a pair of bit strings (σ, τ ) outputs either accept or reject.

For all k ∈ N, all pairs (pk, sk) output by Setup(k), if Sign and User follow the certificate issuing protocol with input sk and pk respectively, then Sign outputs completed and User outputs a pair (σ, τ ) that satisfies Verif(pk, (σ, τ )) = accept.

A pair (σ, τ ) is termed valid with regard to pk if on input (pk, (σ, τ )) Verif outputs accept, in which case, we say that (σ, τ ) is a certificate for pk and τ is termed the blind component of the certificate. We denote T ⊂ {0, 1} * the set of bit-strings which are blind component of some certificate.

Experiment Exp blindness-b A (k) (pk, state) ← A(FIND, k) τ 0 ← T (σ 1 , τ 1 ) ( =⊥) ← User A(state) (pk) b ′ ← A(GUESS, τ b ) RETURN b ′ Experiment Exp forge A (k) (pk, sk) ← Setup(k) ((σ 1 , τ 1 ), . . . , (σ ℓ , τ ℓ )) ← A Sign(sk,•) (pk) IF ∀i ∈ [1, ℓ], Verif(pk, (σ i , τ i )) = accept AND ∀(i, j) ∈ [1, ℓ] 2 , i = j: (σ i , τ i ) = (σ j , τ j ) AND ℓ > m RETURN 1
where m is the number of executions of the certificate issuing protocol where Sign outputs completed.

(1) Partial Blindness (2) Unforgeability Partial Blindness. To define partial blindness, we consider the real-or-random game (i.e., random experiment) among an adversarial signer A and a challenger presented in Fig. 1 (1).

-We define the advantage of A in breaking partial blindness by its advantage in distinguishing the two above experiments (with b = 0 or b = 1):

Adv blindness A (k) := Pr[Exp blindness-1 A (k) = 1] -Pr[Exp blindness-0 A (k) = 1] ,
where the probability is taken over the coin tosses made by the challenger and A. -The scheme (Setup, Sign, User, Verif) is said to be partially blind if no adversary A running in probabilistic polynomial time has a non-negligible advantage Adv blindness A .

Unforgeability. To define unforgeability, we introduce the game among an adversarial user A and an honest signer Sign depicted in Fig. 1 (2).

-We define the success of A in this game by

Succ unforge A (k) := Pr[Exp forge A (k) = 1]
, where the probability is taken over the coin tosses made by A, Setup and Sign.

-The scheme (Setup, Sign, User, Verif) is said to be unforgeable if no adversary A running in probabilistic polynomial time has a non-negligible success Succ unforge A .

Remark 6. In the random experiment Exp forge A , depending on the security model, the executions of the certificate issuing protocol are run sequentially or in a concurrent and interleaving way.

Instantiation

Let (p, G, G T , e, G) be a bilinear group and G, H, K ∈ G be public parameters; define the signer's key pair as sk := ω ← Z p and pk = Ω := ωG. A certificate is defined as

Crt(ω ; x, y) := A = 1 ω + x (K + yG) X = xG X ′ = xH Y = yG Y ′ = yH for x, y ← Z p , with σ := (A, X, X ′ , Y ) and the blind component τ := Y ′ ∈ G. It satisfies: e(X, H) = e(G, X ′ ) e(Y, H) = e(G, Y ′ ) e(A, Ω + X) = e(K + Y, G) (1)
Fig. 2 depicts an efficient protocol to interactively generate such a certificate between the signer (issuer) that controls x and the user that partially controls y: at the end, the signer has no information about y, except that it is uniformly distributed.

(1) User Choose r, y 1 ← Z p , compute and send: R 1 := r(K + y 1 G), T := rG and zero-knowledge proofs of knowledge of r and y 1 satisfying the relations (cf. Remark 7).

(2) Sign Choose x, y 2 ← Z p and compute R := R 1 + y 2 T (note that R = r(K + yG) with y := y 1 + y 2 .)

Send S 1 := 1 ω+x R, S 2 := xG, S 3 := xH, S 4 := y 2 G, S 5 := y 2 H (3) User Check whether (S 1 , S 2 , S 3 , S 4 , S 5 ) is correctly formed: e(S 2 , H) ? = e(G, S 3 ) e(S 4 , H) ? = e(G, S 5 ) e(S 1 , Ω + S 2 ) ? = e(R, G)
If so, compute a certificate Remark 7. In the first round of the User protocol, one can use interactive Schnorr-like zero-knowledge proofs of knowledge (ZKPoK) [START_REF] Schnorr | Efficient identification and signatures for smart cards[END_REF]. Extraction is then only possible for constant-depth concurrency [START_REF] Okamoto | Efficient blind and partially blind signatures without random oracles[END_REF].

A := 1 r S 1 , X := S 2 , X ′ := S 3 , Y := y 1 G + S 4 = yG, Y ′ := y 1 H + S 5 = yH
To achieve full concurrency, and at the same time reduce interactivity to 2 moves, one can use the following technique: Make linear commitments [START_REF] Groth | Non-interactive zaps and new techniques for NIZK[END_REF] (cf. Sect. 5.1) to the bits of r and y 1 (which are extractable) and use the proof techniques from [FP08, Appendix A.3 of the full version]. The drawbacks of this approach are that security holds in the common reference string (CRS) model and we incur a loss of efficiency.

Security Results

Theorem 8. Under the DHSDH assumption, the above certificates are unforgeable.

Proof. Let A be an adversary impersonating corrupt users running the issuing protocol up to q -1 times and then outputting q different valid certificates. We build B solving q-DHSDH with the same probability by simulating the signer: B gets a q-DHSDH-instance G, H, K, Ω,

(A i , X i , X ′ i , Y i , Y ′ i ) q-1 i=1 .
If the ZKPoK are non-interactive, it sets the CRS so that it can extract r and y 1 used in R 1 and T -if they are interactive, B rewinds A to extract. In each issuing, A first sends (R 1,i , T i ) and proofs of knowledge. If the proofs are correct, B extracts r i , y 1,i from them and sends S 1,i :=

r i A i , S 2,i := X i , S 3,i := X ′ i , S 4,i := Y i -y 1,i G, S 5,i := Y ′ i -y 2,i H .
Finally, B checks the q certificates and forwards one different from those in the DHSDH-instance to its own challenger.

⊓ ⊔ Theorem 9. Under the DLIN assumption, the above certificates are partially blind.

Proof. Consider A, which after an execution of the blind issuing protocol can decide whether the blind component τ = Y ′ is real or random in G. We build B deciding DLIN with the success probability of A.

The algorithm B gets a DLIN-instance (H, G, T, Z, K, R 1 ), i.e., it has to decide whether

R 1 ? = (log H Z + log G K) T (2)
It gives A the triple (G, H, K) as public parameters (and a simulating CRS in case we use non-interactive ZKPoK) and gets Ω, the issuer's public key from A. B runs the protocol User with A, starting by sending R 1 , and T from its DLIN instance and simulating the PoK. After getting back (S 1 , . . . , S 5 ), B checks its correctness and gives A the following: Y ′ := Z + S 5 , with Z from its DLIN instance. (B can verify correctness of S without knowledge of y 1 and r by checking e(S 2 , H) = e(G, S 3 ), (S 4 , H) = e(G, S 5 ) and e(S 1 , Ω + S 2 ) = e(R, G). Also note that B only needs to Let (U i ) n i=0 ∈ G n+1 be part of the public parameters; let Ω be the issuer's public key.

Certificate Generation. Run the certificate-creation protocol in Fig. 2, except that the issuer running Sign sends an extractable commitment of S 4 = y 2 G before phase (1) and opens it in phase (2).

Signing. -If the DLIN instance is not a linear tuple then Z and therefore Y ′ is independently random.

For a message M = (m 1 , . . . , m n ) ∈ {0, 1} n , denote F (M ) := U 0 + n i=1 m i U i . Given a certificate C = (A, X, X ′ , Y, Y ′ ), a signature on M using randomness s ∈ Z p is defined as Sig(C, M ; s) := (A, X, X ′ , Y, Y ′ + sF (M ), -sG) . Verification. A certified signature (A, X, X ′ , Y, Z, Z ′ ) on message M is verified by checking e(X, H) = e(G, X ′ ) e(Y, H) = e(G, Z) e(Z ′ , F (M )) e(A, Ω + X) = e(K + Y, G)
-If (H, G, T, Z, K, R 1 ) is linear, then with y 1 := log H Z, κ := log G K, and r := log G T , we have R 1 = (y 1 + κ)T by (2). Furthermore, for public parameters (G, H, K), we have

T = rG R 1 = (y 1 + κ)T = (y 1 + κ)rG = r(K + y 1 G) Z = y 1 H
which means that Y ′ = Z + S 5 is the blind component of a correctly produced certificate.

If B outputs the bit returned by A, its success probability is equal to Adv blindness A .

⊓ ⊔

4 A Fully-Secure Group Signature from Partially-Blind Certificates

As a first application of the certification protocol from Sect. 3.2, we construct fully-secure dynamic group signatures (in the sense of [START_REF] Bellare | Foundations of group signatures: The case of dynamic groups[END_REF], in particular satisfying non-frameability and CCA-anonymity) without random oracles. We construct a certified-signature scheme, to which can then be applied Groth's [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF] methodology of transforming certified signatures that respect a certain structure into group signatures using Groth-Sahai NIZK proofs [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] and Kiltz' tag-based encryption [START_REF] Kiltz | Chosen-ciphertext security from tag-based encryption[END_REF], both relying exclusively on the DLIN assumption. The resulting scheme is less efficient than that from [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF]; however, it is based on a more natural assumption, while at the same time being of the same order of magnitude-especially compared to the first instantiations of fully-secure signatures in the standard model (e.g., [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF]). We think of the scheme as somehow being the "natural" extension of [START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF] in order to satisfy non-frameability.

Certified Signatures. A certified-signature scheme consists of a setup algorithm, a key-generation algorithm for the certification authority, an interactive protocol between the authority ("issuer") and a user letting the latter obtain a triple (cert, vk, sk), where vk is a verification key for a signature scheme, sk is the corresponding signing key (unknown to the issuer) and cert is a certificate on vk.

Besides correctness, Groth [START_REF] Groth | Fully anonymous group signatures without random oracles[END_REF] gives two security criteria that a certified signature must satisfy to be transformable into a secure group signature scheme: Unfakeability requires that no user can create a certificate for and a signature under a verification key that was not certified by the issuer. Unforgeability means that even a corrupt authority issuing a tuple (cert, vk, sk) cannot forge a signature under vk.

Our Instantiation. Our certified signature is constructed from a certificate (A, X, X ′ , Y, Y ′ ) by using (Y, Y ′ ) as a pair of public and secret key for Waters' signature scheme [START_REF] Brent | Efficient identity-based encryption without random oracles[END_REF]. A certified signature consists thus of the first four components of the certificate prepended to a Waters signature. Note that what is called cert above corresponds to (A, X, X ′ ) here, and (vk, sk) would be (Y, Y ′ ). The scheme is given in Fig. 3. Our construction satisfies the security requirements given by Groth:

Theorem 10. The certified-signature scheme in Fig. 3 is perfectly correct, unfakeable under DHSDH, and existentially unforgeable under chosen-message attack under CDH.

Proof. Correctness follows by inspection. The two other properties are proved similarly to Theorems 8 and 9, we thus highlight the differences.

(1) Unfakeability means that after running various instances of the issuing protocol with the issuer, no user is able to produce a valid tuple (A, X, X ′ , Y, Z, Z ′ ) with Y different from those in the obtained certificates. The proof works similarly to that of Theorem 8 with the following modifications: For 0 ≤ i ≤ n, B chooses µ i ← Z p and sets the public parameters U i := µ i G. In the issuing protocol, B simulates the additional commitment at the beginning. From a valid (A, X, X ′ , Y, Z, Z ′ ) returned by A, B can then extract a new certificate by setting

Y ′ := Z + (µ 0 + m i µ i )Z ′ .
(2) Existential unforgeability under chosen-message attack (EUF-CMA) follows from partial blindness of certificates and security of Waters signatures, which is implied by CDH (Def. 1): Let A be an adversary impersonating the issuer and mounting a chosen-message attack. We construct B against EUF-CMA of Waters signatures. B is given a Waters public key V ∈ G and a signing oracle.

B runs the certificate-generation protocol playing the role of User with A. When A sends a commitment to S 4 in the first phase of the protocol, B extracts S 4 from it. It then chooses r, sends R 1 := r(K + V -S 4 ) and T := rG and simulates the zero-knowledge proofs. (Note that this implicitly sets V = (y 1 + y 2 )G.) If A returns a valid tuple (S 1 , S 2 , S 3 , S 4 , S 5 ), B can compute an (incomplete) certificate (A := 1 r S 1 , X := S 2 , X ′ := S 3 , Y := V ) which suffices to answer A's signing queries, as B can get the last two components by querying its own oracle. When A returns a successful forgery, B returns the last two components, i.e., a Waters signature under public key V .

⊓ ⊔

5 New Techniques For Groth-Sahai Proof Systems

Preliminaries

We briefly review the results of [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] relevant to our paper: witness-indistinguishable (WI) proofs that elements in G that were committed to via linear commitments satisfy pairing-product equations. We refer to the original work for more details and proofs.

Let P ∈ G be a generator. We define a key for linear commitments. Choose α, β, r 1 , r 2 ∈ Z p and define U = αP , V = βP , and

u 1 := (U, 0, P ) u 2 := (0, V, P ) u 3 := (W 1 , W 2 , W 3 ) (3)
where W 1 := r 1 U , W 2 := r 2 V , and W 3 is either soundness setting: W 3 := (r 1 + r 2 )P (which makes u a binding key); or witness-indistinguishable setting: W 3 := (r 1 + r 2 -1)P (which makes u a hiding key).

A commitment to a group element X ∈ G under commitment key ck = (U, V, W 1 , W 2 , W 3 ) using randomness (s 1 , s 2 , s 3 ) ← Z 3 p is defined as (with ι(X) := (0, 0, X))

Com ck, X; (s 1 , s 2 , s 3 ) := ι(X) + 3 i=1 s i u i = (s 1 U + s 3 W 1 , s 2 V + s 3 W 2 , X + s 1 P + s 2 P + s 3 W 3 ) .
Note that in the soundness setting, given the extraction key ek := (α, β), the committed value can be extracted from a commitment c = (c 1 , c 2 , c 3 ):

Extr((α, β), c) := c 3 -1 α c 1 -1 β c 2 = X + (s 1 + s 2 + s 3 (r 1 + r 2 ))P -1 α (s 1 + s 3 r 1 )U -1 β (s 2 + s 3 r 2 )V ) = X ,
since 1 α U = P and 1 β V = P . On the other hand, in the WI setting we have (with

s ′ 1 := s 1 + s 3 r 1 and s ′ 2 = s 2 + s 3 r 2 ): c = (s ′ 1 U, s ′ 2 V, X + (s ′ 1 + s ′ 2 -s 3 )P )
, which is equally distributed for every X. The two settings are indistinguishable by DLIN since for soundness (W 1 , W 2 , W 3 ) is linear w.r.t. (U, V, P ), whereas in the WI setting it is not.

For the sake of readability and consistency with the work of [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], we stick to their abstract notation, which we sketch briefly:

-For a vector X = (X 1 , . . . , X n ) ⊤ ∈ G n , let X • Y := n i=1 e(X i , Y i ). -Bold letters denote triples, e.g., d = (d 1 , d 2 , d 3 ) ∈ G 1×3 , d denotes a column vector of triples, thus a matrix in G n×3 . Furthermore, define F (c, d) := e(c i , d j )] i,j=1,3 ∈ G 3×3 T .
In G 3×3 T , "+" denotes entry-wise multiplication of matrix elements. Define c

• d := n i=1 1 / 2 F (c i , d i ) + 1 / 2 F (d i , c i ) . A pairing-product equation is an equation for variables Y 1 , . . . , Y n ∈ G of the form n i=1 e(A i , Y i ) n i=1 n j=1 e(Y i , Y j ) γ i,j = t T , with A i ∈ G, γ i,j ∈ Z p and t T ∈ G T . Setting Γ := γ i,j i,j=1,...,n ∈ Z n×n p
, this can be written as

(A • Y) (Y • Γ Y) = t T . (4)
Φ := S ⊤ ι(A) + S ⊤ Γ ι(Y) + S ⊤ Γ ⊤ ι(Y) + S ⊤ Γ Su + 3 i=1 r i H i u , (5)
with r 1 , r 2 , r 3 ← Z p , and is verified by

ι(A) • d + d • Γ d = ι T (t T ) + u • Φ . (6)
Soundness and WI of the proofs. In the soundness setting, if d satisfies (6) for some Φ, then Extr extracts Y satisfying (4). In the WI setting, let c and d be commitments to X and Y, resp., which both satisfy (4). Then Φ and Φ ′ constructed as in (5) for c and d, resp., are equally distributed.

New Techniques I: Commitment Re-randomization and Proof Updating

As observed by [START_REF] Fuchsbauer | Encrypting proofs on pairings and its application to anonymity for signatures[END_REF] and [BCC + 09], commitments of this form can be re-randomized and the corresponding proofs adapted without knowledge of the committed values nor the used randomness: given a commitment d, set c := d + Su, for S ← Z n×3 p , and update the proof Φ for d to Φ for c:

Φ := Φ + S ⊤ ι(A) + S ⊤ Γ d + S ⊤ Γ ⊤ d + S ⊤ Γ Su + 3 i=1 r i H i u (7)
with r i ← Z p . The pair (c, Φ) satisfies (6) and some calculation shows that Φ is constructed as in (5) for c being a commitment to Y using randomness S + S. (In particular (7) yields the same Φ as (5) if in the latter the randomness used for the proof is (r i + α i + r i ) 3 i=1 , where (r 1 , r 2 , r 3 ) is the randomness of Φ and α 1 , α 2 , α 3 are such that A := S ⊤ Γ ⊤ S -S ⊤ Γ S = 3 i=1 α i H i ; such α i exist since A satisfies u • Au = 0 and the H i 's form a basis for the matrices of this form; cf. [GS08, Chapter 4].)

New Techniques II: Linear Equations and Different Commitment Keys

Consider two commitments c, d of Y, Z under different commitment keys u and u ′ , respectively. We construct a re-randomizable WI proof that the committed values satisfy e(H, Y ) = e(G, Z) .

(8)

Let c be a commitment to Y w.r.t. key u: c H,c 2 ) (9b) e(Z, G) e(π 1 , P ) e(π 2 , P ) e(π 3 , W 3 ) = e(H, c 3 ) (9c)

:= (s Y 1 U + s Y 3 W 1 , s Y 2 V + s Y 3 W 2 , Y + s Y 1 P + s Y 2 P + s Y 3 W 3 ). The proof that the committed value Y satisfies equation (8) (in which Z is considered as a constant) is 5 π := (s Y 1 H, s Y 2 H, s Y 3 H), which is verified by e(π 1 , U ) e(π 3 , W 1 ) = e(H, c 1 ) (9a) e(π 2 , V ) e(π 3 , W 2 ) = e(
Regarding (9) as a set of equations over variables c 1 , c 2 , c 3 , Z, π 1 , π 2 , π 3 , we could just use the Groth-Sahai proof system a second time by committing to the new variables under key u ′ and making proofs for the equations in (9). However, this can be optimized, since we need not commit to c 1 , c 2 and c 3 . Correctness and soundness follow from a simple hybrid argument. Let us consider witness indistinguishability. We show that every pair (Y, Z) satisfying (8) generates the same distribution of proofs once both keys u and u ′ are replaced by hiding keys. Let (Y, Z) satisfying (8) be arbitrarily fixed. Since u is perfectly hiding, for any given c there exist (s 1 , s 2 , s 3 ) s.t. c = ι(Y )+ 3 i=1 s i u i . Now WI under key u ′ (of the second layer of commitments/proofs) ensures that every (Z, π 1 , π 2 , π 3 ) satisfying (9) (with the c i 's fixed!) generates identically distributed proofs. Thus for Z := (log G Y )H, π i := s i H, the proof does not leak anything. We present the details:

We make commitments to Z,

π 1 = s Y 1 H, π 2 = s Y 2 H, π 3 = s Y 3 H w.r.t. key u ′ : d :=   s Z1 U ′ + s Z3 W ′ 1 s Z2 V ′ + s Z3 W ′ 2 Z + s Z1 P ′ + s Z2 P ′ + s Z3 W ′ 3   p i :=   t i,1 U ′ + t i,3 W ′ 1 t i,2 V ′ + t i,3 W ′ 2 s Y i H + t i,1 P ′ + t i,2 P ′ + t i,3 W ′ 3   (10)
for 1 ≤ i ≤ 3. The proof ψ i for the i-th equation in ( 9) is defined as follows:

ψ 1 :=   t 1,1 U + t 3,1 W 1 t 1,2 U + t 3,2 W 1 t 1,3 U + t 3,3 W 1   ψ 2 :=   t 2,1 V + t 3,1 W 2 t 2,2 V + t 3,2 W 2 t 2,3 V + t 3,3 W 2   ψ 3 :=   s Z1 G + t 1,1 P + t 2,1 P + t 3,1 W 3 s Z2 G + t 1,2 P + t 2,2 P + t 3,2 W 3 s Z3 G + t 1,3 P + t 2,3 P + t 3,3 W 3   (11)
The final verification relations are the following:

For (9a): e(p 1,1 , U ) e(p 3,1 , W 1 ) = e(ψ 1,1 , U ′ ) e(ψ 1,3 , W ′ 1 ) e(p 1,2 , U ) e(p 3,2 , W 1 ) = e(ψ 1,2 , V ′ ) e(ψ 1,3 , W ′

2 ) e(p 1,3 , U ) e(p 3,3 , W 1 ) = e(H, c 1 ) e(ψ 1,1 , P ′ ) e(ψ 1,2 , P ′ ) e(ψ 1,3 , W ′ 3 ) For (9b): e(p 2,1 , V ) e(p 3,1 , W 2 ) = e(ψ 2,1 , U ′ ) e(ψ 2,3 , W ′ 1 ) e(p 2,2 , V ) e(p 3,2 , W 2 ) = e(ψ 2,2 , V ′ ) e(ψ 2,3 , W ′

2 ) e(p 2,3 , V ) e(p 3,3 , W 2 ) = e(H, c 2 ) e(ψ 2,1 , P ′ ) e(ψ 2,2 , P ′ ) e(ψ 2,3 , W ′ 3 ) For (9c): e(d 1 , G) e(p 1,1 , P ) e(p 2,1 , P ) e(p 3,1 , W 3 ) = e(ψ 3,1 , U ′ ) e(ψ 3,3 , W ′ 1 ) e(d 2 , G) e(p 1,2 , P ) e(p 2,2 , P ) e(p 3,2 , W 3 ) = e(ψ 3,2 , V ′ ) e(ψ 3,3 , W ′

2 ) e(d 3 , G) e(p 1,3 , P ) e(p 2,3 , P ) e(p 3,3 , W 3 ) = e(H, c 3 ) e(ψ 3,1 , P ′ ) e(ψ 3,2 , P ′ ) e(ψ 3,3 , W ′ 3 )

Re-randomization. Given commitments c, d, p 1 , p 2 , p 3 and proofs ψ 1 , ψ 2 , ψ 3 , we can re-randomize the commitments by choosing s ′ Y i , s ′ Zi , t ′ i,j ← Z p for 1 ≤ i, j ≤ 3 and setting (cf. Sect. 5.2)

c :=   c 1 + s ′ Y 3 U ′ + s ′ Y 3 W ′ 1 c 2 + s ′ Y 2 V ′ + s ′ Y 3 W ′ 2 c 3 + s ′ Y 3 P ′ + s ′ Y 2 P ′ + s ′ Y 3 W ′ 3   d :=   d 1 + s ′ Z1 U ′ + s ′ Z3 W ′ 1 d 2 + s ′ Z2 V ′ + s ′ Z3 W ′ 2 d 3 + s ′ Z1 P ′ + s ′ Z2 P ′ + s ′ Z3 W ′ 3   p i :=   p i,1 + t ′ i,1 U ′ + t ′ i,3 W ′ 1 p i,2 + t ′ i,2 V ′ + t ′ i,3 W ′ 2 p i,3 + s ′ Y i H + t ′ i,1 P ′ + t ′ i,2 P ′ + t ′ i,3 W ′ 3   for 1 ≤ i ≤ 3
Note that p i not only re-randomizes p i but at the same time updates the committed proofs π i to the new randomness for the commitments to Y . The proofs ψ i are updated as follows:

ψ 1,j := ψ 1,j + t ′ 1,j U + t ′ 3,j W 1 ψ 2,j := ψ 2,j + t ′ 2,j V + t ′ 3,j W 2 for 1 ≤ j ≤ 3 ψ 3,j := ψ 3,j + s ′ Zj G + t ′ 1,j P + t ′ 2,j P + t ′ 3,j W 3

New Techniques III: Proofs that Commitments Open to the Same Value

Given the extraction key, one can prove that two commitments open to the same value without knowledge of the randomness used when committed. We start by showing how to prove that a commitment (c 1 , c 2 , c 3 ) opens to zero: given the extraction key ek = (α, β) define the proof as (π 1 := 1 α c 1 , π 2 := 1 β c 2 ). It satisfies the following relations: e(π 1 , U ) = e(c 1 , P ), e(π 2 , V ) = e(c 2 , P ),

c 3 = π 1 + π 2 .
It is easily seen that the proofs are perfectly correct and perfectly sound. In addition, they do not leak information about the opener's secret key, since they can be produced without knowledge of ek, given the randomness used to commit and the "trapdoor" (r 1 , r 2 ) for the W i 's: c 1 = s 1 U + s 3 W 1 = α(s 1 + s 3 r 1 )P , thus π 1 = (s 1 + s 3 r 1 )P , and similarly π 2 = (s 2 + s 3 r 2 )P . Now to show that c and d are two commitments to the same value, it suffices to prove that cd opens to 0.

6 Transferable Anonymous Constant-Size Fair E-Cash from Certificates

Formal Model

In our model for e-cash, there are the following protagonists: users U i that-after registering-can withdraw, transfer and spend coins; the system manager S, authorizing users to join the system; the bank B, able to issue coins; merchants M i who deposit the coins at the bank; the double-spending detector D, that can detect if a coin was spent twice; and the tracing authority T , able to trace users that misbehave in some way (e.g., tracing of a double spender or prosecution of criminal activities). The system comprises the following protocols and algorithms:

Setup

A protocol between S (who gets the manager key mk), B (who gets the issuing key ik), D (who gets dk), and T (who gets tk). The protocol also outputs the public parameters pp.

Join

A protocol between a user and S that registers the user in the system and gives him usk. Withdraw A protocol permitting a user to withdraw a coin from B.

Transfer

A protocol between two users U i and U j , where U j gets a coin and a receipt from U i .

Spend

A protocol between a user and a merchant to spend a coin.

Detect

An algorithm enabling D to check for double spendings (without identifying the defrauder).

Trace DS

A protocol conducted by T in order to trace a double spender. Trace C

An algorithm enabling T to match a withdrawal and a spending transcript of the same coin. Trace S An algorithm that lets T reveal the identity of a spender from a spending transcript.

Besides correctness, which requires that honestly issued coins are accepted when transferred or spent by honestly registered users, and that the tracing algorithms work correctly, we define the following security notions for our model: Anonymity of withdrawal means that not even the bank colluding with the (double-spending) detector can tell to which withdrawal a coin corresponds. Anonymity of transfer (or spending) ensures that when transferring/spending a coin a user remains anonymous even with respect to the bank and malicious users the coin was transferred by.

Traceability of double spenders states that for each time a user spends a coin more than once he will be accused, whereas Detectability of double spending means that Detect will determine if a coin was spent multiple times. Non-frameability guarantees that even if everyone else colludes against an honest user, he cannot be wrongfully accused of a spending he did not perform, nor of double spending. See Fig. 4 for the details of the experiments. As for the BSZ-model of group signatures, we call protagonists semi-honest if A impersonates them but however follows protocols as prescribed. Note that in the experiment for non-frameability, U * behaves honestly, so if he is asked to spend more coins than he withdrew he refuses; moreover, a malicious tracer can always accuse an honest user of not having a receipt, which the latter counters by showing it.

We say an e-cash system is traceable, non-frameable, etc., if no p.p.t. adversary can win the respective game with non-negligible probability (non-negligibly more than 1 / 2 for the anonymity notions).

Instantiation

Overview. The core of a coin in our system is a certificate from Sect. 3.2. Defining withdrawal as partially blind issuing guarantees that the bank does not know the last component C 5 . Certificates were designed to consist of elements of G so that their verification relations are paring-product equations; the user can thus encrypt (in Groth-Sahai terminology: commit to) the coin and prove validity. Moreover, each time the coin is transferred, the receiver can re-randomize the encryption (cf. Sect. 5.2), which guarantees unlinkable anonymity.

To check for double spendings, the detector will get the decryption key to compare encrypted certificates. However, this straight-forward approach would not guarantee user anonymity when bank and detector cooperate. The blind component C 5 is thus encrypted under a different key than the rest (in Sect. 5.3 we showed how to construct the corresponding proofs). The detector gets only the key to decrypt C 5 , which suffices to detect double spending. Since the the first 4 components remain hidden from the detector, partial blindness of certificates suffices. The other decryption key is given to the tracer, which enables tracing of a coin by comparing C 3 which is known to the bank. The receipts, given when transferring and spending coins, are group signatures on them, the signing keys for which the users get when joining the system. This guarantees user traceability, while preserving anonymity (only the tracer, holding the group-signature opening key, can reveal users' identities). To identify a double spender, the tracer follows backwards the paths the certificate took before reaching the spender, by opening the receipts. A user that spent or transferred a coin twice is then unable to show two receipts. To guarantee soundness of tracing, we must ensure that each signature corresponds to at most one transfer. We achieve this by having the receiver choose a nonce which is added to the message the sender must sign.

Details. Let GS = (Setup GS , Join GS , GSign GS , GVer GS ) be a dynamic non-frameable group-signature scheme. 6 Let H : G * → {0, 1} n be a collision-resistant hash function.

Setup.

-Set up a group signature scheme GS such that S is the group's issuer (group manager) and T gets opening key ok. The group verification key gvk is added to pp.

-Produce two keys for linear commitments ck T and ck D . The corresponding extraction keys ek T and ek D are given to T (thus tk = (ek T , ek D , ok). D receives dk := ek D . -Set up the CRS (if any) for the blind certificate-issuing scheme from Sect. 3.2. B picks issuing key ik := ω ← Z p , adds Ω := ωG to pp, and gets a group signing key gsk B by joining GS.

Join. A user U i joins the system by running Join GS with S to obtain her group signing key gsk i .

Withdraw. User U i runs the issuing protocol (Fig. Additionally, the bank gives the user a "receipt" R B ← GSign GS (gsk B , H(C 1 , C 2 , C 3 , U i )).7 U i verifies the certificate and the signature R B and makes the following commitments:

c i := Com(ck T , C i ), for 1 ≤ i ≤ 4 c 5 := Com(ck D , C 5 )
and proofs Φ 1 , Φ 2 , Φ 3 for the committed values satisfying each of the equations in (12). Φ 1 and Φ 2 are regular Groth-Sahai proofs; for the last equation on commitments under different keys, see Sect. 5.3. We call (c, Φ) a coin, and refer to Appendix C for its concrete construction.

Transfer / Spend. When U i transfers a coin (c, Φ) to U j , she sends R ← GSig GS (gsk U i , H(c, U j , N )) as well, where N is a nonce set by U j . The receiver U j checks correctness of (c, Φ) and R, re-randomizes c and updates Φ (cf. Sects. 5.2 and 5.3). Spending is defined as transferring. Sect. 5.1). He compares the tag C 5 with that of previously received coins to see if a coin was spent twice, in which case he charges T to trace the double spender.

Tracing of DS.

-If multiple spendings (c (i) , Φ (i) , R (i) ) with Extr(ek D , c 5 (i) ) = C * 5 for all i were detected, the tracer uses the key ok to open the signatures R (i) in order to reveal users U (i) 0 .

-Each U (i) 0 has to prove legal acquisition of his coin, which a user U does as follows:

• If the coin was obtained from the bank, show C = (C 1 , . . . , C 5 ) and the receipt R B .

T accepts if C is valid, GVer GS (gvk, H(C 1 , C 2 , C 3 , U), R B ) = 1 and C 5 = C * 5 . • If the coin was received from a user, show the receipt R received with it, and show (c ′ , Φ ′ ), the received coin (i.e., before re-randomizing it), and the nonce N .

T accepts if (c ′ , Φ ′ ) is valid, GVer GS (gvk, H(c ′ , U, N ), R) = 1 and Extr(ek D , c ′ 5 ) = C * 5 . -In the second case (receipt produced by a user), T opens R to U (i) 1 , who in turn has to prove legal acquisition of the coin. Moreover, the tracer only accepts a receipt if it has not been given to him before.

-Continuing this process for every i produces a chain of users U (i) 0 , U (i) 1 , . . . which either ends with the bank, or with a user failing to prove legal acquisition-in which case that user is accused.

-Correctness of tracing is proved by proving correctness of opening of group signatures and proving that two commitments contain the same certificate using the techniques from Sect. 5.4.

Tracing of coins and users. Given ek T , the tracer can recover C 3 from a coin and thus match withdrawn coins to spent coins. Spender anonymity is revoked by opening the group signature.

Security Results

We briefly argue why our instantiation satisfies the security definitions from Sect. 6.1. Each property follows by a straight-forward reduction to the security of the underlying building blocks.

Detectability and traceability of double spenders. (I) Assuming an honest bank, every certificate is only issued once with all but negligible probability; (II) by unforgeability of certificates (Theorem 8) and soundness of the WI proofs, opening all d spent coins leads to at most q different certificates, where q is the number of Withdraw queries. This proves detectability.

For every i let s (i) be the number of times certificate C (i) was spent. Then the tracing algorithm produces s (i) lists of users, beginning with the spenders and linked by their certificates. Unforgeability of group signatures and (I) guarantees that only one such list ends with the bank. Since s (i) -1 users are thus accused and by (II), we have a = q i=1 (s (i) -1) = d -q, which proves traceability. Non-frameability. If U * uses a random nonce each time then by collision resistance of H, the probability of receiving the same valid receipt twice is negligible. The user can only be provably accused if he spent/transferred a coin of which he cannot justify acquisition. Non-frameability of group signatures guarantees that U * only has to justify coins he actually transferred-and for each such coin he possesses a valid receipt. Note that if a malicious user transfers the same coin (possibly as two different randomizations) twice to U * then U * has two different signatures (due to the nonce) and can thus justify both coins.

Anonymity. Anonymity of withdrawal follows from partial blindness of issuing (indistinguishability of C 5 ) and witness indistinguishability of the commitments (c 1 , . . . , c 4 ) under key ck T . Anonymity of transfer follows from WI of commitments under ck T and ck D and anonymity of group signatures.

Traceability. Traceability of coins follows from soundness of the WI proofs and unforgeability of certificates; traceability of spenders follows from traceability of group signatures.

B Proofs

Similar proofs can be found in [START_REF] Okamoto | Efficient blind and partially blind signatures without random oracles[END_REF], but we recall them for completeness.

Proof (of Lemma 14).

Let us be given a (q + 1)-tuple (P, γP, γ 2 P, . . . , γ q P ), for random elements P ∈ G and γ ∈ Z p . We now generate the input for the SDH-II problem: we randomly choose α ∈ Z p and x i ∈ Z p , for i = 1, . . . , q -1, such that the x i 's are pairwise distinct; -set

G ← α q-1 i=1 (γ + x i ) P Γ ← γG;
simulate the elements, for i = 1, . . . , q -1:

A i ← α    q-1 j=1 j =i (γ + x j )    P . Since G = (γ + x i )A i , we have e(A i , Γ + x i G) = e(A i , γG + x i G) = e(A i , (γ + x i )G) = e(G, G).
Finally, the forgery (x, A) satisfies

x = x i (i = 1, . . . , q -1), A = 1 γ + x G = α γ + x q-1 i=1 (γ + x i ) P = f (γ) γ + x P, with f (γ) = α q-1 i=1 (γ + x i ) = α q-1 i=1 ((γ + x) + (x i -x)) = α q-1 i=1 (x i -x) + (γ + x)g(γ + x) Therefore, A = α q-1 i=1 (x i -x) γ + x P + g(γ + x)P
Since g is a polynomial of degree at most q -2, one can compute R = g(γ + x)P from the SDH-I input.

If one sets

A ′ = 1 α q-1 i=1 (x i -x) (A -R) = 1 γ + x P the pair (x, A ′ ) is a solution to the SDH-I problem. ⊓ ⊔

Proof (of Lemma 16

). There are two ways of solving SDH-III by outputting (x, y, A): Either x = x i for all i = 1, . . . , q -1 or y = y i for all i.

A new x. Let us first assume that the adversary is more likely to solve the SDH-III Problem with an x that is different from all the x i of the input. Then the analysis is similar to the proof of Lemma 14.

Let us be given a (q + 1)-tuple (P , γP , γ 2 P ,. . . , γ q P ), for random elements P ∈ G and γ ∈ Z p . We now generate the input for the SDH-III problem: we randomly choose α, β ∈ Z p and x i , y i ∈ Z p , for i = 1, . . . , q -1, such that the (x i , y i )'s are pairwise

distinct; -set G ← α q-1 i=1 (γ + x i ) • P K ← βG Γ ← γG
simulate the certificates, for i = 1, . . . , q -1:

A i ← α(β + y i )    q-1 j=1 j =i (γ + x j )    P Since (γ + x i )A i = (β + y i )G = K + y i G, we have e(A i , Γ + x i G) = e(A i , γG + x i G) = e(A i , (γ + x i )G) = e(K + y i G, G) = e(K, G)e(G, G) y i .
Finally, a successful output satisfies

x = x i (i = 1, . . . , q), A = 1 γ + x (K + yG) = β + y γ + x G = α(β + y) γ + x q-1 i=1 (γ + x i ) P = f (γ) γ + x P,
where f (γ) = α(β + y)

q-1 i=1 (γ + x i ) = α(β + y)

q-1 i=1 ((γ + x) + (x i -x)) = α(β + y)

q-1 i=1 (x i -x) + (γ + x)g(γ + x)

Therefore, A = α(β + y) q i=1 (x i -x) γ + x P + g(γ + x)P Since g is a polynomial of degree at most q -2, one can compute R = g(γ + x)P from the SDH-I input. If one sets A ′ = 1 α(β + y) q i=1 (x i -x)

(A -R) = 1 γ + x P
the pair (x, A ′ ) is a solution to the SDH-I problem.

An already known x. Let us now assume that the adversary most likely solves the SDH-III Problem with x ∈ {x 1 , . . . , x q-1 } from the input.

Let us be given a (q + 1)-tuple (P , γP , γ 2 P ,. . ., γ q P ), for random elements P ∈ G and γ ∈ Z p . We now generate the input for the SDH-III problem: we randomly choose α, β ∈ Z p and (x i , y i ) ∈ Z p , for i = 1, . . . , q -1, such that the (x i , y i )'s are pairwise distinct; -choose a random index k ∈ {1, . . . , q -1}, and set (thus implicitly defining a new secret exponent ω ← γ -x k ),

G ← β    q-1 i=1 i =k (γ -x k + x i )    • P K ← (αγ -y k )G Γ ← (γG) -x k G = ωG
simulate the certificates, for i = 1, . . . , q -1:

• for i = k, A k ← αG, which satisfies

(ω + x k )A k = αγG = K + y k G • for i = k, A i ← β((y i -y k ) + αγ)    q j=1 j =i,k (γ -x k + x j )    P
We have (ω + x i )A i = ((y i -y k ) + αγ)G = (y i -y k )G + K + y k G = K + y i G Finally, a successful output satisfies (x, y) = (x i , y i ) (i = 1, . . . , q), A = 1 ω + x (K + yG)

Since we assumed that the x is likely in {x 1 , . . . , x q }, and x k is only used under the formula ω = γ -x k , the probability that x = x k is 1/q, in which case

A k = 1 γ (K + y k G) A = 1 γ (K + yG)
Then,

y k A -yA k = y k -y γ K = y k -y γ (αγ -y k )β    q-1 i=1 i =k (γ -x k + x i )    • P = f (γ) γ P, with
f (γ) = (y k -y)(αγ -y k )β    q-1 i=1 i =k (γ -x k + x i )    = (y -y k )y k β    q-1 i=1 i =k (x i -x k )    + γg(γ)
Since g is a polynomial of degree at most q -2, one can compute R = g(γ)P from the SDH-I input. If one sets

A ′ = 1 (y -y k )y k β q-1 i=1 i =k (x i -x k ) (y k A -yA k -R) = 1 γ P,
the pair (0, A ′ ) is a solution to the SDH-I problem. ⊓ ⊔

C The Concrete Form of a Coin

For concreteness we give the form of a coin, i.e., a certificate "encrypted" under two different keys together with a proof of validity. Let ck = (U, V, W 1 , W 2 , W 3 ), ck D = (U ′ , V ′ , W ′ 1 , W ′ 2 , W ′ 3 ), let u and u ′ be as in (3), resp.; let C = (A, X, X ′ , Y, Y ′ ) be a certificate satisfying (1). We commit to its components

c A := ι(A) + s Ai u i c X := ι(X) + s Xi u i c X ′ := ι(X ′ ) + s X ′ i u i c Y := ι(Y ) + s Y i u i c Y ′ := ι(Y ′ ) + s Y ′ i u ′ i
and prove that the plaintexts satisfy the equations in (1):

Equation 1. e(X, H) = e(G, X ′ ), that is e(H, X) e(G -1 , X ′ ) = 1, which is linear. The proof is thus

ξ := (s X1 H + s X ′ 1 G -1 , s X2 H + s X ′ 2 G -1 , s X3 H + s X ′ 3 G -1 )
Equation 2. e(Y, H) = e(G, Y ′ ), with Y and Y ′ being commitments under different keys u and u ′ . This is explained in Sect. 5.3, with Z := Y ′ . The proofs are thus Π := (p 1 , p 2 , p 3 ) as in (10), for random t i,j ← Z p (1 ≤ i, j ≤ 3), and Ψ := (ψ 1 , ψ 2 , ψ 3 ) as in (11) (with s Zi := s Y ′ i ). Constructing Φ ∈ G 3×3 as in (5), we get

Φ =             s A1 s X1 U (s A1 s X2 + r 1 )V s X1 A + s A1 X + s A1 Ω + s Y 1 G -1 + (s A1 s X3 + r 2 )W 1
+ (s A1 s X3 + r 2 )W 2 + (s A1 (s X1 + s X2 ) + r 1 )P + (s A1 s X3 + r 2 )W 3 (s A2 s X1 -r 1 )U s A2 s X2 V s X2 A + s A2 X + s A2 Ω + s Y 2 G -1 + (s A2 s X3 + r 3 )W 1 + (s A2 s X3 + r 3 )W 2 + (s A2 (s X1 + s X2 ) -r 1 )P + (s A2 s X3 + r 3 )W 3

(s A3 s X1 -r 2 )U (s A3 s X2 -r 3 )V s X3 A + s A3 X + s A3 Ω + s Y 3 G -1 + s A3 s X3 W 1 + s A3 s X3 W 2 + (s A3 (s X1 + s X2 ) -r 2 -r 3 )P + s A3 s X3 W 3            
for random r 1 , r 2 , r 3 ← Z p .

A coin is thus of the form (c A , c X , c X ′ , c Y , c Y ′ , ξ, Π, Ψ, Φ) ⊤ ∈ G 15×3 .

c

  Springer-Verlag, 2009.

Fig. 1 .

 1 Fig. 1. Security experiments for partially-blind certificates

Fig. 2 .

 2 Fig. 2. Partially-blind certificate-issuing protocol.

Fig. 3 .

 3 Fig. 3. Chosen-message secure certified signature

Define H 1 

 1 for t T ∈ G T . Let d be a vector of commitments to Y, i.e., d := ι(Y) + Su with S ← Z n×3 p and ι(Y) := [ι(Y i )] i=1,...,n . The proof that the values committed in d satisfy (4) is defined as

••••

  Fig. 4. Security experiments for constant-size e-cash

  2) with B to get (C 1 , . . . C 5 ) ∈ G 5 satisfying e(C 1 , Ω + C 2 ) = e(K + C 4 , G) e(C 2 , H) = e(G, C 3 ) e(C 4 , H) = e(G, C 5 ) (12)

  Detect. After receiving new a coin, D uses extraction key ek D to open c 5 : C 5 := Extr(ek D , c 5 ) (cf.

Equation 3 .

 3 e(A, Ω + X) = e(K + Y, G), that is e(A, Ω) e(Y, G -1 ) e(A, X) = e(K, G), which can be written as (A • Y) (Y • Γ Y) = t T , with := e(K, G), and S =

In fair e-cash, there exists an authority that can trace users (user-tracing) and coins (coin-tracing) under a judge decision, in case of fraud suspicion (not necessarily double spending). We separate the notions of detection of double spendings, which is done on a regular basis when a coin is deposited, from that of tracing, which is performed by a trusted authority only when a fraud was committed.

If one assumes a validity period for coins (after which the issuing key is changed), it suffices to keep a receipt only as long as the respective coin is valid.

Note that in our context, due to re-randomization of encryptions (cf. Sect. 6.2 for details), it seems even impossible to replace the Groth-Sahai techniques with the Fiat-Shamir heuristic[START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] to improve efficiency at the expense of relying on the random oracle model.

We say that a computational problem is intractable if no probabilistic polynomial-time (p.p.t.) adversary can solve it with non-negligible probability. A decisional problem is intractable if no p.p.t. adversary can decide it with probability of non-negligibly more than 1 /2.

Groth-Sahai proofs for linear equations reduce to 3 group elements; see Sect.

6.1 of the full version of[START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF].

Encrypting the certified signatures from Sect. 4 and proving validity by adding a Groth-Sahai proof yields a (CPAanonymous) non-frameable group signature scheme that does not require any further assumptions.

Abusing notation slightly, we let Ui be a unique encoding of the user's identity in G. Note that for the receipts from the issuer, no nonce is required, since the user contributes to the randomness of the certificate.

Acknowledgments

The authors would like to thank the members of the PACE research project for the fruitful discussions that led to the new primitive discussed in this paper. This work was supported by the French ANR 07-TCOM-013-04 PACE Project, the European Commission through the ICT Program under Contract ICT-2007-216676 ECRYPT II, and EADS.

A The Strong Diffie-Hellman Assumptions and the Hidden Variants

We present the Strong Diffie-Hellman Problem for G 1 = G 2 and variants of it whose hardness follows from that of the original problem.

Definition 11 (The Strong Diffie-Hellman Problem I (SDH-I)). Given a (q + 1)-tuple (G, γG, γ 2 G, . . . , γ q G), for a random element γ ∈ Z p , output a pair x, A = 1 γ+x G , with x ∈ Z p . It satisfies e(A, Γ + xG) = e(G, G) with Γ = γG.

Definition 12 (The Strong Diffie-Hellman Assumption). The q-SDH assumption states that this problem is intractable for a given q.

Definition 13 (The Strong Diffie-Hellman Problem II (SDH-II)). Given (G, Γ = γG) and q -1 pairs See Appendix B for the proof.

In [START_REF] Boyen | Full-domain subgroup hiding and constant-size group signatures[END_REF], a "hidden" version of SDH-II is defined, where in the pairs (x i , A i ), the scalar x i is not given in the clear but as (x i G, x i H) for a fixed group generator H. It is easily seen that under the Knowledge of Exponent Assumption [Dam92,BP04], the following problem is equivalent to SDH-II.

Definition 17 (The Hidden Strong Diffie-Hellman Problem (HSDH)). Given (G, H, Γ = γG) and q -1 triples

Definition 18 (The Hidden Strong Diffie-Hellman Assumption). The q-HSDH assumption states that the Hidden Strong Diffie-Hellman II Problem is intractable for a given q.

We now apply the same methodology to SDH-III, i.e., we give (and expect in a forgery) the two scalars x and y in a hidden form analogously to HSDH.

Definition 19 (The Double Hidden Strong Diffie-Hellman Problem (DHSDH)). Given (G, H, K, Γ = γG) and q -1 tuples Definition 20 (The Double Hidden Strong Diffie-Hellman Assumption). The q-DHSDH assumption states that the Double Hidden Strong Diffie-Hellman Problem is intractable for a given q.