Transferable E-Cash: A Cleaner Model and the First Practical Instantiation

Abstract

Transferable e-cash is the most faithful digital analog of physical cash, as it allows users to transfer coins between them in isolation, that is, without interacting with a bank or a “ledger”. Appropriate protection of user privacy and, at the same time, providing means to trace fraudulent behavior (double-spending of coins) have made instantiating the concept notoriously hard. Baldimtsi et al. (PKC’15) gave a first instantiation, but, as it relies on a powerful cryptographic primitive, the scheme is not practical. We also point out a flaw in their scheme.

In this paper we revisit the model for transferable e-cash and propose simpler yet stronger security definitions. We then provide the first concrete construction, based on bilinear groups, give rigorous proofs that it satisfies our model, and analyze its efficiency in detail.

1 Introduction

Contrary to so-called “crypto”-currencies like Bitcoin [Nak08], a central ambition of the predating cryptographic e-cash has been user anonymity. Introduced by Chaum [Cha83], the goal was to realize a digital analog of physical cash, which allows users to pay without revealing their identity; and there has been a long line of research since [CFN88, Bra93, CHL05, BCKL09, FHY13, CPST16, BPS19] (to name only a few). In e-cash, a bank issues electronic coins to users, who can then spend them with merchants, who in turn can deposit them at the bank to get their account credited. User privacy should be protected in that not even the bank can link the withdrawing of a coin to its spending.

The main difference to the physical world is that digital coins can easily be duplicated, and therefore a so-called “double-spending” of a coin must be prevented. This can be readily achieved when all actors are online and connected (as with cryptocurrencies), since every spending is broadcast and payees simply refuse a coin that has already been spent.

Even in “anonymous” cryptocurrencies like Monero [vS13], which now also uses confidential transactions [Max15], or systems based on the Zerocoin/-cash [MGGR13, BCG+14] protocol, like Zcash [Zec20], or on Mimblewimble [Poe16, FOS19], users must be connected when they accept a payment, in order to prevent double-spending.

When users are allowed to spend coins to other users (or merchants) without continuous connectivity, then double-spending cannot be prevented; however, starting with [CFN88], ingenious methods have been devised for revealing a double-spender’s identity while guaranteeing the privacy of all honest users.

Transferable E-Cash. In all traditional e-cash schemes, including such “offline” e-cash, once a coin is spent (transferred) after withdrawal, it must be deposited at the bank by the payee. A more powerful concept, and much more faithful to physical e-cash, is transferable e-cash, which allows users to re-transfer obtained coins, while at the same time remaining offline. Note that cryptocurrencies are inherently online, and every transfer of a coin could be seen as depositing a coin (and marking it spent) and re-issuing a new one (in the ledger).

Transferable e-cash was first proposed by Okamoto and Ohta [OO89, OO91], but the constructions only guaranteed very weak forms of anonymity. It was then shown [CP93] that unbounded adversaries can recognize coins they owned earlier and that a coin must grow in size with every transfer (since information about potential double-spenders needs to be encoded in it).

While other schemes [Bla08, CGT08] only achieve unsatisfactory anonymity notions, Canard and Gouget [CG08] define a stronger notion (which we call coin transparency): it requires that a (polynomial-time) adversary cannot recognize a coin he has already owned when it is later given back to him. This is not achieved by physical cash, as banknotes can be marked by users (or the bank); however, if an e-cash scheme allowed a merchant to identify users by tracing the coins given out as change, then it would violate the central claim of e-cash, namely anonymous payments. (Anonymous cryptocurrencies also satisfy a notion analogous to coin transparency.) A limitation of this notion is that the bank (more specifically, the part dealing with deposits) must be honest, as it must be able to link occurrences of the same coin to detect double-spending.

Prior Schemes. The first scheme achieving coin transparency [CG08] was completely impractical, as at every transfer, the payer sends a proof of (a proof of (...(a proof of a coin)...)) that she received earlier. The first practical scheme was given by Fuchsbauer et al. [FPV09], but it makes unacceptable compromises elsewhere: when a double-spending is detected, all (even innocent) users up to the double-spender must give up their anonymity.

Blazy et al. [BCF+11] overcome this problem and propose a scheme that assumes a trusted party (called the “judge”) that can trace all coins and users in the system and has to actively intervene to identify double-spenders. The scheme thus reneges on the promise that users remain anonymous as long as they follow the protocol. Moreover, their proof of anonymity was flawed, as shown by Baldimtsi et al. [BCFK15].

Despite all its problems, Blazy et al.’s [BCF+11] scheme, which elegantly combined randomizable non-interactive zero-knowledge (NIZK) proofs [BCC+09] and commuting signatures [Fuc11], serves as starting point for our construction. In their scheme a coin consists of a signature by the bank and at every transfer the spender adds her own signature (thereby committing to her spending). To achieve anonymity, these signatures are not given in the clear; instead, coins are NIZK proofs of knowledge of signatures. Since the proofs can be rerandomized (that is, from a proof, anyone can produce a new proof of the same statement that looks unrelated to the original proof), coins can change appearance after every transfer. Users will thus not recognize a coin when they see it again later, meaning the scheme satisfies coin transparency.

Baldimtsi et al. [BCFK15] give an instantiation that avoids the “judge” by using a double-spending-tracing mechanism from classical offline e-cash. They add “tags” to the coin that hide the identity of the owner of the coin, except when she spends the coin twice, then the bank can from two such tags compute the user’s identity. Users must also include signatures in the coin during transfer, which represent irrefutable proof of double-spending.

The main drawback of their scheme is efficiency. They rely on the concept of malleable signatures [CKLM14], a generalization of digital signatures, where a signature on a message m can be transformed into a signature on a message T(m) for any allowed transformation T. Simulation unforgeability requires that from a signature one can extract all transformations it has undergone (even when the adversary that created it has seen “simulated” signatures).

In their scheme [BCFK15] a coin is a malleable signature computed by the bank, which can be transformed by a user if she correctly encodes her identity in a double-spending tag, adds an encryption (under the bank’s public key) to it and randomizes all encryptions of previous tags contained in the coin.

None of the previous schemes explicitly considers denominations of coins (and neither do we). This is because efficient (“compact”) withdrawing and spending can be easily achieved if the bank associates different keys to different denominations (since giving change is readily supported in transferable e-cash). Note that, in contrast to cryptocurrencies, where every transaction is publicly posted, hiding the amount of a payment is meaningless in transferable e-cash.

Our Contribution: Security Model. We revisit the formal model for transferable e-cash, starting from [BCFK15], whose model was a refined version of earlier ones. We then exhibit attacks against users who follow the protocol, against which previous models did not protect:

• When a user receives a coin (that is, the protocol accepts the received coin), then previous models did not guarantee that this coin will be accepted by other (honest) users when transferred. An adversary could thus send a mal-formed coin to a user, which the latter accepts but can then not spend.

• There were also no guarantees against a malicious bank which at coin deposit refuses to credit the user’s account (e.g., by claiming that the coin was invalid or had been double-spent). In our model, when the bank refuses a coin, it must accuse a user of double-spending and provide a proof for this.

We then simplify the anonymity definitions, which in earlier version had been cluttered with numerous oracles the adversary has access to, and for which the intuitive notion that they were formalizing was hard to grasp. While our definitions are simpler, they are stronger in that they imply previous definitions (except for the previous notion of “spend-then-receive (StR) anonymity”, whose existing formalizations we argue are not relevant in practice).

We also show that the proof of “StR anonymity” (a notion similar to coin transparency) of the scheme from [BCFK15] is flawed and that it only satisfies a weakening of the notion (Sect. 3.2).

Our Contribution: Instantiation. Our main contribution is a transferable e-cash scheme, which we prove satisfies our security model, and which is more efficient than the only previous realization [BCFK15]. Unfortunately, the authors do not provide concrete numbers, as they use malleable signatures in a blackbox way. Arguably, these signatures are the main source of inefficiency, due to their generality and the strong security notions in the spirit of simulation-sound extractability, requiring that a coin (i.e., a malleable signature) stores every transformation it has undergone.

In contrast, we give a direct construction from the following primitives: Groth-Sahai proofs [GS08], which are randomizable; structure-preserving signatures [AFG+10], which are compatible with GS proofs; and rerandomizable encryption satisfying RCCA-security [CKN03] (the corresponding variant of CCA security, see Fig. 6). While we use signature schemes from the literature [AGHO11, Fuc11], we construct a new RCCA-secure encryption scheme that is tailored to our scheme, basing it on prior work [LPQ17]. Finally, our scheme also uses the (efficient) double-spending tags used previously [BCFK15].

Due to the existence of an omnipotent “judge”, no such tags were required by Blazy et al. [BCF+11]. Interestingly, although we do not assume any active trusted parties, we achieve a comparable efficiency, which is a result of realizing the full potential of the tags: previously [BCFK15], tags had only served to encode a user’s identity; but, as we show, they can in addition be used to commit the user. This allows us, contrary to all previous instantiations, to completely forgo the inclusion of user signatures in the coins, which considerably reduces their size. For a more detailed (informal) overview of our scheme see Sect. 5.1.

In terms of efficiency, our coins grow by around 100 elements from a bilinear group per transfer (see table on p. 28). We view this as practical by current standards, especially in view of numbers for deployed schemes: e.g., the parameters for Zcash consist of several 100 000 bilinear-group elements [Zec20].

2 Definition of Transferable E-Cash

The syntax and security definitions we present in the following are refinements of earlier work [CG08, BCF+11, BCFK15].

2.1 Algorithms and Protocols

An e-cash scheme is set up by running $\mathsf{{ParamGen}}$ and the bank generating its key pair via $\mathsf{{BKeyGen}}$. The bank maintains a list of users $\mathcal {UL}$ and a list of deposited coins $\mathcal {DCL}$. Users run the protocol $\mathsf{{Register}}$ with the bank to obtain their secret key, and their public keys are added to $\mathcal {UL}$. With her secret key a user can run $\mathsf{{Withdraw}}$ with the bank to obtain coins, which she can transfer to others via the protocol $\mathsf{{Spend}}$.

$\mathsf{{Spend}}$ is also used when a user deposits a coin at the bank. After receiving a coin, the bank runs $\mathsf{{CheckDS}}$ (for “double-spending”) on it and the previously deposited coins in $\mathcal {DCL}$, which determines whether to accept the coin. If so, it is added to $\mathcal {DCL}$; if not (in case of double-spending), $\mathsf{{CheckDS}}$ returns the public key of the accused user and a proof $\varPi$, which can be verified using $\mathsf{{VfyGuilt}}$.

• $\mathsf{{ParamGen}}(1^{\lambda }),\!$ on input the security parameter $\lambda$ in unary, outputs public parameters ${\textit{par}}$, which are an implicit input to all of the following algorithms.

• $\mathsf{{BKeyGen}}()\!$ is run by the bank $\mathcal {B}$ and outputs its public key ${ {pk}}_{\mathcal {B}}$ and its secret key ${ {sk}}_\mathcal {B}= \left( { {sk}}_{\mathcal {W}}, { {sk}}_{\mathcal {D}}, { {sk}}_{\mathcal {CK}}\right)$, where ${ {sk}}_\mathcal {W}$ is used to issue coins in $\mathsf{{Withdraw}}$ and to register users in $\mathsf{{Register}}$; ${ {sk}}_\mathcal {D}$ is used as the receiver secret key when coins are deposited via $\mathsf{{Spend}}$; and ${ {sk}}_\mathcal {CK}$ is used for $\mathsf{{CheckDS}}$.

• ${\mathsf{{Register}}\langle \mathcal {B}({ {sk}}_\mathcal {W}), \mathcal {U}({ {pk}}_\mathcal {B})\rangle }\!$ is a protocol between the bank and a user. The user obtains a secret key ${ {sk}}$ and the bank gets ${ {pk}}$, which it adds to $\mathcal {UL}$.

• ${\mathsf{{Withdraw}}\langle \mathcal {B}({ {sk}}_\mathcal {W}), \mathcal {U}({ {sk}}_{\mathcal {U}}, { {pk}}_{\mathcal {B}})\rangle }\!$ is run between the bank and a user, who outputs a coin ${ {c}}$ (or $\bot$ in case of error), while the bank outputs ok (in which case it debits the user’s account) or $\bot$.

• ${\mathsf{{Spend}}\langle \mathcal {U}({ {c}}, { {sk}}, { {pk}}_{\mathcal {B}}), \mathcal {U}^\prime ({ {sk}}^\prime , { {pk}}_\mathcal {B})\rangle }\!$ is run between two users and lets $\mathcal {U}$ spend a coin ${ {c}}$ to $\mathcal {U}^\prime$ (who could be the bank). $\mathcal {U}^\prime$ outputs a coin ${ {c}}'$ (or $\bot$), while $\mathcal {U}$ outputs ok (or $\bot$).

• $\mathsf{{CheckDS}}({ {sk}}_{\mathcal {CK}}, \mathcal {UL}, \mathcal {DCL}, { {c}})\!,$ run by the bank, takes as input its checking key, the lists of registered users $\mathcal {UL}$ and of deposited coins $\mathcal {DCL}$ and a coin ${ {c}}$. It outputs an updated list $\mathcal {DCL}$ (when the coin is accepted) or a user public key ${ {pk}}_\mathcal {U}$ and an incrimination proof $\varPi$.

• $\mathsf{{VfyGuilt}}({ {pk}}_\mathcal {U}, \varPi )$ can be executed by anyone. It takes a user public key and an incrimination proof and returns 1 (acceptance of $\varPi$) or 0 (rejection).

Note that we define a transferable e-cash scheme as stateless, in that there is no state information shared between the algorithms. A withdrawn coin, whether it was the first or the n-th coin issued to a specific user, is always distributed the same. Moreover, a received coin will only depend on the spent coin (and not on other spent or received coins). Thus, the bank and the users need not store anything about past transactions for transfer; the coin itself must be sufficient.

In particular, the bank can separate withdrawing from depositing, in that $\mathsf{{CheckDS}}$, used during deposit, need not be aware of the withdrawn coins.

2.2 Security Definitions

Global Variables. In our security games, we store all information about users and their keys in the user list $\mathcal {UL}$. Its entries are of the form $\left( { {pk}}_i, { {sk}}_i, {\textit{uds}}_i\right)$, where ${\textit{uds}}_i$ indicates how many times user $\mathcal {U}_i$ has double-spent.

In the coin list $\mathcal {CL}$, we keep information about the coins created in the system. For each withdrawn or spent coin ${ {c}}$, we store a tuple $({\textit{owner}}, { {c}},{\textit{cds}}, {\textit{origin}})$, where owner stores the index i of the user who withdrew or received the coin (coins obtained by the adversary are not stored); ${\textit{cds}}$ counts how often this specific instance of the coin has been spent; ${\textit{origin}}$ is set to “$\mathcal {B}$” if the coin was issued by the honest bank and to “$\mathcal {A}$” if it originates from the adversary; if the coin was originally spent by the challenger itself, then ${\textit{origin}}$ indicates which original coin this transferred coin corresponds to.

Finally, we maintain a list of deposited coins $\mathcal {DCL}$.

Oracles. Our security games use oracles, which differ depending on whether the adversary impersonates a corrupt bank or users. If during the oracle execution an algorithm fails (i.e., it outputs $\bot$) then the oracle also stops. Otherwise the call to the oracle is considered successful; a successful deposit oracle call must also not detect any double-spending.

Registration and Corruption of Users. The adversary can instruct the creation of honest users and either play the role of the bank during registration, or passively observe registration. It can moreover “spy” on users, meaning it can learn the user’s secret key. This will strengthen yet simplify our anonymity games compared to [BCFK15], where once the adversary had learned the secret key of a user (by “corrupting” her), the user could not be a challenge user in the anonymity games anymore (yielding selfless anonymity, while we achieve full anonymity).

• $\mathtt{BRegist}()\!$ plays the bank side of $\mathsf{{Register}}$ and interacts with $\mathcal {A}$. If successful, it adds $({ {pk}}, \bot ,{\textit{uds}}=0)$ to $\mathcal {UL}$ (where ${\textit{uds}}$ is the number of double-spends).

• $\mathtt{URegist}()\!$ plays the user side of the $\mathsf{{Register}}$ protocol when the bank is controlled by the adversary. Upon successful execution, it adds $({ {pk}}, { {sk}}, 0)$ to $\mathcal {UL}$.

• $\mathtt{Regist}()\!$ plays both parties in the $\mathsf{{Register}}$ protocol and adds $({ {pk}}, { {sk}}, 0)$ to $\mathcal {UL}$.

• $\mathtt{Spy}(i),\!$ for $i\le |\mathcal {UL}|$, returns user i’s secret key ${ {sk}}_i$.

Withdrawal Oracles. The adversary can either withdraw a coin from the bank, play the role of the bank, or passively observe a withdrawal.

• $\mathtt{BWith}()\!$ plays the bank side of the $\mathsf{{Withdraw}}$ protocol. Coins withdrawn by $\mathcal {A}$ (and thus unknown to the experiment) are not added to the coin list $\mathcal {CL}$.

• $\mathtt{UWith}(i)\!$ plays user i in $\mathsf{{Withdraw}}$ when the bank is controlled by the adversary. Upon obtaining a coin ${ {c}}$, it adds $({\textit{owner}}=i, { {c}}, {\textit{cds}}=0,{\textit{origin}}= \mathcal {A})$ to $\mathcal {CL}$.

• $\mathtt{With}(i)\!$ simulates a $\mathsf{{Withdraw}}$ protocol execution playing both $\mathcal {B}$ and user i. It adds $({\textit{owner}}=i, { {c}}, {\textit{cds}}=0, {\textit{origin}}=\mathcal {B})$ to $\mathcal {CL}$.

Spend and deposit oracles.

• $\mathtt{Spd}(j)\!$ spends the coin from the j-th entry $({\textit{owner}}_j, { {c}}_j, {\textit{cds}}_j,{\textit{origin}}_j)$ in $\mathcal {CL}$ to $\mathcal {A}$, who could be impersonating a user, or the bank during a deposit. The oracle plays $\mathcal {U}$ in the $\mathsf{{Spend}}$ protocol with secret key ${ {sk}}_{{\textit{owner}}_j}$. It increments the coin spend counter ${\textit{cds}}_j$ by 1. If afterwards ${\textit{cds}}_j>1$ then the owner’s double-spending counter ${\textit{uds}}_{{\textit{owner}}_j}$ is incremented by 1.

• $\mathtt{Rcv}(i)\!$ makes honest user i receive a coin from $\mathcal {A}$. The oracle plays $\mathcal {U}^{\prime }$ in the $\mathsf{{Spend}}$ protocol with user i’s secret key. It adds a new entry $({\textit{owner}}=i, { {c}}, {\textit{cds}}=0,{\textit{origin}}=\mathcal {A})$ to $\mathcal {CL}$.

• $\mathtt{S} \& \mathtt{R}(j,i)\!$ spends the j-th coin in $\mathcal {CL}$ to user i. It runs $(ok, { {c}})\leftarrow \mathsf{{Spend}}\langle \mathcal {U}({ {c}}_j,{ {sk}}_{{\textit{owner}}_j}, { {pk}}_\mathcal {B}), \mathcal {U}^{\prime }({ {sk}}_i, { {pk}}_\mathcal {B})\rangle$ and adds $({\textit{owner}}=i,{ {c}}, {\textit{cds}}=0, {\textit{origin}}=j)$ to $\mathcal {CL}$. It increments the coin spend counter ${\textit{cds}}_j$ by 1. If afterwards ${\textit{cds}}_j>1$, then ${\textit{uds}}_{{\textit{owner}}_j}$ is incremented by 1.

• $\mathtt{BDepo}()\!$ lets $\mathcal {A}$ deposit a coin. It runs $\mathcal {U}'$ in $\mathsf{{Spend}}$ using the bank’s secret key ${ {sk}}_\mathcal {D}$ with the adversary playing $\mathcal {U}$. If successful, it runs $\mathsf{{CheckDS}}$ on the received coin and either updates $\mathcal {DCL}$ or returns a pair $\big ({ {pk}}, \varPi \big )$.

• $\mathtt{Depo}(j),\!$ the honest deposit oracle, runs $\mathsf{{Spend}}$ between the owner of the j-th coin in $\mathcal {CL}$ and an honest bank. If successful, it increments ${\textit{cds}}_j$ by 1; if afterwards ${\textit{cds}}_j>1$, it also increments ${\textit{uds}}_{{\textit{owner}}_j}$. It runs $\mathsf{{CheckDS}}$ on the received coin and either updates $\mathcal {DCL}$ or returns a pair $\big ({ {pk}}, \varPi \big )$.

(No “UDepo” is needed since Spd lets user deposit at an adversarial bank.)

2.3 Economic Properties

We distinguish two types of security properties of transferable e-cash schemes. Besides anonymity notions, economic properties ensure that neither the bank nor users will incur an economic loss when participating in the system.

The following property was not required in any previous formalization of transferable e-cash in the literature and is analogous the property clearing defined for classical e-cash [BPS19].

Soundness. If an honest user accepted a coin during a withdrawal or a transfer, then she is guaranteed that the coin will be accepted by others, either honest users when transferring, or the bank when depositing. The game is formalized in Fig. 1 where $i_2$ plays the role of the receiver of a spending or the bank. For convenience, we define probabilistic polynomial-time (PPT) adversaries $\mathcal {A}$ to be stateful in all our security games.

Fig. 1.

Game for soundness (protecting users from financial loss)

Definition 1 (Soundness)

A transferable e-cash system is sound if for any PPT $\mathcal {A}$, we have $\mathbf{Adv}^{\mathtt{sound}}_\mathcal {A}(\lambda ):= \Pr [\mathbf{Expt}^{\mathtt{sound}}_{\mathcal {A}} (\lambda ) =1]$ is negligible in $\lambda$.

Unforgeability. This notion covers both unforgeability and user identification from [BCFK15] (which were not consistent as we explain in Sect. 3.2). It protects the bank, ensuring that no (coalition of) users can spend more coins than the number of coins they withdrew. Unforgeability also guarantees that whenever a coin is deposited and refused by $\mathsf{{CheckDS}}$, it returns the identity of a registered user, who is accused of double-spending. (Exculpability, below, ensures that no innocent user will be accused.) The game is given in Fig. 2 and lets the adversary impersonate all users.

Fig. 2.

Game for unforgeability (protecting the bank from financial loss)

Definition 2 (Unforgeability)

A transferable e-cash system is unforgeable if $\mathbf{Adv}^{\mathtt{unforg}}_\mathcal {A}\left( \lambda \right) := \Pr [\mathbf{Expt}^{\mathtt{unforg}}_{\mathcal {A}} \left( \lambda \right) =1]$ is negligible in $\lambda$ for any PPT $\mathcal {A}$.

Exculpability. This notion, a.k.a. non-frameability, ensures that the bank, even when colluding with malicious users, cannot wrongly accuse an honest user of double-spending. Specifically, it guarantees that an adversarial bank cannot produce a double-spending proof $\varPi ^*$ that verifies for the public key of a user $i^*$ that has never double-spent. The game is formalized as in Fig. 3.

Fig. 3.

Game for exculpability (protecting honest users from accusation)

Definition 3 (Exculpability)

A transferable e-cash system is exculpable if $\mathbf{Adv}^{\mathtt{excul}}_\mathcal {A}(\lambda ) := \Pr [\mathbf{Expt}^{\mathtt{excul}}_{\mathcal {A}} (\lambda )=1]$ is negligible in $\lambda$ for any PPT $\mathcal {A}$.

2.4 Anonymity Properties

Instead of following previous anonymity notions [BCF+11, BCFK15], we introduce new ones which clearly distinguish between the adversary’s capabilities; in particular, whether or not it is able to detect double-spending. When the adversary impersonates the bank, we consider two cases: user anonymity and coin anonymity (and explain why this distinction is necessary).

As transferred coins necessarily grow in size [CP93], we can only guarantee indistinguishability of comparable coins. We therefore define comp$\left( { {c}}_1, { {c}}_2\right) =1$ iff $\texttt {size}\left( { {c}}_1\right) = \texttt {size}\left( { {c}}_2\right)$, where $\texttt {size}({ {c}})=1$ after ${ {c}}$ was withdrawn and it increases by 1 after each transfer.

Coin Anonymity. This notion is closest to (and implies) the anonymity notion of classical e-cash: an adversary, who also impersonates the bank, issues two coins to the challenger and when she later receives them (via a deposit in classical e-cash), she should not be able to associate them to their issuances. In transferable e-cash, we allow the adversary to determine two series of honest users via which the coins are respectively transferred before being given back to the adversary.

The experiment is specified on the left of Fig. 4: users $i^{_{(0)}}_0$ and $i^{_{(1)}}_0$ withdraw a coin from the adversarial bank, user $i^{_{(0)}}_0$ passes it to $i^{_{(0)}}_1$, who passes it to $i^{_{(0)}}_2$, etc., In the end, the last users of the two chains spend the coins to the adversary, but the order in which this happens depends on a bit b that parametrizes the game, and which the adversary must decide.

Fig. 4.

Games for coin and user anonymity (protecting users from a malicious bank)

User Anonymity. Coin anonymity required that users who transfer the coin are honest. If one of the users through which the coin passes colluded with the bank, there would be a trivial attack: after receiving the two challenge coins, the bank simulates the deposit of one of them and the deposit of the coin intercepted by the colluding user. If a double-spending is detected, it knows that the received coin corresponds to the sequence of users which the colluder was part of.

Since double-spending detection is an essential feature of e-cash, attacks of this kind are impossible to prevent. However, we still want to guarantee that, while the bank can trace coins, the involved users remain anonymous. We formalize this in the game on the right of Fig. 4, where, in contrast to coin anonymity, there is only one coin and the adversary must distinguish the sequence of users through which the coin passes before returning to her. In contrast to coin anonymity, we now allow the coin to already have some “history”, rather than being freshly withdrawn.

Fig. 5.

Game for coin transparency (protecting users from malicious users)

Coin Transparency. This is arguably the strongest anonymity notion and it implies that a user that transfers a coin cannot recognize it if she receives it again. As the bank can necessarily trace coins (for double-spending detection), it is assumed to be honest for this notion. Actually, only the detection key ${ {sk}}_\mathcal {CK}$ must remain hidden from the adversary, while ${ {sk}}_\mathcal {W}$ and ${ {sk}}_{\mathcal {D}}$ can be given.

The game formalizing this notion, specified in Fig. 5, is analogous to coin anonymity, except that the challenge coins are not freshly withdrawn; instead, the adversary spends two coins of its choice to users of its choice, both are passed through a sequence of users of the adversary’s choice and one of them is returned to the adversary.

There is another trivial attack that we need to exclude: the adversary could deposit the coin that is returned to him and one, say the first, of the coins he initially transferred to an honest user. Now if the deposit does not succeed because of double-spending, the adversary knows that it was the first coin that was returned to him. Again, this attack is unavoidable due to the necessity of double-spending detection. It is a design choice that lies outside of our model to implement sufficient deterrence from double-spending, so that it would exceed the utility of breaking anonymity.

This is the reason why the game aborts if the adversary deposits twice a coin from the set of “challenge coins” (consisting of the two coins the adversary transfers and the one it receives). The variable ${ ctr}$ counts how often a coin from this set was deposited. Note also that because $\mathcal {A}$ has ${ {sk}}_\mathcal {W}$, and can therefore create unregistered users, we do not consider $\mathcal {UL}$ in this game.

Definition 4 (Anonymity)

For $\mathtt{x}\in \{\mathtt{c-an}, \mathtt{u-an}, \mathtt{c-tr}\}$ a transferable e-cash scheme satisfies $\mathtt{x}$ if $\mathbf{Adv}^{\mathtt{x}}_\mathcal {A}(\lambda ):= \Pr [\mathbf{Expt}^{\mathtt{x}}_{\mathcal {A},1}\left( \lambda \right) =1] \,-\,\Pr [\mathbf{Expt}^{\mathtt{x}}_{\mathcal {A},0} \left( \lambda \right) =1]$ is negligible in $\lambda$ for any PPT adversary $\mathcal {A}$.

3 Comparison with Previous Work

3.1 Model Comparison

In order to justify our new model, we start with discussing a security vulnerability of the previous model [BCFK15].

No Soundness Guarantees. In none of the previous models was there a security notion that guaranteed that an honest user could successfully transfer a coin to another honest user or the bank, even if the coin was obtained regularly.

Fuzzy Definition of “Unsuccessful Deposit”. Previous models defined a protocol called “$\mathsf{{Deposit}}$”, which we separated into an interactive ($\mathsf{{Spend}}$) and a static part ($\mathsf{{CheckDS}}$). In their definition of unforgeability, the authors [BCFK15] use the concept of “successful deposit”, whose meaning is unclear, since an “unsuccessful deposit” could mean one of the following:

• The bank detects a double-spending and provides a proof accusing the cheater (who could be different from the depositer).

• The user did not follow the protocol (e.g., by sending a malformed coin), in which case we cannot expect a proof of guilt from the bank.

• The user followed the protocol but using a coin that was double-spent (either earlier or during deposit); however, the bank does not obtain a valid proof of guilt and outputs $\bot$.

Our interpretation of the definition in [BCFK15] is that it does not distinguish the second and the third case. This is an issue, as the second case cannot be avoided (and must be dealt with outside the model, e.g. by having users sign their messages). But the third case should be prevented so the bank does not lose money without being able to accuse the cheater. This is now guaranteed by our unforgeability notion in Definition 2.

Simplification of Anonymity Definitions. We believe that our notions are more intuitive and simpler (e.g. by reducing the number of oracles of previous work). Our notions imply prior notions from the literature: we can prove that the existence of an adversary in a game from a prior notion implies the existence of an adversary in one of our games. (The general idea is to simulate most of the oracles using the secret keys of the bank or users, which in our notions can be obtained via the $\mathtt{Spy}$ oracle.) In particular:

$$\begin{aligned} \texttt {c-an}&\Rightarrow \texttt {OtR-fa}&\text {and}&\qquad \qquad \texttt {u-an}\Rightarrow \texttt {StR*-fa} \end{aligned}$$

where OtR-fa is observe-then-receive full anonymity [CG08, BCF+11, BCFK15] and StR*-fa is a variant of spend-then-receive full anonymity from [BCFK15].

The notion $\texttt {StR-fa}$ [CG08, BCF+11] is similar to our coin transparency c-tr, with the following differences: in $\texttt {StR-fa}$, when the adversary deposits a coin, the bank provides a guilt proof when it can; and it lets the adversary obtain user secret keys. Coin transparency would imply $\texttt {StR-fa}$ if $\mathsf{{CheckDS}}$ replaced its argument $\mathcal {UL}$ by $\emptyset$. This change is justified since (in both StR-fa and c-tr) the adversary can create unregistered users (using ${ {sk}}_\mathcal {W}$), and thus $\mathsf{{CheckDS}}$ could return $\bot$ because it cannot accuse anyone in $\mathcal {UL}$.

Finally, no prior scheme, including [BCFK15], achieves $\texttt {StR-fa}$, as shown next.

3.2 A Flaw in a Proof in BCFK15

The authors [BCFK15] claim that their scheme satisfies $\texttt {StR-fa}$ as defined in [BCF+11] (after having discovered a flaw in the $\texttt {StR-fa}$ proof of the scheme of that paper). To achieve this anonymity notion (the most difficult one, as they note), they use malleable signatures, which guarantee that whenever an adversary, after obtaining simulated signatures, outputs a valid message/signature pair $(m, \sigma )$, it must have derived the pair from received signatures. Formally, there exists an extractor that can extract a transformation from $\sigma$ that links m to the messages on which the adversary queried signatures.

In the game formalizing $\texttt {StR-fa}$ [BCF+11] (analogously to $\mathbf{Expt} ^{\texttt {c-tr}}$ in Fig. 5) the adversary receives ${ {sk}}_\mathcal {W}$, which formalizes the notion that the part of the bank that issues coins can be corrupt. In their scheme [BCFK15], ${ {sk}}_\mathcal {W}$ contains the signing key for the malleable signatures. However, with this the adversary can easily compute a fresh signature, and thus no extractor can recover a transformation explaining the signed message. This shows that a scheme based on malleable signatures only satisfies a weaker notion of StR-fa/c-tr, where all parts of the bank must be honest.

In contrast, we prove that our scheme satisfies c-tr; it can therefore be seen as the first scheme to satisfy the “spirit” of $\texttt {StR-fa}$, as captured by c-tr.

4 Primitives Used in Our Construction

4.1 Bilinear Groups

The building blocks of our scheme will be defined over a (Type-3, i.e., “asymmetric”) bilinear group, which is a tuple ${ Gr}=(p, \mathbb {G}, \hat{\mathbb {G}}, \mathbb {G}_T, e, g, \hat{g})$, where $\mathbb {G},\hat{\mathbb {G}}$ and $\mathbb {G}_T$ are groups of prime order p; $\langle g\rangle = \mathbb {G}$, $\langle \hat{g}\rangle = \hat{\mathbb {G}}$, and $e:\mathbb {G}\times \hat{\mathbb {G}} \rightarrow \mathbb {G}_T$ is a bilinear map (i.e., for all $a,b\in \mathbb Z_p$: $e(g^a,\hat{g}^b)=e(g,\hat{g})^{ab}$) so that $e(g,\hat{g})$ generates $\mathbb {G}_T$. We assume that the groups are discrete-log-hard and other computational assumptions, such as SXDH, defined in the full version [BFQ20], hold as well. We assume that there exists an algorithm $\mathsf{{GrGen}}$ that, on input the security parameter $\lambda$ in unary, outputs the description of a bilinear group with $p\ge 2^{\lambda -1}$.

4.2 Randomizable Proofs of Knowledge and Signatures

Commit-and-Prove Proof Systems. As coins must be unforgeable, at their core lie digital signatures. To achieve anonymity, these must be hidden, which can be achieved via non-interactive zero-knowledge (NIZK) proofs of knowledge; if these proofs are re-randomizable, then they can not even be recognized by a past owner. We will use Groth-Sahai NIZK proofs [GS08], which are randomizable [FP09, BCC+09] and include commitments to the witnesses.

We let $\mathcal {V}$ be set of values that can be committed, $\mathcal {C}$ be the set of commitments, $\mathcal {R}$ the randomness space and $\mathcal {E}$ the set of equations (containing equality) whose satisfiability can be proved. We assume that $\mathcal {V}$ and $\mathcal {R}$ are groups. We will use an extractable commitment scheme, which consists of the following algorithms:

• $\mathsf{C}.\mathsf{{Setup}}({ Gr})\!$ takes as input a description of a bilinear group and returns a commitment key ${ {ck}}$, which implicitly defines the sets $\mathcal {V}, \mathcal {C}, \mathcal {R}$ and $\mathcal {E}$.

• $\mathsf{C}.\mathsf{{ExSetup}}({ Gr})\!$ returns an extraction key ${ {xk}}$ in addition to a commitment key ${ {ck}}$.

• $\mathsf{C}.\mathsf{{SmSetup}}({ Gr})\!$ returns a commitment key ${ {ck}}$ and a simulation trapdoor ${ {td}}$.

• $\mathsf{C}.\mathsf{{Cm}}({ {ck}}, v, \rho ),\!$ on input a key ${ {ck}}$, a value $v \in \mathcal {V}$ and randomness $\rho \in \mathcal {R}$, returns a commitment in $\mathcal {C}$.

• $\mathsf{C}.\mathsf{{ZCm}}({ {ck}}, \rho ),$ used when simulating proofs, is defined as $\mathsf{C}.\mathsf{{Cm}}({ {ck}}, 0_\mathcal {V}, \rho )$.

• $\mathsf{C}.\mathsf{{RdCm}}({ {ck}}, c, \rho )$ randomizes a commitment c to a fresh $c^{\prime }$ using randomness $\rho$.

• $\mathsf{C}.\mathsf{{Extr}}({ {xk}}, c),$ on input extraction key ${ {xk}}$ and a commitment c, outputs a value in $\mathcal {V}$. (This is the only algorithm that might not be polynomial-time.)

We extend $\mathsf{C}.\mathsf{{Cm}}$ to vectors in $\mathcal {V}^n$: for $M = (v_1, \dots , v_n)$ and $\rho = (\rho _1, \dots , \rho _n)$ we define $\mathsf{C}.\mathsf{{Cm}}({ {ck}}, M, \rho ):= \big (\mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_1, \rho _1),\dots , \mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_n, \rho _n)\big )$ and likewise $\mathsf{C}.\mathsf{{Extr}}({ {xk}}, (c_1, \dots , c_n )):= \big (\mathsf{C}.\mathsf{{Extr}}({ {xk}}, c_1 ),\dots , \mathsf{C}.\mathsf{{Extr}}({ {xk}}, c_n)\big )$.

We now define a NIZK proof system that proves that committed values satisfy given equations from $\mathcal {E}$. Given a proof for commitments, the proof can be adapted to a randomization (via C.RdCm) of the commitments using C.AdptPrf.

• $\mathsf{C}.\mathsf{{Prv}}({ {ck}}, E, (v_1, \rho _1), \dots , (v_n, \rho _n) ),$ on input a key ${ {ck}}$, a set of equations $E \subset \mathcal {E}$, values $(v_1, \dots , v_n)$ and randomness $(\rho _1, \dots , \rho _n)$, outputs a proof $\pi$.

• $\mathsf{C}.\mathsf{{Verify}}({ {ck}}, E, c_1, \dots , c_n, \pi ),$ on input a commitment key ${ {ck}}$, a set of equations in $\mathcal {E}$, a commitment vector $(c_1, \dots , c_n),$ and a proof $\pi$, outputs a bit b.

• $\mathsf{C}.\mathsf{{AdptPrf}}({ {ck}}, E, c_1, \rho _1, \dots , c_n, \rho _n, \pi ),$ on input a set of equations, commitments $(c_1, \dots , c_n)$, randomness $(\rho _1, \dots , \rho _n)$ and a proof $\pi$, outputs a proof $\pi ^{\prime }$.

• $\mathsf{C}.\mathsf{{SmPrv}}({ {td}}, E, \rho _1, \dots , \rho _n),$ on input the simulation trapdoor, a set of equations E with n variables and randomness $(\rho _1, \dots , \rho _n)$, outputs a proof $\pi$.

$\varvec{\mathcal {M}}$-Structure-Preserving Signatures. To prove knowledge of signatures, we require a scheme that is compatible with Groth-Sahai proofs [AFG+10].

• $\mathsf{S}.\mathsf{{Setup}}({ Gr}),$ on input the bilinear group description, outputs signature parameters ${\textit{par}}_S$, defining a message space $\mathcal {M}$. We require $\mathcal {M}\subseteq \mathcal {V}^n$ for some n.

• $\mathsf{S}.\mathsf{{KeyGen}}({\textit{par}}_S),$ on input the parameters ${\textit{par}}_S$, outputs a signing key and a verification key $({ {sk}}, { {vk}})$. We require that ${ {vk}}$ is composed of values in $\mathcal {V}$.

• $\mathsf{S}.\mathsf{{Sign}}({ {sk}}, M),$ on input a signing key ${ {sk}}$ and a message $M \in \mathcal {M}$, outputs a signature $\varSigma$. We require that $\varSigma$ is composed of values in $\mathcal {V}$.

• $\mathsf{S}.\mathsf{{Verify}}({ {vk}}, M, \varSigma ),$ on input a verification key ${ {vk}}$, a message M and a signature $\varSigma$, outputs a bit b. We require that $\mathsf{S}.\mathsf{{Verify}}$ proceeds by evaluating equations from $\mathcal {E}$ (which we denote by $E_{\mathsf{S}.\mathsf{{Verify}}(\cdot , \cdot , \cdot )}$).

$\varvec{\mathcal {M}}$-Commuting Signatures. As in a previous construction of transferable e-cash [BCF+11], we will use commuting signatures [Fuc11], which let the signer, given a commitment to a message, produce a commitment to a signature on that message, together with a proof, via the following functionality:

• $\mathsf{{SigCm}}({ {ck}}, { {sk}}, c),$ given a signing key ${ {sk}}$ and a commitment c of a message $M \in \mathcal {M}$, outputs a committed signature $c_{\varSigma }$ and a proof $\pi$ that the signature in $c_\varSigma$ is valid on the value in c, i.e., the committed values satisfy ${\mathsf{S}.\mathsf{{Verify}}({ {vk}}, \cdot , \cdot )}$.

• $\mathsf{{SmSigCm}}({ {xk}}, { {vk}}, c, \varSigma ),$ on input the extraction key ${ {xk}}$, a verification key ${ {vk}}$, a commitment c and a signature $\varSigma$, outputs a committed signature $c_{\varSigma }$ and a proof $\pi$ of validity for $c_\varSigma$ and c (the key ${ {xk}}$ is needed to compute $\pi$ for c).

Correctness and Soundness Properties. We require the following properties of commitments, proofs and signatures, when the setup algorithms are run on any output ${ Gr}\leftarrow \mathsf{{GrGen}}(1^\lambda )$ for any $\lambda \in \mathbb {N}$:

• Perfectly binding commitments: $\mathsf{C}.\mathsf{{Setup}}$ and the first output of $\mathsf{C}.\mathsf{{ExSetup}}$ are distributed equivalently. Let $({ {ck}}, { {xk}})\leftarrow \mathsf{C}.\mathsf{{ExSetup}}$; then for every $c\in \mathcal {C}$ there exists exactly one $v\in \mathcal {V}$ such that $c= \mathsf{C}.\mathsf{{Cm}}({ {ck}}, v, \rho )$ for some $\rho \in \mathcal {R}$. Moreover, $\mathsf{C}.\mathsf{{Extr}}({ {xk}}, c)$ extracts that value v.

• $\mathcal {V}'$-extractability: Committed values from a subset $\mathcal {V}^{\prime } \subset \mathcal {V}$ can be efficiently extracted (e.g., $\mathcal {V}'=\mathbb {G}_1\cup \mathbb {G}_2$ [GS08]). Let $({ {ck}}, { {xk}}) \leftarrow \mathsf{C}.\mathsf{{ExSetup}}$; then $\mathsf{C}.\mathsf{{Extr}}({ {xk}}, \cdot )$ is efficient for all $c=\mathsf{C}.\mathsf{{Cm}}({ {ck}},v,\rho )$ for any $v \in \mathcal {V}^{\prime }$ and $\rho \in \mathcal {R}$.

• Proof completeness: Let ${ {ck}}\leftarrow \mathsf{C}.\mathsf{{Setup}}$; then for all $(v_1, \dots , v_n) \in \mathcal {V}^n$ satisfying $E \subset \mathcal {E}$, and $(\rho _1, \dots , \rho _n) \in \mathcal {R}^n$ and $\pi \leftarrow \mathsf{C}.\mathsf{{Prv}}({ {ck}}, E, (v_1, \rho _1), \dots ,(v_n, \rho _n) )$ we have $\mathsf{C}.\mathsf{{Verify}}({ {ck}}, E, \mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_1, \rho _1), \dots , \mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_n, \rho _n), \pi ) = 1.$

• Proof (knowledge) soundness: Let $({ {ck}}, { {xk}}) \!\leftarrow \! \mathsf{C}.\mathsf{{ExSetup}}$, $E \subset \mathcal {E}$, $(c_1, \dots , c_n) \!\in \! \mathcal {C}^n$. If $\mathsf{C}.\mathsf{{Verify}}({ {ck}}, E, c_1, \dots , c_n, \pi )=1$ for some $\pi$, then letting $v_i:= \mathsf{C}.\mathsf{{Extr}}({ {xk}}, c_i)$, for all i, we have that $(v_1, \dots , v_n)$ satisfy E.

• Randomizability: Let ${ {ck}}\leftarrow \mathsf{C}.\mathsf{{Setup}}$ and $E\subset \mathcal {E}$; for all $(v_1, \dots , v_n)\in \mathcal {V}^n$ satisfying E, and $\rho _1, \rho ^{\prime }_1, \dots , \rho _n, \rho ^{\prime }_n\in \mathcal {R}$ the following are distributed equivalently:

  $$\begin{aligned}&\Big ( \mathsf{C}.\mathsf{{RdCm}}(\mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_1, \rho _1), \rho _1^{\prime }), \dots , \mathsf{C}.\mathsf{{RdCm}}(\mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_n, \rho _n), \rho _n^{\prime }),\\[-.6ex]&\qquad \mathsf{C}.\mathsf{{AdptPrf}}\big ({ {ck}},E, \mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_1, \rho _1),\rho ^{\prime }_1, \dots , \mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_n, \rho _n), \rho ^{\prime }_n,\\[-.6ex]&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \; \mathsf{C}.\mathsf{{Prv}}({ {ck}}, E, (v_1, \rho _1), \dots , (v_n, \rho _n))\big ) \Big )\ \text {and} \\[-.6ex]&\Big ( \mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_1, \rho _1 + \rho _1^{\prime }), \dots , \mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_n, \rho _n + \rho _n^{\prime }), \\[-.8ex]& \mathsf{C}.\mathsf{{Prv}}({ {ck}}, E, (v_1, \rho _1 + \rho _1^{\prime }), \dots , (v_n, \rho _n + \rho _n^{\prime }))\Big ) \end{aligned}$$

• Signature correctness: Let $({ {sk}}, { {vk}}) \leftarrow \mathsf{S}.\mathsf{{KeyGen}}(\mathsf{S}.\mathsf{{Setup}})$ and $M \in \mathcal {M}$; then we have $\mathsf{S}.\mathsf{{Verify}}({ {vk}}, M, \mathsf{S}.\mathsf{{Sign}}({ {sk}}, M ))=1$.

• Correctness of signing committed messages: Let $({ {ck}}, { {xk}})\leftarrow \mathsf{C}.\mathsf{{ExSetup}}$ and let $({ {sk}},{ {vk}})\leftarrow \mathsf{S}.\mathsf{{KeyGen}}(\mathsf{S}.\mathsf{{Setup}})$, and $M \in \mathcal {M}$; for $\rho , \rho ^{\prime } \xleftarrow {{}_\$} \mathcal {R}$, the following three are distributed equivalently:

  $$\begin{aligned}&\big (\mathsf{C}.\mathsf{{Cm}}\big ({ {ck}}, \mathsf{S}.\mathsf{{Sign}}({ {sk}}, M), \rho ^{\prime }\big ),\ \mathsf{C}.\mathsf{{Prv}}\big ({ {ck}}, E_{\mathsf{S}.\mathsf{{Verify}}({ {vk}}, \cdot , \cdot )}, (M, \rho ), (\varSigma , \rho ^{\prime })\big )\big ) \text {~~and} \\&\mathsf{{SigCm}}\big ({ {ck}}, { {sk}}, \mathsf{C}.\mathsf{{Cm}}({ {ck}}, M, \rho )\big ) \text {~~and} \mathsf{{SmSigCm}}\big ({ {xk}}, { {vk}}, \mathsf{C}.\mathsf{{Cm}}({ {ck}}, M, \rho ), \mathsf{S}.\mathsf{{Sign}}({ {sk}}, M)\big ) \end{aligned}$$

  The first equivalence also holds for ${ {ck}}\leftarrow \mathsf{C}.\mathsf{{Setup}}$, since it is distributed like ${ {ck}}$ output by $\mathsf{C}.\mathsf{{ExSetup}}$.

Security Properties

• Mode indistinguishability: Let ${ Gr}\leftarrow \mathsf{{GrGen}}(1^\lambda )$; then the outputs of $\mathsf{C}.\mathsf{{Setup}}({ Gr})$ and the first output of $\mathsf{C}.\mathsf{{SmSetup}}({ Gr})$ are computationally indistinguishable.

• Perfect zero-knowledge in hiding mode: Let $({ {ck}}, { {td}}) \leftarrow \mathsf{C}.\mathsf{{SmSetup}}({ Gr})$, $E\subset \mathcal {E}$ and $v_1, \dots , v_n \in \mathcal {V}$ such that $E(v_1, \dots , v_n)=1$. For $\rho _1,\dots ,\rho _n \xleftarrow {{}_\$} \mathcal {R}$ the following are distributed equivalently:

  $$\begin{aligned} \big (\mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_1, \rho _1),\dots ,\mathsf{C}.\mathsf{{Cm}}({ {ck}}, v_n, \rho _n), \mathsf{C}.\mathsf{{Prv}}\big ({ {ck}}, E, (v_1, \rho _1), \dots , (v_n, \rho _n)\big )\big ) \\ \text {and} \ \ \big (\mathsf{C}.\mathsf{{ZCm}}({ {ck}}, \rho _1), \dots , \mathsf{C}.\mathsf{{ZCm}}({ {ck}}, \rho _n), \mathsf{C}.\mathsf{{SmPrv}}\big ({ {td}}, E, \rho _1, \dots , \rho _n\big )\big ) \end{aligned}$$

• Signature unforgeability (under chosen message attack): No PPT adversary that is given ${ {vk}}$ output by $\mathsf{S}.\mathsf{{KeyGen}}$ and an oracle for adaptive signing queries on messages $M_1,M_2,\dots$ of its choice can output a pair $(M, \varSigma )$, such that $\mathsf{S}.\mathsf{{Verify}}({ {vk}}, M, \varSigma )=1$ and $M\notin \{M_1,M_2,\dots \}$.

4.3 Rerandomizable Encryption Schemes

In order to trace double-spenders, some information must be retrievable from the coin by the bank. For anonymity, we encrypt this information. Since coins must change appearance in order to achieve coin transparency (Definition 4), we use rerandomizable encryption. We will prove consistency of encrypted messages with values used elsewhere, and to produce such a proof, knowledge of parts of the randomness is required; we therefore make this an explicit input of some algorithms, which thus are still probabilistic.

A rerandomizable encryption scheme $\mathsf{E}$ consists of four algorithms:

• $\mathsf{E}.\mathsf{{KeyGen}}({ Gr}),$ on input the group description, outputs an encryption key ${ {ek}}$ and a corresponding decryption key ${ {dk}}$.

• $\mathsf{E}.\mathsf{{Enc}}({ {ek}}, M, \nu )$ is probabilistic and on input an encryption key ${ {ek}}$, a message M and (partial) randomness $\nu$ outputs a ciphertext.

• $\mathsf{E}.\mathsf{{ReRand}}({ {ek}}, C, \nu '),$ on input an encryption key, a ciphertext and (partial) randomness, outputs a new ciphertext.

• $\mathsf{E}.\mathsf{{Dec}}({ {dk}}, C),$ on input a decryption key and a ciphertext, outputs either a message or $\bot$ indicating an error.

To prove statements about encrypted messages, we add two functionalities: $\mathsf{E}.\mathsf{{Verify}}$ lets one check that a ciphertext encrypts a given message M, for which it is also given partial randomness $\nu$. This will allow us to prove that a commitment $c_M$ and a ciphertext $C$ contain the same message. For this, we require that the equations defining $\mathsf{E}.\mathsf{{Verify}}$ are in the set $\mathcal {E}$ supported by $\mathsf{C}.\mathsf{{Prv}}$.

This lets us define an equality proof $\tilde{\pi }=(\pi , c_\nu )$, where $c_\nu$ is a commitment to the randomness $\nu$, and $\pi$ proves that the values in $c_M$ and $c_\nu$ verify the equations $\mathsf{E}.\mathsf{{Verify}}({ {ek}}, \cdot , \cdot , C)$. To support rerandomization of ciphertexts, we define a functionality $\mathsf{E}.\mathsf{{AdptPrf}}$, which adapts a proof $(\pi ,c_\nu )$ to a rerandomization.

• $\mathsf{E}.\mathsf{{Verify}}({ {ek}}, M, \nu , C),$ on input an encryption key, a message, randomness and a ciphertext, outputs a bit.

• $\mathsf{E}.\mathsf{{AdptPrf}}({ {ck}}, { {ek}}, c_M, C, \tilde{\pi }= (\pi , c_\nu ), \nu '),$ a probabilistic algorithm which, on input keys, a commitment, a ciphertext, an equality proof (i.e., a proof and a commitment) and randomness, outputs a new equality proof $(\pi ',c_\nu ')$.

Correctness Properties. We require the scheme to satisfy the following correctness properties for all key pairs $({ {ek}}, { {dk}}) \leftarrow \mathsf{E}.\mathsf{{KeyGen}}({ Gr})$ for ${ Gr}\leftarrow \mathsf{{GrGen}}(1^\lambda )$:

• For all $M\in \mathcal {M}$ and randomness $\nu$ we have: $\mathsf{E}.\mathsf{{Enc}}({ {ek}}, M, \nu )=C$ if and only if $\mathsf{E}.\mathsf{{Verify}}({ {ek}}, M, \nu , C)=1$.

• For all $M\in \mathcal {M}$ and $\nu$: $\mathsf{E}.\mathsf{{Verify}}({ {ek}}, M, \nu , C)=1$ implies $\mathsf{E}.\mathsf{{Dec}}({ {dk}}, C)=M$. (These two notions imply the standard correctness notion.)

• For all $M\in \mathcal {M}$ and randomness $\nu , \nu '$, if $C\leftarrow \mathsf{E}.\mathsf{{Enc}}({ {ek}}, M, \nu )$ then the following are equally distributed: $\mathsf{E}.\mathsf{{ReRand}}({ {ek}}, C, \nu ')$ and $\mathsf{E}.\mathsf{{Enc}}({ {ek}}, M, \nu + \nu ')$.

• For all ${ {ck}}\leftarrow \mathsf{C}.\mathsf{{Setup}}$, all $({ {ek}}, { {dk}}) \leftarrow \mathsf{E}.\mathsf{{KeyGen}}$, $M\in \mathcal {M}$ and randomness $\nu , \nu ', \rho _M, \rho _\nu$, if we let

  $$\begin{aligned} c_M&\leftarrow \mathsf{C}.\mathsf{{Cm}}({ {ck}}, M, \rho _M)&C&\leftarrow \mathsf{E}.\mathsf{{Enc}}({ {ek}}, M, \nu ) \\ c_\nu&\leftarrow \mathsf{C}.\mathsf{{Cm}}({ {ck}}, \nu , \rho _\nu )&\pi&\leftarrow \mathsf{C}.\mathsf{{Prv}}\big ({ {ck}}, \mathsf{E}.\mathsf{{Verify}}({ {ek}}, \cdot , \cdot , C), (M, \rho _M), (\nu , \rho _\nu )\big ) \end{aligned}$$

  then the following are equivalently distributed (with $\rho _\nu '\xleftarrow {{}_\$}\mathcal {R}$):

  $$\begin{aligned}&\mathsf{E}.\mathsf{{AdptPrf}}\big ({ {ck}}, { {ek}}, c_M, \mathsf{E}.\mathsf{{Enc}}({ {ek}}, C, \nu ), (\pi , c_\nu ), \nu '\big ) \qquad \text {and} \\&\big (\mathsf{C}.\mathsf{{Prv}}({ {ck}}, \mathsf{E}.\mathsf{{Verify}}({ {ek}}, \cdot , \cdot , \mathsf{E}.\mathsf{{ReRand}}({ {ek}}, C, \nu ')), (M, \rho _M), (\nu + \nu ', \rho _\nu + \rho _\nu ') ),\\&\mathsf{C}.\mathsf{{RdCm}}({ {ck}}, c_\nu , \rho _\nu ')\big )\ \end{aligned}$$

Security Properties. We require two properties: the standard (strongest possible) variant of CCA security; a new notion that is easier to achieve.

Replayable-CCA (RCCA) Security. We use the definition by Canetti et al. [CKN03], formalized in Fig. 6.

Fig. 6.

Security games for rerandomizable encryption schemes

Indistinguishability of Adversarially Chosen and Randomized Ciphertexts (IACR). An adversary that is given a public key, chooses two ciphertexts and is then given the randomization of one of them cannot, except with a negligible advantage, distinguish which one it was given. The game is formalized in Fig. 6.

Definition 5

For $\mathtt{x}\in \{\mathtt{RCCA}, \mathtt{IACR}\}$, a rerandomizable encryption scheme is $\mathtt{x}$-secure if $\Pr [\mathbf{Expt}^{\mathtt{x}}_{\mathcal {A}, 1} (\lambda ) =1]-\Pr [\mathbf{Expt}^{\mathtt{x}}_{\mathcal {A}, 0} (\lambda ) =1]$ is negligible in $\lambda$ for any PPT $\mathcal {A}$.

4.4 Double-Spending Tag Schemes

Our e-cash scheme follows earlier approaches [BCFK15], where the bank represents a coin in terms of its serial number ${ sn}= { sn}_0 \Vert \ldots \Vert { sn}_k$, which grows with every transfer. In addition, a coin contains ${ tag}= { tag}_1 \Vert \ldots \Vert { tag}_{k}$, which enables tracing of double-spenders. The part ${ sn}_i$ is chosen by a user when she receives the coin, while the tag ${ tag}_i$ is computed by the sender as a function of ${ sn}_{i-1}$, ${ sn}_{i}$ and her secret key.

Baldimtsi et al. [BCFK15] show how to construct such tags so they perfectly hide user identities, except when a user computes two tags with the same ${ sn}_{i-1}$ but different values ${ sn}_i$: then her identity can be computed from the two tags. Note that this precisely corresponds to double-spending the coin that ends in ${ sn}_{i-1}$ to two users that choose different values for ${ sn}_i$ when receiving it.

We use the tags from [BCFK15], which we first formally define, and then show that their full potential had not been leveraged yet: in particular, we realize that the tag can also be used as method for users to authenticate the coin transfer. In earlier works [BCF+11, BCFK15], at each transfer the spender computed a signature that was included in a coin and that committed the user to the spending (and made her accountable in case of double-spending). Our construction does not require any user signatures and thus gains in efficiency.

Furthermore, in [BCFK15] (there were no tags in [BCF+11]), the malleable signatures took care of ensuring well-formedness of the tags, while we give an explicit construction. To be compatible with Groth-Sahai proofs, we define structure-preserving proofs of well-formedness for serial numbers and tags.

Syntax. An $\mathcal {M}$-double-spending tag scheme $\mathsf{T}$ is composed of the following polynomial-time algorithms:

• $\mathsf{T}.\mathsf{{Setup}}({ Gr}),$ on input a group description, outputs the parameters ${\textit{par}}_\mathsf{T}$ (which are an implicit input to all of the following).

• $\mathsf{T}.\mathsf{{KeyGen}}(),$ on (implicit) input the parameters, outputs a tag key pair $({ {sk}}, { {pk}})$.

• $\mathsf{T}.\mathsf{{SGen}}({ {sk}}, n)$, the serial-number generation function, on input a secret key and a nonce $n\in \mathcal {N}$ (the nonce space), outputs a serial-number component ${ sn}$ and a proof ${ sn-pf}$ of well-formedness.

• $\mathsf{T}.\mathsf{{SGen}}_\mathrm{init} ({ {sk}}, n)$, a variant of $\mathsf{T}.\mathsf{{SGen}}$, outputs a message $M\in \mathcal {M}$ instead of a proof. ($\mathsf{{SGen}}_\mathrm{init}$ is used for the first SN component, which is signed by the bank using a signature scheme that requires messages to be in $\mathcal {M}$.)

• $\mathsf{T}.\mathsf{{SVfy}}({ {pk}}, { sn}, { sn-pf}),$ on input a public key, a serial number and a proof verifies that ${ sn}$ is consistent with ${ {pk}}$ by outputting a bit b.

• $\mathsf{T}.\mathsf{{SVfy}}_\mathrm{init} ({ {pk}}, { sn}, M),$ on input a public key, a serial number and a message in $\mathcal {M}$, checks their consistency by outputting a bit b.

• $\mathsf{T}.\mathsf{{SVfy}}_\mathrm{all},$ depending on the type of the input, runs $\mathsf{T}.\mathsf{{SVfy}}_\mathrm{init}$ or $\mathsf{T}.\mathsf{{SVfy}}$.

• $\mathsf{T}.\mathsf{{TGen}}({ {sk}}, n, { sn}),$ the double-spending tag generator, takes as input a secret key, a nonce $n\in \mathcal {N}$ and a serial number, and outputs a double-spending tag ${ tag}\in \mathcal {T}$ (the set of the double-spending tags) and a tag proof ${ t-pf}$.

• $\mathsf{T}.\mathsf{{TVfy}}({ {pk}}, { sn}, { sn}^{\prime }, { tag}, { t-pf}),$ on input a public key, two serial numbers, a double-spending tag, and a proof, checks consistency of the tag w.r.t. the key and the serial numbers by outputting a bit b.

• $\mathsf{T}.{\mathsf{Detect}}({ sn}, { sn}^{\prime }, { tag}, { tag}^{\prime }, \mathcal {L})$, double-spending detection, takes two serial numbers ${ sn}$ and ${ sn}^\prime$, two tags ${ tag},{ tag}^{\prime }\in \mathcal {T}$ and a list of public keys $\mathcal {L}$ and outputs a public key ${ {pk}}$ (of the accused user) and a proof $\varPi$.

• $\mathsf{T}.\mathsf{{VfyGuilt}}({ {pk}}, \varPi )$, incrimination-proof verification, takes as input a public key and a proof and outputs a bit b.

Fig. 7.

Game for tag anonymity (with oracles also used in exculpability) for double-spending tag schemes

Correctness Properties. For a double-spending tag scheme $\mathsf{T}$ we require that for all ${\textit{par}}_\mathsf{T}\leftarrow \mathsf{T}.\mathsf{{Setup}}({ Gr})$ the following hold:

• Verifiability: For every $n, n'\in \mathcal {N}$, after computing

  • $({ {sk}}, { {pk}}) \leftarrow \mathsf{T}.\mathsf{{KeyGen}}$; $({ {sk}}^\prime , { {pk}}^\prime ) \leftarrow \mathsf{T}.\mathsf{{KeyGen}}$

  • $({ sn}, X)\leftarrow \mathsf{T}.\mathsf{{SGen}}({ {sk}}, n)$ or $({ sn}, X)\leftarrow \mathsf{T}.\mathsf{{SGen}}_\mathrm{init} ({ {sk}}, n)$

  • $({ sn}^{\prime }, { sn-pf}^\prime ) \leftarrow \mathsf{T}.\mathsf{{SGen}}( { {sk}}^\prime , n^\prime )$

  • $({ tag}, { t-pf})\leftarrow \mathsf{T}.\mathsf{{TGen}}({ {sk}}, n, { sn}^\prime )$

  we have $\mathsf{T}.\mathsf{{SVfy}}_\mathrm{all}({ {pk}}, { sn}, X)=\mathsf{T}.\mathsf{{TVfy}}({ {pk}}, { sn}, { sn}^\prime , { tag}, { t-pf})=1$.

• SN-identifiability: For all tag public keys ${ {pk}}_1$ and ${ {pk}}_2$, all serial numbers ${ sn}$ and all $X_1$ and $X_2$, which can be messages in $\mathcal {M}$ or SN proofs, if

  $$\begin{aligned} \mathsf{T}.\mathsf{{SVfy}}_\mathrm{all}({ {pk}}_1, { sn}, X_1)= \mathsf{T}.\mathsf{{SVfy}}_\mathrm{all}({ {pk}}_2, { sn}, X_2) = 1 \end{aligned}$$

  then ${ {pk}}_1={ {pk}}_2$.

• Bootability: There do not exist an SN message $M$, serial numbers ${ sn}_1\ne { sn}_2$ and tag keys (not necessarily distinct) ${ {pk}}_1, { {pk}}_2$ such that:

  $$\mathsf{T}.\mathsf{{SVfy}}_\mathrm{init} ({ {pk}}_1, { sn}_1, M)= \mathsf{T}.\mathsf{{SVfy}}_\mathrm{init} ({ {pk}}_2, { sn}_2, M)= 1.$$

• 2-show extractability: Let ${ {pk}}_0$, ${ {pk}}_1$ and ${ {pk}}_2$ be tag public keys, ${ sn}_0$, ${ sn}_1$ and ${ sn}_2$ be serial numbers, $X_0$ be either an SN proof or a message in $\mathcal {M}$, and ${ sn-pf}_1$ and ${ sn-pf}_2$ be SN proofs. Let ${ tag}_1$ and ${ tag}_2$ be tags, and ${ t-pf}_1$ and ${ t-pf}_2$ be tag proofs, and let $\mathcal {L}$ be a set of tag public keys with ${ {pk}}_0 \in \mathcal {L}$. If

  $$\begin{aligned} \mathsf{T}.\mathsf{{SVfy}}_\mathrm{all}\big ({ {pk}}_0, { sn}_0, X_0\big ) = 1 \\ \mathsf{T}.\mathsf{{SVfy}}\big ({ {pk}}_1, { sn}_1, { sn-pf}_1\big )= \mathsf{T}.\mathsf{{SVfy}}\big ({ {pk}}_2, { sn}_2, { sn-pf}_2\big ) = 1 \\ \mathsf{T}.\mathsf{{TVfy}}\big ({ {pk}}_1, { sn}_0, { sn}_1, { tag}_1, { t-pf}_1\big ) = \mathsf{T}.\mathsf{{TVfy}}\big ({ {pk}}_2, { sn}_0, { sn}_2, { tag}_2, { t-pf}_2\big ) = 1 \end{aligned}$$

  and ${ sn}_1 \ne { sn}_2$ then $\mathsf{T}.{\mathsf{Detect}}({ sn}_1,{ sn}_2, { tag}_1, { tag}_2, \mathcal {L})$ extracts $({ {pk}}_0, \varPi )$ efficiently and we have $\mathsf{T}.\mathsf{{VfyGuilt}}({ {pk}}_0, \varPi )=1$.

• $\mathcal {N}$ -injectivity: For any secret key ${ {sk}}$, the function $\mathsf{T}.\mathsf{{SGen}}({ {sk}}, \cdot )$ is injective.

Security Properties

• Exculpability: This notion formalizes soundness of double-spending proofs, in that no honestly behaving user can be accused. Let ${\textit{par}}_\mathsf{T}\leftarrow \mathsf{T}.\mathsf{{Setup}}$ and $({ {sk}}, { {pk}})\leftarrow \mathsf{T}.\mathsf{{KeyGen}}({\textit{par}}_\mathsf{T})$. Then we require that for a PPT adversary $\mathcal {A}$ that is given ${ {pk}}$ and can obtain SNs and tags for receiver SNs of its choice, both produced with ${ {sk}}$ (but no two tags for the same sender SN), is computationally hard to return a proof $\varPi$ with $\mathsf{T}.\mathsf{{VfyGuilt}}({ {pk}}, \varPi )=1$. Formally, $\mathcal {A}$ gets access to oracles $O_1({ {sk}})$ and $O_2({ {sk}}, \cdot , \cdot )$ defined in Fig. 7.

• Tag anonymity: Our anonymity notions for transferable e-cash should hold even against a malicious bank that gets to see the serial numbers and double-spending tags for deposited coins and the secret keys of the users. We require thus that as long as the nonce $n$ is random and only used once, serial numbers and tags reveal nothing about the user-specific values, such as ${ {sk}}$ and ${ {pk}}$, that were used to generate them. The game is given in Fig. 7.

Definition 6 (Tag anonymity)

A double-spending tag scheme is anonymous if $\Pr [\mathbf{Expt}^{\mathtt{tag-anon}}_{\mathcal {A}, 1} (\lambda ) \!=\!1]-\Pr [\mathbf{Expt}^{\mathtt{tag-anon}}_{\mathcal {A}, 0} (\lambda ) \!=\!1]$ is negligible in $\lambda$ for any PPT $\mathcal {A}$.

5 Our Transferable E-Cash Construction

5.1 Overview

The bank validates new users in the system and creates money, and digital signatures can be used for both purposes: when a new user joins, the bank signs her public key, which serves as proof of being registered; during a coin issuing, the bank signs a message $M_{ sn}$ that is associated to the initial serial-number (SN) component ${ sn}_0$ of a coin (chosen by the user withdrawing the coin), and this signature makes the coin unforgeable.

After a coin has been transferred k times, its core consists of a list of SNs ${ sn}_0, { sn}_1, \dots , { sn}_k$, together with a list of tags ${ tag}_1, \dots , { tag}_k$ (for a freshly withdrawn coin, we have $k=0$). When a user spends such a coin, the receiver generates a fresh SN component ${ sn}_{k+1}$, for which the spender must generate a tag ${ tag}_{k+1}$, which is also associated with her public key and the last serial number ${ sn}_k$ (which she generated when she received the coin.)

These tags allow the bank to identify the cheater in case of double-spending, while they preserve honest users’ anonymity, also towards the bank. A coin moreover contains the users’ public key w.r.t. which the tags were created, as well as certificates from the bank on them. To provide anonymity, all these components are not given in the clear, but as a zero-knowledge proof of knowledge. As we use a commit-and-prove proof system, a coin contains commitments to its serial number, its tags, the user public keys and their certificates and proofs that ensure all of them are consistent.

Recall that a coin also includes a signature by the bank on (a message related to) the initial SN component. To achieve anonymity towards the bank (coin anonymity), the bank must sign this message blindly, which is achieved by using the $\mathsf{{SigCm}}$ functionality: the user sends a commitment to the serial number, and the bank computes a committed signature on the committed value.

Finally, the bank needs to be able to detect whether a double-spending occurred and identify the user that committed it. One way would be to give the serial numbers and the tags (which protect the anonymity of honest users) in the clear. This would yield a scheme that satisfies coin anonymity and user anonymity (note that in these two notions the bank is adversarially controlled). In contrast, coin transparency, the most intricate anonymity notion, would not be achieved, since the owner of a coin could easily recognize it when she receives it again by looking at its serial number.

Coin transparency requires to hide the serial numbers (and the associated tags), and to use a randomizable proof system, since the appearance of a coin needs to change after every transfer. At the same time we need to provide the bank with access to them; we thus include encryptions, under the bank’s public key, in the coin. And we add proofs of consistency of the encrypted values. Now all of this must interoperate with the randomization of the coin, which is why we require rerandomizable encryption. Moreover, this has to be tied into the machinery of updating the proofs, which is necessary every time the ciphertexts and the commitments contained in a coin are refreshed.

5.2 Technical Description

Primitives Used. The basis of our transferable e-cash scheme is a randomizable extractable NIZK commit-and-prove scheme $\mathsf{C}$ to which we add compatible schemes: an $\mathcal {M}$-structure-preserving signature scheme $\mathsf{S}$ that admits an $\mathcal {M}$-commuting signature add-on $\mathsf{{SigCm}}$, as well as a (standard) $\mathcal {M}'$-structure-preserving signature scheme $\mathsf{S}'$ (all defined in Sect. 4.2).

Our scheme moreover uses rerandomizable encryption (Sect. 4.3): a scheme $\mathsf{E}$, which only needs to be IACR-secure, and an RCCA-secure scheme $\mathsf{E}'$, which will only be used for a single ciphertext per coin. (One can instantiate $\mathsf{E}$ withmore efficient schemes.) Finally, we use a double-spending tag scheme $\mathsf{T}$ (Sect. 4.4). We require $\mathsf{E}$, $\mathsf{E}'$ and $\mathsf{T}$ to be compatible with the proof system $\mathsf{C}$, that is, the equations for $\mathsf{E}.\mathsf{{Verify}}$ and $\mathsf{E}'.\mathsf{{Verify}}$, as well as $\mathsf{T}.\mathsf{{SVfy}}$, $\mathsf{T}.\mathsf{{SVfy}}_\mathrm{init}$ and $\mathsf{T}.\mathsf{{TVfy}}$, are all in the set $\mathcal {E}$ of equations supported by $\mathsf{C}$.

Auxiliary Functions. To simplify the description of our scheme, we first define several auxiliary functions. We let $\mathsf{{Rand}}$ denote an algorithm that randomizes a given tuple of commitments and ciphertext, as well as proofs for them (and adapts the proofs to the randomizations) by internally running $\mathsf{C}.\mathsf{{RdCm}}$, $\mathsf{E}.\mathsf{{ReRand}}$, $\mathsf{C}.\mathsf{{AdptPrf}}$ and $\mathsf{E}.\mathsf{{AdptPrf}}$ with the same randomness.

Below, we define $\mathsf{C}.\mathsf{{Prv}}_{\mathrm{sn}, \mathrm{init}}$ that produces a proof that a committed initial serial number ${ sn}$ was correctly generated w.r.t. a committed key ${ {pk}}_\mathsf{T}$ and a committed message M (given the randomness $\rho _{ {pk}}$, $\rho _{ sn}$ and $\rho _M$ used for the commitments). We also define $\mathsf{C}.\mathsf{{Verify}}_{\mathrm{sn}, \mathrm{init}}$ that verifies such proofs. $\mathsf{C}.\mathsf{{Prv}}_\text {sn}$ and $\mathsf{C}.\mathsf{{Verify}}_\text {sn}$ do the same for non-initial serial numbers (for which there are no messages, but which require a proof of well-formedness instead).

• $\mathsf{C}.\mathsf{{Prv}}_{\mathrm{sn}, \mathrm{init}} ({ {ck}}, { {pk}}_\mathsf{T}, { sn}, M, \rho _{{ {pk}}}, \rho _{ sn}, \rho _{M})$:

  • Return $\pi \leftarrow \mathsf{C}.\mathsf{{Prv}}\big ({ {ck}}, \mathsf{T}.\mathsf{{SVfy}}_\mathrm{init} (\cdot , \cdot , \cdot ) = 1, ({ {pk}}_\mathsf{T}, \rho _{{ {pk}}}), ({ sn}, \rho _{ sn}), (M, \rho _{M})\big )$

• $\mathsf{C}.\mathsf{{Verify}}_{\mathrm{sn}, \mathrm{init}}({ {ck}}, c_{ {pk}}, c_{ sn}, c_M, \pi _{ sn})$:

  • Return $\mathsf{C}.\mathsf{{Verify}}({ {ck}}, \mathsf{T}.\mathsf{{SVfy}}_\mathrm{init} (\cdot , \cdot , \cdot )=1, c_{{ {pk}}}, c_{ sn}, c_M, \pi _{ sn})$

• $\mathsf{C}.\mathsf{{Prv}}_\text {sn} ({ {ck}}, { {pk}}_\mathsf{T}, { sn}, { sn-pf}, \rho _{{ {pk}}}, \rho _{ sn}, \rho _{{ sn-pf}})$:

  • $\pi \leftarrow \mathsf{C}.\mathsf{{Prv}}\big ({ {ck}}, \mathsf{T}.\mathsf{{SVfy}}(\cdot , \cdot , \cdot ) = 1, ({ {pk}}_\mathsf{T}, \rho _{{ {pk}}}), ({ sn}, \rho _{ sn}), ({ sn-pf}, \rho _{{ sn-pf}})\big )$

  • Return $(\pi , \mathsf{C}.\mathsf{{Cm}}({ {ck}}, { sn-pf}, \rho _{{ sn-pf}}))$

• $\mathsf{C}.\mathsf{{Verify}}_\text {sn}({ {ck}}, c_{ {pk}}, c_{ sn}, \tilde{\pi }_{ sn}=(\pi _{ sn}, c_{{ sn-pf}}))$:

  • Return $\mathsf{C}.\mathsf{{Verify}}({ {ck}}, \mathsf{T}.\mathsf{{SVfy}}(\cdot , \cdot , \cdot )=1, c_{{ {pk}}}, c_{ sn}, c_{{ sn-pf}}, \pi _{ sn})$

$\mathsf{C}.\mathsf{{Prv}}_{\mathrm{tag}}$ produces a proof that a committed ${ tag}$ was correctly generated w.r.t. committed serial numbers ${ sn}$ and ${ sn}'$; and $\mathsf{C}.\mathsf{{Verify}}_{\mathrm{tag}}$ verifies such proofs.

• $\mathsf{C}.\mathsf{{Prv}}_{\mathrm{tag}} ({ {ck}}, { {pk}}_\mathsf{T}, { sn}, { sn}^{\prime }, { tag}, \rho _{{ {pk}}}, \rho _{ sn}, \rho ^{\prime }_{ sn}, \rho _{ tag}, { t-pf}, \rho _{{ t-pf}})$

  • $\pi \leftarrow \mathsf{C}.\mathsf{{Prv}}\big ({ {ck}}, \mathsf{T}.\mathsf{{TVfy}}(\cdot , \cdot , \cdot , \cdot , \cdot )=1,({ {pk}}_\mathsf{T}, \rho _{{ {pk}}}), ({ sn}, \rho _{ sn}), ({ sn}^{\prime }, \rho ^{\prime }_{ sn}),$ $({ tag}, \rho _{ tag}), ({ t-pf}, \rho _{{ t-pf}})\big )$

  • $\text {Return }(\pi , \mathsf{C}.\mathsf{{Cm}}({ {ck}}, { t-pf}, \rho _{{ t-pf}}))$

• $\mathsf{C}.\mathsf{{Verify}}_{\mathrm{tag}} ({ {ck}}, c_{ {pk}}, c_{ sn}, c^{\prime }_{ sn}, c_{ tag}, \pi _{ tag}=(\pi , c_{{ t-pf}}))$:

  • Return $\mathsf{C}.\mathsf{{Verify}}({ {ck}}, \mathsf{T}.\mathsf{{TVfy}}(\cdot , \cdot , \cdot , \cdot )=1, c_{{ {pk}}}, c_{ sn}, c^{\prime }_{ sn}, c_{ tag}, c_{{ t-pf}}, \pi )$

$\mathsf{C}.\mathsf{E}.\mathsf{{Prv}}_\mathrm{enc}$ produces a proof that a ciphertext $\tilde{c}$ of M and $\mathsf{C}.\mathsf{{Cm}}({ {ck}}, M, \rho _M)$ contain the same message; $\mathsf{C}.\mathsf{E}.\mathsf{{Verify}}_\mathrm{enc}$ verifies such proofs. (Note that the output of $\mathsf{C}.\mathsf{E}.\mathsf{{Prv}}_\mathrm{enc}$ is the same $\pi$ as in the input of $\mathsf{E}.\mathsf{{AdptPrf}}$; moreover, since $\rho _\nu$ is not used outside of $\mathsf{C}.\mathsf{E}.\mathsf{{Prv}}_\mathrm{enc}$, it can be sampled locally.)

• $\mathsf{C}.\mathsf{E}.\mathsf{{Prv}}_\mathrm{enc}({ {ck}}, { {ek}}, M, \rho _M, \nu _M, \tilde{c})$:

  • $\rho _\nu \xleftarrow {_\$} \mathcal {R}$; $\pi \leftarrow \mathsf{C}.\mathsf{{Prv}}({ {ck}}, \mathsf{E}.\mathsf{{Verify}}$ $({ {ek}}, \cdot , \cdot , \tilde{c}) = 1, (M, \rho _M), (\nu _M, \rho _\nu ))$

  • Return $(\pi , \mathsf{C}.\mathsf{{Cm}}({ {ck}}, \nu _M, \rho _\nu ))$

• $\mathsf{C}.\mathsf{E}.\mathsf{{Verify}}_\mathrm{enc}({ {ck}}, { {ek}}, c_M, \tilde{c}_M, \tilde{\pi }_\mathrm{eq}=(\pi _\mathrm{eq}, c_\nu ))$:

  • Return $\mathsf{C}.\mathsf{{Verify}}({ {ck}}, \mathsf{E}.\mathsf{{Verify}}({ {ek}}, \cdot , \cdot , \tilde{c}_M)=1, c_M, c_\nu , \pi _\mathrm{eq})$

Components of the Coin. There are two types of components, the initial components , and the standard components . The first is of the form

(1)

where the “c-values” are commitments to the withdrawer’s key ${ {pk}}$, her certificate ${ {cert}}$, the initial serial number ${ sn}$ and the related message M, the bank’s signature $\sigma$ on M; and $\tilde{c}_{ sn}$ is an encryption of ${ sn}$. Moreover, $\pi _{ {cert}}$ and $\pi _{ sn}$ prove validity of ${ {cert}}$ and ${ sn}$, and $\tilde{\pi }_{ sn}$ proves that $c_{ sn}$ and $\tilde{c}_{ sn}$ contain the same value. We use “empty values” $\varepsilon$ for padding so that both coin-component types have the same format. Validity of an initial component is verified w.r.t. an encryption key for $\mathsf{E}'$ and two signature verification keys for $\mathsf{S}$ and $\mathsf{S}'$:

• : Return 1 iff the following hold:  //  as in (1)

  • $\mathsf{C}.\mathsf{{Verify}}\big ({ {ck}}, \mathsf{S}'.\mathsf{{Verify}}({ {vk}}',\cdot , \cdot ) = 1, c^0_{{ {pk}}}, c^0_{ {cert}}, \pi ^0_{ {cert}}\big )$

  • $\mathsf{C}.\mathsf{{Verify}}\big ({ {ck}}, \mathsf{S}.\mathsf{{Verify}}({ {vk}}, \cdot , \cdot ) = 1, c_M, c^0_\sigma , \pi ^0_\sigma \big )$

  • $\mathsf{C}.\mathsf{{Verify}}_{\mathrm{sn}, \mathrm{init}} \big ({ {ck}}, c^0_{{ {pk}}}, c^0_{ sn}, c_M, \pi ^0_{ sn}\big )$ $\wedge$ $\mathsf{C}.\mathsf{E}'.\mathsf{{Verify}}_\mathrm{enc}\big ({ {ck}}, { {ek}}', c^0_{ sn}, \tilde{c}^0_{ sn}, \tilde{\pi }^0_{ sn}\big )$

Standard components of a coin are of the form

(2)

and instead of M and the bank’s signature they contain a commitment $c_{ tag}$ and an encryption $\tilde{c}_{ tag}$ of the tag produced by the spender (and a proof $\pi _{ tag}$ of validity and $\tilde{\pi }_{ tag}$ proving that the values in $c_{ tag}$ and $\tilde{c}_{ tag}$ are equal). A coin is verified by checking the validity and consistency of each two consecutive components. If the first is an initial component then the values and are $\varepsilon$; if it is a standard component then and are $\varepsilon$.

• : //  as in (2) Return 1 iff the following hold:

  • $\mathsf{C}.\mathsf{{Verify}}\big ({ {ck}}, \mathsf{S}'.\mathsf{{Verify}}({ {vk}}', \cdot , \cdot ) = 1, c^{i}_{{ {pk}}}, c^{i}_{ {cert}}, \pi ^{i}_{ {cert}}\big )$

  • $\mathsf{C}.\mathsf{{Verify}}_\text {sn} \big ({ {ck}}, c^{i}_{{ {pk}}}, c^{i}_{ sn}, \pi ^{i}_{ sn}\big )\ \wedge \mathsf{C}.\mathsf{{Verify}}_{\mathrm{tag}} \big ({ {ck}}, c^{{i-1}}_{{ {pk}}}, c^{i-1}_{ sn}, c^{i}_{ sn}, c^{i}_{ tag}, \pi ^{i}_{{ tag}} \big )$

  • $\mathsf{C}.\mathsf{E}.\mathsf{{Verify}}_\mathrm{enc}\big ({ {ck}}, { {ek}}, c^{i}_{ sn}, \tilde{c}^{i}_{ sn}, \tilde{\pi }^{i}_{ sn}\big ) \ \wedge \ \mathsf{C}.\mathsf{E}.\mathsf{{Verify}}_\mathrm{enc}\big ({ {ck}}, { {ek}}, c^{i}_{ tag}, \tilde{c}^{i}_{ tag}, \tilde{\pi }^{i}_{ tag}\big )$

Our Scheme. We now formally define our transferable e-cash scheme.

:

• ${ Gr}\leftarrow \mathsf{{GrGen}}(1^\lambda )$

• ${\textit{par}}_\mathsf{S}\leftarrow \mathsf{S}.\mathsf{{Setup}}({ Gr})$ ; ${\textit{par}}_{\mathsf{S}'} \leftarrow \mathsf{S}'.\mathsf{{Setup}}({ Gr})$

• ${\textit{par}}_\mathsf{T}\leftarrow \mathsf{T}.\mathsf{{Setup}}({ Gr})$ ; ${ {ck}}\leftarrow \mathsf{C}.\mathsf{{Setup}}({ Gr})$

• Return ${\textit{par}}= (1^\lambda , { Gr}, {\textit{par}}_\mathsf{S}, {\textit{par}}_{\mathsf{S}'}, {\textit{par}}_\mathsf{T}, { {ck}})$

Recall that ${\textit{par}}$, parsed as above, is an implicit input to all other algorithms.

:

• $({ {sk}}, { {vk}}) \leftarrow \mathsf{S}.\mathsf{{KeyGen}}({\textit{par}}_\mathsf{S})$ ; $({ {sk}}', { {vk}}') \leftarrow \mathsf{S}'.\mathsf{{KeyGen}}({\textit{par}}_{\mathsf{S}'})$

• $({ {ek}}', { {dk}}') \leftarrow \mathsf{E}'.\mathsf{{KeyGen}}({ Gr})$ ; $({ {ek}}, { {dk}}) \leftarrow \mathsf{E}.\mathsf{{KeyGen}}({ Gr})$

• $({ {sk}}_\mathsf{T}, { {pk}}_\mathsf{T}) \leftarrow \mathsf{T}.\mathsf{{KeyGen}}({\textit{par}}_\mathsf{T})$             //  $({ {sk}}_\mathsf{T}, { {pk}}_\mathsf{T},{ {cert}})$ let the bank act...

• ${ {cert}}\leftarrow \mathsf{S}'.\mathsf{{Sign}}({ {sk}}', { {pk}}_\mathsf{T})$                    //  dots as $\mathcal {U}'$ in $\mathsf{{Spend}}$ during deposit

• Return $\big ({ {sk}}_{\mathcal {W}} = ({ {sk}}, { {sk}}'), { {sk}}_\mathcal {CK}=({ {dk}}', { {dk}}),$ ${ {sk}}_\mathcal {D}= ({ {cert}},{ {pk}}_\mathsf{T}, { {sk}}_\mathsf{T}), { {pk}}_\mathcal {B}= ({ {ek}}', { {ek}}, { {vk}}, { {vk}}')\big )$

:

• $\mathcal {U}$: $({ {sk}}_\mathsf{T}, { {pk}}_\mathsf{T}) \leftarrow \mathsf{T}.\mathsf{{KeyGen}}({\textit{par}}_\mathsf{T})$ ; send ${ {pk}}_\mathsf{T}$ to $\mathcal {B}$

• $\mathcal {B}$: ${ {cert}}_\mathcal {U}\leftarrow \mathsf{S}'.\mathsf{{Sign}}({ {sk}}', { {pk}}_\mathsf{T})$ ; send ${ {cert}}_\mathcal {U}$ to $\mathcal {U}$ ; output ${ {pk}}_\mathsf{T}$

• $\mathcal {U}$: If $\mathsf{S}'.\mathsf{{Verify}}({ {vk}}', { {pk}}_\mathsf{T}, { {cert}}_\mathcal {U}) = 1$, output ${ {sk}}_\mathcal {U}\leftarrow ({ {cert}}_\mathcal {U},{ {pk}}_\mathsf{T}, { {sk}}_\mathsf{T})$; else $\bot$

:

$\mathcal {U}$::

−:

$n\xleftarrow {_\$} \mathcal {N}$ ; $\rho _{{ {pk}}}, \rho _{ {cert}}, \rho _{ sn}, \rho _M \xleftarrow {_\$} \mathcal {R}$

−:

$({ sn}, M_{ sn}) \leftarrow \mathsf{T}.\mathsf{{SGen}}_{\mathrm{init}} ({ {sk}}_\mathsf{T}, n)$

−:

$c_{{ {pk}}} \leftarrow \mathsf{C}.\mathsf{{Cm}}({ {ck}}, { {pk}}_\mathsf{T}, \rho _{ {pk}})$

−:

$c_{ {cert}}\leftarrow \mathsf{C}.\mathsf{{Cm}}({ {ck}}, { {cert}}_\mathcal {U}, \rho _{ {cert}})$

−:

$c_{ sn}\leftarrow \mathsf{C}.\mathsf{{Cm}}({ {ck}}, { sn}, \rho _{ sn})$

−:

$c_M \leftarrow \mathsf{C}.\mathsf{{Cm}}({ {ck}}, M_{ sn}, \rho _M)$

−:

$\pi _{ {cert}}\leftarrow$ $\mathsf{C}.\mathsf{{Prv}}({ {ck}}, \mathsf{S}'.\mathsf{{Verify}}({ {vk}}', \cdot , \cdot ) = 1, ({ {pk}}_\mathsf{T}, \rho _{{ {pk}}}), ({ {cert}}_\mathcal {U}, \rho _{ {cert}}))$

−:

$\pi _{{ sn}}\leftarrow$ $\mathsf{C}.\mathsf{{Prv}}_{\text {sn}, \text {init}} ({ {ck}}, { {pk}}_\mathsf{T}, { sn}, M_{ sn}, \rho _{{ {pk}}}, \rho _{ sn}, \rho _M)$

−:

Send $(c_{{ {pk}}}, c_{ {cert}}, \pi _{{ {cert}}}, c_{ sn}, c_M, \pi _{{ sn}})$ to $\mathcal {B}$

$\mathcal {B}$::

−:

if $\mathsf{C}.\mathsf{{Verify}}({ {ck}}, \mathsf{S}'.\mathsf{{Verify}}({ {vk}}', \cdot , \cdot )=1, c_{{ {pk}}}, c_{ {cert}}, \pi _{{ {cert}}})=0$ or       $\mathsf{C}.\mathsf{{Verify}}_{\mathrm{sn}, \mathrm{init}} ({ {ck}}, c_{{ {pk}}}, c_{ sn}, c_M, \pi _{ sn})=0$ then abort and output $\bot$

−:

$(c_\sigma , \pi _\sigma ) \leftarrow \mathsf{{SigCm}}({ {ck}}, { {sk}}, c_M)$ ; send $(c_\sigma , \pi _\sigma )$ to $\mathcal {U}^\prime$ ; return ok

$\mathcal {U}$::

−:

if then abort and output $\bot$

−:

;

−:

−:

//since $\tilde{\pi }_{ sn}$ contains a commitment,

we also sample randomness for it

−:

−:

Output

:

::

−:

;

−:

−:

;

−:

;

−:

−:

−:

−:

−:

Send to $\mathcal {U}$

$\mathcal {U}$::

−:

Parse ${ {c}}$ as $\big (c^0, \big (c^j\!=\! ( c^j_{{ {pk}}}, c^j_{ {cert}}, \pi ^j_{ {cert}}, c^j_{ sn}, \pi ^j_{ sn}, c^j_{ tag}, \pi ^j_{{ tag}},$ $\tilde{c}^j_{ sn}, \tilde{c}^j_{ tag},\tilde{\pi }^j_{ sn}, \tilde{\pi }^j_{ tag}) \big )^i_{j=1}, n, { sn}, \rho _{ sn}, \rho _{ {pk}}\big )$ // i could be 0

−:

$\rho _{ tag}, \nu _{ tag}, \rho _{{ t-pf}}\xleftarrow {_\$}\mathcal {R}$

−:

$({ tag}, { t-pf}) \leftarrow \mathsf{T}.\mathsf{{TGen}}({\textit{par}}_\mathsf{T}, { {sk}}_\mathsf{T}, n, { sn}^{\prime })$

−:

$c_{ tag}\leftarrow \mathsf{C}.\mathsf{{Cm}}({ {ck}}, { tag}, \rho _{ tag})$ ; $\tilde{c}_{ tag}\leftarrow \mathsf{E}.\mathsf{{Enc}}({ {ek}}, { tag}, \nu _{ tag})$

−:

$\pi _{{ tag}} \leftarrow \mathsf{C}.\mathsf{{Prv}}_{ tag}({ {ck}}, { {pk}}_\mathsf{T}, { sn}, { sn}^{\prime }, { tag}, { t-pf}, \rho _{ {pk}}, \rho _{ sn}, \rho ^{\prime }_{ sn}, \rho _{ tag}, \rho _{{ t-pf}})$

−:

$\tilde{\pi }_{ tag}\leftarrow \mathsf{C}.\mathsf{E}.\mathsf{{Prv}}_\mathrm{enc} ({ {ck}}, { {ek}}, { tag}, \rho _{ tag}, \nu _{ tag}, \tilde{c}_{ tag})$

−:

Send ${ {c}}^\prime =\big (c^0, (c^j)_{j=1}^i, c_{ tag}, \pi _{ tag}, \tilde{c}_{ tag}, \tilde{\pi }_{ tag}\big )$ to $\mathcal {U}^{\prime }$ ; output ok

$\mathcal {U}'$::

−:

If any of the following occur then abort and output $\bot$:

−:

$\mathsf{VER}_\mathrm{init} ({ {ek}}',{ {vk}},{ {vk}}', c^0)=0$

−:

$\mathsf{VER}_\text {std} ({ {ek}}, { {vk}}, { {vk}}', c^{j-1}, c^j)=0$, for some $j=1,\dots ,i$

−:

$\mathsf{C}.\mathsf{{Verify}}_{\mathrm{tag}}({ {ck}}, c^i_{{ {pk}}}, c^i_{{ sn}}, c_{ sn}^{\prime }, c_{ tag}, \pi _{{ tag}})=0$

−:

$\mathsf{C}.\mathsf{E}.\mathsf{{Verify}}_\mathrm{enc} ({ {ck}}, { {ek}}, c_{ tag}, \tilde{c}_{ tag}, \tilde{\pi }_{ tag})=0$

−:

pick uniform random

−:

−:

Output

:

• Parse ${ {c}}$ as $\big (c^0 = ( c^0_{{ {pk}}}, c^0_{ {cert}}, \pi ^0_{ {cert}}, c^0_{ sn}, \pi ^0_{ sn}, c^0_M, c_\sigma , \pi _\sigma , \tilde{c}^0_{ sn}, \tilde{\pi }^0_{ sn}),$ $(c^j = (c^j_{{ {pk}}},\ c^j_{ {cert}},\ \pi ^j_{ {cert}},\ c^j_{ sn},\, \pi ^j_{ sn},\, c^j_{ tag},\, \pi ^j_{{ tag}},\, \tilde{c}^j_{ sn},\, \tilde{\pi }^j_{ sn},\, \tilde{c}^j_{ tag},\, \tilde{\pi }^j_{ tag}))^i_{j=1},\, n,\, { sn}, \rho _{ sn}, \rho _{ {pk}}\big )$

• 
• 

• If for all // initial SN of checked coin... then return

  // ...different from those of deposited coins

• Else let j be minimal so that

• $({ {pk}}_\mathsf{T}, \varPi ) \leftarrow \mathsf{T}.{\mathsf{Detect}}\big ({{ sn}}_{j}, { sn}^{\prime }_{j}, {{ tag}}_{j}, { tag}^{\prime }_{j}, \mathcal {UL}\big )$

• Return $({ {pk}}_\mathsf{T}, \varPi )$

: Return $\mathsf{T}.\mathsf{{VfyGuilt}}({ {pk}}_\mathsf{T}, \varPi )$.

5.3 Security Analysis

Theorem 7

Our transferable e-cash scheme is perfectly sound.

Because a user verifies the validity of all components of a coin before accepting it, perfect soundness of our scheme is a direct consequence of the correctness properties of $\mathsf{S}$, $\mathsf{S}'$ and $\mathsf{C}$, as well as perfect soundness of $\mathsf{C}$ and verifiability of $\mathsf{T}$.

Detailed proofs of the following theorems are given in the full version [BFQ20]

Theorem 8

Let $\mathcal {N}$ be the nonce space and $\mathcal S$ be the space of signatures of scheme $\mathsf{S}$. Let $\mathcal {A}$ be an adversary that wins the unforgeability game with advantage and makes at most d calls to $\mathtt{BDepo}$. Suppose that $\mathsf{C}$ is perfectly sound and $(\mathcal {M}\cup \mathcal{S})$-extractable. Then there exist adversaries against the unforgeability of the signature schemes $\mathsf{S}$ and $\mathsf{S}'$ with advantages and , resp., such that

Assume that during the adversary’s deposits the bank never picks the same final nonce twice. (The probability that there is a collision is at most $d^2/|\mathcal {N}|$.) In this case, there are two ways for the adversary to win:

(1) $\mathsf{{CheckDS}}$ outputs $\bot$, or an invalid proof, or an unregistered user: Suppose that, during a $\mathtt{BDepo}$ call for a coin ${ {c}}$, $\mathsf{{CheckDS}}$ does not return a coin list. Recall that, by assumption, the final part (chosen by the bank at deposit) of the serial number of ${ {c}}$ is fresh. Since $\mathsf{{CheckDS}}$ runs T.Detect, by soundness of $\mathsf{C}$ and two-extractability of $\mathsf{T}$, this will output a pair $({ {pk}}, \varPi )$, such that $\mathsf{{VfyGuilt}}({ {pk}}, \varPi )=1$. Since a coin contains a commitment to a certificate for the used tag key (and proofs of validity), we can, again by soundness of $\mathsf{C}$, extract an $\mathsf{S}'$-signature on ${ {pk}}$. Now if ${ {pk}}$ is not in $\mathcal {UL}$, then it was never signed by the bank, and $\mathcal {A}$ has thus broken unforgeability of $\mathsf{S}'$.

(2) $q_W < |\mathcal {DCL}|$: If the adversary creates a valid coin that has not been withdrawn, then by soundness of $\mathsf{C}$, we can extract a signature by the bank on a new initial serial number and therefore break unforgeability of $\mathsf{S}$.

Theorem 9

Let $\mathcal {A}$ be an adversary that wins exculpability game with advantage and makes u calls to the oracle $\mathtt{URegist}$. Then there exist adversaries against mode-indistinguishability of $\mathsf{C}$ and tag-exculpability of $\mathsf{T}$ with advantages and , resp., such that

An incrimination proof in our e-cash scheme is simply an incrimination proof of the tag scheme $\mathsf{T}$. Thus, if the reduction correctly guesses the user u that will be wrongfully incriminated by $\mathcal {A}$ (which it can with probability 1/u), then we can construct an adversary against exculpability of $\mathsf{T}$. The term comes from the fact that we first need to switch $\mathsf{C}$ to hiding mode, so we can simulate $\pi _{ sn}$ and $\pi _{ tag}$ for the target user, since the oracles $O_1$ and $O_2$ in the game for tag exculpability (see Fig. 7) do not return ${ sn-pf}$ and ${ t-pf}$.

Theorem 10

Let $\mathcal {A}$ be an adversary that wins the coin anonymity game (c-an) with advantage and let k be an upper-bound on the number of users transferring the challenge coins. Then there exist adversaries against mode-indistinguishability of $\mathsf{C}$ and tag-anonymity of $\mathsf{T}$ with advantages and , resp., such that

Theorem 11

Let $\mathcal {A}$ be an adversary that wins the user anonymity game (u-an) with advantage and let k be a bound on the number of users transferring the challenge coin. Then there exist adversaries against mode-indistinguishability of $\mathsf{C}$ and tag-anonymity of $\mathsf{T}$ with advantages and , resp., such that

In the proof of both theorems, we first define a hybrid game in which the commitment key is switched to hiding mode (hence the loss , which occurs twice for $b=0$ and $b=1$). All commitments are then perfectly hiding (and proofs reveal nothing either) and the only information contained in a coin are the serial numbers and tags. They are encrypted, but the adversary, impersonating the bank, can decrypt them.

We then argue that, by tag anonymity of $\mathsf{T}$, the adversary cannot link a user to a pair $({ sn},{ tag})$, even when it knows the users’ secret keys. We define a sequence of $k+1$ hybrid games (as k transfers involve $k+1$ users); going through the user vector output by the adversary, we can switch, one by one, all users from the first two the second vector. Each switch can be detected by the adversary with probability at most . Note that the additional factor 2 for in game $\texttt {c-an}$ is due to the fact that there are two coins for which we switch users, whereas there is only one in game $\texttt {u-an}$.

Theorem 12

Let $\mathcal {A}$ be an adversary that wins the coin-transparency game ($\mathtt{c-tr}$) with advantage , let $\ell$ be the size of the two challenge coins, and k be an upper-bound on the number of users transferring the challenge coins. Then there exist adversaries against mode-indistinguishability of $\mathsf{C}$, tag-anonymity of $\mathsf{T}$, IACR-security of $\mathsf{E}$ and RCCA-security of $\mathsf{E}'$ with advantages , , and , resp., such that

The crucial difference to the previous anonymity theorems is that the bank is honest (which makes this strong notion possible). We therefore must rely on the security of the encryptions, for which the reduction thus does not know the decryption key. At the same time, the reduction must be able to detect double-spendings, when the adversary deposits coins. Since we use RCCA encryption, the reduction can do so by using its own decryption oracle.

As for c-an and u-an, the reduction first makes all commitments perfectly hiding and proofs perfectly simulatable (which loses twice). Since all ciphertexts in the challenge coin given to the adversary are randomized, the reduction can replace all of them, except the initial one, by IACR-security of $\mathsf{E}$. (Note that in the game these ciphertexts never need to be decrypted.) The factor $2\ell$ is due to the fact that there are at most $\ell$ encryptions of SN/tag pairs. Finally, replacing the initial ciphertext (the one that enables detection of double-spending) can be done by a reduction to RCCA-security of $\mathsf{E}'$: the oracle $\mathtt{Depo}'$ can be simulated by using the reduction’s own oracles $\mathsf{{Dec}}$ and $\mathsf{{GDec}}$ (depending on whether $\mathtt{Depo}'$ is called before or after the reduction receives the challenge ciphertext) in the RCCA-security game. Note that, when during a simulation of CheckDS, oracle GDec outputs replay, the reduction knows that a challenge coin was deposited, and uses this information to increase ctr.

6 Instantiation of the Building Blocks and Efficiency

The instantiations we use are all proven secure in the standard model under non-interactive hardness assumptions.

Commitments and Proofs. The commit-and-prove system $\mathsf{C}$ will be instantiated with the SXDH-based instantiation of Groth-Sahai proofs [GS08].

Theorem 13

([GS08]). The Groth-Sahai proof system, allowing to commit values from $\mathcal {V}:=\mathbb {Z}_p\, \cup \,\mathbb {G}\,\cup \,\hat{\mathbb {G}}$ is perfectly complete, perfectly sound and randomizable; it is $(\mathbb {G}\cup \hat{\mathbb {G}})$-extractable, mode-indistinguishable assuming SXDH, and perfectly hiding in hiding mode.

We note that moreover, all our proofs can be made zero-knowledge [GS08], and thus simulatable, because all pairing-product equations we use are homogeneous (i.e., the right-hand term is the neutral element). We have (efficient) extractability, as we only need to efficiently extract group elements from commitments (and no scalars) in our reductions. (Note that for information-theoretic arguments concerning soundness, $\mathsf{{Extr}}$ can also be inefficient.)

Signature Schemes. For efficiency and type-compatibility reasons, we use two different signature schemes. The first one, $\mathsf{S}$, must support the functionality $\mathsf{{SigCm}}$, which imposes a specific format of messages. The second scheme, $\mathsf{S}'$, is less restrictive, which allows for more efficient instantiations. While all our other components rely on standard assumptions, we instantiate $\mathsf{S}$ with a scheme that relies on a non-interactive q-type assumption defined in [AFG+10].

Theorem 14

The signature scheme from [AFG+10, Sect. 4] with message space $\mathcal {M}:=\{(g^m, \hat{g}^m)\,|\,m\in \mathbb {Z}_p\}$ is (strongly) unforgeable assuming q-ADHSDH and AWFCDH (see [BFQ20]), and it supports the $\mathsf{{SigCm}}$ functionality [Fuc11].

Theorem 15

The signature scheme from [AGHO11, Sect. 5] is structure-preserving with message space $\mathcal {M}':=\hat{\mathbb {G}}$ and (strongly) unforgeable assuming SXDH.

Randomizable Encryption Schemes. To instantiate the RCCA-secure scheme $\mathsf{E}'$ we follow the approach by Libert et al. [LPQ17]. Their construction is only for one group element, but by adapting the scheme, it can support encryption of a vector in $\mathbb {G}^n$ for arbitrary n. In our e-cash scheme, we need to encrypt a vector in $\mathbb {G}^2$, and since it is not clear whether more recent efficient schemes like [FFHR19] can be adapted to this, we give an explicit construction, which we detail in the full version [BFQ20].

Recall that the RCCA-secure scheme $\mathsf{E}'$ is only used to encrypt the initial part of the serial number; using a less efficient scheme thus has a minor impact on the efficiency of our scheme. From all other ciphertexts contained in a coin (which are under scheme $\mathsf{E}$) we only require IACR security, which standard ElGamal encryption satisfies under DDH(!). Thus, we instantiate $\mathsf{E}$ with ElGamal vector encryption. (Note that our instantiation of $\mathsf{E}'$ is also built on top of ElGamal). We prove the following in the full version [BFQ20].

Theorem 16

Assuming SXDH, our randomizable encryption scheme [BFQ20] is RCCA-secure and ElGamal vector encryption is IACR-secure.

Double-Spending Tags. We will use a scheme that builds on the one given in [BCFK15]. We have optimized the size of the tags and made explicit all the functionalities not given previously. We defer this to the full version [BFQ20].

Efficiency Analysis

We conclude by summarizing the sizes of objects in our scheme in the table below and refer to the full version [BFQ20] for the details of our analysis.

For a group $G \in \{\mathbb {G}, \hat{\mathbb {G}}, \mathbb {Z}_p\}$, let |G| denote the size of an element of G. Let ${ {c}}_\text {btsrap}$ denote the coin output by $\mathcal {U}$ at the end of the $\mathsf{{Withdraw}}$ protocol (which corresponds to ${ {c}}_\text {init}$ plus secret values, like n, $\rho _{ sn}$, etc., to be used when transferring the coin), and let ${ {c}}_\text {std}$ denote one (non-initial) component of the coin. After k transfers the size of a coin is $|{ {c}}_\text {btsrap}|+ k|{ {c}}_\text {std}|$.