Florian Bourse

David Pointcheval

Olivier Sanders

Divisible E-Cash from Constrained Pseudo-Random Functions

Electronic cash (e-cash) is the digital analogue of regular cash which aims at preserving users' privacy. Following Chaum's seminal work, several new features were proposed for e-cash to address the practical issues of the original primitive. Among them, divisibility has proved very useful to enable efficient storage and spendings. Unfortunately, it is also very difficult to achieve and, to date, quite a few constructions exist, all of them relying on complex mechanisms that can only be instantiated in one specific setting. In addition security models are incomplete and proofs sometimes hand-wavy. In this work, we first provide a complete security model for divisible e-cash, and we study the links with constrained pseudo-random functions (PRFs), a primitive recently formalized by Boneh and Waters. We exhibit two frameworks of divisible e-cash systems from constrained PRFs achieving some specific properties: either key homomorphism or delegability. We then formally prove these frameworks, and address two main issues in previous constructions: two essential security notions were either not considered at all or not fully proven. Indeed, we introduce the notion of clearing, which should guarantee that only the recipient of a transaction should be able to do the deposit, and we show the exculpability, that should prevent an honest user to be falsely accused, was wrong in most proofs of the previous constructions. Some can easily be repaired, but this is not the case for most complex settings such as constructions in the standard model. Consequently, we provide the first construction secure in the standard model, as a direct instantiation of our framework.

Introduction

Electronic payment systems offer high usage convenience to their users but at the cost of their privacy. Indeed, transaction data, such as payee's identity, date and location, leak sensitive information about the users, such as their whereabouts, their religious beliefs, their health status, etc.

However, secure e-payment and strong privacy are not incompatible, as shown by Chaum in 1982 [Cha82] when he introduced the concept of electronic cash (e-cash). Informally, e-cash can be thought of as the digital analogue of regular cash with special focus on users' privacy. Such systems indeed consider three kinds of parties: the bank, the user and the merchant. The bank issues coins that can be withdrawn by users and then spent to merchants. Eventually, the latter deposit the coins on their account at the bank. Compared to other electronic payment systems, the benefit of e-cash systems is that the bank is unable to identify the author of a spending. More specifically, it can neither link a particular withdrawal -even if it knows the user's identity at this stage-to a spending nor link two spendings performed by the same user.

At first sight, this anonymity property might seem easy to achieve: one could simply envision a system where the bank would issue the same coin (more specifically, one coin for each possible denomination) to each user. Such a system would obviously be anonymous but it would also be insecure. Indeed, although e-cash aims at mimicking regular cash, there is an intrinsic difference between them: e-cash, as any electronic data, can easily be duplicated. This is a major issue because it means that a user could spend the same coin to different merchants. Of course, some hardware countermeasures (such as storing the coins on a secure element) can be used to mitigate the threat but they cannot completely remove it. Moreover, the prospect of having an endless (and untraceable) reserve of coins will constitute a strong incentive to attack this hardware whose robustness is not without limits.

To deter this bad behaviour, e-cash systems must therefore enable (1) detection of re-used coins and (2) identification of defrauders. Besides invalidating the trivial solution sketched above (a unique coin for each denomination) these requirements impose very strong constraints on ecash systems: users should remain anonymous as long as they behave honestly while becoming traceable as soon as they begin overspending, from the first cent.

Chaum's idea, taken up by all subsequent works, was to associate each withdrawn coin with a unique identifier called a "serial number"1 . The latter remains unknown to all parties, except the user, until the coin is spent. At this time, it becomes public and so can easily be compared to the set of all serial numbers of previously spent coins. A match then acts as a fraud alert for the bank which can then run a specific procedure to identify the cheater.

Unfortunately, by reproducing the features of regular cash, e-cash also reproduces its drawbacks, in particular the problem of paying the exact amount. Worse, as we explain below, the inherent limitations of e-cash compound this issue that becomes much harder to address in a digital setting. This has led cryptographers to propose a wide variety of solutions to mitigate the impact on user's experience. They include for example on-line e-cash, transferable e-cash or divisible e-cash.

Related Work

On-line/Off-line Anonymous e-Cash. The original solution proposed by Chaum for anonymous payment was based on the concept of blind signature. This primitive, later formalized in [PS96, PS00], allows anyone to get a signature σ on a message m that is unknown to the signer. Moreover, the latter will be unable to link the pair (σ, m) to a specific issuance. Applying this idea to the payment context leads to the following e-cash system. A coin is a blind signature issued by a bank to a user during a withdrawal. To spend his coin, the user simply shows the signature to a merchant who is able to verify it using the bank's public key. Two cases may then appear. Either the e-cash system does not allow identification of defrauders, in which case the bank must be involved in the protocol to check that this coin has not already been spent. The resulting system is then referred to as on-line e-cash. Otherwise, the coin may be deposited later to the bank, leading to an off-line e-cash system. Obviously, the latter solution is preferable since it avoids a costly connection to the servers of the bank during the payment. In the following, we will only consider off-line e-cash systems.

Transferable vs. Divisible e-Cash. In theory, the problem of anonymous payment is thus solved by blind signatures for which several instantiations have been proposed (see e.g. [PS00]). However, as we mention above, it remains to address the problem of paying the exact amount, which becomes trickier in a digital setting. Indeed, let us consider a consumer that owns a coin whose denomination is e 10 and that wants to pay e 8.75. A first solution could be to contact his bank to exchange his coin against coins of smaller denominations but this would actually reintroduce the bank in the spending process and so would rather correspond to an on-line system. It then mainly remains two kinds of solutions: those where the merchant gives back change and those that only use coins of the smallest possible denomination (e.g. e 0.01). They both gave rise to two main streams in e-cash: transferable e-cash and compact/divisible e-cash.

Let us go back to our example. At first sight, the simplest solution (inspired from regular cash) is the one where the merchant gives back change, by returning, for example, a coin of e 0.05, one of e 0.20 and one of e 1. However, by receiving coins, the user technically becomes a merchant (in the e-cash terminology) which is not anonymous during deposit. Therefore, the only way to retain anonymity in this case is to ensure transferability of the coin, meaning that the user will be able to (anonymously) re-spend the received coins instead of depositing them. While this is a very attractive feature, it has unfortunately proved very hard to achieve. Worse, Chaum and Pedersen [CP93] have shown that a transferable coin necessarily grows in size after each spending. Intuitively, this is due to the fact that the coins must keep information about each of its owner to ensure identification of defrauders. In the same paper, Chaum and Pedersen also proved that some anonymity properties cannot be achieved in the presence of an unbounded adversary. Their results were later extended by Canard and Gouget [CG08] who proved that these properties were also unachievable under computational assumptions. More generally, identifying the anonymity properties that a transferable e-cash system can, and should, achieve has proved to be tricky [CG08,BCFK15].

All these negative results perhaps explain the small number of results on transferable e-cash, and quite recent constructions [CGT08, BCF + 11, BCFK15] are too complex for a large-scale deployment or rely on a very unconventional model [FPV09]. In particular, none of them achieves optimality with respect to the size, meaning that the coin grows much faster than the theoretical pace identified by Chaum and Pedersen. Now, let us consider our spending of e 8.75 in the case where all coins are of the smallest possible denomination. This means that the user no longer has a coin of e 10 but has 1000 coins of e 0.01. Such a system can handle any amount without change but must provide an efficient way to store and to spend hundreds of coins at once. A system offering efficient storage is called compact and a system supporting both efficient storage and spending is called divisible.

Anonymous Compact e-Cash. Anonymous compact e-cash was proposed by Camenisch,Hohenberger and Lysyanskaya [CHL05] and was informally based on the following idea. Let N be the amount of a wallet withdrawn by a user (i.e. the wallet contains N coins that all have the same value). During a withdrawal, a user gets a certificate on some secret value s that will be used as a seed for a pseudo-random function (PRF) F , thus defining the serial numbers of the N coins as F s (i) for i ∈ [1, N ].

To spend the i-th coin, a user must then essentially reveal F s (i) and prove, in a zeroknowledge way, that it is well-formed, i.e. that (1) s has been certified and that (2) the serial number has been generated using F s on an input belonging to the set [1, N ]. All of these proofs can be efficiently instantiated in many settings. Anonymity follows from the zero-knowledge properties of the proofs and from the properties of the pseudo-random function, as it is hard to decide whether F s (i) and F s (j) have been generated under the same secret key s.

Unfortunately, compact e-cash only provides a partial answer to the practical issues of spendings: storage is very efficient but the coins must still be spent one by one, which quickly becomes cumbersome. An ultimate answer to this issue was actually provided by Okamoto and Ohta [OO92] and later named divisible e-cash. The core idea of divisible e-cash is that the serial numbers of a divisible coin2 can be revealed by batches, leading to efficient spendings.

However, this is easier said than done, and it took 15 years to construct the first anonymous divisible e-cash system [CG07]. Moreover, the latter was more a proof of concept than a practical scheme, as pointed out in [ASM08,CG10]. Although several improvements followed (e.g. [ASM08, CG10,CPST15a,PST17]), the resulting constructions are still rather complex, which makes their analysis difficult. We highlight this issue by pointing out below a problem on exculpability that has been overlooked in the security proofs of these constructions.

A Major Issue with Exculpability in Previous Constructions

Intuition of the Problem. Among the natural properties expected from an e-cash system is the one, called exculpability, stating that a coin withdrawn by a user whose public key is upk * can only be spent by the latter. In particular this means that he cannot falsely be accused of double-spendings: in case of overspending detection, this user is necessarily guilty. All ecash constructions enforce this property by requiring a signature (potentially a signature of knowledge) on the transaction under upk * . Intuitively, this seems enough: a transaction accusing an honest user of fraud should contain a signature (or more specifically a proof of knowledge of a signature) under upk * and so would imply a forgery. Actually, this argument is ubiquitous in previous papers Unfortunately, this argument is not correct because of the complex identification process of e-cash systems, based on so-called double spending tags. Indeed, the public key upk * returned by the identification algorithm is not extracted from the signature itself, but from a complex formula involving several elements, such as PRF seeds, scalars, etc. An adversary might then select appropriate values that will lead this algorithm to output upk * while taking as input two transactions generated with different public keys. This scenario, that has not been taken into account in previous papers, invalidates their proofs4 because, in such a case, the transactions do not contain a valid signature under upk * .

Concrete Example. To illustrate this problem, let us consider the lattice-based construction proposed by Libert et al [LLNW17]. In this system, each user selects a short vector e and defines his public key as F.e for some public matrix F. Each coin withdrawn by this user is associated with two vectors k and t. The former is used to generate the i-th serial number y S = A i •k p for some public matrix A i while the latter is used to generate the double-spending tag y T = upk + H(R) • A i • t p , where H(R) is a matrix derived from public information associated with the transaction R.

If two transactions R and R' yield the same serial number, then one computes y * = (H(R)-H(R')) -1 (y T -y T ) and returns y T -H(R) • y * . One can note that this formula indeed returns a public key upk * if both transactions have been generated by the user upk * and tag t, as y * is then A i • t p . However, there is no equivalence here, and an adversary might manage to generate R, R', t, t', upk, upk (in the exculpability game the adversary controls the bank, the merchants and all dishonest users) such that upk

* = y T -H(R) • (H(R) -H(R')) -1 (y T -y T ).
If we modify the original protocol, to ensure that collisions only occur when t = t , the previous relation still gives us

upk * = upk -H(R) • (H(R) -H(R')) -1 (upk -upk )
from which it is not possible to conclude that upk * = upk = upk . In particular, it does not seem possible to extract from these transactions a short vector e * such that upk * = F • e * , which invalidates the original proof.

Discussion. This problem is not exclusive to lattice-based constructions but we note that the proofs can be fixed in the case where upk = g x for some secret scalar x and where the transactions contain a signature of knowledge of the different secret values (including x). This is actually quite frequent in existing constructions (e.g. [CHL05, CG07, CG10] and the ROM constructions of [CPST15a, CPST15b, PST17]).

Indeed, in such a case, the double-spending tag is of the form T = upk•F s (i) R where s is a seed, i ∈ [1, N ] is an integer, and R is derived from public information. In case of double-spending, there are two tags T and T from which one can recover upk by computing

(T R /(T ) R ) 1 R -R .
Here again, an adversary might generate upk, s, R, upk , s , R such that the corresponding tags T and T satisfy (T R /(T ) R ) 1 R -R = upk * , for some honest public key upk * . However, in this case, the reduction can recover the discrete logarithm of upk * by extracting all the secret values from the proofs generated by the adversary. This means that exculpability can still be proven under the discrete logarithm assumption and so that the original proofs can easily be fixed by adding this remark.

Unfortunately, this patch is inherent to signatures of knowledge of discrete logarithms in the Random Oracle Model, and so cannot be applied to other settings (e.g. lattices [LLNW17]) or to standard model constructions [CPST15a,CPST15b,PST17]. In particular, this means that divisible e-cash secure in the standard model or even lattice-based compact e-cash is still an open problem.

Contributions

One can note that the above issue has remained undetected for more than a decade, whereas all compact/divisible e-cash systems are based on the same intuition. However, the latter has never been formalized. Intuition is necessary to design and understand a scheme but we must be very careful when it comes to complex primitives. This pleads for a more formal approach, where the common intuition are translated into a generic framework.

In addition, this lack of generic framework leads designers to create and combine several ad-hoc mechanisms, with complex security proofs that often rely on tailored computational assumptions. This stands in sharp contrast with a related primitive, group signature, whose foundations were studied by Bellare et al [BMW03,BSZ05] and for which very efficient constructions exist.

Two Generic Frameworks and Concrete Instantiations. In this work, we propose two generic frameworks that yield secure divisible e-cash systems from constrained PRFs, a wellknown cryptographic primitive. For each framework, we identify the properties it must achieve and, so, we reduce the problem of constructing divisible e-cash systems to a simpler one: efficient instantiations of the building blocks. We additionally provide examples of instantiations to show that our frameworks are not artificial but can lead to practical schemes.

Our Approach: Constrained Pseudo-Random Functions. Starting from the work of Camenisch et al [CHL05] that defines the serial numbers as outputs of a PRF, we formalize the requirements on divisible e-cash systems as properties that must be achieved by the PRFs. Actually, the main requirement is that the serial numbers can be revealed by batches, which means that it must be possible to reveal some element k S that (1) allows to compute F s (i) ∀i ∈ S ⊂ [1, N ] and (2) does not provide any information on the other serial numbers, i.e. on the outputs of the PRF outside S. This exactly matches the definition of constrained PRF, a notion formalized in [BW13, KPTZ13,BGI14].

There are also several requirements that must implicitly be fulfilled by the constrained key k S , for anonymity to hold, and namely unlinkability of the transactions: different constrained keys generated from the same master key must be unlinkable, which also requires k S to hide any information on the subset S (besides its cardinality, which will represent the amount). All these notions were already defined in previous papers on constrained PRFs (e.g. [BFP + 15, BLW17, BKM17]), although we only need here weaker versions of the original definitions.

Collision Resistance. Intuitively, unlinkability of k S will ensure honest users' privacy. However, e-cash systems must also be able to deal with dishonest parties, including the bank itself. In such a case, the adversary has much more power than in usual PRF security games: it has a total control on the seeds and could use it to create collisions between serial numbers or worse, falsely accuse an honest user. To thwart such attacks, we need to introduce a new security property for constrained PRFs, that we call collision resistance. It requires that different keys (even chosen by the adversary) yield different outputs, similarly to the standard collision resistance notion for hash functions. We provide more details in Section 2.2. Key Homomorphic vs. Delegable Constrained PRFs. We then investigate two different scenarios, leading to two different (but related) frameworks. In the former, we consider key homomorphic constrained PRF [BFP + 15] whereas we use delegatable constrained PRF [KPTZ13] in the latter. Interestingly, we note that all existing divisible e-cash systems can be associated with one of these frameworks, which brings two benefits. First, this means that it is possible to get, from existing systems, constrained PRFs (either key homomorphic or delegatable) that achieve all the properties we list above. We therefore believe that our results might be of independent interest outside e-cash since it draws attention on (implicit) constructions of constrained PRFs that might have been ignored. Second, it means that some of the constructions affected by the exculpability issue (see Section 1.2) could be fixed by using the same tricks we introduce in our frameworks.

Serial Numbers and Double Spending Tags. Once we have identified the sufficient properties for our PRFs, we explain how to use them to generically construct the serial numbers and the double spending tags. This is definitely the main contribution of the paper. We then describe how to combine these PRFs with very standard primitives, namely digital signatures, commitment schemes and NIZK proofs, to get a divisible e-cash system.

First Divisible e-Cash System Secure in the Standard Model. Finally, we provide detailed proofs for both frameworks to show that the security of the overall construction generically holds under the security of each of the building blocks. Concretely, this means that, for any setting, one can construct a secure divisible e-cash system by essentially designing a constrained PRF achieving some simple properties. To illustrate this point, we describe, by using our framework, the first divisible e-cash system secure in the standard model, since previous analyses in the standard model are all wrong, as explained above.

Several Security Issues. Another interesting outcome of our formalization process is that it highlights some security issues that have often been overlooked in previous papers.

First, there is the critical issue with exculpability, as discussed in Section 1.2. Second, security models of e-cash systems only deal with the security of the users and the bank. We indeed note that (almost) no property related to the security of the merchant has ever been formalized. In particular, the ability of the merchants to deposit the electronic coins they received is not ensured by the e-cash scheme itself. For example, in most systems, nothing prevents the spender from depositing the coins he has just spent5 : we define a new property, called clearing, that formalizes the security requirements for the merchants.

Eventually, in the withdrawal procedure, the coins secret values are traditionally generated collaboratively by the bank and the user. Our security analysis shows that this collaborative generation does not seem to provide any relevant benefit, at least for our frameworks.

Organization

We recall in Section 2.1 the notion of constrained pseudo-random functions and detail the security properties required in order to construct divisible e-cash systems in Section 2.2 . Concrete instantiations of constrained PRFs can be found in Section 9. The syntax and the security model of divisible e-cash are described in Section 3. We provide, in Section 4, the intuition behind our two frameworks before presenting the formal description of the latter in Sections 5 and 7. The security analysis of our generic constructions are respectively provided in Sections 6 and 8. Finally, a standard model instantiation of our first framework can be found in Section 10.

Constrained Pseudo-Random Function

Our constructions of divisible e-cash systems will heavily rely on constrained pseudo-random functions [BW13, KPTZ13, BGI14] with special features that we present below. But first, we recall the syntax of this primitive.

Syntax

For sake of simplicity, our PRF K × S → Y will only be constrained on subsets of S. We will then not consider the more general setting where it is constrained according to a circuit. Our PRF thus consists of the following five algorithms.

-Setup(1 λ , {S i } n i=1 ): On input a security parameter λ and a set of admissible subsets S i ⊂ S, this algorithm outputs the public parameters pp that will be implicitly taken as inputs by all the following algorithms; -Keygen(): this algorithm outputs a master secret key s ∈ K; -CKey(s, X ): On input the master key s and a set X , this deterministic6 algorithm outputs a constrained key k X ∈ K X or ⊥; -Eval(s, x): On input the master key s and an element x ∈ S, this deterministic algorithm outputs a value y ∈ Y; -CEval(X , k X , x): On input a set X , a constrained key k X and an element x ∈ X , this deterministic algorithm outputs a value y ∈ Y.

For conciseness, we will denote CEval(X , k X , x) by CEval X (k X , x).

A constrained PRF is correct for a family of subsets

{S i } n i=1 if, for all λ ∈ N, pp ← Setup(1 λ , {S i } n i=1
), s ← Keygen() and x ∈ S i ⊆ S, we have, with overwhelming probability, CEval S i (CKey(s, S i ), x) = Eval(s, x). And this common value is PRF s (x).

Definition 1. A constrained PRF is key homomorphic [BLMR13, BFP + 15] if: 1. Y, K and K S i are groups ∀i ∈ [1, n] 2. ∀i ∈ [1, n], CEval S i (k 1 • k 2 , x) = CEval S i (k 1 , x) • CEval S i (k 2 , x), ∀k 1 , k 2 ∈ K S i and x ∈ S i . 3. CKey(s 1 • s 2 , S i ) = CKey(s 1 , S i ) • CKey(s 2 , S i ), ∀s 1 , s 2 ∈ K and i ∈ [1, n]
We use the multiplicative notation for our group operations, in K and K S i . As in [BFP + 15], we require that the CKey algorithm, for any S i , is a group homomorphism from K into K S i .

Finally, some of our constructions will require the ability to derive a constrained key k S i from any key k S j such that S i ⊂ S j . This requires the following modifications of the syntax and of the correctness property.

Definition 2. A constrained pseudo-random function is delegatable [KPTZ13] if it additionally supports the following algorithm:

-CKey(k X , X ): on input a constrained key k X ∈ K X and a set X ⊆ X , this algorithm outputs a constrained key k X ∈ K X or ⊥.

To be correct, the delegatable constrained PRF must additionally satisfy, for a family of subsets {S i } n i=1 , that, for all λ ∈ N, pp ← Setup(1 λ , {S i } n i=1 ), s ← Keygen(), S i ⊂ S j ⊆ S, and k S j ← CKey(s, S j ), we have, with overwhelming probability, CKey(k S j , S i ) = CKey(s, S i ).

Security Model

Our divisible e-cash constructions will use different types of constrained PRF, satisfying some of the following security requirements. Most of them have already been defined in previous works but we will need specific variants for some of them.

Pseudo-Randomness (PR). The first property one may expect from a constrained PRF is pseudo-randomness, which informally requires that an adversary, even given access to constrained keys, cannot distinguish the PRF evaluation from random, for a new point (not already queried and outside sets of known constrained keys). It is defined by 1 where the adversary has access to the following oracles:

Exp pr -b A (1 λ , {S i } n i=1 ) in Figure
-OCKey(X ): on input a set X , this algorithm returns CKey(s, X ) if ∃i ∈ [1, n] such that X = S i and ⊥ otherwise. -OEval(x): on input an element x ∈ S, this algorithm returns Eval(s, x).

A constrained PRF is pseudo-random if Adv pr (A) = | Pr[Exp pr -1 A (1 λ , {S i } n i=1 ) = 1] -Pr[Exp pr -0 A (1 λ , {S i } n i=1 ) = 1]| is negligible for any A. Exp pr -b A (1 λ , {Si} n i=1 ) -Pseudo-Randomness 1. pp ← Setup(1 λ , {Si} n i=1 ) 2. s ← Keygen() 3. x ← A OCKey,OEval (pp) 4. y0 ← Eval(s, x) 5. y1 $ ← Y 6. b * ← A OCKey,OEval (pp, y b ) 7. If OEval was queried on x, return 0 8. If OCKey was queried on X x, return 0 9. Return b * Exp kpr -b A (1 λ , {Si} n i=1 ) -Key Pseudo-Randomness 1. pp ← Setup(1 λ , {Si} n i=1 ) 2. s ← Keygen() 3. i * ← A OCKey,OEval (pp) 4. k0 ← CKey(s, Si * ) 5. k1 $ ← KS i * 6. b * ← A OCKey,OEval (pp, k b ) 7. If OEval was queried on x ∈ Si * , return 0 8. If OCKey was queried on X such that X ∩ Si * = ∅, return 0 9. Return b * Exp ckpr -b A (1 λ , {Si} n i=1 ) -Combined Key Pseudo-Randomness 1. ppj ← Fj.Setup(1 λ , {Si} n i=1 ), ∀j ∈ [1, t] 2. s ← F1.Keygen() 3. i * ← A OCKey,OEval ({ppj} t j=1 ) 4. (k 1 0 , . . . , k t 0 ) ← (F1.CKey(s, Si * ), . . . , Ft.CKey(s, Si * )) 5. (k 1 1 , . . . , k t 1 ) $ ← K t S i * 6. b * ← A OCKey,OEval ({ppj} t j=1 , (k 1 b , . . . , k t b )) 7.
If OEval was queried on x ∈ Si * , return 0 8. If OCKey was queried on X such that X ∩ Si * , return 0 9. Return b * Fig. 1. Pseudo-Randomness Games for Constrained Pseudo-Random Functions Key Pseudo-Randomness (KPR). We note that the previous definition only requires pseudorandomness for the output of the PRF. As in [BFP + 15] we extend this property to the constrained keys themselves, leading to a property that we call key pseudo-randomness. However, compared to [BFP + 15], we additionally require some form of key privacy, in the sense of [KPTZ13]. In particular, we need that constrained keys issued for subsets of the same size7 should be indistinguishable.

Let F be a constrained PRF defined for a family of subsets

{S i } n i=1 satisfying K S i = K S j ∀i, j such that |S i | = |S j |. F is key pseudo-random if Adv kpr (A) = | Pr[Exp kpr -1 A (1 λ , {S i } n i=1 ) = 1] - Pr[Exp kpr -0 A (1 λ , {S i } n i=1 ) = 1]| is negligible for any A, where the game Exp kpr -b A (1 λ , {S i } n i=1
) is defined in Figure 1.

Combined Key Pseudo-Randomness (CKPR). In practice, divisible e-cash systems require multiple pseudo-random values, some acting as the unique identifier of the coin (the serial number) and some being used to mask the spender's identity. If F is key pseudo-random, a solution could be to split the constrained key k S i ← CKey(s, S i ) into several parts, each of them being used as pseudo-random values. Unfortunately, combining this solution with zeroknowledge proofs would be very complex. In our frameworks, we will follow a different approach and will generate several pseudo-random values by using different PRFs F 1 , . . . , F t evaluated on the same master key s and the same subset S i : Let F 1 . . . , F t be constrained PRFs K × S → Y defined for the same family of subsets {S i } n i=1 satisfying K S i = K S j ∀i, j such that |S i | = |S j |. We say that the family (F 1 , . . . , F t ) achieves combined key pseudo-randomness if

Adv ckpr (A) = | Pr[Exp ckpr -1 A (1 λ , {S i } n i=1 ) = 1] -Pr[Exp ckpr -0 A (1 λ , {S i } n i=1 ) = 1]| is negligible for any A, where the game Exp ckpr -b A (1 λ , {S i } n i=1
) is defined in Figure 1. This can be done very easily by constructing each F i similarly but with different public parameters: let us assume that F 1 .CKey(s,

S i ) = k 1 S i = g α i •s 1
∀i for some generator g 1 of K S i . We can define other PRFs F 2 , . . . F t with the same input spaces by setting F j .CKey(s,

S i ) = k j S i = g α i •s j
for a different generator g j . In such a case, we get t values (k 1 S i , . . . , k t S i ) which are indistinguishable from a random element of K t S i assuming key pseudo-randomness of F 1 and the DDH assumption (see Section 9 for more details).

Strong Key Pseudo-Randomness. In the case where F is a delegatable constrained PRF, we will need a variant of the key pseudo-randomness property that we call strong key pseudorandomness. The latter requires that key pseudo-randomness hold even if some information leaks during the delegation process. For sake of simplicity, in this context, we will only consider a family of subsets {S i } of S such that:

S i ∩ S j = ∅ ⇒ S i ⊂ S j or S j ⊂ S i
We can therefore define the function D which returns for each subset S i = S the smallest subset containing (strictly) S i . We will define our leakage by introducing a family of functions

H, {H S i } n i=1 such that H : K → G and H S i : K D(S i ) → G for some group G.
In our new experiment, when b = 0, the adversary still receives the constrained key k S i for the subset S i of its choice, but now it additionally receives the evaluation of H S i on the constrained key k D(S i ) of its parent subset 8 . We require this pair to be indistinguishable from a random pair generated from the corresponding domains. We note that this property is achieved by any key pseudo-random delegatable PRF when H and {H S i } n i=1 are random oracles. We will also show in Appendix 9 that it is possible to construct such PRFs and functions H and {H S i } n i=1 in the standard model.

A function F achieves strong key pseudo-randomness for a family of function H,

{H S i } n i=1 if Adv skpr (A) = | Pr[Exp skpr -1 A (1 λ , {S i } n i=1 , {H S i } n i=1 ) = 1] -Pr[Exp skpr -0 A (1 λ , {S i } n i=1 , {H S i } n i=1 ) = 1]| is negligible for any A, where the game Exp skpr -b A (1 λ , {S i } n i=1 , {H S i } n i=1 ) is defined in Figure 2.
Finally, we define the strong combined key pseudo-randomness where the adversary receives a tuple of constrained keys (k 1 0 , . . . , k t 0 ) ← (F 1 .CKey(s, S i * ), . . . , F t .CKey(s, S i * )) in addition to

H D(S * i ) (CKey(s, S D(S i * )
)), instead of just one constrained key.

Exp skpr -b A (1 λ , {Si} n i=1 , H, {HS i } n i=1 ) -Strong Key Pseudo-Randomness 1. pp ← Setup(1 λ , {Si} n i=1 ) 2. s ← Keygen() 3. i * ← A OCKey,OEval (pp) 4. If Si * = S 5. (k 0 0 , k 1 0 ) ← (CKey(s, S), H(s)) 6. (k 0 1 , k 1 1 ) $ ← K × G 7. else 8. (k 0 0 , k 1 0 ) ← (CKey(s, Si * ), H S * i (CKey(s, D(Si * )))) 9. (k 0 1 , k 1 1 ) $ ← KS i * × G 10. b * ← A OCKey,OEval (pp, H, {HS i } n i=1 , (k 0 b , k 1 b )) 11.
If OEval was queried on x ∈ Si * return 0 12. If OCKey was queried on X such that X ∩ Si * , return 0. 13. Return b * Fig. 2. Strong Key Pseudo-Randomness Collision Resistance (CR). In our divisible e-cash constructions, the PRFs will mostly be used to generate serial numbers that act as unique identifiers of the coins. If a coin is spent twice (or more) the same serial number will appear in several transactions, which provides a very simple way to detect frauds. However, it is important to ensure that collisions between serial numbers only occur in such cases. Otherwise, this could lead to false alerts and even false accusations against an honest user.

8 the case Si = S is addressed separately. Collision Resistance 1 Exp cr -1 A (1 λ , {Si} n i=1 ) 1. pp ← Setup(1 λ , {Si} n i=1 ) 2. (s1, s2, x1, x2) ← A(pp) 3. If (s1, x1) = (s2, x2), return 0 4. Return Eval(s1, x1) = Eval(s2, x2) Collision Resistance 2 Exp cr -2 A (1 λ , {Si} n i=1 ) 1. pp ← Setup(1 λ , {Si} n i=1 ) 2. (i, k1, k2, x) ← A(pp) 3. If k1 = k2, return 0 4. Return CEvalS i (k1, x) = CEvalS i (k2, x) Collision Resistance 3 Exp cr -3 A (1 λ , {Si} n i=1 ) (for Key Homomorphic Constrained PRFs only) 1. pp ← Setup(1 λ , {Si} n i=1 ) 2. (i, j, ki, kj, x) ← A(pp) 3. If i = j, return 0 4. If ki = 1K S i ∨ kj = 1K S j , return 0 5. Return CEvalS i (ki, x) = CEvalS j (kj, x)
At first sight, it might seem that this property is implied by pseudo-randomness. Unfortunately, this is not true in the context of e-cash where the adversary has total control of the master secret keys, contrarily to the adversary of the pseudo-randomness game. We therefore need to define a new property that we call collision resistance. Informally, it says that it should be hard to generate collisions between the outputs of the PRFs. However, some subtleties arise because of the different kinds of keys (secret master keys, constrained keys) that we consider here. We then define three variants of this property that are described in Figure 3.

For k ∈ {1, 2, 3}, a constrained PRF achieves collision resistance-k if, for any A,

Adv cr -k (A) = Pr[Exp cr -k A (1 λ , {S i } n i=1 ) = 1] is negligible.
We provide in Section 9 several examples of PRFs achieving these properties.

Divisible E-Cash

The syntax and the formal security model are drawn from [CPST15a, PST17]. We nevertheless introduce several changes to make them more generic but also to add some specifications that were previously implicit only.

Syntax

A divisible e-cash system is defined by the following algorithms, that involve three types of entities, the bank B, a user U and a merchant M. Our model defines a unique value N for the divisible coin but it can easily be extended to support several different denominations.

-Setup(1 λ , N ): On input a security parameter λ and an integer N , this probabilistic algorithm outputs the public parameters pp for divisible coins of global value N . We assume that pp are implicit to the other algorithms, and that they include λ and N . They are also given as an implicit input to the adversary, we will then omit them. -BKeygen(): This probabilistic algorithm executed by the bank B outputs a key pair (bsk, bpk).

It also sets L as an empty list, that will store all deposited coins. We assume that bsk contains bpk. -Keygen(): This probabilistic algorithm executed by a user U (resp. a merchant M) outputs a key pair (usk, upk) (resp. (msk, mpk)). We assume that usk (resp. msk) contains upk (resp. mpk).

-Withdraw(B(bsk, upk), U(usk, bpk)): This is an interactive protocol between the bank B and a user U. At the end of this protocol, the user gets a divisible coin C of value N or outputs ⊥ (in case of failure) while the bank stores the transcript of the protocol execution or outputs ⊥. -Spend(U(usk, C, bpk, V ), M(msk, bpk, info, V )): This is an interactive protocol between a user U and a merchant M. Here, info denotes a set of public information associated to the transaction, by the merchant, and V denotes the amount of this transaction. At the end of the protocol the merchant gets Z along with a proof of validity Π or outputs ⊥. U then either updates C or outputs ⊥.

-Deposit(M(msk, bpk, (V, info, Z, Π)), B(bsk, L, mpk)): This is an interactive protocol between a merchant M and the bank B where the former first sends a transcript (V, info, Z, Π) along with some additional data µ. B then checks (1) the validity of all these elements and (2) that this merchant has not already deposited a transcript associated with info. If condition (1) is not fulfilled, then B aborts and outputs ⊥. If condition (2) is not fulfilled, then B returns another transcript (V , info, Z , Π ) along with the associated µ . Otherwise, B recovers the V serial numbers SN i 0 , . . . , SN i V -19 derived from Z and compares them to the set L of all serial numbers of previously spent coins. If there is a match for some index i k , then B returns a transcript (V , Z , Π , info ) such that SN i k is also a serial number derived from Z . Else, B stores these new serial numbers in L and keeps a copy of (V, info, mpk, Z, Π).

-Identify((V, info, mpk, Z, Π), (V , info , mpk , Z , Π ), bpk): On the wo transcripts, this deterministic algorithm outputs 0 if info = info , if one of the transcripts is invalid, or if the serial numbers derived from these transcripts do not collide. Else it outputs a user's public key upk or ⊥.

-CheckDeposit([(V, info, mpk, Z, Π), µ], bpk): This deterministic algorithm outputs 1 if [(V,
info, Z, Π), µ] are valid elements deposited by a merchant whose public key is mpk and 0 otherwise.

Our model does not place restrictions on the values that can be spent nor on the size of a spending transcript. It is therefore more generic and in particular also fits compact e-cash systems where the serial numbers can only be revealed one by one.

Security Model

Existing security models essentially focus on the the user's and the bank's interests. The former must indeed be able to spend their coins anonymously without being falsely accused of frauds while the latter must be able to detect frauds and identify the perpetrators. This is formally defined by three security properties in [CPST15a]: anonymity (user' spendings are anonymous, even with respect to the bank), exculpability (honest users cannot be falsely accused, even by the bank) and traceability (an author of overspending should be traced back). However, all these notions (and the corresponding ones in previous papers) fail to capture an important security property for the merchant: he must always be able to clear his transactions, but also, he should be the only one able to deposit them. This is especially problematic for e-cash because users can reproduce the transcripts of their spendings. Designers of existing divisible e-cash systems seem to be more or less aware of this issue10 because they usually attribute a signing key to the merchant. However, these systems do not specify the security properties expected from the corresponding signature scheme and most of them even do not specify which elements should be signed.

For completeness, we therefore add the property of clearing (only the recipient merchant can perform the deposit) to the above usual ones. All of them are defined in Figure 4 and make use of the following oracles:

-OAdd() is an oracle used by the adversary A to register a new honest user (resp. merchant).

The oracle runs the Keygen algorithm, stores usk (resp. msk) and returns upk (resp. mpk) to A. In this case, upk (resp. mpk) is said honest. -OCorrupt(upk/mpk) is an oracle used by A to corrupt an honest user (resp. merchant) whose public key is upk (resp. mpk). The oracle then returns the corresponding secret key usk (resp. msk) to A along with the secret values of every coin withdrawn by this user. From now on, upk (resp. mpk) is said corrupted. -OAddCorrupt(upk/mpk) is an oracle used by A to register a new corrupted user (resp. merchant) whose public key is upk (resp. mpk). In this case, upk (resp. mpk) is said corrupted.

The adversary could use this oracle on a public key already registered (during a previous OAdd query) but for simplicity, we do not consider such case as it will gain nothing more than using the OCorrupt oracle on the same public key. -OWithdraw U (upk) is an oracle that executes the user's side of the Withdraw protocol. This oracle will be used by A playing the role of the bank against the user with public key upk. -OWithdraw B (upk) is an oracle that executes the bank's side of the Withdraw protocol. This oracle will be used by A playing the role of a user whose public key is upk against the bank. -OSpend(upk, V ) is an oracle that executes the user's side of the Spend protocol for a value V . This oracle will be used by A playing the role of the merchant M. -OReceive(mpk, V ) is an oracle that executes the merchant's side of the Spend protocol for a value V . This oracle will be used by A playing the role of a user. -ODeposit(mpk, V, info) is an oracle that executes the merchant's side of the Deposit protocol for a transaction of amount V associated with the value info. This oracle cannot be queried on two inputs with the same value info. It will be used by A playing the role of the bank.

In the experiments, users are denoted by their public keys upk, c upk denotes the amount already spent by user upk during OSpend queries, m upk the number of divisible coins that he has withdrawn and Tr i the transcript (V i , info i , mpk i , Z i , Π i ) for any i ∈ N. This means that the total amount available by a user upk is m upk • N . The number of coins withdrawn by all users during an experiment is denoted by m.

For sake of simplicity, we assume that all merchants are corrupted, and added through OAddCorrupt queries, in the traceability, exculpability and anonymity experiments. We therefore do not need to add access to the OReceive and ODeposit oracles in the latter. We stress that this is not a restriction since the OAddCorrupt oracle provides more power to the adversary than the OAdd and OCorrupt ones. Similarly, we assume that the bank and all the users are corrupted in the clearing game and so do not provide access to the OSpend, OWithdraw U and OWithdraw B oracles in it.

Our clearing game ensures that no one can forge a valid deposit query from the merchant. This means in particular that the bank cannot rightfully refuse the deposit of an honest merchant (because it will not be able to provide a valid proof that the transcript has already been deposited) and that it cannot falsely accuse a merchant of trying to deposit the same transcript several times.

A divisible E-cash system is said to be traceable, exculpable, anonymous, and/or clearable if Succ tra (A), Succ excu (A), Adv anon (A), and/or Succ clear (A), are respectively negligible for any probabilistic polynomial adversary A, where

Succ tra (A) = Pr[Exp tra A (1 λ , N ) = 1] Succ excu (A) = Pr[Exp excu A (1 λ , N ) = 1] Succ clear (A) = Pr[Exp clear A (1 λ , N ) = 1] Adv anon (A) = | Pr[Exp anon-1 A (1 λ , N ) = 1] -Pr[Exp anon-0 A (1 λ , N ) = 1]| Exp tra A (1 λ , N ) -Traceability Security Game 1. pp ← Setup(1 λ , N ) 2. (bsk, bpk) ← BKeygen() 3. {(Vi, infoi, mpk i , Zi, Πi)} u i=1 $ ← A OAdd,OCorrupt,OAddCorrupt,OWithdraw B ,OSpend (bpk) 4. If u i=1
Vi > m • N and ∀i = j, Identify(Tri, Trj, bpk) =⊥, then return 1 5. Return 0

Exp excu A (1 λ , N ) -Exculpability Security Game 1. pp ← Setup(1 λ , N ) 2. bpk ← A() 3. [Tr1, Tr2] ← A OAdd,OCorrupt,OAddCorrupt,OWithdraw U ,OSpend () 4. If Identify(Tr1, Tr2, bpk) = upk and upk not corrupted, then return 1 5. Return 0 Exp anon-b A (1 λ , N ) -Anonymity Security Game 1. pp ← Setup(1 λ , N ) 2. bpk ← A() 3. (V, upk 0 , upk 1 , mpk) ← A OAdd,OCorrupt,OAddCorrupt,OWithdraw U ,OSpend () 4. If upk i is not registered for i ∈ {0, 1}, then return 0 5. If c upk i > m upk i • N -V for i ∈ {0, 1}, then return 0 6. (V, Z, Π, info) ← Spend(C(usk b , C, mpk, V ), A()) 7. c upk 1-b ← c upk 1-b + V 8. b * ← A OAdd,OCorrupt,OAddCorrupt,OWithdraw U ,OSpend () 9. If upk i has been corrupted for i ∈ {0, 1}, then return 0 10. Return (b = b * ) Exp clear A (1 λ , N ) -Clearing Security Game 1. pp ← Setup(1 λ , N ) 2. bpk ← A() 3. [(V, info, mpk, Z, Π), µ] ← A OAdd,OCorrupt,OAddCorrupt,OReceive,ODeposit () 4. If CheckDeposit([(V, info, mpk, Z, Π), µ]
, bpk) = 0, then return 0 5. If mpk is corrupted, then return 0 6. If (mpk, V, info) has been queried to ODeposit, then return 0 7. Return 1 Fig. 4. Security Games for Divisible E-Cash 4 High-Level Description Before introducing a generic framework for divisible e-cash, we focus on the heart of such systems, namely the construction of the serial numbers and of the double-spending tags.

Regarding the former, the fact that each serial number SN must look random has led designers to use pseudo-random functions (PRFs). More specifically, every anonymous divisible e-cash scheme defines SN i as F.Eval(s, i) where s is the master key and i ∈ [1, N ]. However, to avoid a cost linear in the amount V it is necessary to provide a way to reveal these serial numbers by batches. Designers of divisible e-cash systems (e.g. [CG07, ASM08, CG10, CPST15a, CPST15b, PST17]) have thus constructed pseudo-random functions with a special feature: given s and a subset X ⊆ [1, N ], one can compute k X allowing to evaluate the PRF only on the elements of X . This matches the definition of constrained PRFs, as described above. To spend a value V , the user can now simply reveal a constrained key k X for a set X of size V . However additional properties are required here to achieve anonymity. Indeed, informally, the constrained key must hide information on the spender (more specifically on the master secret key) and on the subset X11 itself. All these properties are captured by key pseudo-randomness that we defined in Section 2. Eventually, to avoid false positive in the fraud detection process, we will need the collision resistance properties defined in the same section.

Therefore, constructing divisible e-cash with efficient double-spending detections is roughly equivalent to constructing a key pseudo-random, collision resistant constrained PRF for subsets of [1, N ] that smoothly interacts with Non-Interactive Zero-Knowledge (NIZK) proofs. However, detection of double spending is not enough, it must also be possible to identify double spenders by using the additional information contained in the double-spending tag. This adds further requirements on the PRF and leads to two constructions that we present below.

Construction using Key Homomorphism

Our first construction of double-spending tag is reminiscent of the techniques used by compact e-cash systems [CHL05, LLNW17]. In these papers, the double spending tag T i associated with SN i is of the form ID • (F .Eval(s , i)) R , where ID is the "identity" of the spender (usually his public key), F is a PRF seeded with a master secret key s (note that we may have F = F or s = s but not both) and R is a public identifier of the transaction.

Intuitively, the idea behind this tag is that (F .Eval(s , i)) R will perfectly mask the user's identity as long as the latter does not overspend his coin. In case of double spendings, there will indeed be two tags T

(1) i and T

(2) i of the form ID • (F .Eval(s , i)) R 1 and ID • (F .Eval(s , i)) R 2 . Therefore, by computing:

((T (1) i ) R 2 /(T (2) i ) R 1 ) 1/(R 2 -R 1 )
the bank can directly recover the identity ID of the defrauder. This idea was adapted in [CPST15a, CPST15b, PST17] to the context of divisible e-cash by replacing F .Eval(s , i) with a key constrained to the appropriate subset.

However, we have explained in Section 1.2 that this process of identification is problematic and could lead to false accusations against honest user, thus breaking exculpability. Concretely, the problem arises from the fact that the above formula may output ID while involving tags T

(1) i and T

(2) i produced for different identities. Indeed, in the exculpability game, a malicious bank could cooperate with malicious users and merchants to select values

ID 1 , ID 2 , R 1 , R 2 , s 1 and s 2 such that ((T (1) i ) R 2 /(T (2) i ) R 1 ) 1/(R 2 -R 1 ) = ((ID 1 • (F .Eval(s 1 , i 1 )) R 1 ) R 2 /(ID 2 • (F .Eval(s 2 , i 2 )) R 2 ) R 1 ) 1/(R 2 -R 1 ) = ID.
This means that, in general, this tag construction cannot be used as it is.

To prevent this problem, our generic construction uses four PRFs, that we will denote by F 1 , F 2 , F 3 and F 4 , defined for the same family of subsets {S i } n i=1 and sharing the same key space K. We additionally require F 2 , F 3 and F 4 to be key homomorphic.

Let s ∈ K be a secret master key and S i be a subset of size V , the amount of the transaction. As previously12 , our first PRF will be used to reveal k

(1) S i ← F 1 .CKey(s, S i ). Likewise, our third PRF will be used to generate an element of the form13 ID R • k 3 S i , with k 3 S i ← F 3 .CKey(s, S i ). The novelty here is that these values will only constitute a part of the serial number and of the double spending tag. The other parts will be derived from k

(2)

S i ← F 2 .CKey(s • id, S i ),
where id is some element of K associated with the public identity ID, and from ID•k 4 S i where k 4 S i ← F 4 .CKey(s, S i ). More specifically,

SN j = F 1 .CEval S i (k (1) S i , j)||F 2 .CEval S i (k (2) S i , j) T S i = (ID R • k 3 S i , ID • k 4 S i ).
Intuitively, the fact that the master secret key of F 2 depends on id will ensure that no collision can occur for different users, which thwarts the previous attack. Moreover, the first part of SN j still ensures that collisions can only occur for spendings involving the same master key, evaluated on the same element j ∈ S. The last element of the double-spending tag has a more technical purpose, it prevents identification errors in the case where the colliding serial numbers have been generated using different subsets (see Remark 3). Therefore, if two spendings with respective tags T

(1) S i 1 and T

(2) S i 2 lead to a collision, then we have:

T (1) S i 1 = (ID R 1 • k 3 S i 1 , ID • k 4 S i 1 ) T (2) S i 2 = (ID R 2 • k 3 S i 2 , ID • k 4 S i 2 ) with j ∈ S i 1 ∩ S i 2 . If S i 1 = S i 2 = S i , we can compute: F 3 .CEval S i (T (1)
S i [1], j) = F 3 .CEval S i (ID R 1 , j) • F 3 .CEval S i (k 3 S i , j) F 3 .CEval S i (T (2) S i [1], j) = F 3 .CEval S i (ID R 2 , j) • F 3 .CEval S i (k 3 S i , j) Since k 3 S i 1 and k 3 S i 2
are derived from the same master key, correctness ensures that F 3 .CEval S i (k 3 S i , j) = F 3 .CEval S i (k 3 S i , j). Therefore:

F 3 .CEval S i (T (2) S i [1], j) • F 3 .CEval S i (T (1)
S i [1], j) -1 = F 3 .CEval S i (ID R 2 , j) • F 3 .CEval S i (ID -R 1 , j)
The bank can then perform an exhaustive search on the set of public identities {ID i } until it gets a match. Identification of defrauders is then possible with a linear cost in the number of users of the system. Now in the case where S i 1 = S i 2 , we have, for any identity ID * :

F 4 .CEval S i 1 (T (1) S i 1 [2]/(ID * ), j) = F 4 .CEval S i 1 (ID/(ID * ), j) • F 4 .CEval S i 1 (k 4 S i 1 , j) F 4 .CEval S i 2 (T (1) S i 2 [2]/(ID * ), j) = F 4 .CEval S i 2 (ID/(ID * ), j) • F 4 .CEval S i 2 (k 4 S i 2 , j)
Here again,

F 4 .CEval S i 1 (k 4 S i 1 , j) = F 4 .CEval S i 2 (k 4 S i 2
, j), therefore:

F 4 .CEval S i 1 (T (1) S i 1 [2]/(ID * ), j)/F 4 .CEval S i 2 (T (1) S i 2 [2]/(ID * ), j) = F 4 .CEval S i 1 (ID/(ID * ), j)/F 4 .CEval S i 2 (ID/(ID * ), j)
and one can easily identify the case where ID * = ID since this it is the only one where the right member equals to 1 Y if F 4 achieves collision resistance-3.

Remark 3. The use of two elements in the double-spending tag may seem surprising, in particular because the equality

F 3 .CEval S i 1 (T (2) S i 2 [1], j) • F 3 .CEval S i 2 (T (1) S i 2 [1], j) -1 = F 3 .CEval S i 1 (ID R 2 , j) • F 3 .CEval S i 2 (ID -R 1 , j)
still holds for the right ID in the case where S i 1 = S i 2 . However, in this case, we cannot ensure that this equality only holds for ID, it might also work for other identities, leading to obvious identification issues.

Construction using Delegation

Our second construction is inspired by what has been the main framework for divisible e-cash for many years (e.g. [CG07,CG10,Mär15]). It makes use of a family of two delegatable PRFs (F 1 , F 2 ) that achieves strong combined key pseudo-randomness for a family of functions (H, {H S i } n i=1 ) such that H : K → G and H S i : K D(S i ) → G for some group G.We recall that we have defined this notion for a PRF supporting a family of subsets {S i } of [1, N ] such that:

S i ∩ S j = ∅ ⇒ S i ⊂ S j or S j ⊂ S i
Therefore, for each subset S i = [1, N ], it is possible to define the smallest subset containing strictly S i . It is given by a function D.

To spend a value V , a user whose coin secret key is s selects a subset S i containing V elements and will reveal the following information:

1. k (1) S i ← F 1 .CKey(s, S i ) 2. k (2) S i ← upk • F 2 .CKey(s, S i ) 3. T S i ← upk • H S i ) (F 1 .CKey(s, D(S i ))) R
for some public element R. The first element will be used by the bank to derive the serial numbers SN t ← F 1 .CEval S i (k

(1) S i , t) ∀t ∈ S i . The second element prevents the problem we mention in Section 4.1: it will be used to discard collisions between spendings involving different users. Finally, the last element is the double-spending tag but the identification process is more subtle than in the previous case, as we explain below.

Let (k

(1)

S i , k (2)
S i , T S i ) and (k

(1)

S j , k (2)
S j , T S j ) be two spendings leading to a collision, i.e. such that there are t i ∈ S i and t j ∈ S j verifying the equation:

F 1 .CEval S i (k (1) S i , t i ) = F 1 .CEval S j (k (1) S j , t j ).
Collision resistance of F 1 implies that t i = t j and that k

(1) S i and k

(1) S j were both derived from the same master secret key. Moreover, t i ∈ S i ∩ S j = ∅ which implies that S i ⊂ S j or S j ⊂ S i . Let us assume that S j ⊂ S i . We then distinguish the two following cases.

-Case 1: S j S i , which implies that D(S j ) ⊂ S i . From k

(1)

S i , one can then compute T * ← H S i ) (F 1 .CKey(k (1)
S i , D(S j ))) and thus recover upk = T S j /(T * ) R i .

-Case 2: S j = S i . In such a case, k

(2)

S i = k (2)
S j if and only if both elements have been generated using the same public key upk. Therefore, one aborts if this equality does not hold. Else, one computes upk ← (T

R j S i /T R i S j ) 1/(R j -R i ) .

Discussion

To our knowledge, all anonymous divisible e-cash systems can be associated with one of these frameworks. The main difference is that existing constructions require less PRFs but, as we explain in Section 1.2, this leads to a problem that has been overlooked in the proofs. Although some of them can be patched without adding new PRFs, we note that this patch is very specific to some constructions and so cannot be applied to our generic frameworks.

Starting from the seminal work of Canard and Gouget [CG07], several schemes [ASM08, CG10, Mär15]) implicitly followed the second framework14 and so constructed (or re-used) delegatable PRFs satisfying the properties listed above. Unfortunately, the resulting PRFs do not interact nicely with NIZK, leading to quite complex constructions.

Recently, a series of papers [CPST15a, CPST15b, PST17] followed a different approach that actually matches our first framework. It is then possible to extract from these papers constrained key homomorphic PRFs that achieve key pseudo-randomness. Moreover, these PRFs interact smoothly with NIZK, even in the standard model, leading to very efficient constructions.

However, in practice, efficiency does not only depend on the compatibility with NIZK proofs. Divisible e-cash indeed achieves its ultimate goal when it allows the user to spend efficiently the V coins associated with a transaction of amount V . This means that the family of subsets {S i } supported by the PRF must be as rich and as diverse as possible. For decades, the constructions have only been compatible with intervals of the form [1 + j • 2 k , (j + 1)2 k ] due to the use of binary trees. It is only recently that Pointcheval, Sanders and Traoré [PST17] proposed a construction supporting any interval [a, b] ⊆ [1, N ]. This led to the first constant-size divisible e-cash systems.

Our Framework

We now elaborate on the solutions sketched in the previous section to construct a full divisible ecash system. We only consider here constructions based on key homomorphic constrained PRFs but describe those based on delegatable PRF in Section 7.

Building Blocks

Our framework makes use of three standard cryptographic primitives, namely digital signature, commitment scheme and non-interactive zero-knowledge (NIZK) proofs that we recall below, along with their respective security properties.

Digital Signature. A digital signature scheme Σ is defined by three algorithms:

-Keygen(1 λ ): on input a security parameter λ, this algorithm outputs a pair of signing and verification keys (sk, pk); -Sign(sk, m): on input the signing key sk and a message m, this algorithm outputs a signature σ; -Verify(pk, m, σ): on input the verification key pk, a message m and its alleged signature σ, this algorithm outputs 1 if σ is a valid signature on m under pk, and 0 otherwise.

The standard security notion for a signature scheme is existential unforgeability under chosen message attacks (EUF-CMA) [GMR88]: it means that it is hard, even given access to a signing oracle, to output a valid pair (m, σ) for a message m never asked to the signing oracle. The formal definition is provided in Figure 5 and makes use of an oracle OSign that, on input a message m, returns Sign(sk, m). A signature scheme is EUF-CMA secure if Pr[Exp euf-cma

A

(1 λ ) = 1] is negligible for any A.

(1 λ ) 1. (ck) ← Keygen(1 λ ) 2. m ← A(ck) 3. r $ ← R, c0 ← Commit(ck, m, r) 4. c1 $ ← C 5. b * ← A OSign (ck, c b ) 6. Return (b = b * ) Binding Security Game Exp bind A (1 λ ) 1. (ck) ← Keygen(1 λ ) 2. (m0, m1, r0, r1) ← A(ck) 3. If Commit(ck, m0, r0) = Commit(ck, m1, r1)
or m0 = m1, then return 0 4. Return 1 Fig. 6. Security Game for Commitment Schemes Commitment Scheme. A commitment scheme Γ is defined by the following two algorithms:

-Keygen(1 λ ): on input a security parameter λ, this algorithm outputs a commitment key ck that specifies a message space M, a randomizer space R along with a commitment space C; -Commit(ck, m, r) : on input ck, an element r ∈ R and a message m ∈ M, this algorithm returns a commitment c ∈ C.

Informally, a commitment should be binded to the committed message, but still hiding the latter. This is formally defined by the games

Exp bind A (1 λ ) and Exp hid-b A (1 λ ) of Figure 6. A commitment scheme is binding if Pr[Exp bind A (1 λ ) = 1] is negligible, while it is hiding if Pr[Exp hid-1 A (1 λ ) = 1] -Pr[Exp hid-0 A (1 λ ) = 1] is negligible.
NIZK Proofs. Let R be an efficiently computable relation with triples (crs, φ, w), where crs is called the common reference string and w is said to be a witness to the instance φ. A NIZK proof system is defined by the following three algorithms:

-Setup(1 λ ): on input a security parameter λ, this algorithm outputs the common reference string crs. -Prove(crs, w, φ): on input a triple (crs, w, φ) ∈ R, this algorithm outputs a proof π.

-Verify(crs, φ, π): on input crs, a proof π and an instance φ this algorithm outputs either 1 (accept) or 0 reject.

A NIZK proof is correct if the probability that Verify(crs, φ, Prove(crs, w, φ)) returns 0 is negligible for all (crs, w, φ) ∈ R. We will additionally require the properties of zero-knowledge and extractability. Both of them are defined in Figure 7. Extractability requires the existence of an extractor X A that takes as input the transcript trans A of the adversary A. Zero-knowledge requires the existence of a simulator consisting of the algorithms SimSetup and SimProve that share state with each other. In the security experiment Exp zk-b

A

(1 λ ), the adversary has access to the following oracle:

-OProve-b(w, φ): on input (w, φ), this algorithm returns ⊥ if (crs b , w, φ) / ∈ R. Else, it returns Prove(crs b , w, φ) if b = 0 and SimProve(crs b , φ) otherwise.

A NIZK proof is zero-knowledge if Pr[Exp zk-1 A (1 λ )]-Pr[Exp zk-0 A (1 λ )] is negligible. It is extractable if Pr[Exp ext A (1 λ )] is negligible. Zero-Knowledge Game Exp zk-b A (1 λ ) 1. crs0 ← Setup(1 λ ) 2. crs1 ← SimSetup(1 λ ) 3. b * ← A OProve-b (crs b ) 4. Return (b = b * ) Extractability Game Exp ext A (1 λ ) 1. crs ← Setup(1 λ ) 2. (φ, π) ← A(crs) 3. w ← XA(transA)
4. If Verify(crs, φ, π) = 0 or (crs, w, φ) / ∈ R, then return 0 5. Return 1 Fig. 7. Security Game for NIZK Proofs

Construction

Our construction makes use of a digital signature scheme Σ, a commitment scheme Γ and a NIZK proof system Π as described above. The difficulty here is to provide the description of a framework that encompasses very different settings such as cyclic groups or lattices. For example, the element ID R of Section 4 that was involved in double-spending tags does not make sense in a lattice setting and would in practice be replaced by R • ID where R is a matrix and ID is a vector. To remain as generic as possible, we will then introduce several functions that will abstract the properties we need. In our example, we need that

ID R+R = ID R • ID R and that (R + R ) • ID = R • ID + R • ID and so will represent ID R and R • ID by G(ID, R)
where G is a bilinear map (see remark 5 for more details). Such functions make the description of our framework rather complex but we stress that they are actually very easy to instantiate. In particular, we emphasize that the following framework essentially formalises the high-level ideas described in Section 4 and does not significantly increase the practical complexity of our construction.

-Setup(1 λ , N ): To generate the public parameters pp, the algorithm first computes crs ← Π.Setup(1 λ ). It then selects four constrained PRFs F 1 , F 2 , F 3 and F 4 with the same master key space K and that support the same subsets S 1 , . . . , S n with

S i ⊂ [1, N ] ∀i ∈ [1, n].
For sake of simplicity, we assume that K S i = K S j = K S for all i, j ∈ [1, n]. F 2 , F 3 and F 4 must additionally be key homomorphic. Finally, it selects a hash function H : {0, 1} * → G for some group G, two functions G 1 : {0, 1} * → K, G 2 : {0, 1} * → K S along with a non degenerate bilinear map G 3 : K S × G → K S (see remark 5). The public parameters pp are then set as crs,

F 1 , F 2 , F 3 , F 4 , H, G 1 , G 2 , G 3 . -BKeygen():
The bank generates a commitment key ck ← Γ.Keygen(1 λ ) and a key pair (sk B , pk B ) ← Σ.Keygen(1 λ ). It then sets bsk as sk B and bpk as (ck, pk B ). -Keygen() : The user (resp. the merchant) generates a signature key pair (usk, upk) (resp.

(msk, mpk)) using Σ.Keygen. -Withdraw(B(bsk, upk), U(usk, bpk)): To withdraw a divisible coin, the user first generates s ← F 1 .Keygen(1 λ , {S i } n i=1 ) and a random element r from the randomizer space R of Γ . It then sends c ← Γ.Commit(ck, [s, upk], r) to the bank along with a signature τ c ← Σ.Sign(usk, c). If τ c is valid, the bank returns a signature σ c ← Σ.Sign(sk B , c) to the user. The latter can then set its coin C as (c, s, r, σ c ).

-Spend(U(usk, C, bpk, V ), M(msk, bpk, info, V )): During a spending of amount V , the merchant first selects a string info that he never used before 15 and sends it to the user along with his public key mpk.

The user then selects a subset S i with |S i | = V such that SN j has never been revealed for all j ∈ S i , and computes k

(1)

S i ← F 1 .CKey(s, S i ), k (2)
S i ← F 2 .CKey(s • G 1 (upk), S i ) and T S i ← (G 3 (G 2 (upk), H(mpk||info)) • k (3) S i , G 2 (upk) • k (4) S i ) where k (3) S i = F 3 .CKey(s, S i ) and k (4) S i = F 4 .CKey(s, S i ).
Finally, it generates a signature τ ← Σ.Sign(usk, (mpk, V, info, k

(1)

S i , k (2)
S i , T S i )) along with a NIZK proof π of (upk, s, c, r, σ c , S i , τ ) such that:

1. ∃i * ∈ [1, n] : S i = S i * ∧ |S i | = V 2. c = Γ.Commit(ck, [s, upk], r) 3. 1 = Σ.Verify(pk B , c, σ c ) 4. k (1) S i = F 1 .CKey(s, S i ) 5. k (2) S i = F 2 .CKey(s • G 1 (upk), S i ) 6. T S i = (G 3 (G 2 (upk), H(mpk||info)) • F 3 .CKey(s, S i ), G 2 (upk) • F 4 .CKey(s, S i )) 7. 1 = Σ.Verify(upk, (mpk, V, info, k (1) S i , k (2) S i , T S i ), τ ) The elements (k (1) S i , k (2)
S i , T S i , π) are then sent to the merchant who accepts them as a payment if π is valid.

-Deposit(M(msk, bpk, (V, info, k

(1)

S i , k (2) S i , T S i , π)), B(bsk, L, mpk)):
To deposit a transaction, the merchant sends its transcript Tr ← (V, info, k

(1)

S i , k (2)
S i , T S i , π) along with a signature µ ← Σ.Sign(msk, Tr). The bank then checks that (1) the proof π is valid, (2) π proves knowledge of a signature on a tuple whose first coordinate is mpk, (3) Σ.Verify(mpk, Tr, µ) = 1 and (4) that this merchant has not previously deposited a transaction associated with info. If one of the first three conditions is not satisfied, then the bank returns ⊥. If the last condition is not satisfied then the bank knows another transcript (V , info, k

(1)

S j , k (2)
S j , T S j , π ) along with a signature µ . All these elements, along with [Tr, µ] constitute a proof of double-deposit. Else, the bank recovers, for all j ∈ S i (see remark 6 below), the serial numbers

SN j ← F 1 .CEval S i (k (1) S i , j)||F 2 .CEval S i (k (2)
S i , j). It then distinguishes the following two cases: • ∃j * ∈ S i such that SN j * already belongs to L. In such a case, the bank recovers the first transcript (V , info , mpk , k

(1) S i , k (2) S i
, T S i , π ) that yields this serial number and returns it along with Tr.

• SN j / ∈ L ∀j ∈ S i , in which case the bank simply adds these serial numbers to L -Identify((V, info, mpk, k

(1)

S i , k (2)
S i , T S i , π), (V , info , mpk , k

(1)

S j , k (2)
S j , T S j , π ), bpk) : Given two transcripts, this algorithm first checks that (1) mpk||info = mpk ||info and (2) both proofs π and π are valid. If one of these conditions is not satisfied, then it returns 0. Else, it checks that there is a collision between the serial numbers derived from these transcripts, i.e. there are x ∈ S i and x ∈ S j such that F 1 .CEval S i (k

(1) S i , x)||F 2 .CEval S i (k (2) S i , x) = F 1 .CEval S j (k (1) S j , x )||F 2 .CEval S j (k (2)
S j , x ). If there is no collision, it outputs 0. Else, it proceeds as in Section 4.1 to identify the defrauder. If

T S i [2] = T S j [2], it computes R = H(mpk||info), R = H(mpk ||info ) along with F 3 .CEval S i (T S i [1], x)/F 3 .CEval S j (T S j [1], x ) and F 3 .CEval S i (G 3 (G 2 (upk), R), x)/F 3 .CEval S j (G 3 (G 2 (upk), R ), x)
for all upk until it gets a match. It then returns the corresponding public key upk * (or ⊥ if the exhaustive search fails). Else,

T S i [2] = T S j [2] and it computes F 4 .CEval S i (T S i [2]/G 2 (upk), x)/F 4 .CEval S j (T S i 2 [2]/G 2 (upk), x )
for all public keys upk until it gets 1 Y . It then returns the corresponding public key upk * (or ⊥ if the exhaustive search fails).

-CheckDeposit([(V, info, mpk, k

(1) S i , k

(2) S i , T S i , π), µ], bpk) : this algorithm checks that π is valid and that 1 = Σ.Verify(mpk, (V, info, k

(1) S i , k

(2) S i , T S i , π), µ) in which case it outputs 1. Else, it returns 0. Remark 4. An example of instantiation of our full construction, in the standard model, is provided in Section 10 to assess the practical complexity of our framework. Nevertheless, we note that a spending essentially consists in generating 4 constrained keys along with a zero-knowledge proof that they have been correctly computed from a certified master key. In bilinear groups, such proofs can easily be produced in the random oracle model or by using Groth-Sahai proofs [GS08] if one selects an appropriate digital signature scheme for Σ, as illustrated in Section 10. In particular, the latter section shows that the complexity of our framework is very similar to the one of (unsecure) schemes from the state-of-the-art. The case of lattices is more complex but we note that the proofs and the signature scheme required here are similar to those described in [LLNW17].

Remark 5. The only purpose of the functions G 1 , G 2 and G 3 is to project the different elements of our system on the appropriate spaces, which ensures compatibility with most PRFs. As we illustrate on concrete examples in Section 9, these functions are in practice very simple (for example G 2 is usually the identity function) and nicely interact with zero-knowledge proofs. In particular, our bilinear map G 3 can easily be instantiated in most settings. For example, when K S is a cyclic group of order p, we will simply have G = Z p and G 3 (x, y) = x y . Similarly, when K S = F n q , we will have G ⊂ M m,n and G 3 (x, A) = A • x. We will also manage to make G 1 and G 2 injective in practice which means that the collision resistance will be trivially satisfied. We recall that the bilinear map

G 3 is non degenerate if G 3 (x, y) = 1 K S implies x = 1 K S or y = 1 G .
Remark 6. Note that, even if the bank does not know the subset S i , it is always able to recover all the serial numbers SN j ← CEval S i (k S i , j), for j ∈ S i . Indeed, it can generates the list L containing SN k ← CEval S (k S i , k), for all S containing V elements and k ∈ S. Such a list contains the valid serial numbers (those for which S = S i ) and so can still be used to detect double-spendings. Moreover, due to the properties of PRF, the "invalid" serial numbers (those for which S = S j ) are random elements and so are unlikely to create false positives (collisions in the list L that are not due to double-spendings).

However, we stress that this is only a generic solution that works for any instantiation of our construction. In practice, it leads to quite complex deposits and so should be avoided, if possible. Actually, to our knowledge, it is only used in [CPST15a]. All other divisible e-cash systems manage to construct PRFs that can be evaluated on the elements of S i without knowing S i . More specifically, theses PRFs are compatible with an algorithm CEval that takes as input a constrained key and the size of the corresponding subset and that outputs CEval(k

S i , |S i |) = {CEval S i (k S i , x), ∀x ∈ S i }.
The security of our construction is stated by the following theorem, proven in Section 6.

Theorem 7. Our divisible e-cash system is

-traceable if F 1 and F 2 achieve collision resistance-1, Γ is computationally binding, Σ is EUF-CMA secure, Π is extractable, and G 1 is collision resistant. -exculpable if Σ is EUF-CMA secure, Π is extractable, F 1 and F 2 achieve collision resistance- 1, F 3 achieves collision resistance-2, F 4 achieves collision resistance-3 and H, G 1 and G 2 are collision resistant. -clearable if Σ is EUF-CMA secure.
anonymous if (F 1 , F 2 , F 3 , F 4 ) achieves combined key pseudo-randomness, Γ is computationally hiding and Π is zero-knowledge.

Remark 8. Most existing constructions require a collaborative generation of the coin secret values. Our framework can easily support this feature if Γ is homomorphic. In such a case, traceability no longer requires collision resistance for F 1 and F 2 because the randomness added by the bank (which is honest in this game) will make collisions very unlikely. Unfortunately, the collaborative generation has no effect on exculpability since both parties (the user and the bank) can be corrupted in this game. We therefore choose to simplify our withdrawal protocol by removing this step since we need collision resistance of F 1 and F 2 anyway.

6 Security Analysis

Proof of Traceability

A successful adversary A against the traceability is able to spend more than it has withdrawn without being identified. Formally, this means that there are u transcripts Tr i = {(V i , info i , mpk i , k

(1)

S i , k (2)
S i , T S i , π i )} u i=1 where:

- u i=1 V i > m.N , with m the number of withdrawn coins -Identify(Tr i , Tr j ) =⊥ ∀i, j ∈ [1, u]
The latter condition implies that all the proofs π i are valid (otherwise Identify would have returned 0 and not ⊥). Therefore, the challenger is able to extract from them tuples W i = (upk i , s i , r i , σ i , c i , S i , τ i ) satisfying the 7 relations defined by the Spend algorithm. Else, A could be trivially converted into an adversary against the extractability of Π.

We then distinguish the following cases:

-Type 1 Adversary: ∃i ∈ [1, u] such that none of the coins generated through OWithdraw B queries contains the commitment c i . -Type 2 Adversary: all the commitments c i have been generated during a query to the OWithdraw B oracle but the serial numbers do not collide. -Type 3 Adversary: all the commitments c i have been generated during a query to the OWithdraw B oracle and there is a collision in the list of serial numbers.

Informally, the first two types of adversary essentially imply an attack against the signature scheme or the commitment scheme. The last type of adversary implies a collision of one of the functions involved in our construction. This is formally stated by the following lemmas.

Lemma 9. Any type 1 adversary A can be converted into an adversary succeeding against the EUF-CMA security of Σ with the same probability.

Proof. The reduction R generates as usual the public parameters along with the commitment key ck but sets pk B as pk * , where pk * is the public key received from the challenger of the EUF-CMA security experiment.

Each time it receives an OAdd query it generates a new key pair for the user, allowing it to answer any OSpend query.

Upon receiving an OWithdraw B query, it forwards the commitment c to its signing oracle. It then receives a signature σ c that it can send to A.

The simulation is perfect so A eventually outputs several transcripts, one of which involving a commitment c * and a signature σ * such that Σ.Verify(pk * , c * , σ * ) = 1. Since we here consider the first type of adversary, c * has never been submitted to the signing oracle, which means that (c * , σ * ) is a valid forgery. R is then able to extract this pair and so to break the EUF-CMA security of Σ.

Lemma 10. Any type 2 adversary A can be converted into an adversary succeeding against the binding security of Γ , with the same probability.

Proof. The reduction R generates the public parameters and (sk B , pk B ) ← Σ.Keygen(1 λ ) but receives ck from the challenger of the binding security experiment. R is able to answer any oracle query because it knows all the corresponding secret keys. At the end of the game, A then outputs u transcripts Tr i that foil the mechanisms of identification. R extracts the u i=1 V i > m•N serial numbers which are assumed to be distinct since we only consider type 2 adversary. Since all the commitments c i have been certified during a query to the OWithdraw B oracle (otherwise A would be of type 1) and since there have been m withdrawals, there are at most m distinct commitments c i . Let (s k , upk k ) be the secret master key/user public key pair extracted from Tr k , for k ∈ [1, u]. We note that {(s k , upk k )} u k=1 contains at least m + 1 elements, otherwise these pairs would yield at most m • N < u i=1 V i serial numbers and there would be at least one collision.

Therefore, there are only m commitments c i that can be opened to at least m + 1 distinct pairs (s k , upk k ). This implies that there is at least one commitment c * that can be opened in two different ways. By extracting all the commitments c i and all the pairs (s k , upk k ), R can easily recover c * along with the different openings that constitute a valid attack against Γ .

Lemma 11. Any type 3 adversary A succeeding with probability can be converted into an adversary succeeding against the collision resistance-1 of F 1 or F 2 or against the one of G 1 , with the same probability.

Proof. The reduction R generates the public parameters and the public key of the bank as usual, and is thus able to answer any query. At the end of the experiment, the type 3 adversary outputs u transcripts that yield at least two identical serial numbers SN i and SN j such that

SN i = F 1 .CEval S i (F 1 .CKey(s i , S i ), x i )||F 2 .CEval S i (F 2 .CKey(s i • G 1 (upk i ), S i ), x i ) and SN j = F 1 .CEval S j (F 1 .CKey(s j , S j ), x j )||F 2 .CEval S j (F 2 .CKey(s j • G 1 (upk j ), S j ), x j )
The relation SN i = SN j implies that F 1 .CEval S i (F 1 .CKey(s i , S i ), x i ) = F 1 .CEval S j (F 1 .CKey(s j , S j ), x j ) and hence that s i = s j and x i = x j , otherwise R could be straightforwardly converted into an adversary against the collision resistance of F 1 .

If we now consider the second part of the serial numbers, we have:

F 2 .CEval S i (F 2 .CKey(s i • G 1 (upk i ), S i ), x i ) = F 2 .CEval S j (F 2 .CKey(s i • G 1 (upk j ), S j ), x i )
We can simplify the previous relation by using the homomorphism of F 2 and thus get:

F 2 .CEval(F 2 .CKey(G 1 (upk i ), S i ), x i ) = F 2 .CEval(F 2 .CKey(G 1 (upk j ), S j ), x i )
We distinguish three cases:

-Case 1: G 1 (upk i ) = G 1 (upk j ) -Case 2: upk i = upk j but G 1 (upk i ) = G 1 (upk j ) -Case 3 upk i = upk j
Case 1 implies that A managed to generate two master secret keys G 1 (upk i ) and G 1 (upk j ) such that F 2 .Eval(G 1 (upk i ), x i ) = F 2 .Eval(G 1 (upk j ), x i ), which means that A can directly be converted into an adversary against the collision resistance of F 2 . Similarly, case 2 implies a collision of the function G 1 . Let us consider the third case. Let R i = H(mpk i ||info i ) and R j = H(mpk j ||info j ). We have:

F 3 .CEval S i (T S i [1], x i ) = F 3 .CEval S i (G 3 (G 2 (upk i ), R i ) • F 3 .CKey(s i , S i ), x i ) and F 3 .CEval S j (T S j [1], x i ) = F 3 .CEval S j (G 3 (G 2 (upk i ), R j ) • F 3 .CKey(s i , S j ), x i ) Therefore, F 3 .CEval S i (T S i [1], x i )/F 3 .CEval S j (T S j [1], x i ) = F 3 .CEval S i (G 3 (G 2 (upk i ), R i ), x i )/F 3 .CEval S j (G 3 (G 2 (upk i ), R j ), x i )
However, in such a case, the Identify algorithm would necessarily output a public key (at least upk i ), which contradicts our assumption on A. This third case thus cannot occur if A is a successful adversary against traceability.

Remark 12. We recall that traceability only requires to output a public key in case of doublespending but does not care if this public key is correct. This latter property is ensured by exculpability. This explains why our proof of traceability does not place any requirements on the last element of the double-spending tag, nor on the functions G 2 or G 3 .

Proof of Exculpability

Let A be a successful adversary that outputs two valid transcripts Tr = (V, info, mpk, k

(1)

S i , k (2) S i , T S i , π)], Tr = (V , info , mpk , k (1) S j , k (2)
S j , T S j , π )] accusing an honest user upk * of double spendings, i.e. such that Identify(Tr, Tr ) = upk * .

Since upk * is an honest user, at least one of this transcript must have been forged by the adversary. Let us assume that it is the first one. It is possible to extract from π the tuple (upk, s, c, r, σ c , S i , τ ), otherwise A could be used against the extractability of Π. We then distinguish the two following cases.

-Type 1 Adversary: upk = upk * .

-Type 2 Adversary: upk = upk * .

The first case implies that the adversary has generated a valid signature under upk * , which leads to an attack against the signature scheme Σ, as stated below.

Lemma 13. Any type 1 adversary A succeeding with probability can be converted into an adversary succeeding against the EUF-CMA security of Σ with probability q A , where q A is a bound on the number of OAdd queries.

Proof. the reduction R generates the public parameter as usual and receives the public key of the bank from A. It then selects a random i * $ ← [1, q A ] and answer the i-th OAdd query as follows:

-If i = i * , then R generates a new key pair (usk, upk) for this user.

-Else, it returns the public key pk * that it has received from the challenger of the EUF-CMA security experiment.

One can note that R may answer any query that involves upk = pk * because it knows the corresponding signing key usk. For the other ones, R uses its signing oracle and forwards the signature to A.

A then eventually outputs a forged transcript from which it is possible to extract a valid signature τ under some public key upk. If upk = pk * , then R aborts. Else, R recovers the signature τ on (mpk, V, info, k

S i , k (1)
S i , T S i ). The elements k (1) S i , k (2)
S i and T S i have never been part of a query to the signing oracle (otherwise the reduction would have double-spent its own coin), which means that [(mpk, V, info, k

(1)

S i , k (2)
S i , T S i ), τ ] is a valid forgery. R then breaks the security of Σ if it does not abort, which occurs with probability at least 1 q A . Lemma 14. Any type 2 adversary can be converted into an adversary succeeding against the collision resistance-1 of F 1 or F 2 , the collision resistance-2 of F 3 , the collision resistance-3 of F 4 or against the one of H, G 1 or G 2 , with the same probability.

Proof. The fact that Identify does not output 0 on inputs Tr and Tr means that there is at least one collision between the serial numbers derived from Tr and those derived from Tr . There are thus x ∈ S i and x ∈ S j such that

(1) F 1 .CEval S i (k (1)
S i , x) = F 1 .CEval S j (k (1)
S j , x ) (2) F 2 .CEval S i (k (2) S i , x) = F 2 .CEval S j (k (2) S j , x )
Let s and s be the master secret keys extracted from Π and Π respectively. Since k

(1) andk (1) S j = F 1 .CKey(s , S j ), the relation (1) implies that s = s and that x = x , otherwise (s, s , x, x ) could directly be used against the collision resistance-1 of F 1 .

S i = F 1 .CKey(s, S i )
The equation (2) thus becomes:

F 2 .CEval S i (F 2 .CKey(s • G 1 (upk)), S i ), x) = F 2 .CEval S j (F 2 .CKey(s • G 1 (upk )), S j ), x) which means that F 2 .CEval S i (F 2 .CKey(G 1 (upk)), S i ), x) = F 2 .CEval S j (F 2 .CKey(G 1 (upk )), S j ), x).
We then distinguish three cases.

-Case 1:

G 1 (upk) = G 1 (upk ) -Case 2: upk = upk but G 1 (upk) = G 1 (upk ) -Case 3: upk = upk
The first case implies that (G 1 (upk), G 1 (upk ), x, x) can directly be used against the collision resistance-1 of F 2 . The second case implies an obvious attack against the collision resistance of G 1 . So let us consider the third case.

If upk = upk , then

T S i [2] = T S j [2] is equivalent to S i = S j .
If S i = S j , we have: andk (3) S j are derived from the same master secret key s, we additionally know that F 3 .CEval S i (k

F 3 .CEval S i (T S i [1], x) = F 3 .CEval S i (G 3 (G 2 (upk), R) • k (3) S i , x) = F 3 .CEval S i (G 3 (G 2 (upk), R), x) • F 3 .CEval S i (k (3) S i , x) and F 3 .CEval S j (T S j [1], x) = F 3 .CEval S j (G 3 (G 2 (upk), R ) • k (3) S j , x) = F 3 .CEval S j (G 3 (G 2 (upk), R ), x) • F 3 .CEval S j (k (3) S j , x) Since k (3) S i
(3) S i , x) = F 3 .CEval S j (k (3)
S j , x). During the identification process, one then gets

F 3 .CEval S i (T S i [1], x)/F 3 .CEval S j (T S j [1], x) = F 3 .CEval S i (G 3 (G 2 (upk), R), x)/F 3 .CEval S j (G 3 (G 2 (upk), R ), x) = F 3 .CEval S i (G 3 (G 2 (upk), R/R ), x)
since S i = S j . The fact that A is a type 2 adversary means that:

F 3 .CEval S i (G 3 (G 2 (upk), R/R ), x) = F 3 .CEval S i (G 3 (G 2 (upk * ), R/R ), x)
with upk = upk * . We can then distinguish two cases:

-G 3 (G 2 (upk), R/R ) = G 3 (G 2 (upk * ), R/R ), which implies an attack against the collision resistance-2 of F 3 . -G 3 (G 2 (upk), R/R ) = G 3 (G 2 (upk * ), R/R ) which is equivalent to 1 = G 3 (G 2 (upk)/G 2 (upk * ), R/R ). Since G 3 is non degenerate, this means that G 2 (upk) = G 2 (upk * ) or that R = R . But upk = upk * and (R, R ) = (H(mpk i ||info i ), H(mpk j ||info j )) with (mpk i ||info i ) = (mpk j ||info j ).
Therefore, this second case necessarily implies a collision against G 2 or against H. Now, let us consider the case S i = S j . The fact that the identification process returns upk * means that

F 4 .CEval S i (T (1) S i [2]/G 2 (upk * ), x)/F 4 .CEval S j (T (1) S j [2]/G 2 (upk * ), x) = 1.
We can use the fact that F 4 .CEval S i (k

(4) S i , x) = F 4 .CEval S j (k (4)
S j , x) to simplify the left member of the previous equation and thus get:

F 4 .CEval S i (G 2 (upk)/G 2 (upk * ), x)/F 4 .CEval S j (G 2 (upk)/G 2 (upk * ), x) = 1. with upk = upk * . If G 2 (upk)/G 2 (upk * ) = 1, then (i, j, G 2 (upk)/G 2 (upk * ),
x) constitutes a valid attack against the collision resistance 3 of F 4 . Else, G 2 (upk) = G 2 (upk * ), which implies a collision against G 2 .

Proof of Anonymity

Let A be an adversary breaking the anonymity of our construction with probability . We define the following sequence of games to show that this advantage is negligible. For each game i, we define Adv i = |P r(S i ) -1/2|, where S i is the event that A succeeds in game i.

Game 1. Our first game is exactly the anonymity game defined in Figure 4 with a random bit b where the reduction R generates normally the secret values. The advantage Adv 1 is then .

Game 2. In our second game, we make a guess on the coin that will be available to user upk b at the challenge time. More specifically, the reduction selects a random * ∈ [1, q w ] where q w is a bound on the number of queries and aborts if the * -th coin issued by the bank has not been withdrawn by upk b or if this user has entirely spent it before the challenge phase. The reduction still generates all the secret values and so the simulation is perfect unless the guess of R is not correct. We then have Adv 2 ≥ 1 qw .

Game 3. In our third game, R generates a simulated common reference string using the SimSetup and uses the SimProve algorithm to output the NIZK proofs. Any change in the behaviour of A in this game can then be used against the zero-knowledge property of Π. We then have Adv 3 ≥ Adv 2 -Adv zk A .

Game 4. In our fourth game, R proceeds as in the previous game except that during the * -th withdrawal query it replaces the commitment c by a random element from the commitment space. We note that this is not a problem for further NIZK proofs since the SimProve algorithm does not need witnesses as inputs. Any significant change in the behaviour of A then yields an adversary against the hiding property, which means that Adv 4 ≥ Adv 3 -Adv hid A .

Game 5. In our fifth game, R proceeds as in the previous game, but it answers the challenge query (V, upk 0 , upk 1 , mpk) as follows. First, it selects a subset S containing V elements that have never been involved in previous spendings of the * -th coin. We recall that Game 2 ensures that such subset exists, otherwise R would abort. Moreover, this game also ensures that this coin belongs to upk 0 or upk 1 . Let us denote this user by upk * . R then selects four random values (k 1 , k 2 , k 3 , k 4 ) $ ← K 4 S and returns (k

(1) S , k (2)
S ) = (k 1 , k 2 • F 2 .CKey(G 1 (upk * ), S)) along with T S = (G 3 (G 2 (upk * ), H(mpk||info)) • k 3 , G 2 (upk * ) • k 4 ).
Here again, the NIZK proofs can still be produced by using the SimProve algorithm. The simulation is perfect unless A is able to distinguish the random tuple (k 1 , k 2 , k 3 , k 4 ) from (F 1 .CKey(s, S), F 2 .CKey(s, S), F 3 .CKey(s, S), F 4 .CKey(s, S)), which would yield an adversary against the combined key pseudo-randomness of the family (F 1 , F 2 , F 3 , F 4 ). We therefore have Adv 5 ≥ Adv 4 -Adv ckps A . We can note that in Game 5, the values received by the adversary are simulated proofs along with random elements (k

(1) S , k (2)
S ) and T S . The advantage Adv 5 of A in this game is then 0. This means that:

q w ≤ Adv zk A + Adv hid A + Adv ckps A
which concludes the proof since q w is polynomial in the security parameter λ.

Proof of Clearability

An adversary succeeding in the clearing security game with probability is able to output a valid proof [Tr, µ] of deposit of a transcript Tr = (V, info, mpk, k

(1)

S i , k (2)
S i , T S i , π) that has not been generated by the merchant mpk. Informally, since the CheckDeposit algorithm mostly consists in verifying the signature µ, this means that A has managed to forge the latter and so that A can be used against the security of the signature scheme.

Proof. The reduction R generates all the parameters as usual but selects a random * ∈ [1, q a ] where q a is a bound on the number of OAdd queries for merchants. In the simulation, it proceeds as usual except that it answers the * -th OAdd query by returning the public key mpk * received from the challenger C of the EUF-CMA security experiment for Σ. Each time mpk * is involved in a query to the ODeposit oracle, R simply sends the corresponding transaction transcript Tr i to C and then forwards the signature µ i to the adversary.

At the end of the game, A returns [Tr, µ] involving an honest merchant mpk. If mpk = mpk * , then R aborts. Else, the fact that A succeeds means that ODeposit has never been queried on this transaction and so that Tr has never been sent to the signing oracle provided by C. This means that µ is a valid forgery that R can forward to C. R then outputs a valid forgery unless it aborts. It then succeeds against the EUF-CMA security of Σ with probability at least qa .

Framework based on Delegatable PRFs

As in Section 5.2, our construction makes uses of a digital signature scheme Σ, an homomorphic commitment scheme Γ and a NIZK proof system Π.

-Setup(1 λ , N ): To generate the public parameters pp, the algorithm first computes crs ← Π.Setup(1 λ ). It then selects two constrained PRFs F 1 , F 2 with the same master key space K and that support the same subsets S 1 , . . . , S n with

S i ⊂ [1, N ] ∀i ∈ [1, n].
For sake of simplicity, we assume that K S i = K S j = K S for all i, j ∈ [1, n]. As we describe in 4.2, the algorithm also defines the functions (H, {H S i } n i=1 ) such that H : K → G 1 and H S i : K S i → G 1 for some group G 1 . We recall that our family of subsets has the following property:

S i ∩ S j = ∅ ⇒ S i ⊂ S j or S j ⊂ S i Finally, it selects a hash function H 0 : {0, 1} * → G 2 for some group G 2 , a function G 1 : {0, 1} * → K S , G 2 : {0, 1} * → G 1 along with a non degenerate bilinear map G 3 : G 1 × G 2 → G 1 . The public parameters pp are then set as crs, F 1 , F 2 , H, H , H 0 , G 1 , G 2 , G 3 .
-BKeygen(): The bank generates a commitment key ck ← Γ.Keygen(1 λ ) and a key pair (sk B , pk B ) ← Σ.Keygen(1 λ ). It then sets bsk as sk B and bpk as (ck, pk B ). -Keygen() : The user (resp. the merchant) generates a signature key pair (usk, upk) (resp.

(msk, mpk)) using Σ.Keygen. -Withdraw(B(bsk, upk), U(usk, bpk)): To withdraw a divisible coin, the user first generates s ← F 1 .Keygen(1 λ , {S i } n i=1 ) and a random element r from the randomizer space R of Γ . It then sends c ← Γ. Commit(ck, [s, upk], r) to the bank along with a signature τ c ← Σ.Sign(usk, c). If τ c is valid, the bank returns a signature σ c ← Σ.Sign(sk B , c) to the user. The latter can then set its coin C as (c, s, r, σ c ).

-Spend(U(usk, C, bpk, V ), M(msk, bpk, info, V )): During a spending of amount V , the merchant first selects a string info that he never used before and sends it to the user along with his public key mpk.

The user then selects an unspent subset S i of V elements, i.e. one such that SN j has never been revealed for all j ∈ S i , and computes 1. k

(1)

S i ← F 1 .CKey(s, S i ) 2. k (2) S i ← G 1 (upk) • F 2 .CKey(s, S i ) 3. T S i ← G 3 (G 2 (upk), H 0 (mpk||info)) • H S i (F 1 .CKey(s, D(S i ))) if S i = [1, N ] and 1. k (1) S i ← F 1 .CKey(s, S i ) 2. k (2) S i ← G 1 (upk) • F 2 .CKey(s, S i ) 3. T S i ← G 3 (G 2 (upk), H 0 (mpk||info)) • H(s) otherwise.
Finally, it generates a signature τ ← Σ.Sign(usk, (mpk, V, info, k

(1)

S i , k (2)
S i , T S i )) along with a NIZK proof π of (upk, s, c, r, σ c , S i , τ ) such that:

1. ∃i * ∈ [1, n] :

S i = S i * ∧ |S i | = V 2. c = Γ.Commit(ck, [s, upk], r) 3. 1 = Σ.Verify(pk B , c, σ c ) 4. k (1)
S i = F 1 .CKey(s, S i ) 5. k (2) S i ← G 1 (upk) • F 2 .CKey(s, S i ) 6. if S i = [1, N ], T S i ← G 3 (G 2 (upk), H 0 (mpk||info)) • H S i (F 1 .CKey(s, D(S i ))) 7. else, T S i ← G 3 (G 2 (upk), H 0 (mpk||info)) • H(s) 8. 1 = Σ.Verify(upk, (mpk, V, info, k (1) S i , k (2) S i , T S i ), τ ) The elements (k (1) S i , k (2)
S i , T S i , π) are then sent to the merchant who accepts them as a payment if π is valid.

-Deposit(M(msk, bpk, (V, info, k

(1)

S i , k (2)
S i , T S i , π)), B(bsk, L, mpk)): To deposit a transaction, the merchant sends its transcript Tr ← (V, info, k

(1)

S i , k (2)
S i , T S i , π) along with a signature µ ← Σ. Sign(msk, Tr). The bank then checks that (1) the proof π is valid, (2) π proves knowledge of a signature on a tuple whose first coordinate is mpk, (3) Σ.Verify(mpk, Tr, µ) = 1 and (4) that this merchant has not previously deposited a transaction associated with info. If one of the first three conditions is not satisfied, then the bank returns ⊥. If the last condition is not satisfied then the bank knows another transcript (V , info, k

(1)

S j , k (2)
S j , T S j , π ) along with a signature µ . All these elements, along with [Tr, µ] constitute a proof of double-deposit. Else, the bank recovers the serial numbers SN j ← F 1 .CEval S i (k

(1) S i , j) for all j ∈ S i . It then distinguishes the following two cases:

• SN j / ∈ L ∀j ∈ S i , in which case the bank simply adds these serial numbers to L • ∃j * ∈ S i such that SN j * already belongs to L. In such a case, the bank recovers the first transcript Tr = (V , info , mpk , k

(1) S i , k

(2) S i , T S i , π ) that yields this serial number. If S i = S i , then the bank returns this transcript, along with Tr. If S i = S i and k

(2)

S i = k (2) S i
, then the bank also returns [Tr, Tr ]. Else, it does not return anything.

-Identify((V, info, mpk, k

(1)

S i , k (2) S i , T S i , π), (V , info , mpk , k (1) S j , k (2)
S j , T S j , π ), bpk) : Given two transcripts, this algorithm first checks that (1) mpk||info = mpk ||info and (2) both proofs π and π are valid. If one of these conditions is not satisfied, then it returns 0. Else, it checks that there is a collision between the serial numbers derived from these transcripts, i.e. there are x ∈ S i and x ∈ S j such that F 1 .CEval S i (k

(1) S i , x) = F 1 .CEval S j (k (1)
S j , x ). If there is no collision or if x i = x j , it outputs 0. If there is a collision with S i = S j but k

(2)

S i = k (2)
S j , then it outputs 0. The fact that x i ∈ S i ∩ S j = ∅ implies that S i ⊂ S j or S j ⊂ S i . Let us assume that S j ⊂ S i . We then distinguish the two following cases.

• Case 1: S j = S i (which is equivalent to V = V ). In such a case, it computes T S i /T S j and G 3 (G 2 (upk), R/R ) for all public key upk, with R = H(mpk||info) and R = H(mpk ||info ).

If it gets a match, then it returns the corresponding public upk. Else, it returns ⊥. • Case 2: S j S i , which implies that D(S j ) ⊂ S i . From k

(1) S i , this algorithm computes T * ← H S j (F 1 .CKey(k (1) S i , D(S j ))) and T = T S j /(T * ). It then compares T with G 3 (G 2 (upk), R ) for all public key upk. If it gets a match, then it returns the corresponding public upk. Else, it returns ⊥.

Tr i = (V i , info i , mpk i , k (1) S i , k (2)
S i , T S i , π i ) and Tr j = (V j , info j , mpk j , k

(1)

S j , k (2)
S j , T S j , π j ) such that S i = S j or such that S i = S j ∧ k

(2)

S i = k (2) S j .
Indeed, let us extract for t ∈ [1, u] and x ∈ S t the pairs (SN t,x , upk t ) from the transcripts Tr t = (V t , info t , mpk t , k

(1) St , k (2)
St , T St , π t ), i.e. the V t serial numbers and the user's public key associated with each transaction. Since we here consider a type-3 adversary, all these transcripts involve at most m distinct pairs (s k , upk k ). There are thus at most m.N distinct pairs (F 1 .Eval(s k , x), upk k ) for x ∈ [1, N ]. We then have:

{(SN t,x , upk t )} t∈[1,u],x∈St ⊂ {(F 1 .Eval(s k , x), upk k )} k∈[1,m] , x ∈ [1, N ] Since u i=1 V i > m•N
, there are at least two indices i, j such that (SN i,x i , upk i ) = (SN j,x j , upk j ). Moreover, we necessarily have i = j, otherwise two serial numbers derived from the same transcript would collide, leading to an obvious attack against the collision resistance of F 1 . Therefore, these serial numbers are derived from two different transcripts Tr i and Tr j involving respectively a subset S i and S j . If S i = S j , we are done. Else, we recall that

SN i = F 1 .CEval S i (F 1 .CKey(s i , S i ), x i ) and SN j = F 1 .CEval S j (F 1 .CKey(s j , S j ), x j ).
Therefore, the relation SN i = SN j implies that s i = s j (and so that upk i = upk j ) and x i = x j , otherwise R could be straightforwardly converted into an adversary against the collisions resistance of F 1 . Moreover we consider here the case S i = S j , which means that k

(2)

S i = k (2)
S j and thus concludes the proof.

We can then only consider the two following cases:

-Case 1: S i = S j ∧ k

(2)

S i = k (2) S j . -Case 2: S i = S j .
Case 1. As we explain, this case implies s i = s j , x i = x j and upk i = upk j = upk. Therefore, T S i and T S j are of the form

G 3 (G 2 (upk), R i ) • T * and G 3 (G 2 (upk), R j ) • T * for some element T * ∈ G 1 . Computing T S i /T S j then gives G 3 (G 2 (upk), R i /R j )
. However in such a case, Identify would have at least returned upk.

Case 2. Here again, the collision between the serial numbers implies that s i = s j and x i = x j = x. In particular, we have x ∈ S i ∩ S j , which implies that S i S j or that S j S i . We assume, without loss of generality, that the latter situation occurs. We then have S D(S j ) ⊂ S i . From

k (1) S i , this algorithm computes T * ← H S j (F 1 .CKey(k (1) S i , S S j )) and T S j /(T * ) = G 3 (G 2 (upk j ), R j ).
However, in this case Identify would have at least returned upk j .

Therefore, if F 1 achieves collision resistance-1, then no adversary can succeed against the traceability of our scheme.

Proof of Exculpability

Let A be a successful adversary that outputs two valid transcripts Tr

i = (V i , info i , mpk i , k (1) S i , k (2) S i , T S i , π i )], Tr j = (V j , info j , mpk j , k (1) S j , k (2)
S j , T S j , π j )] accusing an honest user upk * of double spendings, i.e. such that Identify(Tr i , Tr j ) = upk * .

Since upk * is an honest user, at least one of this transcript must have been forged by the adversary. Let us assume that it is the first one. It is possible to extract from π i the tuple (upk, s, c, r, σ c , S i , τ ), otherwise A could be used against the extractability of Π. We then distinguish the two following cases.

-Type 1 Adversary: upk = upk * .

-Type 2 Adversary: upk = upk * .

The first case implies that the adversary has generated a valid signature under upk * , which leads to an attack against the signature scheme Σ. The proof is exactly the same as the one provided in Appendix 6 so here we only consider type 2 adversary.

Lemma 17. Any type 2 adversary can be converted into an adversary succeeding against the collision resistance-1 of F 1 or against the collision resistance of H 0 , G 1 or G 2 , with the same probability.

Proof. The fact that Identify does not output ⊥ on inputs Tr i and Tr j means that there is at least one collision between the serial numbers derived from these transcripts. There are thus x i ∈ S i and x j ∈ S j such that

SN i = F 1 .CEval S i (F 1 .CKey(s i , S i ), x i ) and SN j = F 1 .CEval S j (F 1 .CKey(s j , S j ), x j ).
By using the same argument as above, we know that s i = s j and that x i = x j = x if F 1 achieves collision resistance-1. Moreover we know that one of the following two cases necessarily occurs.

-Case 1:

S i = S j ∧ k (2) S i = k (2) S j . -Case 2: S i = S j .
Case 1. The equalities k

(2)

S i = k
(2) S j and s i = s j imply that Tr i and Tr j have been generated by the same user upk. Moreover, it implies that T S i = G 3 (G 2 (upk), R i )•(T * ) and T S j = G 3 (G 2 (upk), R j )• (T * ) for some element T * ∈ G 1 . Therefore, T S i /T S j = G 3 (G 2 (upk), R i /R j ). We additionally know that Identify returns upk * , which means that:

G 3 (G 2 (upk), R i /R j ) = G 3 (G 2 (upk * ), R i /R j ) Since G 3 is non degenerate, this is only possible if R i = R j or if G 2 (upk) = G 2 (upk * ).
The former case implies a collision of H 0 , whereas the second one implies a collision of G 2 .

Case 2. By using the same argument as in the traceability proof, we know that T S j /(T * ) = G 3 (G 2 (upk j ), R j ), where upk j is the public key involved in the transaction Tr j . Therefore, the fact that Identify returns upk * means that

G 3 (G 2 (upk j ), R j ) = G 3 (G 2 (upk * ), R j )
which implies a collision of G 2 .

Proof of Anonymity

Let A be an adversary breaking the anonymity of our construction with probability . We define the following sequence of games to show that this advantage is negligible. For each game i, we define Adv i = |P r(S i ) -1/2|, where S i is the event that A succeeds in game i.

Game 1. Our first game is exactly the anonymity game defined in Figure 4 with a random bit b where the reduction R generates normally the secret values. The advantage Adv 1 is then .

Game 2. In our second game, we make a guess on the coin that will be available to user upk b at the challenge time. More specifically, the reduction selects a random * ∈ [1, q w ] where q w is a bound on the number of queries and aborts if the * -th coin issued by the bank has not been withdrawn by upk b or if this user has entirely spent it before the challenge phase. The reduction still generates all the secret values and so the simulation is perfect unless the guess of R is not correct. We then have Adv 2 ≥ 1 qw .

Game 3. In our third game, R generates a simulated common reference string using the SimSetup and uses the SimProve algorithm to output the NIZK proofs. Any change in the behaviour of A in this game can then be used against the zero-knowledge property of Π. We then have Adv 3 ≥ Adv 2 -Adv zk A .

Game 4. In our fourth game, R proceeds as in the previous game except that during the * -th withdrawal query it replaces the commitment c by a random element from the commitment space. We note that this is not a problem for further NIZK proofs since the SimProve algorithm does not need witnesses as inputs. Any significant change in the behaviour of A then yields an adversary against the hiding property, which means that Adv 4 ≥ Adv 3 -Adv hid A .

Game 5. In our fifth game, R proceeds as in the previous game, but it answers the challenge query (V, upk 0 , upk 1 , mpk) as follows. First, it selects a subset S containing V elements that have never been involved in previous spendings of the * -th coin. We recall that Game 2 ensures that such a subset exists, otherwise R would abort. Moreover, this game also ensures that this coin belongs to upk 0 or upk 1 . Let us denote this user by upk * . R then selects three random values

(k 1 , k 2 , k 3 ) $ ← K 2 S × G 1 and returns (k (1)
S , k

S ) = (k 1 , k 2 • G 1 (upk)) along with T S = G 3 (G 2 (upk), H(mpk||info)) • k 3 . (2)
Here again, the NIZK proofs can still be produced by using the SimProve algorithm. We note that the simulation is perfect unless A is able to distinguish the random tuples (k 1 , k 2 , k 3 ) from (F 1 .CKey(s, S), F 2 .CKey(s, S), H(s)) if V = N or from (F 1 .CKey(s, S), F 2 .CKey(s, S), H S (F 1 .CKey(s, D(S)))) otherwise, which would yield an adversary against the strong combined key pseudo-randomness of F 1 and F 2 for the family (H, H ). We therefore have Adv 5 ≥ Adv 4 -Adv ckps A . We can note that in Game 5, the values received by the adversary are simulated proofs along with random elements (k

(1) S , k (2)
S ) and T S . The advantage Adv 5 of A in this game is then 0. This means that:

q w ≤ Adv zk A + Adv hid A + Adv ckps A
which concludes the proof since q w is polynomial in the security parameter λ.

PRFs Instantiations

In this section we describe some constrained PRFs that one can use to instantiate our generic frameworks above. All of them are derived from published e-cash schemes, we therefore do not claim novelty here but simply show that these PRFs achieve the properties required by our constructions.

Key Homomorphic Constrained PRF

The divisible e-cash schemes described in [CPST15a,CPST15b,PST17] yield efficient constrained PRFs in a bilinear setting that nicely interact with Groth-Sahai non-interactive proofs [GS08].

For sake of simplicity, we only consider the PRF implicitly defined in [CPST15a] but we stress that similar arguments apply to the ones defined in [CPST15b, PST17]. Before providing a formal definition of the PRF, we first recall the notion of bilinear groups and introduce some useful notations.

It now only remains to explain how one can generate a family of PRFs that achieves combined key pseudo-randomness. Actually, the technique is implicitly used in [CPST15a, CPST15b, PST17]. Given the previous PRF, one can generate a family of PRFs (F 1 , . . . , F t ) of arbitrary size by using the same random values in the Setup algorithm but with a different generator g i for i ∈ [1, t]. Therefore, for any subset S i,j , the family of constrained key is (k

(1) S i,j , . . . , k (t) S i,j ) = (g r i,j •s 1 , . . . , g r i,j •s t
). It was shown in [PST17] that this tuple is indistinguishable from a random element of G t 1 under the key pseudo-randomness of the underlying PRF and under the DDH assumption in G 1 .

In our context, since the weak-EXDH assumption implies the DDH one, we have combined key pseudo-randomness for free.

Remark 22. As we mention at the beginning of this section, we can extract from [CPST15b, PST17] alternative PRFs with better efficiency but that rely on stronger assumptions. However, we note that the one from [PST17] supports any subinterval of [1, N ], contrarily to the one we have just described.

Remark 23. In this bilinear setting, the user's key pair (usk, upk) is usually (x, g x ) ∈ Z p × G 1 for some secret scalar x. Therefore, one can define G 1 : g a ∈ G 1 → a ∈ Z p and G 2 : X ∈ G 1 → X. We stress that we do not need G 1 to be efficiently computable since it will only be used by the users on their own public key upk for which they know the discrete logarithm usk. Such functions G 1 and G 2 are injective and thus trivially achieve collision resistance. Finally we define G 3 : (X, a) ∈ G 1 × Z p → X a ∈ G 1 which is bilinear and non-degenerate.

Delegatable Constrained PRF

We note that the GGM construction [GGM84] instantiated with hash functions yields simple delegatable constrained PRFs that have already been used in e-cash systems [ASM08]. Unfortunately, they do not interact nicely with NIZK proofs leading either to impractical constructions or to systems [ASM08] where correct evaluation of the PRF can only be proven through cutand-choose techniques that seriously impact the overall security.

We therefore choose to describe the construction from [CG07] which, despite being very complex, does not need general zero-knowledge arguments.

Construction. Let S = [1, 2 m ] for some integer m ≥ 0. For i ∈ [0, m] and j ∈ [0, 2 i [, we define S i,j = [1 + j • 2 m-i , (j + 1)2 m-i ] and a sequence of prime p i such that p i divides p i+1 -1. We define below a PRF: K × S → Y, where K = Z p 0 -1 , K S i,j = Z p i , ∀i, j and Y = Z pm .

-Setup(1 λ , {S i,j } i,j : This algorithm selects a generator g 0 of Z * p 0 and, for i ∈ [1, m], two elements g i,0 and g i,1 of Z p i of order p i-1 . Note that these elements necessarily exist because p i divides p i+1 -1. All these elements are included in the public parameters.

-Keygen(): this algorithm returns a random s $ ← K. -CKey(s, S i,j ): On input s ∈ K and a subset S i,j , this algorithms first selects b 0 , . . . , b i-1 ∈ {0, 1} such that j = i-1 =0 b • 2 i-1-. Let k = g s 0 . For = 0, . . . , i -

1 it computes k ← g k +1,b
and finally returns the constrained key k S i,j = k. -Eval(s, t): On input the master key s and an element t ∈ [1, 2 m ], this algorithm returns CKey(s, S m,t-1 ). -CEval(S i,j , k S i,j , t): On input a set S i,j , a constrained key k S i,j and an element t ∈ S, this algorithm first selects b 0 , . . . , b m-1 such that t -1 = m-1 =0 b • 2 m-1-. It then sets k ← k S i,j and computes, for = i, . . . , m -1, k ← g k +1,b . Finally, it returns the last value of k. -CKey(k S i,j , S i ,j ) : on input a constrained key k S i,j and a set S i ,j , this algorithm returns ⊥ if S i ,j S i,j . Else, it selects b 0 , . . . , b i -1 ∈ {0, 1} such that j = i -1 =0 b • 2 i -1-and sets k = k S i,j . It then computes, for = i, . . . i -1, k ← g k +1,b and outputs k. i-1 ∈ {0, 1} be such that j = i-1 =0 b (j) • 2 i-1-. One can note that for any t ∈ [1, 2 m ], t ∈ S i,j ⇔ b = b (j) ∀ ∈ [0, i -1]. Indeed:

t ∈ S i,j ⇔ j • 2 m-i ≤t -1 ≤ (j + 1)2 m-i -1 ⇔ 2 m-i i-1 =0 b (j) • 2 i-1-≤t -1 ≤ 2 m-i (1 + i-1 =0 b (j) • 2 i-1-) -1 ⇔ i-1 =0 b (j) • 2 m-1-≤t -1 ≤ i-1 =0 b (j) • 2 m-1-+ 2 m-i -1 ⇔ b = b (j) ∀ ∈ [0, i -1].
Therefore, the CKey algorithm evaluated on (s, S i,j ) computes the i first steps of the Eval algorithm that are common to all elements t ∈ S i,j whereas CEval(S i,j , k S i,j , t) computes the missing steps. This means that CEval S i,j (CKey(s, S i,j ), t) = Eval(s, t), ∀S i,j t. It then only remain to prove that CKey(k S i,j , S i ,j ) = CKey(s, S i ,j ), ∀S i,j ⊃ S i ,j . The condition S i,j ⊃ S i ,j means that:

1 + j • 2 m-i ≤ 1 + j • 2 m-i ≤ (j + 1)2 m-i ≤ (j + 1)2 m-i
The first inequality implies that j ≥ i-1 =0 b

(j) 2 i -1-whereas the last one implies that j ≤ i-1 =0 b (j) 2 i -1-+ 2 i -i -1. Due to the unicity of the binary decomposition of j , this is only possible if b (j) = b (j ) for all ∈ [0, i-1]. Here again, this means that the CKey algorithm evaluated on (k S i,j , S i ,j ) computes the missing steps of the induction to get k S i ,j , which concludes the proof of correctness.

Collision Resistance. We recall that our framework based on delegatable CPRFs only requires collision resistance-1. So let us assume that an adversary manages to output two distinct pairs (s, t) and (s , t ) such that Eval(s, t) = Eval(s , t ). First, we note that we cannot have t = t . Indeed, one can easily prove by induction that this would mean g s 0 = g s 0 and so that s = s . Let us now write

t -1 = m-1 =0 b (t) • 2 m-1- t -1 = m-1 =0 b (t ) • 2 m-1-
the inequality t = t implies that there is an index * ∈ [0, m -1] such that (1) b Therefore, any adversary succeeding against the collision resistance of this PRF can be converted into an adversary against the discrete logarithm in one of the groups Z p i .

k

(2)

S i,j = (g (2)
i,j ) s+usk 6. T S i,j = ((g (3) i,j ) s • g usk•H(mpk||info) , (g (4) i,j ) s • g usk ) 7. τ is valid:

• e(τ 1 , X • g usk•H (mpk||V ||info||k (1) S i,j ||k (2) S i,j
||T S i,j ) ) • e(τ 2 , g) -1 = 1

The elements (k (1) S i , k

(2) S i , T S i , π) are then sent to the merchant who accepts them as a payment if π is valid.

The remaining algorithms can straightforwardly be derived from our generic framework since they do not really depend on the instantiations of our signature schemes. Nevertheless, in practice, we note that we can reduce the complexity of the Deposit procedure. Indeed, each of our serial numbers SN j theoretically requires to evaluate two CPRFs F 1 .CEval S i (k

(1) S i , j) and F 2 .CEval S i (k

(2) S i , j). However a fraud only occurs when the outputs of both PRFs collide with the outputs obtained from a different transcript. We can then simply compute F 1 .CEval S i (k

(1) S i , j) and stores it as a partial serial number. In case of collision (which is very unlikely, unless an active attack occurs), the other half of SN j would be computed to eliminate false positives.

Efficiency. We here only focus on the spending complexity, since the Withdraw algorithm only involves few exponentiations and since the complexity of the Deposit algorithm is the same as the one from [CPST15a], if we use the trick described above.

One can note that spending an amount V = 2 i can be done in constant time, for any i ∈ [0, m]. We could handle any amount in constant time if we had use the implicit CPRF in [PST17], but at the cost of a less standard assumption.

The bulk of the spending process is the generation of the NIZK proof. Indeed, the serial number and the double spending tag only represents 2 elements of G 1 , each. Using the Groth-Sahai proofs systems, the commitments to the secret variables represent 24 elements of G 1 and 4 elements of G 2 . Proving all the relations we have listed above represents 18 elements of G 1 and 34 elements of G 2 . Therefore, the whole Spend transcript contains 46 elements of G 1 and 38 elements of G 2 , which is very similar to the complexity of the (unsecure) standard model construction described in the full version of [CPST15a].

Conclusion

Decades after their introduction, divisible e-cash systems are still remarkably hard to design, and even to analyse. Existing schemes are based on intricate mechanisms, tailored to very specific settings, and so can hardly be reproduced in different contexts. Moreover, such mechanisms often rely on ad-hoc computational problems whose intractability is hard to assess.

In this paper we introduce the first frameworks for divisible e-cash systems that only use constrained PRFs and very standard cryptographic primitives. We prove the security of our global constructions assuming that each of the building blocks achieve some properties that we identify.

Our work thus presents this complex primitive in a new light, highlighting its strong relations with constrained PRFs. More specifically, it shows that the bulk of the design of a divisible ecash system is the construction of a constrained PRF with some specific features. We therefore hope that our results will encourage designers of constrained PRFs to add these features to their constructions, so as to implicitly define a new divisible e-cash scheme. We in particular believe that it is an important step towards a post-quantum divisible e-cash system.

  3 and leads to quite simple security proofs. It is explicitly stated in Section D.3 of the full version of [LLNW17] and in Section 4.6 of [CG10], and implicitly used in Section 6.3 of [CPST15a], in Section 6.2 of [PST17], and in the security proofs (page 22) of the full version of [CHL05].

Fig. 3 .

 3 Fig. 3. Collision Resistance Games for Constrained Pseudo-Random Functions

Fig. 5 .

 5 Fig. 5. Security Game for Digital Signature

Correctness.

  Let b 0 , . . . , b m-1 ∈ {0, 1} be such that t -1 = m-1 =0 b • 2 m-1-. The value Eval(s, t) = CKey(s, S m,t-1) is defined by induction as follows. Let k = g s 0 . For = 0, . . . , m -1, one computes k ← g k +1,b and finally sets Eval(s, t) = k. Now, for any i ∈ [0, m] and j ∈ [0, 2 i [, let b

=

  ∀ ∈ [ * + 1, m -1]. The latter condition implies that the last steps of the computation of Eval(s, t) and Eval(s , t ) are the same. More specifically, there are k m-1 and k m-1 , such that Eval(s, t) = g Eval(s , t ), which means that k m-1 = k m-1 and so on until we get g k * * +1,b (t) * = g k * * +1,b (t ) * . The latter equation means that the discrete logarithm of g * +1,b (t ) * in base g * +1,b (t) * is k * /k * , which can easily be recovered from s and s .

Actually, this specific terminology appeared later [CFN90] but this notion is implicit in the Chaum's paper.

The terminology can be confusing here: the "divisible coin" considered by most of the papers corresponds to the "wallet" of a compact e-cash system. In particular, the divisible coin contains several coins that are all associated to a serial number.

Our comment obviously only applies to papers that provide a security proof.

We stress that the problem is located in the proofs and not in the definition of the exculpability property.

Identification of the spender is not possible in this case because the two transcripts received by the bank (the one sent by the spender and the one sent by the merchant) are exactly the same.

Although the general definition in [BW13] allows randomized CKey algorithm, all our constructions will require this algorithm to be deterministic.

We note that our privacy requirements are weaker than the ones of [BLW17, BKM17] since we allow the constrained keys to leak the size of the subsets.

We do not make any assumption on the indices i0, . . . , iV -1, contrarily to some previous works that assume they are consecutive.

The "correctness for merchant", informally defined in [ASM08], is related to this issue. It ensures that the transcript deposited by an honest merchant will be accepted, even if the spender is dishonest and doublespends his coin. However, it only considers an honest bank and it does not consider situations where the transcript would be deposited by another entity. In particular, the scheme in [ASM08] does not ensure that the merchant is the only one able to clear his coins.

Actually the size of X can leak as it corresponds to the public amount of the transaction.

For sake of clarity, we assume here that the elements associated with the users' identity live in the right spaces. Our formal definition will make use of suitable maps to ensure this fact.

We need to apply the exponent R on the identity itself instead of the constrained key to rely on the correctness of CEval, but the principle is the same.

We nevertheless note that the cut-and-choose technique used during withdrawal in [ASM08] is very specific to this work and does not fit our framework.

This string can simply be a counter incremented by the merchant after each transaction, or include information that uniquely identifies the transaction such as the date and the hour.

This step will enable efficient proofs of valid constraining. The generation of such signatures can also be performed by the bank, without impact on the security

Acknowledgements

We thank Benoît Libert for very helpful discussions on the exculpability issue of previous works. This work is supported in part by the European Union PROMETHEUS Project (Horizon 2020

-CheckDeposit ([(V, info, mpk, k (1)

S i , T S i , π), µ], bpk) : this algorithm checks that π is valid and that 1 = Σ.Verify(mpk, (V, info, k

(1) S i , k

(2) S i , T S i , π), µ) in which case it outputs 1. Else, it returns 0.

The security of our construction is stated by the following theorem.

Theorem 15. Our divisible e-cash system is traceable if F 1 achieves collision resistance-1, Γ is computationally binding, Σ is EUF-CMA secure and Π is extractable. exculpable if Σ is EUF-CMA secure, Π is extractable, F 1 achieves collision resistance-1 and H 0 , G 1 and G 2 are collision resistant. clearable if Σ is EUF-CMA secure.

anonymous if (F 1 , F 2 ) achieves strong combined key pseudo-randomness for the family (H, H ),

Γ is computationally hiding and Π is zero-knowledge.

8 Proof of Theorem 15

All the proofs provided here are very similar to those provided in Section 6. We therefore mostly focus on the parts that involve double-spending tags because these elements strongly differ from a framework to another. In particular, we do not describe a proof for clearability since the one for our previous framework still works here.

Proof of Traceability

A successful adversary A against the traceability is able to spend more than it has withdrawn without being identified. Formally, this means that there are u transcripts

where:

The latter condition implies that all the proofs π i are valid (otherwise Identify would have returned 0 and not ⊥). Therefore, the challenger is able to extract from them tuples W i = (upk i , s i , r i , σ i , c i , S i , τ i ) satisfying the 7 relations defined by the Spend algorithm. Else, A could be trivially converted into an adversary against the extractability of Π.

We then distinguish the following cases:

-Type 1 Adversary: ∃i ∈ [1, u] such that none of the coins generated through OWithdraw B queries contains the commitment c i . -Type 2 Adversary: all the commitments c i have been generated during a query to the OWithdraw B oracle but the serial numbers do not collide. -Type 3 Adversary: all the commitments c i have been generated during a query to the OWithdraw B oracle and there is a collision in the list of serial numbers.

The first two types of adversary essentially imply an attack against the signature scheme or the commitment scheme. The security proofs are exactly the same as the one provided in Appendix 6. We therefore only consider the third type of adversary.

Lemma 16. Any type 3 adversary A succeeding with probability can be converted into an adversary succeeding against the collision resistance-1 of F 1 .

Proof. The reduction R generates the public parameters and the public key of the bank as usual, and is thus able to answer any query. At the end of the experiment, the type 3 adversary outputs u transcripts that yield at least two identical serial numbers. Among the colliding serial numbers, there is at least a pair (SN i , SN j ), with SN i = SN j , derived from Definition 18. Bilinear groups are a set of three cyclic groups G 1 , G 2 , and G T of prime order p along with a map, called pairing, e : G 1 × G 2 → G T that is 1. bilinear: for any g ∈ G 1 , g ∈ G 2 , and a, b ∈ Z p , e(g a , g b ) = e(g, g) ab ; 2. non-degenerate: for any g ∈ G *

1 and g ∈ G * 2 , e(g, g) = 1 G T ; 3. efficient: for any g ∈ G 1 and g ∈ G 2 , e(g, g) can be efficiently computed.

There are different types of pairings [GPS08] but we will here only make use of type 3 pairings that assume that no efficiently computable homomorphism exists between G 1 and G 2 . In the following every element of G 2 will be denoted with a (e.g. g) to distinguish them from elements of G 1 .

e) be bilinear groups as defined above and let g (resp. g) be a generator of G 1 (resp. G 2 ). We define below a PRF:

It then includes the following elements in the public parameters pp:

-CKey(s, S i,j ): On input s ∈ Z p and a subset S i,j , this algorithms returns a constrained key k S i,j = g s i,j . -Eval(s, t): On input the master key s and an element t ∈ S, this algorithm returns e(g s 0,0 , g 0,0,t ). -CEval(S i,j , k S i,j , t): On input a set S i,j , a constrained key k S i,j and an element t ∈ S, this algorithm returns e(k S i,j , g i,j,t ).

Correctness. For all i ∈ [0, m], j ∈ [0, 2 i [ and t ∈ S i,j , we have:

CEval(S i,j , CKey(s, S i,j ), t) = CEval(S i,j , g s i,j , t) = e(g s i,j , g i,j,t ) = e(g, g) t•s = e(g s 0,0 , g 0,0,t ) = Eval(s, t) which ensures correctness. The bilinearity of e directly implies the key homomorphism of this PRF.

Collision Resistance.

Theorem 19. Our PRF achieves collision resistance 1 under the symmetric discrete logarithm assumption [BCN + 10].

Proof. We recall that the symmetric discrete logarithm problem is the bilinear version of the discrete logarithm problem that assumes it is hard to recover x from the pair (g x , g x ). Given such an instance of this assumption, our reduction R selects a random t * ∈ [1, 2 m ] and generates the parameters as usual except that it implicitly sets t * = x. We note that this is always possible given both g x and g x .

The parameters are correctly distributed, therefore at the end of the game the adversary A returns (s 1 , s 2 , t 1 , t 2 ) such that:

∈ {t 1 , t 2 }, then R aborts. Else let us assume without loss of generality that t * = t 1 .

s 1 unless it aborts, which does not occur with probability at least

which implies that k 1 = k 2 . No adversary can then succeed against collision resistance 2 of our PRF.

Similarly, if CEval S i,j (k, t) = CEval S i ,j (k, t), then e(k, g) t/ri,j = e(k, g) t/r i ,j .

If k = 1 G 1 , then r i,j = r i ,j , which is very unlikely since these scalars have randomly chosen. No adversary can then succeed against collision resistance 3 of our PRF.

Key Pseudo-Randomness. Our proof is derived from the anonymity proof provided in the full version of [CPST15a]. We only prove key pseudo-randomness since it actually implies pseudorandomness.

We first recall the weak-EXDH assumption from [Duc10,CPST15a].

Definition 20. Given (g, g x , g a , g a•y , g z ) and ( g, g a , g y ), the weak-EXDH assumption states that it is hard to distinguish whether z = a • x • y or z is random.

Theorem 21. Our PRF is key pseudo-random under the weak-EXDH assumption.

Proof. The reduction R makes a guess on the set S i * ,j * selected by the adversary of the pseudorandomness and will abort if it is incorrect. We note that this does not occur with probability at least 1 n , where n = 2 m+1 -1 in our context. Now it generates as usual random scalars r i,j and t but sets the public parameters as follows.

g i,j = (g y•a ) r i,j if S i,j ⊂ S i * ,j * g i,j = (g a ) r i,j if S i,j S i * ,j * g i,j = g r i,j otherwise g i,j,t = g t/ri,j if S i,j ⊂ S i * ,j * g i,j,t = ( g y ) t/ri,j if S i,j S i * ,j * and t ∈ S i * ,j * g i,j,t = g t/ri,j if S i,j S i * ,j * and t / ∈ S i * ,j * g i,j,t = ( g a ) t/ri,j otherwise We note that this defines t = a•y • t if t / ∈ S i * ,j * and t = a• t otherwise. Next, the reduction implicitly defines the secret master key as x. We note that, if the guess of R is correct, R will always received OCKey query on subset S i,j such that S i,j ∩ S i * ,j * = ∅. Therefore the constrained key is g x•r i,j , which can always be computed by R since it knows r i,j .

To answer the challenge query from A on S i * ,j * , R simply returns Z = (g z ) r i * ,j * . If z = a•x•y, then Z is a valid constrained key and R plays the key pseudo-randomness game for b = 0. Otherwise, Z is random and R plays the key pseudo-randomness game for b = 1. Any adversary succeeding against key pseudo-randomness is then able to break the weak-EXDH assumption.

Key Pseudo-Randomness. The divisible e-cash system of [CG07] is claimed to be anonymous under a so-called Matching Multi Diffie-Hellman (MMDH) assumption introduced by the authors. Unfortunately, the latter do not provide any detail in the proof and it seems very difficult to introduce an MMDH instance in the security reduction while being able to answer to any adversarial query. We therefore introduce a new assumption which is quite similar to the MMDH assumption, but which allows us to prove the key pseudo-randomness of this PRF.

Definition 24. Let u > 0 be an integer and, for i ∈ [0, u -1], q i be a prime number such that q i divides q i+1 -1. Let g 0,α and g 0,β be generators of Z * p 0 and, for i ∈ [1, u], let g i,α and g i,β be two elements of Z * q i of order q i-1 . For any integer x and i ∈ [0, u], we define by induction P i = g

with P 0 = g x 0,α . The u-MMDH assumption states that it is hard to distinguish Z = P u (x) from a random element of Z * qu of order q u-1 , even given access to {(g i,α , g i,β )} u i=0 and (g x 0,β , g P 0 1,β , . . . g

Theorem 25. The PRF described above is key pseudo-random under the m-MMDH assumption.

Proof. Given a m-MMDH instance, the reduction R makes a guess on the set S i * ,j * that the adversary will output. For ∈ [0, i * ], it sets p = q m-i * + and selects the other primes p as usual for

, where b denotes 1 -b. All the other elements of the public parameters are randomly generated.

In the reduction, R implicitly defines the seed as P m-i * -1 . Since the Eval function returns the output of CKey, we just explain how R can handle the OCKey queries. Let S i,j be the subset queried to the OCKey oracle and j

Otherwise, we would have S i,j ⊂ S i * ,j * or S i * ,j * ⊂ S i,j and the guess would be invalid. Therefore, at the * -th step of the computation of k S i,j , the value k is of the form g k * +1,b * = g k m-i * + * +1,β with k depending on P m-i * -1 and {(g i,α , g i,β )} m m-i * . The element g k m-i * + * +1,β can then easily be derived from the elements provided in the m-MMDH instance which ensures that the simulation is perfect.

When the adversary outputs the challenge subset, R aborts if its guess is incorrect. Otherwise, it returns Z from the m-MMDH instance. If Z = P u (x), then it is a valid constrained key and the adversary A plays the key pseudo-randomness game for b = 0. Else, it is a random element from the corresponding constrained key space, which corresponds to the case where b = 1.

Strong Key Pseudo-Randomness. We note that, for any subset S i,j = [1, 2 m ], the constrained key k S i,j is of the form g

where S i-1,j is the smallest subset strictly containing S i,j . Now let h 0 be a generator of Z p 0 and h i,b be an element of Z p i of order p i-1 for b ∈ {0, 1}. We can then define H : s → h s and H i,j : k → h k i,b . Therefore, in the strong key pseudo-randomness game, the adversary will now have to distinguish pairs of the form (g

) from random elements. By using the same argument as in the key homomorphic case, we can prove that this is not possible under the key pseudorandomness of the PRF and the DDH assumption.

A Standard Model Instantiation

As we have explained in our introduction, the exculpability issue invalidates existing standard model constructions. We therefore describe in this section the first e-cash scheme proven secure in the standard model. It is a direct instantiation of our first framework, using the CPRF presented in Section 9.1.

Our NIZK proofs are instantiated with the Groth-Sahai proof system [GS08] that allows to prove most relations for bilinear groups. We will more specifically use their SXDH setting for our complexity evaluation. For sake of clarity, we will underline all committed values when we will describe the proven relations.

-Setup(1 λ , 2 m ): To generate the public parameters pp for divisible coins of value 2 m , the algorithm first computes a Groth-Sahai common reference string for the SXDH setting. It then generates four constrained PRFs F 1 , F 2 , F 3 and F 4 , as described in Section 9.1, using different generators g (1) , g (2) , g (3) and g (4) for each of them. It then selects a hash function H : {0, 1} * → G and instantiates G 1 , G 2 and G 3 as described in Remark 23.

Next, it generates m + 1 key pairs (sk (i) , pk (i) ), for i ∈ [0, m], for the AGHO structurepreserving signature scheme from [AGHO11]. For each i ∈ [0, m] and j ∈ [0, 2 i [, it uses sk (i) to generate a signature µ i,j = (z

, w (i,j) ) on (g

i,j , g

i,j , g

i,j , g

i,j ) before discarding this secret key. The public keys pk , 4], are included in the public parameters 16 . Finally, it selects a random x ∈ Z p and generators (g, g) ∈ G 1 × G and adds (X, X) ← (g x , g x ) in pp. It also includes the description of a hash function H : {0, 1} * → Z p . This last step provides public parameters for the PS aggregate signature scheme in [PS16].

-BKeygen(): The bank first sets ck = {g, h 1 , h 2 } for some generators h 1 , h 2 ∈ G 1 . It then generates a key pair (sk B , pk B ) for the signature scheme in [AGHO11] and outputs (ck, pk B ), where pk B = ( v 1 , v 2 , w). -Keygen() : The user (resp. the merchant) generates a pair (usk, upk), with usk $ ← Z p and upk = g usk (resp. msk $ ← Z p and mpk = g msk ). We note that this is a valid key pair for the PS signature scheme.

-Withdraw(B(bsk, upk), U(usk, bpk)): To withdraw a divisible coin, the user first generates two random scalars s and r. It then sends c ← h s 1 • h usk 2 • g r along with a PS signature on H (c) using usk. The bank then returns an AGHO signature τ c = (z

-Spend(U(usk, C, bpk, V ), M(msk, bpk, info, V )): During a spending of amount V , the merchant first selects a string info that he never used before and sends it to the user along with his public key mpk.

The user then selects a subset S i,j with |S i,j | = V such that SN j has never been revealed for all j ∈ S i,j , and computes

• k

(1)

i,j ) s • k

(2) ||T S i,j ) ) = (τ 1 , τ 2 ) = τ , for some scalar t along with the following NIZK proof π:

1. S i,j is a valid subset: , w (i,j) ) • e(g, g) -1 = 1 • V = 2 m-i (both i and V are public here) 2. c is a valid commitment:

• c = h