# Divisible E-Cash in the Standard Model

Malika Izabachène, Benoît Libert

► To cite this version:

Malika Izabachène, Benoît Libert. Divisible E-Cash in the Standard Model. Pairing-Based Cryptography - Pairing 2012 - 5th International Conference, May 2012, Cologne, France. hal-05508299

HAL Id: hal-05508299

https://hal.science/hal-05508299v1

Submitted on 13 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Divisible E-Cash in the Standard Model

Malika Izabachène¹ and Benoît Libert² *

¹ Ecole Normale Supérieure de Cachan/CNRS/INRIA (France)

² Université catholique de Louvain (Belgium)

**Abstract.** Off-line e-cash systems are the digital analogue of regular cash. One of the main desirable properties is anonymity: spending a coin should not reveal the identity of the debtor and, at the same time, users should not be able to double-spend coins without being detected. Compact e-cash systems make it possible to store a wallet of $O(2^L)$ coins using $O(L + \lambda)$ bits, where $\lambda$ is the security parameter. They are called divisible whenever the user has the flexibility of spending an amount of $2^\ell$, for some $\ell \le L$, more efficiently than by repeatedly spending individual coins. This paper presents the first construction of divisible e-cash in the standard model (i.e., without the random oracle heuristic). The scheme allows a user to obtain a wallet of $2^L$ coins by running a withdrawal protocol with the bank. Our construction is built on the traditional binary tree approach, where the wallet is organized in such a way that the monetary value of a coin depends on how deep the coin is in the tree.

**Keywords.** E-Cash, provable security, anonymity, non-interactive proofs.

## 1 Introduction

Introduced by Chaum [22, 23] and developed in [24, 20, 25, 40, 29], electronic cash is the digital equivalent of regular money. It allows a user to withdraw a wallet of electronic coins from a bank so that e-coins can be spent to merchants who can then deposit them back to the bank.

The withdrawal, spending and deposit protocols should be designed in such a way that it is infeasible to determine when a particular coin was spent: even if the bank colludes with the merchant, after the deposit protocol, it should be unable to link a received coin to a particular withdrawal protocol. At the same time, users should not be able to covertly double-spend coins: should a cheating user attempt to spend a given coin twice, his identity must be exposed and evidence of his misbehavior must be given. Ideally, dishonest users should be identified without the help of a trusted third party and, as in the off-line scenario [24], the bank should preferably not intervene in the spending protocol between the user and the merchant.

<footnote>* This author acknowledges the Belgian Fund for Scientific Research for his “Collaborateur scientifique” fellowship.</footnote>
RELATED WORK. In 2005, Camenisch, Hohenberger and Lysyanskaya [10] described a *compact* e-cash system allowing a user to withdraw a wallet of $2^L$ coins with a computational cost of $O(L+\lambda)$, where $\lambda$ is the security parameter, in the spending and withdrawal protocols. Using appropriate choices [27, 28] of verifiable random functions [34], they also showed how to store a wallet using only $O(L+\lambda)$ bits and additionally described a coin tracing mechanism allowing to trace all the coins of a misbehaving user. The protocol of Camenisch et al. was subsequently extended into e-cash systems with coin endorsement [13] or transferability properties [15, 16].

The aforementioned e-cash realizations all appeal to the random oracle model [6] – at least if the amount of interaction is to be minimized in the spending protocol – which is known not to accurately reflect world (see [19] for instance). To fill this gap, Belenkiy, Chase, Kohlweiss and Lysyanskaya [5] described a compact e-cash system with non-interactive spending in the standard model. Their construction cleverly combines multi-block extensions of P-signatures [3] and simulatable verifiable random functions [21] with the Groth-Sahai non-interactive proof systems [31]. Independently, Fuchsbauer, Pointcheval and Vergnaud also used Groth-Sahai proofs [30] to build a transferable fair (i.e., involving a semi-trusted third party) e-cash system in the standard model. More recently, Blazy et al. [7] gave a similar construction with stronger anonymity properties.

DIVISIBLE E-CASH. In the constructions of [10], users have to run the spending protocol $N$ times if the amount to be paid is the equivalent of $N$ coins. One possible improvement is to use wallets containing coins of distinct monetary values as in [17]. Unfortunately, this approach does not allow to split individual coins of large value. This problem is addressed by divisible e-cash systems where users can withdraw a coin of value $2^L$ that can be spent in several times by dividing the value of that coin. Divisible e-cash makes it possible for users to spend the equivalent of $N = 2^\ell$ (with $0 \le \ell \le L$) coins more efficiently than by iterating the spending protocol $2^\ell$ times. Constructions of divisible e-cash were proposed in the 90's [36, 38, 26, 37, 20]. Okamoto provided a practical realization [37] that was subsequently improved in [20]. Unfortunately, these schemes are not fully unlinkable since several spends of a given divisible coin can be linked. To address this concern, Nakanishi and Sugiyama [35] described an unlinkable divisible e-cash system but their scheme requires a trusted third party to uncover the identity of double-spenders. In addition, by colluding with the bank, the merchant can obtain information on which part of the divisible coin the user is spending.

In 2007, Canard and Gouget [14] designed the first divisible e-cash system with full anonymity (and unlinkability) where misbehaving users can be identified without involving a trusted third party. Later on, Au et al. [1] came up with a more efficient implementation at the expense of substantially weaker security guarantees. More recently, Canard and Gouget [18] showed how to improve upon the efficiency of their original proposal without sacrificing the original security.

OUR CONTRIBUTION. Prior implementations of truly anonymous divisible e-cash all require the random oracle idealization in their security analysis. In this
paper, we describe the first anonymous divisible e-cash in the standard model. Like the scheme of Belenkiy et al. [5], our construction relies on the Groth-Sahai non-interactive proof systems [31].

Our scheme is less efficient than the fastest random-oracle-based scheme [18] in several metrics. While the spending phase has constant (i.e., independent of the value $2^L$ of the wallet) communication complexity in [18], our spending protocol requires users to transmit $O(L)$ group elements to the merchant in the worst case. On the other hand, due to the use of bounded accumulators [2], the bank has to set up a public key of size $O(2^L)$ in [18]$^3$ whereas we only need the bank to have a key of size $O(1)$.

Achieving divisibility without resorting to random oracles requires to solve several technical issues. The solutions of Canard and Gouget [14, 18] associate each wallet with a binary tree – where nodes correspond to expandable amounts – combined with cyclic groups of *distinct* but related orders. Since these techniques do not appear compatible with the Groth-Sahai toolbox, we had to find other techniques to split the wallet across the nodes of a binary tree. In particular, we use a different method to authenticate the node corresponding to the spent divided coin in the tree.

As in the first truly anonymous construction of divisible e-cash [14], the communication complexity of our spending algorithm depends on how much the initial amount $2^L$ has to be divided: from an initial tree of value $2^L$, when a coin of value $2^\ell$ has to be spent, the communication cost of the spending phase is $O(L - \ell)$. Hence, the more we want to divide the wallet into small coins, the more expensive the spending phase is.

The downside of our e-cash construction is the complexity of the deposit phase, where the computational workload of the bank depends on the number of previously received coins when it comes to check that the received coin does not constitute a double-spending. Even though the bank can be expected to have significant computational resources (and although the double-spending checks can be performed in parallel by clerks testing a subset of previously spent coins each), this would be a real bottleneck in practice. For this reason, our system is not meant to be a practical solution and should only be seen as a feasibility result. We leave it as an open problem to build such a system with a more efficient deposit procedure from the bank's standpoint: as in previous constructions of compact e-cash (e.g. [10, 5]), the bank should only have to look up the coin's serial number in a table of previously spent coins. It would also be interesting to reduce the communication complexity of the spending phase so as to only transmit a constant number of group elements.

<footnote>$^3$ The reason is that, in all known bounded accumulators, the public key has linear size in the maximal number of accumulated values.</footnote>
# 2 Background and Definitions

## 2.1 Definitions for Divisible E-Cash

An e-cash scheme involves a bank $\mathcal{B}$, many users $\mathcal{U}$ and merchants $\mathcal{M}$ (who can be viewed as special users). All these parties interact together with respect to the following protocols:

**CashSetup**($\lambda$): takes as input a security parameter $\lambda$ and outputs the public parameters $\mathcal{p} \mathcal{a} \mathcal{p} \mathcal{a} \mathcal{p}$.

**BankKG**($\mathcal{p} \mathcal{a} \mathcal{p}, L$): generates bank's public and secret parameters ($\mathit{sk}_B, \mathit{pk}_B$) that allow $\mathcal{B}$ to issue wallets of up values up to $2^L$ (we assume that $L$ is part of $\mathit{pk}_B$). It also defines an empty database $\mathit{DB}_B$ for later use.

**UserKG**($\mathcal{p} \mathcal{a} \mathcal{p}$): generates a user key pair ($\mathit{sk}_U, \mathit{pk}_U$). We denote as $\mathcal{H}_U$ the set of honestly generated public keys.

**Withdraw**($\mathcal{U}$($\mathcal{p} \mathcal{a} \mathcal{p}$, $\mathit{pk}_B, \mathit{sk}_U$), $\mathcal{B}$($\mathcal{p} \mathcal{a} \mathcal{p}$, $\mathit{pk}_U, \mathit{sk}_B$)): is an interactive protocol between a user $\mathcal{U}$ and the bank $\mathcal{B}$ that allows an honest user to obtain a coin of value $2^L$. The wallet $\mathcal{W}$ comprises the coins, the user's secret key, a signature from the bank on it and some state information state. The bank debits $\mathcal{U}$'s account and stores a piece of tracing information $T_{\mathcal{W}}$ in a database $T$ that allows uncovering the identity of double-spenders.

**Spend**($\mathcal{p} \mathcal{a} \mathcal{p}$, $\mathit{pk}_B$, $\mathcal{W}$, $2^\ell$, $\mathit{pk}_M$, **info**): is invoked by $\mathcal{U}$ to spend a coin of value $2^\ell$ from his wallet and generates a proof $\Pi$ that the coin is valid. The output is the coin that includes the proof $\Pi$ and some fresh public information **info** specifying the transaction.

**VerifyCoin**($\mathcal{p} \mathcal{a} \mathcal{p}$, $\mathit{pk}_M$, $\mathit{pk}_B$, $\mathit{coin}$, $v = 2^\ell$): allows $\mathcal{M}$ to check the validity of a given coin and output a bit depending on whether the test is successful.

**Deposit**($\mathcal{p} \mathcal{a} \mathcal{p}$, $\mathit{pk}_B$, $\mathit{pk}_M$, $\mathit{coin}$, $2^\ell$, $\mathit{DB}_B$): $\mathcal{B}$ updates the database $\mathit{DB}_B$ with $\{(\mathit{coin}, \mathit{flag}, 2^\ell)\}$ where $\mathit{flag}$ indicates whether $\mathit{coin}$ is a valid coin of value $2^\ell$ and whether a cheating attempt is detected.

- If $\mathit{coin}$ does not verify, $\mathcal{B}$ rejects it and sets $\mathit{flag} = \text{"$\mathcal{M}$"}$ to indicate a cheating merchant.

- If $\mathit{coin}$ verifies, $\mathcal{B}$ runs a double spending detection algorithm, using the database $\mathit{DB}_B$ containing already received coins. If an overspent is detected, the bank sets $\mathit{flag} = \text{"$\mathcal{U}$"}$, outputs the two coins and reports the double-spending.

- If the coin passes all the tests, the bank accepts the coin, sets $\mathit{flag} = \text{"accept"}$ and credits the merchant's account.

**Identify**($\mathcal{p} \mathcal{a} \mathcal{p}$, $\mathit{pk}_B$, $\mathit{coin}_a$, $\mathit{coin}_b$): the bank retrieves the double-spender's public key $\mathit{pk}_U$ using its database $\mathit{DB}_B$ and the two different coins.

The security model builds on the model of non-interactive compact e-cash from [5]. An e-cash scheme is secure if it provides *Correctness*, *Anonymity*, *Balance*, *Identification* and *Exculpability* simultaneously.

**ANONYMITY.** Unlike the model of [14], ours adopts a simulation-based formulation of anonymity (note that simulation-based definitions are often stronger than
indistinguishability-based ones). No coalition of banks and merchants should distinguish a real execution of the Spend protocol from a simulated one. In the security experiment, the adversary is allowed to obtain users' public keys, withdraw and spend coins using the oracles $Q_{GetKey}$, $Q_{withdraw}$, $Q_{Spend}$, respectively, which are defined below. Formally, an e-cash system is anonymous if there exists a simulator (SimCashSetup, SimSpend) such that, for any adversary $\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2)$, there is a negligible function $\text{negl}: \mathbb{N} \to \mathbb{R}$ such that:

$$ \begin{array}{l} \Pr[\text{params} \leftarrow \text{CashSetup}(\lambda); (pk_B, \text{state}) \leftarrow \mathcal{A}_1(\text{params}): \\ \qquad \mathcal{A}_2^{Q_{\text{Spend}}(\text{params}, pk_B, \cdot, \cdot)}(\text{params}, pk_B, \cdot, \cdot), Q_{\text{GetKey}}(\text{params}, \cdot), Q_{\text{withdraw}}(\text{params}, pk_B, \cdot, \cdot)(\text{state}) = 1] \\ \quad - \Pr[(\text{params}, \text{Sim}) \leftarrow \text{SimCashSetup}(\lambda); (pk_B, \text{state}) \leftarrow \mathcal{A}_1(\text{params}): \\ \qquad \mathcal{A}_2^{Q_{\text{SimSpend}}(\text{params}, pk_B, \cdot, \cdot)}(\text{params}, pk_B, \cdot, \cdot), Q_{\text{GetKey}}(\text{params}, \cdot), Q_{\text{withdraw}}(\text{params}, pk_B, \cdot, \cdot)(\text{state}) = 1] | < \text{negl}(\lambda) \end{array} $$

To formalize security against coalition of users, bank and merchants, the anonymity game allows the adversary to generate the bank's public key. It is granted dynamic access to the list of oracles hereafter and has to decide whether it is playing the real game, where the spending oracle is an actual oracle, or the simulation, where the spending oracle is a simulator.

- $Q_{\text{GetKey}}(\text{params}, j)$: outputs $pk_{U_j}$. If $U_j$ does not exist, the oracle generates $(sk_{U_j}, pk_{U_j}) \leftarrow \text{UserKG}(\text{params})$ and outputs $pk_{U_j}$.

- $Q_{\text{withdraw}}(\text{params}, pk_B, j, f)$: given a wallet identifier $f$, this oracle plays the role of user $j$ and creates the key pair $(sk_{U_j}, pk_{U_j})$ if it does not exist yet in an execution of $\text{Withdraw}(\mathcal{U}(\text{params}, pk_B, sk_{U_j}), \mathcal{A}(\text{states}))$, while the adversary $\mathcal{A}$ plays the role of the bank. The oracle then creates a wallet $W_f$ of value $2^i$.

- $Q_{\text{Spend}}(\text{params}, pk_B, f, v = 2^\ell, pk_M, \text{info})$: the oracle firstly checks if wallet $W_f$ has been created via an invocation of $Q_{\text{withdraw}}(\text{params}, pk_B, f, v)$. If not, the oracle outputs $\perp$. Otherwise, if $W_f$ contains a sufficient amount, $Q_{\text{Spend}}$ runs $\text{Spend}(\text{params}, pk_B, W_f, i, v = 2^\ell, pk_M, \text{info})$ and outputs a coin of value $v$ from the wallet $W_f$. In any other case (e.g. if the expandable amount of $W_f$ is less than $2^\ell$), it outputs $\perp$.

- $Q_{\text{SimSpend}}(\text{params}, pk_B, f, v = 2^\ell, pk_M, \text{info})$: if $f$ is not the index of a valid withdrawn wallet obtained from $Q_{\text{withdraw}}$, the oracle outputs $\perp$. Otherwise, the oracle runs a simulator $\text{SimSpend}$ on input of public elements $(\text{params}, pk_B, pk_M, v = 2^\ell, \text{info})$. Note that $\text{SimSpend}$ does not use the user's wallet or his public key.

**BALANCE.** No coalition of users can spend more coins than they withdrew. The adversary is a user and can withdraw or spend coins via oracles defined below. An e-cash system provides the *Balance* property if, for any adversary, every value $L \in \text{poly}(\lambda)$, we have:

$$ \begin{array}{l} \Pr[\text{params} \leftarrow \text{CashSetup}(\lambda); (pk_B, sk_B) \leftarrow \text{BankKG}(\text{params}, L); \\ \qquad (q_w, n_d) \leftarrow \mathcal{A}_{Q_{\text{withdraw}}(\text{params}, \cdot, pk_B, \cdot)}(\cdot), Q_{\text{deposit}}(\text{params}, pk_B, DB_B) : q_w \cdot 2^L < n_d] < \text{negl}(\lambda), \end{array} $$
where $n_d$ is the total amount of deposited money after $q_d$ successful calls to oracle $Q_{\text{deposit}}$ (by successful, we mean that the oracle sets flag = "accept"), $q_w$ is the number of successful calls to $Q_{\text{Withdraw}}$.

- $Q_{\text{withdraw}}(\text{params}, pk_U, sk_B)$: the oracle plays the role of the bank in an execution of the Withdraw protocol, on input $(\mathcal{A}(\text{states}), \mathcal{B}(\text{params}, pk_U, sk_B))$, in interaction with the adversary acting as a cheating user. At the end of the protocol, $Q_{\text{withdraw}}$ stores a piece of tracing information $T_w$ in a database $T$.

- $Q_{\text{deposit}}(\text{params}, pk_B, pk_M, coin, v, DB_B)$: this oracle plays the role of the bank while the adversary plays the role of the merchant in the protocol. The oracle initializes the bank database $DB_B$ at $\emptyset$ and returns the same response as $\text{Deposit}(\text{params}, pk_B, pk_M, coin, v, DB_B)$.

**IDENTIFICATION.** Given two fraudulent but well-formed coins, the bank should identify the double-spender. This property is defined via an experiment where the adversary $\mathcal{A}$ is the double-spender and has access to a $Q_{\text{withdraw}}$ oracle defined hereafter. Its goal is to deposit a coin twice without being identified by the bank. We denote by $coin_a$ and $coin_b$ the two coins produced by $\mathcal{A}$. Their corresponding entries in $DB_B$ are of the form $(coin_a, \text{flag}_a, v_a, pk_{M_a})$ and $(coin_b, \text{flag}_b, v_b, pk_{M_b})$ with $coin_a = (\text{info}_a; *)$ and $coin_b = (\text{info}_b; *)$, respectively. We also define a predicate SameCoin that given two coins $coin_a$ and $coin_b$ and their respective values $v_a$ and $v_b$, outputs 1 if the bank detects a double-spending during the deposit of $coin_a$ and $coin_b$: in the context of divisible e-cash, it means that either $coin_a$ and $coin_b$ are the same coin or that one of them, say $coin_a$, is the result of dividing the other one (and thus $v_a$ divides $v_b$). The adversary is successful if its coins satisfy $\text{SameCoin}(coin_a, coin_b, v_a, v_b) = 1$ but the bank fails to identify the user using the database $T$ of tracing pieces of information that were collected during executions of $Q_{\text{withdraw}}$. An e-cash scheme provides double-spenders identification if for any adversary $\mathcal{A}$ and any $L \in \text{poly}(\lambda)$,

$$
\begin{align*}
\Pr[\text{params} \leftarrow \text{CashSetup}(\lambda); (pk_B, sk_B) \leftarrow \text{BankKG}(\text{params}, L); \\
((coin_a, v_a), (coin_b, v_b)) \leftarrow \mathcal{A}^{\text{Q}_{\text{withdraw}}(\text{params}, \cdot, sk_B, \cdot)}(\text{params}, pk_B) : \\
(\text{info}_a; pk_{M_a}) \neq (\text{info}_b; pk_{M_b}) \wedge \text{SameCoin}(coin_a, coin_b, v_a, v_b) = 1 \\
\wedge \text{VerifyCoin}(\text{params}, pk_{M_t}, pk_B, coin_t, v_t) = 1 \text{ for } t \in \{a, b\} \\
\wedge \text{Identify}(\text{params}, pk_B, coin_a, coin_b) \notin T] < \text{negl}(\lambda)
\end{align*}
$$

The oracle $Q_{\text{withdraw}}$ has the same specification as in the Balance property.

**EXCULPABILITY.** No coalition of bank and merchants interacting with an honest user $U$ should be able to produce two coins $(coin_a, coin_b)$ such that $\text{Identify}(\text{params}, pk_B, coin_a, coin_b) = pk_U$ while user $U$ never double-spent. More formally, we define a game with the challenger playing the role of an honest user and the adversary playing the role of the bank and merchants. The adversary $\mathcal{A}$ is given access to oracles $Q_{\text{GetKey}}$, $Q_{\text{withdraw}}$, $Q_{\text{Spend}}$ that allow it to obtain users' keys, create wallets and spend coins. The exculpability property holds if, for any
PPT adversary $\mathcal{A}$, we have

$$
\begin{align*}
\Pr[\text{params} \leftarrow \text{CashSetup}(\lambda); (pk_B, st) \leftarrow \mathcal{A}(\text{params}); \\
    (pk_B, \text{coin}_a, \text{coin}_b, v_a, v_b) \\
    \leftarrow \mathcal{A}^{\mathcal{Q}_{\text{Spend}}}(\text{params}, pk_B, \cdot, \cdot, \cdot), \mathcal{Q}_{\text{GetKey}}(\text{params}, \cdot), \mathcal{Q}_{\text{withdraw}}(\text{params}, \cdot, \cdot, \cdot) (\text{params}, st); \\
\text{SameCoin}(\text{coin}_a, \text{coin}_b, v_a, v_b) = 1; \\
pk_U \leftarrow \text{Identify}(\text{params}, \text{coin}_a, \text{coin}_b) : pk_U \in \mathcal{H}_U] < \text{negl}(\lambda),
\end{align*}
$$

where $\mathcal{H}_U$ denotes the set of honest users. Oracles $\mathcal{Q}_{\text{GetKey}}$, $\mathcal{Q}_{\text{withdraw}}$ and $\mathcal{Q}_{\text{Spend}}$ are defined exactly as in the notion of anonymity.

## 2.2 F-Unforgeable Signatures

Since the e-cash construction described in the paper relies on a common reference string, the following algorithms all take as input a set of common public parameters $\mathbf{params}_{GS}$. To lighten notations, we omit to explicitly write them in the syntax hereafter.

**Definition 1.** A multi-block signature scheme consists of efficient algorithms $\Sigma = (\text{SigSetup}, \text{KeyGen}, \text{Sign}, \text{Verify})$ with the following specification.

**SigSetup**($\lambda$): takes as input a security parameter $\lambda \in \mathbb{N}$ and outputs params that gives the length $n \in \text{poly}(\lambda)$ of message vectors to be signed.

**Keygen**($\mathbf{params}$): takes as input the public parameters and outputs a key pair $(pk, sk)$.

**Sign**($sk, \vec{m}$): is a (possibly randomized) algorithm that takes in a private key $sk$ and a vector $\vec{m} = (m_1, \dots, m_n)$ of messages. It outputs a signature $\sigma$.

**Verify**($pk, \vec{m}, \sigma$): is a deterministic algorithm that takes as input a public key $pk$, a signature $\sigma$ and a message vector $\vec{m} = (m_1, \dots, m_n)$. It outputs 1 if $\sigma$ is deemed valid for $\vec{m}$ and 0 otherwise.

**Definition 2 ([5]).** A multi-block signature scheme $\Sigma$ is F-unforgeable, for some injective function $F(\cdot)$, if no probabilistic polynomial time (PPT) adversary has non-negligible advantage in the following game:

1. The challenger runs Setup and Keygen to obtain a pair $(pk, sk)$, it then sends $pk$ to $\mathcal{A}$.

2. $\mathcal{A}$ adaptively queries a signing oracle. At each query $i$, $\mathcal{A}$ chooses a vector $\vec{m} = (m_1, \dots, m_n)$ and obtains $\sigma_i = \text{Sign}(sk, \vec{m})$.

3. The adversary $\mathcal{A}$ outputs a pair $((F(m_1^*), \dots, F(m_n^*)), \sigma^*)$ and wins if: (a) $\text{Verify}(pk, m^*, \sigma^*) = 1$; (b) $\mathcal{A}$ did not obtain any signature on the vector $(m_1^*, \dots, m_n^*)$.

**Definition 3 ([5]).** A multi-block P-signature combines an F-unforgeable multi-block signature scheme $\Sigma$ with a commitment scheme (Com, Open) and three protocols:
1. An algorithm SigProve (params, pk, σ, $\vec{m}$ = ($m_1, \dots, m_n$)) that generates a series of n commitments $C_\sigma, C_{m_1}, \dots, C_{m_n}$ and a NIZK proof

$$ \pi \leftarrow \text{NIZPK}(m_1 \text{ in } C_{m_1}, \dots, m_n \text{ in } C_{m_n}, \sigma \text{ in } C_\sigma \\ \qquad \mid \{(F(m_1), \dots, F(m_n), \sigma) : \text{Verify}(\text{pk}, \vec{m}, \sigma) = 1\}) $$

and the corresponding VerifyProof (params, pk, $C_{m_1}, \dots, C_{m_n}, C_\sigma$) algorithm.

2. A NIZK proof that two commitments open to the same value, i.e., a proof for the relation

$$ R = \{((x, y), (\text{open}_x, \text{open}_y)) \\ \qquad | \ C = \text{Com}(x, \text{open}_x) \wedge D = \text{Com}(y, \text{open}_y) \wedge x = y\}. $$

3. A protocol SigIssue $\rightleftarrows$ SigObtain allowing a user to obtain a signature on a committed vector $\vec{m} = (m_1, \dots, m_n)$ without letting the signer learn any information on $\vec{m}$.

## 2.3 Bilinear Maps and Complexity Assumptions

We consider a configuration of asymmetric bilinear groups ($\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$) of prime order p with a mapping $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ such that: (1) $e(g^a, h^b) = e(g, h)^{ab}$ for any $(g, h) \in \mathbb{G}_1 \times \mathbb{G}_2$ and $a, b \in \mathbb{Z}$; (2) $e(g, h) \neq 1_{\mathbb{G}_T}$ whenever $g \neq 1_{\mathbb{G}_1}$ and $h \neq 1_{\mathbb{G}_2}$. Since we rely on the hardness of DDH in $\mathbb{G}_1$ and $\mathbb{G}_2$, we additionally require that no isomorphism be efficiently computable between $\mathbb{G}_2$ and $\mathbb{G}_1$.

**Definition 4.** The q-Hidden Strong Diffie-Hellman problem (q-HSDH) in $(\mathbb{G}_1, \mathbb{G}_2)$ is, given $(g, u, h, \Omega = h^\omega) \in \mathbb{G}_1^2 \times \mathbb{G}_2^2$ and tuples $(g^{1/(\omega+c_i)}$, $g^{c_i}$, $h^{c_i}$, $u^{c_i})$ with $c_1, \dots, c_q \stackrel{R}{\rightleftarrows} \mathbb{Z}_p^*$, finding $(g^{1/(\omega+c)}$, $h^c$, $u^c)$ such that $c \neq c_i$ for $i = 1, \dots, q$.

**Definition 5.** The q-Decision Diffie-Hellman Inversion problem (q-DDHI) in $(\mathbb{G}_1, \mathbb{G}_2)$ consists in, given $(g, g^{(\alpha)}, \dots, g^{(\alpha^q)}) \in \mathbb{G}_1^{q+1}$ and $\eta \in \mathbb{G}_1$, deciding if $\eta = g^{1/\alpha}$ or $\eta \in_R \mathbb{G}_1$.

**Definition 6 ([3]).** The Triple Diffie-Hellman problem (TDH) in $(\mathbb{G}_1, \mathbb{G}_2)$ is, given a tuple $(g, g^a, g^b, h, h^a) \in \mathbb{G}_1^3 \times \mathbb{G}_2^2$, and pairs $(c_i, g^{1/a+c_i})_{i=1, \dots, q}$ where $a, b, c_1, \dots, c_q \stackrel{R}{\rightleftarrows} \mathbb{Z}_p^*$, to find a triple $(g^{\mu b}, h^{\mu a}, g^{\mu ab})$ such that $\mu \neq 0$.

**Definition 7.** The Decision 3-party Diffie-Hellman problem (D3DH) in $(\mathbb{G}_1, \mathbb{G}_2)$ is, given elements $(g, g^a, g^b, g^c, h, h^a, h^b, h^c, \Gamma) \in \mathbb{G}_1^4 \times \mathbb{G}_2^4 \times \mathbb{G}_1$, where $a, b, c \stackrel{R}{\rightleftarrows} \mathbb{Z}_p$, to decide if $\Gamma = g^{abc}$ or $\Gamma \in_R \mathbb{G}_1$.

## 2.4 Building Blocks

**Non-interactive witness indistinguishable proofs.** Our construction uses Groth-Sahai proofs for pairing product equations (PPE) of the form:

$$ \prod_{j=1}^{n} e(\mathcal{A}_j, \mathcal{Y}_j) \prod_{j=1}^{n} e(\mathcal{X}_i, \mathcal{B}_i) \prod_{i=1}^{m} \prod_{j=1}^{n} e(\mathcal{X}_i, \mathcal{Y}_j)^{\gamma_{i,j}} = t_T, $$
where $\mathcal{X}_i, \mathcal{Y}_j$ are variables in $\mathbb{G}_1$ and $\mathbb{G}_2$, respectively, and $\mathcal{A}_j \in \mathbb{G}_1, \mathcal{B}_i \in \mathbb{G}_2$ and $t_T \in \mathbb{G}_T$ are constants for $i \in [1, m]$ and $j \in [1, n]$.

A proof system is a tuple of four algorithms ($\text{Setup}_{\text{GS}}, \text{Prove}_{\text{GS}}, \text{VerifyProof}_{\text{GS}}$): $\text{Setup}_{\text{GS}}$ outputs a common reference string (CRS) crs, $\text{Prove}_{\text{GS}}$ first generates commitments of variables and constructs proofs that these variables satisfy the statement, and $\text{VerifyProof}_{\text{GS}}$ verifies the proof. GS proofs are witness-indistinguishable and some of these can be made zero-knowledge as shown later. The proofs satisfy correctness, soundness and witness-indistinguishability. Correctness requires that a verifier always accepts honestly generated proofs for true statements. Soundness guarantees that cheating provers can only prove true statements. Witness-indistinguishability requires that an efficient simulator $\text{GSSimSetup}$ should be able to produce a common reference string (CRS) crs' that is computationally indistinguishable from a normal crs. When commitments are computed using crs', they are perfectly hiding and the corresponding non-interactive proofs are witness indistinguishable: i.e., they leak no information on the underlying witnesses. Zero-knowledge additionally requires the existence of an algorithm $\text{GSSimProve}$ that, given a simulated CRS crs' and some trapdoor information $\tau$, generates a simulated proof of the statement without using the witnesses and in such a way that the proof is indistinguishable from a real proof.

As a building block, we will use a NIZK proof of equality of committed group elements as defined in [3, 5].

If $C_x = \text{GSSim}(x, \text{open}_x)$ and $C_y = \text{GSSim}(y, \text{open}_y)$ are Groth-Sahai commitments to the group element $x = y \in \mathbb{G}_1$, the NIZK proof can be a proof that committed variables $(x, y, \theta) \in \mathbb{G}_1^2 \times \mathbb{Z}_p$ satisfy the equations $e(x/y, h^\theta) = 1$ and $e(g, h^\theta)e(1/g, h) = 1_{\mathbb{G}_T}$. Using the trapdoor of the CRS, we can trapdoor open to 1 a commitment to 0 and generate fake proofs for the latter relation. Setting $\theta = 0$ and $\theta = 1$, respectively, allows to construct a valid (simulated) witness for each of the two equations. Under the SXDH assumption, commitments cost 2 elements in the group. Thus, if the commitment to $y$ is in $\mathbb{G}_1^2$, the proof above costs 8 elements $\mathbb{G}_1$ and 6 in $\mathbb{G}_2$, 6 multi-exponentiations and 26 pairings (to verify). This includes commitments to $y \in \mathbb{Z}_p$ and $h^\theta$.

**Multi Block P-signatures.** In [5], a multi-block P-signature was proved F-secure under the HSDH and the TDH assumptions. Let $(p, \mathbb{G}_1, \mathbb{G}_2, G_T, e, g, h)$ be parameters for a bilinear map, the public parameters are then defined as $(p, \mathbb{G}_1, \mathbb{G}_2, G_T, e, g, h, \text{params}_{\text{GS}}, e(g, h))$, where $g$ and $h$ are random elements of $\mathbb{G}_1$ and $\mathbb{G}_2$ respectively. The public key and the private key are defined to be pk = $(u, U = g^\beta, \tilde{U} = h^\beta, \{V_i = g^{a_i}, \tilde{V}_i = h^{a_i}\}_{i=1}^n)$ and sk = $(\beta, \tilde{a} = (a_1, \dots, a_n))$, where $u \stackrel{R}{\leftarrow} \mathbb{G}_1$ and for random scalars $\beta, a_1, \dots, a_n$. To sign a vector of message $\tilde{m} = (m_1, \dots, m_n)$, the signer chooses $r \stackrel{R}{\leftarrow} \mathbb{Z}_p$ such that $r \neq -(\beta + \sum_{i=1}^n a_i m_i)$ and computes $\sigma = (g^{1/\beta+r} + \sum_{i=1}^n a_i m_i, h^r, u^r)$. Verification of a signature $\sigma = (\sigma_1, \sigma_2, \sigma_3)$ on some block $\tilde{m}$ is done by checking whether

$$e(\sigma_1, \tilde{U} \cdot \sigma_2 \cdot \prod_{i=1}^{n} \tilde{V}_i^{m_i}) = e(g, h) \quad \text{and} \quad e(u, \sigma_2) = e(\sigma_3, h).$$
As shown in [5], the above scheme can be augmented with the following P-signature protocols.

**SigProve**(*params*, *pk*, *σ*, $\vec{m}$): parse the signature σ as ($\sigma_1, \sigma_2, \sigma_3$) and the vector $\vec{m}$ as ($m_1, \dots, m_n$). To commit to an exponent $m_i \in \mathbb{Z}_p$, compute Groth-Sahai commitments of $h^{m_i}$ and $u^{m_i}$ as

$$ (C_{i,1}, C_{i,2}, C_{i,3}) = \begin{aligned}[t] & \mathrm{Com}(m_i, (\mathrm{open}_{m_i,1}, \mathrm{open}_{m_i,2}, \mathrm{open}_{m_i,3})) \\ & = (\mathrm{GSCom}(h^{m_i}, \mathrm{open}_{m_i,1}), \\ & \qquad \mathrm{GSCom}(u^{m_i}, \mathrm{open}_{m_i,2}), \mathrm{GSCom}(\tilde{V}_i^{m_i}, \mathrm{open}_{m_i,3})). \end{aligned} $$

Generate an auxiliary variable $\theta = 1 \in \mathbb{Z}_p$ with its own commitment $C_\theta = \mathrm{GSCom}(\theta, \mathrm{open}_\theta)$. Then, generate commitments $\{C_{\sigma_\tau}\}_{\tau=1}^3$ to $\{\sigma_\tau\}_{\tau=1}^3$ and give a NIZK proof that

$$ \begin{aligned} e(g^\theta, h) &= e(\sigma_1, \tilde{U} \cdot \sigma_2 \cdot \prod_{i=1}^n \tilde{V}_i^{m_i}), \\ e(u, \sigma_2) &= e(\sigma_3, h), \\ \theta &= 1 \\ e(g, \tilde{V}_i^{m_i}) &= e(V_i, h^{m_i}), \quad e(u, h^{m_i}) = e(u^{m_i}, h) \quad \text{for } i \in \{1, \dots, n\} \end{aligned} $$

We denote the complete proof by

$$ \pi^{sig} = (\{C_{\sigma_\tau}\}_{\tau=1}^3, \pi_1^{sig}, \pi_2^{sig}, \pi_\theta^{sig}, \{\pi_{m_i,1}^{sig}, \pi_{m_i,2}^{sig}\}_{i=1}^n). $$

Note that $\pi_1^{sig}$ is a proof for a quadratic equation and requires 4 elements of $\mathbb{G}_1$ and 4 elements of $\mathbb{G}_2$. Other equations are linear: each of $\pi_2^{sig}$ and $\{\pi_{m_i,2}^{sig}\}_{i=1}^n$ demands 2 elements of $\mathbb{G}_1$ and 2 elements of $\mathbb{G}_2$ whereas proofs $\{\pi_{m_i,1}^{sig}\}_{i=1}^n$ only takes two elements of $\mathbb{G}_1$ each since all variables are in $\mathbb{G}_2$. The NIZK property stems from the fact that, on a simulated CRS, a commitment to 0 can be trapdoor opened to 1. For this reason, except for the equation $\theta = 1$ (for which one can simply equivocate the commitment), all other proofs can be simulated using the witnesses $1_{\mathbb{G}_1}, 1_{\mathbb{G}_2}$ and $\theta = 0$.

**VerifyProof**(*params*, *pk*, $\pi^{sig}$, $(C_1, \dots, C_n)$) Works in the obvious way and returns 1 if and only if the proof $\pi^{sig}$ generated by **SigProve** is convincing.

**EqComProve**(*params*, *pk*, *x*, *y*) The protocol for proving that two commitments open to the same value employ the usual technique already used in [3, 5] and is reviewed section 2.4.

**SigIssue**(*sk*, $(C_1, \dots, C_n)$) $\Rightarrow$ **SigObtain**(*params*, *pk*, $\vec{m}$, $\{(C_i, \mathrm{open}_i)\}_{i=1}^n$) is a secure two-party protocol between the issuer and the receiver where the latter obtains a signature on a committed vector of messages. As suggested in [5], this can be done using the 2-party protocol of [32] for computing a circuit on committed inputs. Another option would be to use the two-party computation protocol from [4] that relies on homomorphic encryption.

**Theorem 1 ([5]).** If the HSDH and the TDH assumptions hold in $(\mathbb{G}_1, \mathbb{G}_2)$, the scheme is F-unforgeable w.r.t. the injective function $F(m) = (h^m, u^m)$.
### 3 Construction of Divisible E-cash

Known approaches for divisible e-cash [37, 35, 15, 18] make use of a binary tree with $L + 1$ levels (for a monetary value of $2^L$) where each node corresponds to an amount of money which is exactly one of half the amount of its father. Double-spenders are detected by making sure that each user cannot spend a coin corresponding to a node and one of its descendants or one of its ancestors.

In these tree-based constructions, one difficulty is for the user to efficiently prove that the path connecting the spent node to the root is well-formed. In [14, 18], this problem is solved using groups of distinct order: [14] uses a sequence of $L+1$ groups $G_1, \dots, G_{L+1}$ of prime order $p_\nu$ where $G_\nu$ is a subgroup of $Z_{p_{\nu-1}}^*$ for $\nu = 1, \dots, L+1$. The solution of [18] uses $L+2$ bounded accumulators (one for each level of the tree and one for the whole tree) so as to only use two distinct group orders. The use of groups of distinct order (and double discrete logarithms in [14]) is hardly compatible with Groth-Sahai proofs and, in our system we need to find a different technique to prevent users from spending coins associated with a node and one of its ancestors in the same tree.

#### 3.1 General Description of the Scheme

<figure><img src="image_2.png" /><figcaption>Fig. 1. Binary tree for spending one coin in a wallet of $2^4$ coins</figcaption></figure>

Our construction uses the tree-based approach. Each wallet $\mathcal{W}$ consists of a divisible coin of value $2^L$, for some $L \in \mathbb{N}$, and the complexity of the spending phase depends on the depth of the node in the tree $\mathcal{W}$: the deeper the node is, the more expensive the spending phase will be. When an honest user $\mathcal{U}$ with key pairs $(pk_{\mathcal{U}}, sk_{\mathcal{U}})$ interacts with the bank $\mathcal{B}$, he obtains a wallet $\mathcal{W} = (s, t, sk_{\mathcal{U}}, \sigma, \text{state})$ consisting of the bank's signature $\sigma$ on the vector $(s, t, sk_{\mathcal{U}})$ where $s, t$ are seeds for the Dodis-Yampolskiy PRF [28]. In our notation, **state** is a variable indicating the availability of coins.

To spend a coin of value $v = 2^\ell$ (with $\ell \le L$) in the tree, the user $\mathcal{U}$ determines the next node corresponding to an unspent coin at height $\ell$: the root of the tree is used if the user wants to spend his entire wallet at once whereas the leaves correspond to the smallest expandable amounts. Each node will be assigned
a unique label consisting of an integer in the interval $[1, 2^{L+1} - 1]$. A simple assignment is obtained by labeling the root as $x_0 = 1$ and the rightmost leaf as $2^{L+1} - 1$, all other nodes being considered in order of appearance, from the left to the right and starting from the root.

In order to construct a valid coin, the user has to choose a previously unspent node of label $x_{coin}$ at the appropriate level and do the following: (1) Prove his knowledge of a valid signature on committed messages $(s, t, sk_U)$ and his knowledge of $sk_U$. (2) Commit to the PRF seeds via commitments to the group elements $(S, T) = (h^s, h^t)$. (3) Commit to the path that connects $x_{coin}$ to the root and prove that commitments pertain to a valid path. (4) Evaluate a coin serial number $Y_{L-\ell} = g^{1/(s+x_{coin})}$ where the input is the label of the node to be spent. (5) Generate NIZK proofs that everything was done consistently. (6) Add some material that makes it impossible to subsequently spend an ancestor or a descendant of $x_{coin}$ without being detected.

At step (1), we use the multi-block P-signature scheme to sign the block $(s, t, sk_U)$. Using the proof produced by SigProve in the P-signature, we can efficiently prove knowledge of a signature on committed inputs in NIZK.

The trickiest problem to solve is actually (6). If $\{x_0, \dots, x_{L-\ell}\}$ denotes the path from the root $x_0$ to $x_{L-\ell} = x_{coin}$, for each $j \in \{0, \dots, L-\ell\}$, we include in the coin a pair $(T_{j,1}, T_{j,2})$ where $T_{j,1} = h^{\delta_{j,1}}$, for some random $\delta_{j,1} \stackrel{R}{\leftarrow} \mathbb{Z}_p$, and $T_{j,2} = e(Y_j, T_{j,1})$, where $Y_j = g^{1/(s+x_j)}$ is the value of the PRF for the label $x_j$. In addition, $\mathcal{U}$ must add a NIZK proof that the pair $(T_{j,1}, T_{j,2})$ was correctly calculated. By doing so, at the expense of $n_s$ pairing evaluations at each deposit (where $n_s$ denotes the number of previously spent coins), the bank will be able to detect whether a spent node is in the path connecting a previously spent node to the root. At the same time, if $\mathcal{U}$ does not overspend at any time, the coins he spends remain computationally unlinkable.

By itself, the pair $(T_{j,1}, T_{j,2})$ only renders cheating attempts evident. In order to expose the public key $pk_U$ of double spenders, $\mathcal{U}$ is required to add a pair $(T_{j,3}, T_{j,4}) = (h^{\delta_{j,2}}, pk_U \cdot e(Y_j, T_{j,3}))$ at each node of the path: by doing so, $pk_U$ is exposed if $\mathcal{U}$ subsequently spends a node above $x_{coin}$ in the path. However, we have to consider a second kind of double-spending, where the two coins involve the same tree node $x_{coin} = x_{L-\ell}$. To deal with this case, we require $\mathcal{U}$ to additionally use the seed $t$ of his wallet and the merchant's data $R$ and compute another security tag $Z_{L-\ell} = g^{sk_U} g^{R/(t+x_{L-\ell})}$. The latter will be used to identify cheating users in the same way as in [10].

Finally, in order to obtain the exculpability property (and prevent a dishonest bank from wrongly accusing the user of double-spending coins), we need to add yet another pair of the form $(h^{\delta_{j,3}}, e(g_0, h^{sk_U}) \cdot e(Y_j, h^{\delta_3}))$, where $g_0 \in \mathbb{G}_1$ is part of the CRS, in such a way that framing the user requires to compute $e(g_0, h^{sk_U})$ and solve a (computational) Bilinear Diffie-Hellman instance.

In order to solve problem (5), we need to generate non-interactive proofs for a number of pairing-product equations. Since the notion of anonymity requires to build a simulator that emulates the prover without knowing any witness, it means that we need NIZK proofs for pairing product equations on multiple
occasions. Fortunately, the specific equations fall into the category of equations for which NIZK proofs are possible at the cost of introducing extra variables. For this reason, we will have to introduce auxiliary variables for each pairing product equations.

**Example.** Suppose that, in his wallet $L = 4$, $\mathcal{U}$ uses the seed $s$ to spend the amount of $v = 2^2$. The left part of Figure 1 represents the state of the wallet when no coin has been spent. In the rightmost tree, the black node indicates the target node $x_{coin}$ of value $v$ and greyed nodes are those that cannot be spent any longer once the black node was spent.

## 3.2 Construction

We now describe our divisible e-cash system where the withdrawal protocol allows users to obtain a wallet of a divisible coin of value $2^L$.

**CashSetup($\lambda$):** chooses bilinear groups $(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T)$ of order $p > 2^\lambda$ and generators $g, g_0 \stackrel{\mathbb{R}}{\leftarrow} \mathbb{G}_1$, $h \stackrel{\mathbb{R}}{\leftarrow} \mathbb{G}_2$. It also generates a Groth-Sahai common reference string $\text{params}_{GS} = \{g, h, \vec{u}_1, \vec{u}_2, \vec{v}_1, \vec{v}_2\}$ for the perfectly soundness setting. The algorithm also selects a collision-resistant hash function $H: \{0, 1\}^* \to \mathbb{Z}_p$. The output is $\text{params} := \{(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T), g_0, \text{params}_{GS}, H\}$.

**BankKG($\text{params}, L$):** runs $\text{SigSetup}(\lambda, n)$ with $n = 3$ to obtain a key pair $(\text{sk}, \text{pk})$ for the P-signature of section 2.4. The bank's key pair is defined to be $(\text{sk}_B, \text{pk}_B) = (\text{sk}, \text{pk})$ and $\text{pk}_B$ consists of

$$pk_B = (u, U = g^\beta, \tilde{U} = h^\beta, \{V_i = g^{a_i}, \tilde{V}_i = h^{a_i}\}_{i=1}^3, L).$$

**UserKG($\text{params}$):** the user $\mathcal{U}$ defines his key pair as $(\text{sk}_\mathcal{U}, \text{pk}_\mathcal{U} = e(g, h)^{sk_\mathcal{U}})$ for a random $\text{sk}_\mathcal{U} \stackrel{\mathbb{R}}{\leftarrow} \mathbb{Z}_p$.

**Withdraw($\mathcal{U}(\text{params}, \text{pk}_B, \text{sk}_\mathcal{U}), \mathcal{B}(\text{params}, \text{pk}_\mathcal{U}, \text{sk}_B)$):** $\mathcal{U}$ and $\mathcal{B}$ run the following interactive protocol:

1. The user $\mathcal{U}$ first picks $s', t' \stackrel{\mathbb{R}}{\leftarrow} \mathbb{Z}_p$ at random and computes perfectly hiding commitments $C_{s'} = \text{Com}(s', \text{open}_{s'})$, $C_{t'} = \text{Com}(t', \text{open}_{t'})$ and $C_{sk_\mathcal{U}} = \text{Com}(\text{sk}_\mathcal{U}; \text{open}_{sk_\mathcal{U}})$. The user sends $(C_{s'}, C_{t'}, C_{sk_\mathcal{U}})$ to $\mathcal{B}$ and provides interactive witness indistinguishable proofs that he knows how to open $(C_{s'}, C_{t'})$. In addition, he provides an interactive zero-knowledge$^4$ proof that $C_{sk_\mathcal{U}}$ is a commitment to the private key $\text{sk}_\mathcal{U}$ that was used to generate $\text{pk}_\mathcal{U}$.

2. If the proofs verifies, $\mathcal{B}$ picks $(s'', t'') \leftarrow \mathbb{Z}_p^2$ which are sent to $\mathcal{U}$.

3. The user $\mathcal{U}$ sets $s = s' + s''$ and $t = t' + t''$, updates commitments $C_{s'}$ and $C_{t'}$ into commitments $C_s = \text{Com}(s, \text{open}_s)$ and $C_t = \text{Com}(t, \text{open}_t)$. The user sends $(C_s, C_t)$ to the bank with a proof that these commitments were properly calculated.

<footnote>$^4$ The zero-knowledge property will be needed in the proof of weak exculpability.</footnote>
4. $\mathcal{U}$ and $\mathcal{B}$ jointly run the protocol

$$ \text{SigIssue}(\text{params}, \text{sk}, (C_s, C_t, C_{sk_{\mathcal{U}}})) \\ \iff \text{SigObtain}(\text{params}, \text{pk}, (s, t, sk_{\mathcal{U}}), (\text{open}_s, \text{open}_t, \text{open}_{sk_{\mathcal{U}}})) $$

in such a way that $\mathcal{U}$ eventually obtains $\mathcal{B}$'s signature $\sigma$ on $(s, t, sk_{\mathcal{U}})$. The user $\mathcal{U}$ stores the wallet $\mathcal{W} = (s, t, sk_{\mathcal{U}}, \sigma, \text{state})$, where state $= \emptyset$.

5. $\mathcal{B}$ records a debit of value $v = 2^L$ on $\mathcal{U}$'s account. It stores the transcript of the protocol and the tracing information $pk_{\mathcal{U}}$ in its database $\mathcal{T}$.

**Spend**($\text{params}, pk_{\mathcal{B}}, \mathcal{W} = (s, t, sk_{\mathcal{U}}, \sigma, \text{state}), 2^\ell, pk_{\mathcal{M}}, \text{info}$): Let us assume that $\mathcal{U}$ wants to spend a coin of value $2^\ell$ for the wallet $\mathcal{W}$ of initial value $2^L$. Using state, $\mathcal{U}$ determines the label $x_{\text{coin}} \in [1, 2^{L+1} - 1]$ of the first node corresponding to an unspent coin at height $\ell$ in the tree associated with the wallet. Let $\{x_0, x_1, \dots, x_{L-\ell}\}$ denote the path connecting node $x_{\text{coin}} = x_{L-\ell}$ to the root $x_0 = 1$ of the tree. The user $\mathcal{U}$ computes $S = h^s$ and $T = h^t$ and conducts the following steps.

1. $\mathcal{U}$ has to prove that he knows a signature $\sigma$ on the committed vector $(s, t, sk_{\mathcal{U}}) \in \mathbb{Z}_p^3$. To this end, he first generates commitments and proofs $(\{C_{S,i}\}_{i=1}^3, \{C_{T,i}\}_{i=1}^3, \{C_{U,i}\}_{i=1}^3, \pi^{\text{sig}}) \leftarrow \text{SigProve}(\text{params}, \text{pk}, \sigma, (s, t, sk_{\mathcal{U}}))$. The output of SigProve includes $\{C_{U,i}\}_{i=1}^3$, which are commitments to $(L_{U,1}, L_{U,2}, L_{U,3}) = (h^{sk_{\mathcal{U}}}, u^{sk_{\mathcal{U}}}, \tilde{V}_3^{sk_{\mathcal{U}}})$, and $\{C_{S,i}, C_{T,i}\}_{i=1}^3$, that contain $(L_{S,1}, L_{S,2}, L_{S,3}) = (h^s, u^s, \tilde{V}_1^s)$ and $(L_{T,1}, L_{T,2}, L_{T,3}) = (h^t, u^t, \tilde{V}_2^t)$, respectively. In addition, $\mathcal{U}$ computes $C_{K_{\mathcal{U}}} = \text{GSCom}(h^{sk_{\mathcal{U}}}, \text{open}'_{\mathcal{U}})$ as a commitment to $K_{\mathcal{U}} = h^{sk_{\mathcal{U}}}$ and generates a NIZK proof $\pi_{K_{\mathcal{U}}} \leftarrow \text{EqComProve}(L_{U,1}, K_{\mathcal{U}})$ that $C_{K_{\mathcal{U}}}$ and $C_{U,1}$ are commitment to the same value. This amounts to prove that

$$ e(L_{U,1}/K_{\mathcal{U}}, h^{\theta}) = 1_{\mathbb{G}_T} \quad \text{and} \quad \theta = 1, \qquad (1) $$

for some variable $\theta \in \mathbb{Z}_p$ contained in $C_{\theta} = \text{GSCom}(\theta, \text{open}_{\theta})$ and that will be re-used in subsequent steps of the spending protocol.

2. For $j = 0$ to $L - \ell$ do the following.

a. If $j > 0$, generate a commitment $C_{X_j} = \text{GSCom}(h^{x_j}, \text{open}_{x_j})$ to $X_j = h^{x_j}$ and a proof that $x_j = 2x_{j-1} + b_j$, for some bit $b_j \in \{0, 1\}$. To this end, generate the commitments $C_{b_j} = \text{GSCom}(g^{b_j}, \text{open}_{b_j})$ and $C'_{b_j} = \text{GSCom}(h^{b_j}, \text{open}'_{b_j})$ as well as a NIZK proof $\pi_{x_j} \leftarrow \text{EqComProve}(C_{X_j}, C'_{X_j})$ that $C_{X_j}$ and $C'_{X_j} = C^2_{X_{j-1}} \cdot C'_{b_j}$ open to the same value. To prove that $b_j \in \{0, 1\}$, $\mathcal{U}$ generates a NIZK proof $(\pi_{b_j,1}, \pi_{b_j,2})$ for the pairing-product equations $e(g^{b_j}, h) = e(g, h^{b_j})$ and $e(g^{b_j}, h^{b_j}) = e(g^{b_j}, h)$, which guarantee that $b_j^2 = b_j$, so that $b_j \in \{0, 1\}$.

b. If $j < L - \ell$, generate a commitment $C_{Y_j} = \text{GSCom}(Y_j, \text{open}_{Y_j})$ to the PRF value $Y_j = g^{1/(s+x_j)}$ as well as a NIZK proof $\pi_{Y_j}$ that it satisfies $e(Y_j, L_{S,1} \cdot X_j) = e(g, h)$, where $X_j = h^{x_j}$. This consists of a commitment $C_{\Phi_{Y_j}}$ to a variable $\Phi_{Y_j} \in \mathbb{G}_1$ and a proof
that $e(\Phi_{Y_j}, L_{S,1} \cdot X_j) = e(g, h)$ and $e(Y_j/\Phi_{Y_j}, h^\theta) = 1_{\mathbb{G}_T}$. Then, pick $\delta_{j,1}, \delta_{j,2}, \delta_{j,3} \stackrel{\sim}{\leftarrow} \mathbb{Z}_p$ and compute

$$T_{j,1} = h^{\delta_{j,1}}, \quad T_{j,2} = e(Y_j, h)^{\delta_{j,1}}$$

$$T_{j,3} = h^{\delta_{j,2}}, \quad T_{j,4} = pk_U \cdot e(Y_j, h)^{\delta_{j,2}},$$

$$T_{j,5} = h^{\delta_{j,3}}, \quad T_{j,6} = e(g_0, h^{sk_U}) \cdot e(Y_j, h)^{\delta_{j,3}}.$$

Generate NIZK proofs $(\pi_{j,T_1}, \pi_{j,T_3}, \pi_{j,T_5})$ that $(Y_j, K_U)$ satisfy

$$\begin{align}
T_{j,2} &= e(Y_j, T_{j,1}) \nonumber \\
T_{j,4} &= e(g, K_U) \cdot e(Y_j, T_{j,3}) \tag{2} \\
T_{j,6} &= e(g_0, K_U) \cdot e(Y_j, T_{j,5}). \nonumber
\end{align}$$

These proofs require new commitments $\{C_{\Phi_{j,k}}\}_{k=1,3,5}$, $C_{\Phi'_{Y_j}}$ and $C_{\Phi''_{Y_j}}$ to auxiliary variables $\{\Phi_{j,k}\}_{k=1,3,5}$, $\Phi'_{Y_j}$, $\Phi''_{Y_j} \in \mathbb{G}_1$ respectively and proofs for relations

$$\begin{align*}
T_{j,2} &= e(Y_j, \Phi_{j,1}), & e(Y_j/\Phi_{Y_j'}, h^\theta) &= 1_{\mathbb{G}_T}, \\
T_{j,4} &= e(g, K_U) \cdot e(\Phi_{Y_j'}, \Phi_{j,3}) & e(Y_j/\Phi_{Y_j''}, h^\theta) &= 1_{\mathbb{G}_T}, \\
T_{j,6} &= e(g_0, K_U) \cdot e(\Phi_{Y_j''}, \Phi_{j,5}), & \{e(g^\theta, T_{j,k}/\Phi_{j,k}) = 1_{\mathbb{G}_T}\}_{k \in \{1,3,5\}}. &
\end{align*}$$

c. If $j = L - \ell$, compute the serial number $Y_{L-\ell} = g^{1/(s+x_{L-\ell})}$ and generate a NIZK proof $\pi_{Y_{L-\ell}}$ that $e(Y_{L-\ell}, L_{S,1} \cdot X_{L-\ell}) = e(g, h)$. This proof consists of a commitment $C_{\Phi_{Y_{L-\ell}}}$ to $\Phi_{Y_{L-\ell}} \in \mathbb{G}_1$ and proofs for equations

$$e(\Phi_{Y_{L-\ell}}, L_{S,1} \cdot X_{L-\ell}) = e(g, h), \quad e(Y_{L-\ell}/\Phi_{Y_{L-\ell}}, h^\theta) = 1_{\mathbb{G}_T}.$$

Compute $Z_{L-\ell} = g^{sk_U} \cdot g^{R/(t+x_{L-\ell})}$, where $R = H(\text{info}, pk_M) \in \mathbb{Z}_p$, and a NIZK proof $\pi_{Z_{L-\ell}}$ that $Z_{L-\ell}$ is well-formed. This requires new Groth-Sahai commitments $C_{W_{L-\ell}}$, $C_{\Phi_{W_{L-\ell}}}$ to auxiliary variables $W_{L-\ell} = g^{1/(t+x_{L-\ell})}$, $\Phi_{W_{L-\ell}} = g^{1/(t+x_{L-\ell})}$ and a proof that:

$$\begin{align*}
e(g, K_U) \cdot e(W_{L-\ell}, h^R) &= e(Z_{L-\ell}, h), \\
e(W_{L-\ell}, L_{T,1} \cdot X_{L-\ell}) &= e(g, h) \\
e(W_{L-\ell}/\Phi_{W_{L-\ell}}, h^\theta) &= 1_{\mathbb{G}_T}.
\end{align*}$$

Finally, update state into state' = state $\cup \{(x_{coin})\}$ and output the coin

$$\begin{align*}
\text{coin} = & \left( \{C_{S,i}\}_{i=1}^3, \{C_{T,i}\}_{i=1}^3, \{C_{U,i}\}_{i=1}^3, C_{K_U}, \pi_{K_U}, \pi^{sig}, \right. \\
& \left. \{C_{X_j}, C_{b_j}, C'_{b_j}, \pi_{x_j}, \pi_{b_j,1}, \pi_{b_j,2}\}_{j=1}^{L-\ell}, \right. \\
& \left. \{(T_{j,1}, T_{j,2}, T_{j,3}, T_{j,4}, T_{j,5}, T_{j,6}), C_{Y_j}, C_{\Phi_{Y_j}}, C'_{\Phi_{Y_j}}, C''_{\Phi_{Y_j}}, \right. \\
& \left. \{C_{\Phi_{j,k}}\}_{k \in \{1,3,5\}}, \pi_{Y_j}, \pi_{j,T_1}, \pi_{j,T_3}, \pi_{j,T_5}\}_{j=0}^{L-\ell-1}, \right. \\
& \left. Y_{L-\ell}, Z_{L-\ell}, C_{\Phi_{Y_{L-\ell}}}, C_{W_{L-\ell}}, C_{\Phi_{W_{L-\ell}}}, \pi_{Y_{L-\ell}}, \pi_{Z_{L-\ell}}, \text{info} \right)
\end{align*}$$
**VerifyCoin**(*params*, *pk*<sub>*M*</sub>, *pk*<sub>*B*</sub>, *v* = 2<sup>*l*</sup>, *coin*): parse *coin* as above. Return 1 iff all proofs verify.

**Deposit**(*params*, *pk*<sub>B</sub>, *pk*<sub>M</sub>, *coin*, 2<sup>*l*</sup>, DB<sub>B</sub>): parse *coin* as above and perform the same checks as **VerifyCoin**. Then, define DB<sub>B</sub>' = DB<sub>B</sub> ∪ {(*coin*, *flag*, 2<sup>*l*</sup>, *pk*<sub>M</sub>)} where the value of *flag* depends on whether *coin* is a valid coin of value 2<sup>*l*</sup> and whether a cheating attempt is detected.

- If coin does not properly verify, $\mathcal{B}$ sets flag = “$\mathcal{M}$” to indicate a cheating merchant.

- If coin properly verifies, the bank $\mathcal{B}$ runs the following test. For each entry $(coin_s, flag_s, 2^{l_s}, pk_{M_s}) \in \text{DB}_{\mathcal{B}}$, where $s = 1$ to $|\text{DB}_{\mathcal{B}}|$, $\mathcal{B}$ parses $coin_s$ as above. If $(info_s, pk_{M_s}) = (info, pk_M)$, $\mathcal{B}$ sets flag = “$M$”. Otherwise, from $coin_s$, it extracts the path $\{(T_{s,j,1}, T_{s,j,2}, T_{s,j,3}, T_{s,j,4})\}_{j=0}^{L-\ell_s-1}$, the serial number $Y_{L-\ell_s} \in \mathbb{G}_1$ and the tag $Z_{L-\ell} \in \mathbb{G}_1$. It also parses coin to extract the path $\{(T_{j,1}, T_{j,2}, T_{j,3}, T_{j,4})\}_{j=0}^{L-\ell-1}$, the serial number $Y_{L-\ell} \in \mathbb{G}_1$ and the tag $Z_{L-\ell}$. If $\ell < \ell_s$ and $T_{L-\ell,s,2} = e(Y_{L-\ell_s}, T_{L-\ell_s,1})$, $\mathcal{B}$ sets flag = “$\mathcal{U}$”, outputs $coin_s$ and coin and reports a double-spending. Likewise, if $\ell > \ell_s$ and $T_{s,L-\ell,2} = e(Y_{L-\ell}, T_{s,L-\ell,1})$, $\mathcal{B}$ also sets flag = “$\mathcal{U}$” and outputs $coin_s$ and coin. Finally, if $\ell = \ell_s$, $\mathcal{B}$ sets flag = “$\mathcal{U}$” if and only if $Y_{L-\ell} = Y_{L-\ell_s}$.

- If coin verifies and no double-spending is detected, $\mathcal{B}$ sets flag = “accept” and credits the account of $pk_M$ by the amount of 2$^l$.

After the above tests, the updated database $DB_B'$ supersedes $DB_B$.

**Identify**(*params*, *pk*<sub>B</sub>, *coin*<sub>a</sub>, *coin*<sub>b</sub>): on input of fraudulent coins *coin*<sub>a</sub> and *coin*<sub>b</sub>, the bank *B* can identify the double-spender as follows.

1. Extract info<sub>a</sub>, {($T_{j,1}^{(a)}$, $T_{j,2}^{(a)}$, $T_{j,3}^{(a)}$, $T_{j,4}^{(a)}$)}<sub>j=0</sub><sup>L-ℓ<sub>a</sub>-1</sup>, (Y<sub>L-ℓ<sub>a</sub></sub><sup>(a)</sup>, Z<sub>L-ℓ<sub>a</sub></sub><sup>(a)</sup>) ∈ G<sub>1</sub><sup>2</sup> from coin<sub>a</sub>. Also, parse coin<sub>b</sub> to retrieve info<sub>b</sub>, {($T_{j,1}^{(b)}$, $T_{j,2}^{(b)}$, $T_{j,3}^{(b)}$, $T_{j,4}^{(b)}$)}<sub>j=0</sub><sup>L-ℓ<sub>b</sub>-1</sup> and (Y<sub>L-ℓ<sub>b</sub></sub><sup>(b)</sup>, Z<sub>L-ℓ<sub>b</sub></sub><sup>(b)</sup>) ∈ G<sub>1</sub><sup>2</sup>.

2. If $\ell_b > \ell_a$, recover $pk_U$ as $pk_U = T_{L-\ell_b,4}^{(a)}/e(Y_{L-\ell_b}^{(b)}, T_{L-\ell_b,3}^{(a)})$. If $\ell_b < \ell_a$, $pk_U$ can be obtained as $pk_U = T_{L-\ell_a,4}^{(b)}/e(Y_{L-\ell_a}^{(a)}, T_{L-\ell_a,3}^{(b)})$. In the case $\ell_a = \ell_b$, we must have $Y_{\ell_a} = Y_{\ell_b}$. Then, $\mathcal{B}$ computes $R_a = H(info_a, pk_{M_a})$, $R_b = H(info_b, pk_{M_b})$ and then $\kappa = (Z_{L-\ell_a}^{(a)}/Z_{L-\ell_b}^{(b)})^{1/(R_a-R_b)}$, which allows recovering $g^{sk_U} = Z_{L-\ell_a}^{(a)}/\kappa^{R_a}$ and thus $pk_U = e(g^{sk_U}, h)$.

The security of the scheme relies on the collision-resistance of $H$ and the intractability assumptions recalled in Section 2.3. More precisely, we state the following theorem for which a proof is given in the full version of the paper.

**Theorem 2.** *Assuming that $H$ is a collision-resistant hash function and that the SXDH, D3DH, TDH, D3DH, $q_w$-HSDH and the 2<sup>*L*+2</sup>-DDHI assumptions where $q_w$ denotes the number of $Q_{withdraw}$ queries all hold in (G<sub>1</sub>, G<sub>2</sub>), our e-cash scheme provides anonymity, balance, identification and weak-exculpability.*

The most difficult part of the security proof is the proof of anonymity. More precisely, when it comes to build a simulator, we need to simulate NIZK proofs
for pairing product equations of the form (2), which is non-trivial. Indeed, as noted in [31], this is only known to be possible when the target element of the equation (which lives in $G_T$) can be written as a pairing of known elements of $G_1$ and $G_2$. The problem is that, in equations like (2), some pairing values have to be gradually replaced by uniformly random values of $G_T$. To deal with this problem, we appeal to the D3DH assumption in a similar way to [33]. Namely, the D3DH input element $\Gamma$, which is either $g^{abc}$ or a random element of $G_1$, is available as a “pre-image” of the target pairing value and makes it possible to simulate proofs for pairing product equations at the expense of introducing auxiliary variables.

## References

1. M. H. Au, W. Susilo, Y. Mu. Practical Anonymous Divisible E-Cash from Bounded Accumulators. In *Financial Cryptography 2008*, LNCS 5143, pp. 287–301, 2008.

2. M. H. Au, Q. Wu, W. Susilo, Y. Mu. Compact E-Cash from Bounded Accumulator. In *CT-RSA'07*, LNCS 4377, pp. 178–195, 2007.

3. M. Belenkiy, M. Chase, M. Kohlweiss, and A. Lysyanskaya. P-signatures and noninteractive anonymous credentials. In *TCC'08*, LNCS 4948, pages 356–374, 2008.

4. M. Belenkiy, J. Camenisch, M. Chase, M. Kohlweiss, A. Lysyanskaya, H. Shacham. Randomizable Proofs and Delegatable Anonymous Credentials. In *Crypto'09*, LNCS 5677, pp. 108–125, 2009.

5. M. Belenkiy, M. Chase, M. Kohlweiss, and A. Lysyanskaya. Compact E-Cash and Simulatable VRFs Revisited. In *Pairing'09*, LNCS 5671, pp. 114–131, 2009.

6. M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In *ACM CCS'93*, pp. 62–73, 1993.

7. O. Blazy, S. Canard, G. Fuchsbauer, A. Gouget, H. Sibert, J. Traoré. Achieving Optimal Anonymity in Transferable E-Cash with a Judge. In *Africacrypt 2011*, LNCS 6737, pp. 206–223, 2011.

8. D. Boneh, C. Gentry, B. Waters. Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. In *Crypto'05*, LNCS 3621, pp. 258–275, 2005.

9. X. Boyen and B. Waters. Full-domain subgroup hiding and constant-size group signatures. In *PKC'07*, LNCS 4450, pp. 1–15, 2007.

10. J. Camenisch, S. Hohenberger, A. Lysyanskaya. Compact E-Cash. In *Eurocrypt'05*, LNCS 3494, pp. 302–321, 2005.

11. J. Camenisch, S. Hohenberger, A. Lysyanskaya. Balancing Accountability and Privacy Using E-Cash. In *SCN'06*, LNCS 4116, pp. 141–155, 2006.

12. J. Camenisch, M. Kohlweiss, C. Soriente. An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. In *PKC'09*, LNCS 5443, pp. 481–500, 2009.

13. J. Camenisch, A. Lysyanskaya, M. Meyerovich. Endorsed E-Cash In *IEEE Security & Privacy'07*, pp. 101–115, 2007.

14. S. Canard, A. Gouget. Divisible E-Cash Systems Can Be Truly Anonymous. In *Eurocrypt'07*, LNCS 4515, pp. 482–497, 2007.

15. S. Canard, A. Gouget, J. Traoré. Improvement of Efficiency in (Unconditional) Anonymous Transferable E-Cash. In *Financial Cryptography 2008*, LNCS 5143, pp 202–214, 2008.
16. S. Canard, A. Gouget. Anonymity in Transferable E-cash. In *ACNS'08*, LNCS 5037, pp. 207-223, 2008.

17. S. Canard, A. Gouget, E. Hufschmitt. A Handy Multi-coupon System. In *ACNS'06*, LNCS 3989, pp. 66-81, 2006.

18. S. Canard, A. Gouget. Multiple Denominations in E-cash with Compact Transaction Data. In *Financial Cryptography 2010*, LNCS 6052, pp. 82-97, 2010.

19. R. Canetti, O. Goldreich, S. Halevi. The Random Oracle Methodology, Revisited. In *STOC'98*, pp. 209-218, ACM Press, 1998.

20. A.-H. Chan, Y. Frankel, Y. Tsiounis. Easy Come - Easy Go Divisible Cash. In *Eurocrypt'98*, LNCS 1403, pp. 561-575, 1998.

21. M. Chase, A. Lysyanskaya. Simulatable VRFs with Applications to Multi-theorem NIZK. In *Crypto'07*, LNCS 4622, pp. 303-322, 2007.

22. D. Chaum. Blind Signatures for Untraceable Payments. In *Crypto'82*, pp. 199-203, 1982.

23. D. Chaum. Blind Signature Systems. In *Crypto'83*, p. 153, 1983.

24. D. Chaum, A. Fiat, M. Naor. Untraceable Electronic Cash. In *Crypto'88*, LNCS 403, pp. 319-327, 1988.

25. D. Chaum, T. Pedersen. Transferred Cash Grows in Size. In *Eurocrypt'92*, LNCS 658, pp. 390-407, 1992.

26. S. D'Amiano, G. Di Crescenzo. Methodology for Digital Money based on General Cryptographic Tools. In *Eurocrypt'94*, LNCS 950, pp. 156-170, 1994.

27. Y. Dodis. Efficient Construction of (Distributed) Verifiable Random Functions. In *PKC'03*, LNCS 2567, pp. 1-17, 2003.

28. Y. Dodis, A. Yampolskiy. A Verifiable Random Function with Short Proofs and Keys. In *PKC'05*, LNCS 3386, pp. 416-431, 2005.

29. M. K. Franklin, M. Yung. Secure and Efficient Off-Line Digital Money. In *ICALP'93*, LNCS 700, pp. 265-276, 1993.

30. G. Fuchsbauer, D. Pointcheval, D. Vergnaud. Transferable Constant-Size Fair E-Cash. In *CANS'09*, LNCS 5888, pp. 226-247, 2009.

31. J. Groth and A. Sahai. Efficient non-interactive proof systems for bilinear groups. In *Eurocrypt'08*, LNCS 4965, pp. 415-432, 2008.

32. S. Jarecki, V. Shmatikov. Efficient Two-Party Secure Computation on Committed Inputs. In *Eurocrypt'07*, LNCS 4515, pp. 97-114, 2007.

33. B. Libert, D. Vergnaud. Group Signatures with Verifier-Local Revocation and Backward Unlinkability in the Standard Model. In *CANS'09*, LNCS 5888, pp. 498-517, 2009.

34. S. Micali, M.-O. Rabin, S. Vadhan. Verifiable Random Functions. In *FOCS'99*, pp. 120-130, 1999.

35. T. Nakanishi, Y. Sugiyama. Unlinkable Divisible Electronic Cash. In *ISW'00*, LNCS 1975, pp. 121-134, 2000.

36. T. Okamoto. K. Ohta. Universal Electronic Cash. In *Crypto'91*, LNCS 576, pp. 324-337, 1991.

37. T. Okamoto. An Efficient Divisible Electronic Cash Scheme. In *Crypto'95*, LNCS 963, pp. 438-451, 1991.

38. J.-C. Pailles. New Protocols for Electronic Money. In *Auscrypt'92*, LNCS 718, pp. 263-274, 1992.

39. T. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In *Crypto'91*, LNCS 576, pp. 129-140, 1991.

40. Y. Tsiounis. Efficient Electronic Cash: New Notions and Techniques. PhD Thesis, Northeaster University, Boston, 1997.