% This is samplepaper.tex, a sample chapter demonstrating the
% LLNCS macro package for Springer Computer Science proceedings;
% Version 2.20 of 2017/10/04
%
\documentclass[runningheads]{llncs}
%
\usepackage{graphicx}
%\usepackage{hyperref}
\usepackage{amsmath,amssymb}
% Used for displaying a sample figure. If possible, figure files should
% be included in EPS format.
%
% If you use the hyperref package, please uncomment the following line
% to display URLs in blue roman font according to Springer's eBook style:
% \renewcommand\UrlFont{\color{blue}\rmfamily}

\usepackage[utf8]{inputenc}

\begin{document}
\title{Robust and Income-transparent Online E-Cash}
\maketitle

\begin{abstract}
  We present an anonymous e-cash protocol that protects against economic losses
  when protocols are aborted.  Furthermore, we ensure that customers have
  cryptographic evidence that they spent e-cash on a particular business
  transaction and introduce \emph{conservation} as an additional security
  property to anonymity and unforgeability, and preserve anonymity when wallets
  are restored from backup or synchronized with other devices.  We argue from
  this position that a protocol for unlinkable change is necessary even in
  schemes that provide divisibility. As a na\"ive implementation of a change
  protocol opens up the possibility of abuse for tax evasion, we define a new
  \emph{income transparency} security property.

  We furthermore show that an e-cash protocol that fulfills these properties
  can be used to implement Camenisch-style fair exchange, tick payments, and
  can be used to provide anonymous refunds.
\keywords{E-cash  \and blind signature \and key exchange}
\end{abstract}

\def\Z{\mathbb{Z}}

\def\mathperiod{.}
\def\mathcomma{,}

\newcommand*\ST[5]%
{\left#1\,#4\vphantom{#5} \;\right#2 \left. #5 \vphantom{#4}\,\right#3}

% uniform random selection from set
\newcommand{\randsel}[0]{\ensuremath{\xleftarrow{\text{\$}}}}

\newcommand{\Exp}[1]{\ensuremath{E\left[#1\right]}}

% oracles
\newcommand{\ora}[1]{\ensuremath{\mathcal{O}\mathsf{#1}}}
% oracle set
\newcommand{\oraSet}[1]{\ensuremath{\mathcal{O}\textsc{#1}}}
% algorithm
\newcommand{\algo}[1]{\ensuremath{\mathsf{#1}}}
% party
\newcommand{\prt}[1]{\ensuremath{\mathcal{#1}}}
% long-form variable
\newcommand{\V}[1]{\ensuremath{\mathsf{#1}}}

% probability with square brackets of the right size
\newcommand{\Prb}[1]{\ensuremath{\Pr\left [#1 \right ]}}

\newcommand{\mycomment}[1]{~\\ {\small \textcolor{blue}{({#1})}}}

%\theoremstyle{definition}
%\newtheorem{definition}{Definition}[section]
%\theoremstyle{corollary}
%\newtheorem{corollary}{Corollary}[section]

\section{Introduction}
Anonymous e-cash, originally invented by Chaum in 1982 \cite{chaum1983blind},
enables customers to withdraw digital cash tokens from a bank and then
anonymously spend them with merchants.  Cryptographic protocols allow
the withdrawal of coins to remain unlinkable to the spending operations.
Coins are either checked online for double-spending, or double-spending
reveals the identity of the culprit.

In recent years, many advances have been made on e-cash, improving the efficiency
for withdrawing/spending arbitary values to constant time and proving security
in the standard model \cite{pointcheval2017cut}.  Most attention was given to schemes
that allow offline spending.

With the rising ubiquity of mobile Internet, IoT and smart phones, online
e-cash could gain importance, as it does not suffer from the difficulty of
prosecuting double-spenders or convicting users with faulty hardware as
double-spenders.  On mobile devices, backup and synchronization is especially
important, and unlike smart-cards that interact with payment terminals or ATMs,
communication is asynchronous and likely to be interrupted.  E-cash protocols
need to be robust in these failure scenarios and preserve anonymity properties, even
when the wallet's state is synchronized with other devices or restored from backup.

We describe new security properties for e-cash that preserve anonymity without
loss of funds in certain failure scenarios, which are made possible with an
anonymous change protocol \cite{brickell1995trustee}.  We improve a na\"ive
change protocol so that is cannot be used for hiding transaction from tax
authorities as a merchant.  An e-cash variant with these property easily lends
itself for the implementation of fair exchange \cite{camenisch2007endorsed} and
tick payments \cite{pedersen1996electronic}.


\section{Model and Syntax}

We consider a Chaum-style~\cite{chaum1983blind}
payment system with an exchange (Chaum: bank) and multiple,
dynamically created customers and merchants.
We model withdrawing digital coins, spending them with
merchants and subsequently depositing them at the exchange, as well as
obtaining unlinkable change for partially spent coins with a
``refresh'' protocol.

The exchange offers digital coins in multiple denominations.  We mostly
ignore the denomination
values here, including their impact on anonymity, in keeping with existing
literature~\cite{camenisch2007endorsed,pointcheval2017cut}.  For anonymity, we
believe this amounts to assuming that all customers have similar financial
behavior.  We note logarithmic storage, computation and bandwidth demands
denominations distributed by powers of a fixed constant.

%We do not model fees taken by the exchange.  Reserves\footnote{%
%  ``Reserve'' is Taler's terminology for funds submitted to the exchange that
%  can be converted to digital coins.
%}
%are also omitted.
Coins can be partially spent by specifying a fraction $0 < f \le 1$ of the
total value associated with the coin's denomination.  Unlinkable change below
the smallest denomination cannot be given.  In
practice the unspendable, residual value should be seen as a fee
charged by the exchange.

Spending multiple coins is modeled non-atomically: to spend (fractions
of) multiple coins, they must be spent one-by-one.  The individual
spend/deposit operations are correlated by a unique identifier for the
transaction.
%In practice this identifier is the hash $\V{transactionId} =
%H(\V{contractTerms})$ of the contract terms\footnote{The contract terms
%are a digital representation of an individual offer for a certain product or service the merchant sells
%for a certain price.}.  Contract terms include a nonce to make them
%unique, that merchant and customer agreed upon.  Note that this transaction
%identifier and the correlation between multiple spend operations for one
%payment need not be disclosed to the exchange (it might, however, be necessary
%to reveal during a detailed tax audit of the merchant):  When spending the $i$-th coin
%for the transaction with the identifier $\V{transactionId}$, messages to the
%exchange would only contain $H(i \Vert \V{transactionId})$.  This is preferable
%for merchants that might not want to disclose to the exchange the individual
%prices of products they sell to customers, but only the total transaction
%volume over time.  For simplicity, we do not include this extra feature in our
%model.

Our system model tracks the total amount of
coins withdrawn by each customer.
Customers are identified by their public key $\V{pkCustomer}$.  Every customer's wallet
keeps track of the following data:
\begin{itemize}
  \item $\V{wallet}[\V{pkCustomer}]$ contains sets of the customer's coin records,
   which individually consist of the coin key pair, denomination and exchange's signature.
  \item $\V{acceptedContracts}[\V{pkCustomer}]$ contains the sets of
    transaction identifiers accepted by the customer during spending
    operations, together with coins spent for it and their contributions $0 < f
    \le 1$.
  \item $\V{withdrawIds}[\V{pkCustomer}]$ contains the withdraw identifiers of
    all withdraw operations that were created for this customer.
  \item $\V{refreshIds}[\V{pkCustomer}]$ contains the refresh identifiers of
    all refresh operations that were created for this customer.
\end{itemize}

\noindent
The exchange in our model keeps track of the following data:
\begin{itemize}
  \item $\V{withdrawn}[\V{pkCustomer}]$ contains the total amount withdrawn by
    each customer, i.e. the sum of the financial value of the denominations for
    all coins that were withdrawn by $\V{pkCustomer}$.
  \item The overspending database of the exchange is modeled by
    $\V{deposited}[\V{pkCoin}]$ and $\V{refreshed}[\V{pkCoin}]$, which record
    deposit and refresh operations respectively on each coin.  Note that since
    partial deposits and multiple refreshes to smaller denominations are
    possible, one deposit and multiple refresh operations can be recorded for a
    single coin.
\end{itemize}

We say that a coin is \emph{fresh} if it appears in neither the $\V{deposited}$
or $\V{refreshed}$ lists nor in $\V{acceptedContracts}$.  We say that a coin is
being $\V{overspent}$ if recording an operation in $\V{deposited}$ or
$\V{refreshed}$ would cause the total spent value from both lists to exceed
the value of the coin's denomination.
%
Note that the adversary does not have direct read or write access to these
values; instead the adversary needs to use the oracles (defined in Section~\ref{sec:oracles}) to
interact with the system.

We parameterize our system with two security parameters:  The general security
parameter $\lambda$, and the refresh security parameter $\kappa$.  While
$\lambda$ determines the length of keys and thus the security level, using a
larger $\kappa$ will only decrease the success chance of malicious merchants
conspiring with customers to obtain unreported (and thus untaxable) income.

\subsection{Algorithms and Protocols} \label{sec:algorithms}

Our e-cash scheme is modeled by the following probabilistic\footnote{Our
instantiation is not probabilistic (except key
generation), but we do not want to prohibit this for other instantiations.}
polynomial-time algorithms and interactive protocols.  The notation $P(X_1,\dots,X_n)$
stands for a party $P \in \{\prt{E}, \prt{C}, \prt{M}\}$ (Exchange, Customer
and Merchant respectively) in an interactive protocol, with $X_1,\dots,X_n$
being the (possibly private) inputs contributed by the party to the protocol.
Interactive protocols can access the state maintained by party $P$.

While the adversary can freely execute the interactive protocols by creating
their own parties, the adversary is not given direct access to the private data
of parties maintained by the challenger in the security games which we define later.

\begin{itemize}
  \item $\algo{ExchangeKeygen}(1^{\lambda}, 1^{\kappa}, \mathfrak{D}) \mapsto (\V{sksE}, \V{pksE})$:
    Algorithm executed to generate keys for the exchange, with general security
    parameter $\lambda$ and refresh security parameter $\kappa$, both given as
    unary numbers.  The denomination specification $\mathfrak{D} = d_1,\dots,d_n$ is a
    finite sequence of positive rational numbers that defines the financial
    value of each generated denomination key pair.  We henceforth use $\mathfrak{D}$ to
    refer to some appropriate denomination specification, but our analysis is
    independent of a particular choice of $\mathfrak{D}$.

    The algorithm generates the exchange's master signing key pair
    $(\V{skESig}, \V{pkESig})$ and denomination secret and public keys
    $(\V{skD}_1, \dots, \V{skD}_n), (\V{pkD}_1, \dots, \V{pkD}_n)$.  We write
    $D(\V{pkD}_i)$, where $D : \{\V{pkD}_i\} \rightarrow \mathfrak{D}$ to look
    up the financial value of denomination $\V{pkD_i}$.

    We collectively refer to the exchange's secrets by $\V{sksE}$ and to the exchange's
    public keys together with $\mathfrak{D}$ by $\V{pksE}$.

  \item $\algo{CustomerKeygen}(1^\lambda,1^\kappa) \mapsto (\V{skCustomer}, \V{pkCustomer})$:
    Key generation algorithm for customers with security parameters $\lambda$
    and $\kappa$.

  \item $\algo{MerchantKeygen}(1^\lambda,1^\kappa) \mapsto (\V{skMerchant},
    \V{pkMerchant})$: Key generation algorithm for merchants.  Typically the
    same as \algo{CustomerKeygen}.

  \item $\algo{WithdrawRequest}(\prt{E}(\V{sksE}, \V{pkCustomer}),
    \prt{C}(\V{skCustomer}, \V{pksE}, \V{pkD})) \mapsto (\mathcal{T}_{WR},
    \V{wid})$: Interactive protocol between the exchange and a customer that
    initiates withdrawing a single coin of a particular denomination.

    The customer obtains a withdraw identifier $\V{wid}$ from the protocol
    execution and stores it in $\V{withdrawIds}[\V{pkCustomer}]$.

    The \algo{WithdrawRequest} protocol only initiates a withdrawal.  The coin
    is only obtained and stored in the customer's wallet by executing the
    \algo{WithdrawPickup} protocol on the withdraw identifier \V{wid}.

    The customer and exchange persistently store additional state (if required
    by the instantiation) such that the customer can use $\algo{WithdrawPickup}$

    Returns a protocol transcript $\mathcal{T}_{WR}$ of all messages exchanged
    between the exchange and customer, as well as the withdraw identifier
    \V{wid}.

  \item $\algo{WithdrawPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}),
    \prt{C}(\V{skCustomer}, \V{pksE}, \V{wid})) \mapsto (\mathcal{T}_{WP},
    \V{coin})$: Interactive protocol between the exchange and a customer to
    obtain the coin from a withdraw operation started with
    $\algo{WithdrawRequest}$, identified by the withdraw identifier $\V{wid}$.

    The first time $\algo{WithdrawPickup}$ is run with a particular withdraw
    identifier $\V{wid}$, the exchange increments
    $\V{withdrawn}[\V{pkCustomer}]$ by $D(\V{pkD})$, where $\V{pkD}$ is the
    denomination requested in the corresponding $\algo{WithdrawRequest}$
    execution.  How exactly $\V{pkD}$ is restored depends on the particular instantiation.

    The resulting coin $\V{coin} := (\V{skCoin}, \V{pkCoin}, \V{pkD}, \V{coinCert})$,
    consisting of secret key $\V{skCoin}$, public key
    $\V{pkCoin}$, denomination public key $\V{pkD}$ and certificate $\V{coinCert}$ from the exchange,
    is stored in the customers wallet $\V{wallet}[\V{pkCustomer}]$.

    Executing the $\algo{WithdrawPickup}$ protocol multiple times with the same
    customer and the same withdraw identifier does not result in any change of
    the customer's withdraw balance $\V{withdrawn}[\V{pkCustomer}]$,
    and results in \mbox{(re-)}adding the same coin to the customer's wallet.

    Returns a protocol transcript $\mathcal{T}_{WP}$ of all messages exchanged
    between the exchange and customer.

  \item $\algo{Spend}(\V{transactionId}, f, \V{coin}, \V{pkMerchant}) \mapsto \V{depositPermission}$:
    Algorithm to produce and sign a deposit permission \V{depositPermission}
    for a coin under a particular transaction identifier.  The fraction $0 < f \le 1$ determines the
    fraction of the coin's initial value that will be spent.
%
    The contents of the deposit permission depend on the instantiation, but it
    must be possible to derive the public coin identifier $\V{pkCoin}$ from
    them.

  \item $\algo{Deposit}(\prt{E}(\V{sksE}, \V{pkMerchant}), \prt{M}(\V{skMerchant}, \V{pksE}, \V{depositPermission})) \mapsto \mathcal{T}_D$:
    Interactive protocol between the exchange and a merchant.
%
    From the deposit permission we obtain the $\V{pkCoin}$ of the coin to be
    deposited.  If $\V{pkCoin}$ is being overspent, the protocol is aborted with
    an error message to the merchant.
%
    On success, we add $\V{depositPermission}$ to $\V{deposited}[\V{pkCoin}]$.
%
    Returns a protocol transcript $\mathcal{T}_D$ of all messages exchanged
    between the exchange and merchant.

  \item $\algo{RefreshRequest}(\prt{E}(\V{sksE}), \prt{C}(\V{pkCustomer}, \V{pksE}, \V{coin}_0, \V{pkD}_u))
      \rightarrow (\mathcal{T}_{RR}, \V{rid})$
    Interactive protocol between exchange and customer that initiates a refresh
    of $\V{coin}_0$.  Together with $\algo{RefreshPickup}$, it allows the
    customer to convert $D(\V{pkD}_u)$ of the remaining value on coin
    $\V{coin}_0 = (\V{skCoin}_0, \V{pkCoin}_0, \V{pkD}_0, \V{coinCert}_0)$
    into a new, unlinkable coin $\V{coin}_u$ of denomination $\V{pkD}_u$.
%
    Multiple refreshes on the same coin are allowed, but each run subtracts the
    respective financial value of $\V{coin}_u$ from the remaining value of
    $\V{coin}_0$.
%
    The customer only records the refresh operation identifier $\V{rid}$ in
    $\V{refreshIds}[\V{pkCustomer}]$, but does not yet obtain the new coin.  To
    obtain the new coin, \algo{RefreshPickup} must be used.
%
    Returns the protocol transcript $\mathcal{T}_{RR}$ and a refresh identifier $\V{rid}$.

  \item $\algo{RefreshPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}),
      \prt{C}(\V{skCustomer}, \V{pksE}, \V{rid}) \rightarrow (\mathcal{T}_{RP}, \V{coin}_u)$:
    Interactive protocol between exchange and customer to obtain the new coin
    for a refresh operation previously started with \algo{RefreshRequest},
    identified by the refresh identifier $\V{rid}$.
%
    The first time \algo{RefreshPickup} is run for a particular refresh
    identifier, the exchange tries to record the refresh operation of value $D(\V{pkD}_u)$
    in $\V{refreshed}[\V{pkCoin}_0]$, with $\V{pkD}_u$ and $\V{pkCoin}_0$ taken
    from the corresponding $\algo{RefreshRequest}$ that resulted in $\V{rid}$.
    How exactly the exchange obtains $\V{pkD}_u$ and $\V{pkCoin}_0$ depends on
    the instantiation.
%
    If $\V{pkCoin}_0$ is being overspent, the refresh operation is not recorded
    in $\V{refreshed}[\V{pkCoin}_0]$, the exchange sends the customer the
    protocol transcript of the previous deposits and refreshes and aborts the
    protocol.
%
    If the customer \prt{C} plays honestly in \algo{RefreshRequest} and
    \V{RefreshPickup}, the unlinkable coin $\V{coin}_i$ they obtain as change
    will be stored in their wallet $\V{wallet}[\V{pkCustomer}]$.  If \prt{C} is
    caught playing dishonestly, the \algo{RefreshPickup} protocol aborts.
%
    An honest customer must be able to repeat a \algo{RefreshPickup} with the
    same $\V{rid}$ multiple times and (re-)obtain the same coin, even if
    previous $\algo{RefreshPickup}$ executions were aborted.
%
    Returns a protocol transcript $\mathcal{T}_{RP}$.

  \item $\algo{Link}(\prt{E}(\V{sksE}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{coin}_0)) \rightarrow (\mathcal{T}, (\V{coin}_1, \dots, \V{coin}_n))$:
    Interactive protocol between exchange and customer.  If $\V{coin}_0$ is a
    coin that was refreshed, the customer can recompute all the coins obtained
    from previous refreshes on $\V{coin}_0$, with data obtained from the
    exchange during the protocol.  These coins are added to the customer's
    wallet $\V{wallet}[\V{pkCustomer}]$ and returned.

\end{itemize}

\subsection{Oracles} \label{sec:oracles}

%We now specify how the adversary can interact with the system by defining
%oracles.  Oracles are queried by the adversary, and upon a query the challenger
%will act according to the oracle's specification.  Note that the adversary for
%the different security games is run with specific oracles, and does not
%necessarily have access to all oracles simultaneously.

We refer to customers in the parameters to an oracle query simply by their
public key. The adversary needs the ability to refer to coins to trigger
operations such as spending and refresh, but to model anonymity we cannot give
the adversary access to the coins' public keys directly.  Therefore we allow
the adversary to use the (successful) transcripts of the withdraw, refresh and
link protocols to indirectly refer to coins.  We refer to this as a coin handle
$\mathcal{H}$.  Since the execution of a link protocol results in a transcript
$\mathcal{T}$ that can contain multiple coins, the adversary needs to select a
particular coin from the transcript via the index $i$ as $\mathcal{H} =
(\mathcal{T}, i)$.  The respective oracle tries to find the coin that resulted
from the transcript given by the adversary.  If the transcript has not been
seen before in the execution of a link, refresh or withdraw protocol; or the
index for a link transcript is invalid, the oracle returns an error to the
adversary.

In oracles that trigger the execution of one of the interactive protocols
defined in Section~\ref{sec:algorithms}, we give the adversary the ability to actively
control the communication channels between the exchange, customers and
merchants; i.e. the adversary can effectively record, drop, modify and inject
messages during the execution of the interactive protocol. Note that this
allows the adversary to leave the execution of an interactive protocol in an
unfinished state, where one or more parties are still waiting for messages.  We
use $\mathcal{I}$ to refer to a handle to interactive protocols where the
adversary can send and receive messages.

\begin{itemize}
  \item $\ora{AddCustomer}() \mapsto \V{pkCustomer}$:
    Generates a key pair $(\V{skCustomer}, \V{pkCustomer})$ using the
    \algo{CustomerKeygen} algorithm, and sets
      $\V{withdrawn}[\V{pkCustomer}] := 0,
      \V{acceptedContracts}[\V{pkCustomer}] := \{ \},
      \V{wallet}[\V{pkCustomer}] := \{\},
      \V{withdrawIds}[\V{pkCustomer}] := \{\},
      \V{refreshIds}[\V{pkCustomer}] := \{\}$.
    Returns the public key of the newly created customer.

    There is no separate oracle for creating merchants, since no information is
    tracked for merchants; generating a key pair with \algo{MerchantKeygen}
    suffices.

  \item $\ora{AddMerchant}() \mapsto \V{pkMerchant}$L
    Generate a key pair $(\V{skMerchant}, \V{pkMerchant})$ using the
    \algo{MerchantKeygen} algorithm.

    Returns the public key of the newly created merchant.

  \item $\ora{SendMessage}(\mathcal{I}, P_1, P_2, m) \mapsto ()$:
    Send message $m$ on the channel from party $P_1$ to party $P_2$ in the
    execution of interactive protocol $\mathcal{I}$.

  \item $\ora{ReceiveMessage}(\mathcal{I}, P_1, P_2) \mapsto m$:
    Read message $m$ in the channel from party $P_1$ to party $P_2$ in the execution
    of interactive protocol $\mathcal{I}$.  If no message is queued in the channel,
    return $m = \bot$.

  \item $\ora{WithdrawRequest}(\V{pkCustomer}, \V{pkD}) \mapsto \mathcal{I}$:
    Triggers the execution of the \algo{WithdrawRequest} protocol.  the
    adversary full control of the communication channels between customer and
    exchange.

  \item $\ora{WithdrawPickup}(\V{pkCustomer}, \V{pkD}, \mathcal{T}) \mapsto \mathcal{I}$:
    Triggers the execution of the \algo{WithdrawPickup} protocol, additionally giving
    the adversary full control of the communication channels between customer and exchange.

    The customer and withdraw identifier $\V{wid}$ are obtained from the \algo{WithdrawRequest} transcript $\mathcal{T}$.

  \item $\ora{RefreshRequest}(\mathcal{H}, \V{pkD}) \mapsto \mathcal{I}$:  Triggers the execution of the
    \algo{RefreshRequest} protocol with the coin identified by coin handle
    $\mathcal{H}$, additionally giving the adversary full control over the communication channels
    between customer and exchange.

  \item $\ora{RefreshPickup}(\mathcal{T}) \mapsto \mathcal{I}$:
    Triggers the execution of the \algo{RefreshPickup} protocol, where the customer and refresh identifier $\V{rid}$
    are obtained from the $\algo{RefreshRequest}$ protocol transcript $\mathcal{T}$.

    Additionally gives the adversary full control over the communication channels
    between customer and exchange.

  \item $\ora{Link}(\mathcal{H}) \mapsto \mathcal{I}$:  Trigger the execution of the
    \algo{Link} protocol for the coin referenced by handle $\mathcal{H}$,
    additionally giving the adversary full control over the communication channels
    between customer and exchange.

  \item $\ora{Spend}(\V{transactionId}, \V{pkCustomer}, \mathcal{H}, \V{pkMerchant}) \mapsto \V{depositPermission}$:
    Makes a customer sign a deposit permission over a coin identified by handle
    $\mathcal{H}$.  Returns the deposit permission on success, or $\bot$ if $\mathcal{H}$
    is not a coin handle that identifies a coin.

    Note that $\ora{Spend}$ can be used to generate deposit permissions that,
    when deposited, would result in an error due to overspending

    Adds $(\V{transactionId}, \V{depositPermission})$ to $\V{acceptedContracts}[\V{pkCustomer}]$.

  \item $\ora{Share}(\mathcal{H}, \V{pkCustomer}) \mapsto ()$:
    Shares a coin (identified by handle $\mathcal{H}$) with the customer
    identified by $\V{pkCustomer}$, i.e. puts the coin identified by $\mathcal{H}$
    into $\V{wallet}[\V{pkCustomer}]$.  Intended to be used by the adversary in attempts to
    violate income transparency.

    Note that this trivially violates anonymity (by sharing with a corrupted customer), thus the usage must
    be restricted in some games.

    % the share oracle is the reason why we don't need a second withdraw oracle

  \item $\ora{CorruptCustomer}(\V{pkCustomer})\mapsto
    \newline{}\qquad (\V{skCustomer}, \V{wallet}[\V{pkCustomer}],\V{acceptedContracts}[\V{pkCustomer}],
    \newline{}\qquad \phantom{(}\V{refreshIds}[\V{pkCustomer}], \V{withdrawIds}[\V{pkCustomer}])$:

    Used by the adversary to corrupt a customer, giving the adversary access to
    the customer's secret key, wallet, withdraw/refresh identifiers and accepted contracts.

    Permanently marks the customer as corrupted.  There is nothing ``special''
    about corrupted customers, beyond that the adversary has used
    \ora{CorruptCustomer} on them in the past.  The adversary cannot modify
    corrupted customer's wallets directly, and must use the oracle again to
    obtain an updated view on the corrupted customer's private data.

  \item $\ora{Deposit}(\V{depositPermission}) \mapsto \mathcal{I}$:
    Triggers the execution of the \algo{Deposit} protocol, additionally giving
    the adversary full control over the communication channels between merchant and exchange.

    Returns an error if the deposit permission is addressed to a merchant that was not registered
    with $\ora{AddMerchant}$.

    This oracle does not give the adversary new information, but is used to
    model the situation where there might be multiple conflicting deposit
    permissions generated via $\algo{Spend}$, but only a limited number can be
    deposited.
\end{itemize}

We write \oraSet{All} for the set of all the oracles we just defined.
We also let $\oraSet{NoShare} := \oraSet{All} - \{ \ora{Share} \}$
stand for access to all oracles except the share oracle.

The exchange does not need to be corrupted with an oracle. A corrupted exchange
is modeled by giving the adversary the appropriate oracles and the exchange
secret key from the exchange key generation.

If the adversary determines the exchange's secret key during the setup,
invoking \ora{WithdrawRequest}, \ora{WithdrawPickup}, \ora{RefreshRequest},
\ora{RefreshPickup} or \ora{Link} can be seen as the adversary playing the
exchange.  Since the adversary is an active man-in-the-middle in these oracles,
it can drop messages to the simulated exchange and make up its own response.
If the adversary calls these oracles with a corrupted customer, the adversary
plays as the customer.

%\begin{mdframed}
%The difference between algorithms and interactive protocols
%is that the ``pure'' algorithms only deal with data, while the interactive protocols
%take ``handles'' to parties that are communicating in the protocol.  The adversary can
%always execute algorithms that don't depend on handles to communication partners.
%However the adversary can't run the interactive protocols directly, instead it must
%rely on the interaction oracles for it.  Different interaction oracles might allow the
%adversary to play different roles in the same interactive protocol.
%
%While most algorithms in Taler are not probabilistic, we still say that they are, since
%somebody else might come up with an instantiation of Taler that uses probabilistic algorithms,
%and then the games should still apply.
%
%
%While we do have a \algo{Deposit} protocol that's used in some of the games, having a deposit oracle is not necessary
%since it does not give the adversary any additional power.
%\end{mdframed}

\section{Games}

We now define four security games (anonymity, conservation, unforgeability and
income transparency) that are later used to define security properties for
our protocol.  Similar to \cite{bellare2006code} we assume that the game and adversary
terminate in finite time, and thus random choices made by the challenger and
adversary can be taken from a finite sample space.

All games except income transpacency return $1$ to indicate that the adversary
has won and $0$ to indicate that the adversary has lost.  The income
transparency game returns $0$ if the adversary has lost, and a positive
``laundering ratio'' if the adversary won.

\subsection{Anonymity}
Intuitively, an adversary~$\prt{A}$ who controls the exchange and merchants wins the
anonymity game if they have a non-negligible advantage in correlating spending operations
with the withdrawal or refresh operations that created a coin used in the
spending operation.

Let $b$ be the bit that will determine the mapping between customers and spend
operations, which the adversary must guess.

We define a helper procedure
\begin{equation*}
  \algo{Refresh}(\prt{E}(\V{sksE}), \prt{C}(\V{pkCustomer}, \V{pksE}, \V{coin}_0)) \mapsto \mathfrak{R}
\end{equation*}
that refreshes the whole remaining amount on $\V{coin}_0$ with repeated application of $\algo{RefreshRequest}$
and $\algo{RefreshPickup}$ using the smallest possible set of target denominations, and returns all protocol transcripts
in $\mathfrak{R}$.

\begin{figure}
\fbox{\begin{minipage}{\textwidth}
\small
\noindent $\mathit{Exp}_{\prt{A}}^{anon}(1^\lambda, 1^\kappa, b)$:
\vspace{-0.5\topsep}
\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(\V{sksE}, \V{pksE}, \V{skM}, \V{pkM}) \leftarrow {\prt{A}}()$
  \item $(\V{pkCustomer}_0, \V{pkCustomer}_1, \V{transactionId}_0, \V{transactionId}_1, f) \leftarrow {\prt{A}}^{\oraSet{NoShare}}()$
  \item Select distinct fresh coins
    \begin{align*}
      \V{coin}_0 &\in \V{wallet}[\V{pkCustomer}_0]\\
      \V{coin}_1 &\in \V{wallet}[\V{pkCustomer}_1]
    \end{align*}
    Return $0$ if either $\V{pkCustomer}_0$ or $\V{pkCustomer}_1$ are not registered customers with sufficient fresh coins,
    or an oracle has been called with the coin handle for $\V{coin}_0$ or $\V{coin}_1$.
  \item  For $i \in \{0,1\}$ run
      \begin{align*}
        &\V{dp_i} \leftarrow \algo{Spend}(\V{transactionId}_i, f, \V{coin}_{i-b}, \V{pkM}) \\
        &\algo{Deposit}(\prt{A}(), \prt{M}(\V{skM}, \V{pksE}, \V{dp}_i)) \\
        &\mathfrak{R}_i \leftarrow \algo{Refresh}(\prt{A}(), \prt{C}(\V{pkCustomer}_i, \V{pksE}, \V{coin}_{i-b}))
      \end{align*}
  \item $b' \leftarrow {\cal A}^{\oraSet{NoShare}}(\mathfrak{R}_0, \mathfrak{R}_1)$ \\
  \item Return $0$ if $\ora{Spend}$ was used by the adversary on the coin handles
    for $\V{coin}_0$ or $\V{coin}_1$ or $\ora{CorruptCustomer}$ was used on $\V{pkCustomer}_0$ or $\V{pkCustomer}_1$.
  \item If $b = b'$ return $1$, otherwise return $0$.
\end{enumerate}
\end{minipage}}
\end{figure}

Note that unlike other anonymity games defined in the literature (such as
\cite{pointcheval2017cut}), our anonymity game always lets both customers spend
in order to avoid having to hide the missing coin in one customer's wallet
from the adversary.

\subsection{Conservation}
The adversary wins the conservation game if it can bring an honest customer in a
situation where the spendable financial value left in the user's wallet plus
the value spent for transactions known to the customer is less than the value
withdrawn by the same customer through by the exchange.

In practice, this property is necessary to guarantee that aborted or partially
completed withdrawals, payments or refreshes, as well as other (transient)
misbehavior from the exchange or merchant do not result in the customer losing
money or privacy.

\begin{figure}
\fbox{\begin{minipage}{\textwidth}
\small
\noindent $\mathit{Exp}_{\cal A}^{conserv}(1^\lambda, 1^\kappa)$:
\vspace{-0.5\topsep}
\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(\V{sksE}, \V{pksE}) \leftarrow \mathrm{ExchangeKeygen}(1^\lambda, 1^\kappa, M)$
  \item $\V{pkCustomer} \leftarrow {\cal A}^{\oraSet{NoShare}}(\V{pksE})$
  \item Return $0$ if $\V{pkCustomer}$ is a corrupted user.
  \item \label{game:conserv:run} Run $\algo{WithdrawPickup}$ for each withdraw identifier $\V{wid}$
    and $\algo{RefreshPickup}$ for each refresh identifier $\V{rid}$ that the user
    has recorded in $\V{withdrawIds}$ and $\V{refreshIds}$.  Run $\algo{Deposit}$
    for all deposit permissions in $\V{acceptedContracts}$.
  \item Let $v_{C}$ be the total financial value left on valid coins in $\V{wallet}[\V{pkCustomer}]$,
    i.e. the denominated values minus the spend/refresh operations recorded in the exchange's database.
    Let $v_{S}$ be the total financial value of contracts in $\V{acceptedContracts}[\V{pkCustomer}]$.
  \item Return $1$ if $\V{withdrawn}[\V{pkCustomer}] > v_{C} + v_{S}$.
\end{enumerate}
\end{minipage}}
\end{figure}

Hence we ensure that:
\begin{itemize}
  \item if a coin was spent, it was spent for a contract that the customer
    knows about, i.e. in practice the customer could prove that they ``own'' what they
    paid for,
  \item if a coin was refreshed, the customer ``owns'' the resulting coins,
    even if the operation was aborted, and
  \item if the customer withdraws, they can always obtain a coin whenever the
    exchange accounted for a withdrawal, even when protocol executions are
    intermittently aborted.
\end{itemize}

We do not give the adversary access to the \ora{Share} oracle,
which naively lets them win the conservation game, because doing so
correctly requires tracking the corrupted customers more carefully,
which harms our exposition.
In practice, conservation only holds for customers that do not share
coins with parties that they do not fully trust.

\subsection{Unforgeability}

Intuitively, adversarial customers win if they can obtain more valid coins than
they legitimately withdraw.

\begin{figure}
\fbox{\begin{minipage}{\textwidth}
\small
\noindent $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, 1^\kappa)$:
\vspace{-0.5\topsep}
\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$
  \item $(C_0, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{All}}(pkExchange)$
  \item Return $0$ if any $C_i$ is not of the form $(\V{skCoin}, \V{pkCoin}, \V{pkD}, \V{coinCert})$
    or any $\V{coinCert}$ is not a valid signature by $\V{pkD}$ on the respective $\V{pkCoin}$.
  \item Return $1$ if the sum of the unspent value of valid coins in $C_0
    \dots, C_\ell$ exceeds the amount withdrawn by corrupted
    customers, return $0$ otherwise.
\end{enumerate}
\end{minipage}}
\end{figure}


\subsection{Income Transparency}

Intuitively, the adversary wins if coins are in exclusive control of corrupted
customers, but the exchange has no record of withdrawal or spending for them.
This presumes that the adversary cannot delete from non-corrupted customer's
wallets, even though it can use oracles to force protocol interactions of
non-corrupted customers.

For practical e-cash systems, income transparency disincentivizes the emergence
of ``black markets'' among mutually distrusting customers, where currency
circulates without the transactions being visible.  This is in contrast to some
other proposed e-cash systems and cryptocurrencies, where disintermediation is
an explicit goal. The Link protocol introduces the threat of losing exclusive
control of coins (despite having the option to refresh them) that were received
without being visible as income to the exchange.

\begin{figure}
\fbox{\begin{minipage}{\textwidth}
\small
\noindent $\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)$:
\vspace{-0.5\topsep}
\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$
  \item $(\V{coin}_1, \dots, \V{coin}_\ell) \leftarrow \mathcal{A}^{\oraSet{All}}(pkExchange)$

    (The $\V{coin}_i$ must be coins, including secret key and signature by the
    denomination, for the adversary to win. However these coins need not be
    present in any honest or corrupted customer's wallet.)
  \item\label{game:income:spend} Augment the wallets of all non-corrupted customers with their
    transitive closure using the \algo{Link} protocol.
    Mark all remaining value on coins in wallets of non-corrupted customers as
    spent in the exchange's database.
  \item Let $L$ denote the sum of unspent value on valid coins in $(\V{coin}_1, \dots\, \V{coin}_\ell)$,
    after accounting for the previous update of the exchange's database.
    Also let $w'$ be the sum of coins withdrawn by corrupted customers.
    Then $p := L - w'$ gives the adversary's untaxed income.
  \item Let $w$ be the sum of coins withdrawn by non-corrupted customers, and
    $s$ be the value marked as spent by non-corrupted customers, so that
    $b := w - s$ gives the coins lost during refresh, that is the losses incurred attempting to hide income.
  \item If $b+p \ne 0$, return $p \over b + p$, i.e. the laundering ratio for attempting to obtain untaxed income.  Otherwise return $0$.
\end{enumerate}
\end{minipage}}
\end{figure}


\section{Security Definitions}\label{sec:security-properties}
We now give security definitions based upon the games defined in the previous
section.

\begin{definition}[Anonymity]
  We say that an e-cash scheme satisfies \emph{anonymity} if the success
  probability $\Prb{b \randsel \{0,1\}: \mathit{Exp}_{\cal A}^{anon}(1^\lambda,
  1^\kappa, b) = 1}$ of the anonymity game is negligibly close to $2^{-\lambda}$ for any
  polynomial time adversary~$\mathcal{A}$.
\end{definition}

\begin{definition}[Conservation]
  We say that an e-cash scheme satisfies \emph{conservation} if
  the success probability $\Prb{\mathit{Exp}_{\cal A}^{conserv}(1^\lambda, 1^\kappa) = 1}$
  of the conservation game is negligible for any polynomial time adversary~$\mathcal{A}$.
\end{definition}

\begin{definition}[Unforgeability]
  We say that an e-cash scheme satisfies \emph{unforgeability} if the success
  probability $\Prb{\mathit{Exp}_{\cal A}^{forge}(1^\lambda, 1^\kappa) = 1}$ of
  the unforgeability game is negligible for any polynomial time adversary
  $\mathcal{A}$.
\end{definition}


\begin{definition}[Weak Income Transparency]
  We say that an e-cash scheme satisfies \emph{weak income transparency}
  if, for any polynomial time adversary~$\mathcal{A}$,
  the return value of the the income transparency game satisfies
  \begin{equation}\label{eq:income-transparency-expectation}
    E\left[\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)\right] \le {1\over\kappa} \mathperiod
  \end{equation}
  In (\ref{eq:income-transparency-expectation}), the expectation runs over
  any probability space used by the adversary and challenger.
\end{definition}

For some instantiations, e.g. ones based on zero knowledge proofs, $\kappa$
might be a security parameter in the traditional sense.  However for an e-cash
scheme to be useful in practice, the adversary need not have only
negligible success probability in the income transparency game.
It suffices that the financial losses of the adversary in the game are a
deterrent, after all our purpose of the game is to characterize tax evasion.


\section{Instantiation}

We give an instantiation of our protocol syntax that is generic over
a blind signature scheme, a signature scheme, a combined signature scheme / key
exchange, a collision-resistant hash function and a pseudo-random function family (PRF).

%\subsection{Generic Instantiation}
Let $\textsc{BlindSign}$ be a blind signature scheme with the following syntax, where the party $\mathcal{S}$
is the signer and $\mathcal{R}$ is the signature requester:
\begin{itemize}
  \item $\algo{KeyGen}_{BS}(1^\lambda) \mapsto (\V{sk}, \V{pk})$ is the key generation algorithm
    for the signer of the blind signature protocol.
  \item $\algo{Blind}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\V{pk}, m)) \mapsto (\overline{m}, r)$ is a possibly interactive protocol
    to blind a message $m$ that is to be signed later.  The result is a blinded message $\overline{m}$ and
    a residual $r$ that allows to unblind a blinded signature on $m$ made by $\V{sk}$.
  \item $\algo{Sign}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\overline{m})) \mapsto
    \overline{\sigma}$ is an algorithm to sign a blinded message $\overline{m}$.
    The result $\overline{\sigma}$ is a blinded signature that must be unblinded
    using the $r$ returned from the corresponding blinding operation before
    verification.
  \item $\algo{UnblindSig}_{BS}(r, m, \overline{\sigma}) \mapsto \sigma$
    is an algorithm to unblind a blinded signature.
  \item $\algo{Verify}_{BS}(\V{pk}, m, \sigma) \mapsto b$ is a algorithm to check the validity of a blind
    signature.  Returns $1$ if the signature $\sigma$ was valid for $m$ and $0$ otherwise.
\end{itemize}

Note that this syntax excludes some blind signature protocols, such as those
with interactive/probabilistic verification or those without a ``blinding
factor'', where the $\algo{Blind}_{BS}$ and $\algo{Sign}_{BS}$ and
$\algo{UnblindSig}_{BS}$ would be merged into one interactive signing protocol.
Such blind signature protocols have already been used to construct e-cash
\cite{camenisch2005compact}.

We require the following two security properties for $\textsc{BlindSign}$:
\begin{itemize}
  \item \emph{blindness}: It should be computationally infeasible for a
    malicious signer to decide which of two messages and has been signed first
    in two executions with an honest user.  The corresponding game can defined as
    in Abe and Okamoto \cite{abe2000provably}, with the additional enhancement
    that the adversary generates the signing key \cite{schroder2017security}.
  \item \emph{unforgeability}:  An adversary that requests $k$ signatures with $\algo{Sign}_{BS}$
    is unable to produce $k+1$ valid signatures with non-negligible probability.
\end{itemize}
For more generalized notions of the security of blind signatures, see e.g.
\cite{fischlin2009security,schroder2017security}.

Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange protocol:

\begin{itemize}
  \item $\algo{KeyGenSec}_{CSK}(1^\lambda) \mapsto \V{sk}$ is a secret key generation algorithm.
  \item $\algo{KeyGenPub}_{CSK}(\V{sk}) \mapsto \V{pk}$ produces the corresponding public key.
  \item $\algo{Sign}_{CSK}(\V{sk}, m) \mapsto \sigma$ produces a signature $\sigma$ over message $m$.
  \item $\algo{Verify}_{CSK}(\V{pk}, m, \sigma) \mapsto b$ is a signature verification algorithm.
    Returns $1$ if the signature $\sigma$ is a valid signature on $m$ by $\V{pk}$, and $0$ otherwise.
  \item $\algo{Kx}_{CSK}(\V{sk}_1, \V{pk}_2) \mapsto x$ is a key exchange algorithm that computes
    the shared secret $x$ from secret key $\V{sk}_1$ and public key $\V{pk}_2$.
\end{itemize}

We occasionally need these key generation algorithms separately, but
we usually combine them into $\algo{KeyGen}_{CSK}(1^\lambda) \mapsto (\V{sk}, \V{pk})$.

We require the following security properties to hold for $\textsc{CoinSignKx}$:
\begin{itemize}
  \item \emph{unforgeability}:  The signature scheme $(\algo{KeyGen}_{CSK}, \algo{Sign}_{CSK}, \algo{Verify}_{CSK})$
    must satisfy existential unforgeability under chosen message attacks (EUF-CMA).

  \item \emph{key exchange completeness}:
    Any probabilistic polynomial-time adversary has only negligible chance to find
    a degenerate key pair $(\V{sk}_A, \V{pk}_A)$ such that for some
    honestly generated key pair 
    $(\V{sk}_B, \V{pk}_B) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$
    the key exchange fails, that is
      $\algo{Kex}_{CSK}(\V{sk}_A, \V{pk}_B) \neq \algo{Kex}_{CSK}(\V{sk}_B, \V{pk}_A)$,
    while the adversary can still produce a pair $(m, \sigma)$ such that $\algo{Verify}_{BS}(\V{pk}_A, m, \sigma) = 1$.

  \item \emph{key exchange security}:  The output of $\algo{Kx}_{CSK}$ must be computationally
    indistinguishable from a random shared secret of the same length, for inputs that have been
    generated with $\algo{KeyGen}_{CSK}$.
\end{itemize}

Let $\textsc{Sign} = (\algo{KeyGen}_{S}, \algo{Sign}_{S}, \algo{Verify}_{S})$ be a signature
scheme that satisfies selective unforgeability under chosen message attacks (SUF-CMA).

Let $\V{PRF}$ be a pseudo-random function family and $H : \{0,1\}^* \rightarrow \{0,1\}^\lambda$
a collision-resistant hash function.

Using these primitives, we now instantiate the syntax of our income-transparent e-cash scheme:

\begin{itemize}
  \item $\algo{ExchangeKeygen}(1^{\lambda}, 1^{\kappa}, \mathfrak{D})$:

    Generate the exchange's signing key pair $\V{skESign} \leftarrow \algo{KeyGen}_{S}(1^\lambda)$.

    For each element in the sequence $\mathfrak{D} = d_1,\dots,d_n$, generate
    denomination key pair $(\V{skD}_i, \V{pkD}_i) \leftarrow \algo{KeyGen}_{BS}(1^\lambda)$.
  \item $\algo{CustomerKeygen}(1^\lambda,1^\kappa)$:
    Return key pair $\algo{KeyGen}_S(1^\lambda)$.
  \item $\algo{MerchantKeygen}(1^\lambda,1^\kappa)$:
    Return key pair $\algo{KeyGen}_S(1^\lambda)$.

  \item $\algo{WithdrawRequest}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{pkD}))$:

    Let $\V{skD}$ be the exchange's denomination secret key corresponding to $\V{pkD}$.

    \begin{enumerate}
      \item \prt{C} generates coin key pair $(\V{skCoin}, \V{pkCoin}) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$
      \item \prt{C} runs $(\overline{m}, r) \leftarrow \algo{Blind}_{CSK}(\mathcal{E}(\V{skD}), \mathcal{C}(\V{pkD}, \V{pkCoin}))$
        with the exchange
    \end{enumerate}

    The withdraw identifier is then
    \begin{equation*}
      \V{wid} := (\V{skCoin}, \V{pkCoin}, \overline{m}, r)
    \end{equation*}


  \item $\algo{WithdrawPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{wid}))$:

    The customer looks up $\V{skCoin}$, $\V{pkCoin}$, \V{pkD}, $\overline{m}$
    and $r$ via the withdraw identifier $\V{wid}$.

    \begin{enumerate}
      \item \prt{C} runs $\overline{\sigma} \leftarrow \algo{Sign}_{BS}(\mathcal{E}(\V{skD}), \mathcal{C}(\overline{m}))$ with the exchange
      \item \prt{C} unblinds the signature $\sigma \leftarrow \algo{UnblindSig}_{BS}(\overline{\sigma}, r, \overline{m})$
        and stores the coin $(\V{skCoin}, \V{pkCoin}, \V{pkD}, \sigma)$ in their wallet.
    \end{enumerate}

  \item $\algo{Spend}(\V{transactionId}, f, \V{coin}, \V{pkMerchant})$:

    The deposit permission is computed as $\V{depositPermission} = (\V{pkCoin},
    \sigma_D, m)$ where $m := (\V{transactionId}, f, \V{pkMerchant})$ and $\sigma_D
    := \algo{Sign}_{CSK}(skCoin, m)$.

  \item $\algo{Deposit}(\prt{E}(\V{sksE}, \V{pkMerchant}), \prt{M}(\V{skMerchant}, \V{pksE}, \V{depositPermission}))$:

    Exchange checks the signature $\sigma_D$ in the deposit permission, records
    contribution $f$ in database $\V{deposited}$ of deposited coins.

  \item $\algo{RefreshRequest}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{coin}_0, \V{pkD}_u))$:

    Let $\V{skD}_u$ be the secret key corresponding to $\V{pkD}_u$.

    We write \[ \algo{Blind}^*_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(R,
    \V{skR}, \V{pk}, m)) \mapsto (\overline{m}, r, \mathcal{T}_{B*}) \] for a
    modified version of $\algo{Blind}_{BS}$ where the signature requester
    $\mathcal{R}$ takes all randomness from the sequence
    $\left(\V{PRF}(R,\texttt{"blind"}\Vert n)\right)_{n>0}$, the messages from the exchange are
    recorded in transcript $\mathcal{T}_{B*}$, and all messages sent by the
    requester are signed with $\V{skR}$.

    Furthermore we write \[ \algo{KeyGen}^*_{CSK}(R, 1^\lambda) \mapsto
    (\V{sk}, \V{pk}) \] for a modified version of the key generation algorithm
    that takes randomness from the sequence $\left(\V{PRF}(R,\texttt{"key"}\Vert
    n)\right)_{n>0}$.

    For each $i\in \{1,\dots,\kappa \}$, the customer
    \begin{enumerate}
      \item generates seed $s_i \randsel \{1, \dots, 1^\lambda\}$
      \item generates transfer key pair $(t_i, T_i) \leftarrow \algo{KeyGen}^*_{CSK}(s_i, 1^\lambda)$
      \item computes transfer secret $x_i \leftarrow \algo{Kx}(t_i, \V{pkCoin}_0)$
      \item computes coin key pair $(\V{skCoin}_i, \V{pkCoin}_i) \leftarrow
        \algo{KeyGen}^*_{CSK}(x_i, 1^\lambda)$
      \item and executes the modified blinding protocol
      \[
        (\overline{m}_i, r_i, \mathcal{T}_{(B*,i)}) \leftarrow
          \algo{Blind}^*_{BS}(\mathcal{E}(\V{skD_u}), \mathcal{C}(x_i, \V{skCoin}_0, \V{pkD}_u, \V{pkCoin}_i))
      \]
        with the exchange.
    \end{enumerate}

    The customer stores the refresh identifier
    \begin{equation}
      \V{rid} := (\V{coin}_0, \V{pkD}_u, \{ s_i \}, \{ \overline{m}_i \}, \{r_i\}, \{\mathcal{T}_{(B*,i)}\} ).
    \end{equation}

    Now, the customer's wallet sends the commitment $\pi_1 := (\V{pkCoin}_0, \V{pkD}_u, h_C)$ together with signature $\V{sig}_1
    \leftarrow \algo{Sign}_{CSK}(\V{skCoin}_0, \pi_1)$ to the exchange, where
    \begin{align*}
      h_T &:= H(T_1, \dots, T_\kappa)\\
      h_{\overline{m}} &:= H(\overline{m}_1, \dots, \overline{m}_\kappa)\\
      h_C &:= H(h_T \Vert h_{\overline{m}})
    \end{align*}

    The exchange checks the signature $\V{sig}_1$, and aborts if invalid.  Otherwise,
    depending on the commitment:
    \begin{enumerate}
      \item if the exchange did not see $\pi_1$ before, it marks $\V{pkCoin}_0$
        as spent for $D(\V{pkD}_u)$, chooses a uniform random $0 \le \gamma < \kappa$, stores it under $\pi_1$,
        and sends this choice in a signed message $(\gamma, \V{sig}_2)$ to the customer,
        where $\V{sig}_2 \leftarrow \algo{Sign}_{S}(\V{skESig}, \gamma)$.
      \item otherwise, the exchange sends back the same $\pi_2$ as it sent for the last
        equivalent $\pi_1$.
    \end{enumerate}

  \item $\algo{RefreshPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{rid})) \rightarrow \mathcal{T}$:
    The customer's wallet looks up the refresh identifier $\V{rid}$ and recomputes the transfer key pairs,
    transfer secrets and new coin key pairs.  The customer sends the reveal message
    \begin{equation*}
      \pi_3 := T_\gamma, \overline{m}_\gamma,
      (s_1, \dots, s_{\gamma-1}, s_{\gamma+1}, \dots, s_\kappa)
    \end{equation*}
    and signature
    \begin{equation*}
      \V{sig}_{3} \leftarrow \algo{Sign}_{CSK}(\V{skCoin}_0, (\V{pkCoin}_0,
      \V{pkD}_u, \mathcal{T}_{(B*,\gamma)}, \pi_3))
    \end{equation*} to the exchange.

    The exchange checks the signature $\V{sig}_{3}$ and then computes for $i \ne \gamma$:
    \begin{align*}
      (t_i', T_i') &\leftarrow \algo{KeyGen}^*_{CSK}(s_i, 1^\lambda)\\
      x_i' &\leftarrow \algo{Kx}(t_i, \V{pkCoin}_0)\\
      (\V{skCoin}_i', \V{pkCoin}_i') &\leftarrow
              \algo{KeyGen}^*_{CSK}(x_i', 1^\lambda) \\
      h_T' &:= H(T'_1, \dots, T'_{\gamma-1}, T_\gamma, T_{\gamma+1}', \dots, T_\kappa')
    \end{align*}
    and simulates the blinding protocol with recorded transcripts (without signing each message,
    as indicated by the dot ($\cdot$) instead of a signing secret key), obtaining
    \begin{align*}
      (\overline{m}_i', r_i', \mathcal{T}_i) &\leftarrow
          \algo{Blind}^*_{BS}(\mathcal{S}(\V{skD}_u), \mathcal{R}(x_i', \cdot, \V{pkD}_u, \V{skCoin}'_i))\\
    \end{align*}
    and finally
    \begin{align*}
      h_{\overline{m}}' &:= H(\overline{m}_1', \dots, \overline{m}_{\gamma-1}', \overline{m}_\gamma, \overline{m}_{\gamma+1}',\dots, \overline{m}_\kappa')\\
      h_C' &:= H(h_T' \Vert h_{\overline{m}}').
    \end{align*}

    Now the exchange checks if $h_C = h_C'$, and aborts the protocol if the check fails.
    Otherwise, the exchange sends a message back to $\prt{C}$ that the commitment verification succeeded and includes
    the signature
    \begin{equation*}
      \overline{\sigma}_\gamma := \algo{Sign}_{BS}(\mathcal{E}(\V{skD}_u), \mathcal{C}(\overline{m}_\gamma)).
    \end{equation*}

    As a last step, the customer obtains the signature $\sigma_\gamma$ on the new coin's public key $\V{pkCoin}_u$ with
    \begin{equation*}
      \sigma_\gamma := \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma).
    \end{equation*}

    Thus the new, unlinkable coin is $\V{coin}_u := (\V{skCoin}_\gamma, \V{pkCoin}_\gamma, \V{pkD}_u, \sigma_\gamma)$.

  \item $\algo{Link}(\prt{E}(\V{sksE}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{coin}_0))$:
    The customer sends the public key $\V{pkCoin}_0$ of $\V{coin}_0$ to the exchange.

    For each completed refresh on $\V{pkCoin}_0$ recorded in the exchange's
    database, the exchange sends the following data back to the customer: the
    signed commit message $(\V{sig}_1, \pi_1)$, the transfer public key
    $T_\gamma$, the signature $\V{sig}_{3}$, the blinded signature $\overline{\sigma}_\gamma$, and the
    transcript $\mathcal{T}_{(B*,\gamma)}$ of the customer's and exchange's messages
    during the $\algo{Blind}^*_{BS}$ protocol execution.

    The following logic is repeated by the customer for each response:
    \begin{enumerate}
      \item Verify the signatures (both from $\V{pkESig}$ and $\V{pkCoin}_0$) on the transcript $\mathcal{T}_\kappa$,
        abort otherwise.
      \item Verify that $\V{sig}_1$ is a valid signature on $\pi_1$ by $\V{pkCoin}_0$, abort otherwise.
      \item Re-compute the transfer secret and the new coin's key pair as
        \begin{align*}
          x_\gamma &:= \algo{Kx}_{CSK}(\V{skCoin}_0, T_\gamma)\\
          (\V{skCoin}_\gamma, \V{pkCoin}_\gamma) &:= \algo{KeyGen}_{CSK}^*(x_\gamma, 1^\lambda).
        \end{align*}
      \item Simulate the blinding protocol with the message transcript received from the exchange to obtain
        $(\overline{m}_\gamma, r_\gamma)$.
      \item Check that $\algo{Verify}_{CSK}(\V{pkCoin}_0,
        \V{pkD}_u, \V{skCoin}_0,(\mathcal{T}_{(B*,\gamma)}, \overline{m}_\gamma), \V{sig}_{3})$
        indicates a valid signature, abort otherwise.
      \item Unblind the signature to obtain $\sigma_\gamma := \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma)$.
      \item (Re-)add the coin $(\V{skCoin}_\gamma, \V{pkCoin}_\gamma, \V{pkD}_u, \sigma_\gamma)$ to the customer's wallet.
    \end{enumerate}

\end{itemize}

%In Taler's refresh, we avoid key exchange failures entirely because the
%Edwards addition law is complete abelian group operation on the curve,
%and the signature scheme verifies that the point lies on the curve.
%% https://safecurves.cr.yp.to/refs.html#2007/bernstein-newelliptic
%% https://safecurves.cr.yp.to/complete.html
%We warn however that Weierstrass curves have incomplete addition formulas
%that permit an adversarial merchant to pick transfer keys that yields failures.
%There are further implementation mistakes that might enable collaborative
%key exchange failures, like if the exchange does not enforce the transfer
%private key being a multiple of the cofactor.
%
%In this vein, almost all post-quantum key exchanges suffer from key exchange
%failures that permit invalid key attacks against non-ephemeral keys.
%All these schemes support only one ephemeral party by revealing the
%ephemeral party's private key to the non-ephemeral party,
% ala the Fujisaki-Okamoto transform~\cite{fujisaki-okamoto} or similar.
%We cannot reveal the old coin's private key to the exchange when
%verifying the transfer private keys though, which
% complicates verifying honest key generation of the old coin's key.


\bibliographystyle{splncs04}
\bibliography{ref}


\appendix

\section{Proofs}
%\begin{mdframed}
%  Currently the proofs don't have any explicit tightess bounds.
%  Because we don't know where to ``inject'' the value that we get from the challenger when carrying out
%  a reduction, we need to randomly guess in which coin/signature we should ``hijack'' our challenge value.
%  Thus for the proofs to work fully formally, we need to bound the total number of oracle invocations,
%  and our exact bound for the tightness of the reduction depends on this limit.
%\end{mdframed}

We now give proofs for the security properties defined in Section \ref{sec:security-properties}
with the generic instantiation.

\subsection{Anonymity}

\begin{theorem}
  Our instantiation satisfies anonymity.
\end{theorem}

\begin{proof}
  We give a proof via a sequence of games $\mathbb{G}_0(b), \mathbb{G}_1(b),
  \mathbb{G}_2(b)$, where $\mathbb{G}_0(b)$ is the original anonymity game
  $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, 1^\kappa, b)$.  We show the
  adversary can distinguish between subsequent games with only negligible
  probability.  Let $\epsilon_{HC}$ and $\epsilon_{KX}$ be the advantage of an
  adversary for finding hash collisions and for breaking the security of the
  key exchange respectively.

  We define $\mathbb{G}_1$ by replacing the link oracle \ora{Link} with a
  modified version that behaves the same as \ora{Link}, unless the adversary
  responds with link data that did not occur in the transcript of a successful
  refresh operation, but despite of that still passes the customer's
  verification.  In that case, the game is aborted instead.

  Observe that in case this failure event happens, the adversary must have forged a
  signature on $\V{sig}_{3}$ on values not signed by the customer, yielding
  an existential forgery.  Thus $\left| \Prb{\mathbb{G}_0 = 1} - \Prb{\mathbb{G}_1 = 1}
  \right|$ is negligible.

  In $\mathbb{G}_2$, the refresh oracle is modified so that the customer
  responds with value drawn from a uniform random distribution $D_1$ for the the
  $\gamma$-th commitment instead of using the key exchange function.  We must
  handle the fact that $\gamma$ is chosen by the adversary after seeing the
  commitments, so the challenger first makes a guess $\gamma^*$ and replaces
  only the $\gamma^*$-th commitment with a uniform random value.  If the
  $\gamma$ chosen by the adversary does not match $\gamma^*$, then the
  challenger rewinds \prt{A} to the point where the refresh oracle was called.
  Note that we only replace the one commitment that
  will not be opened to the adversary later.

  Since $\kappa \ll \lambda$ and the security property of $\algo{Kx}$
  guarantees that the adversary cannot distinguish the result of a key exchange
  from randomness, the runtime complexity of the challenger still stays
  polynomial in $\lambda$.  An adversary that could with high probability
  choose a $\gamma$ that would cause a rewind, could also distinguish
  randomness from the output of $\algo{Kx}$.

  %\mycomment{Tighness bound also missing}

  We now show that $\left| \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1}
  \right| \le \epsilon_{KX}$ by defining a distinguishing game $\mathbb{G}_{1
  \sim 2}$ for the key exchange as follows:

  \bigskip
  \noindent $\mathbb{G}_{1 \sim 2}(b)$:
  \vspace{-0.5\topsep}
  \begin{enumerate}
    \setlength\itemsep{0em}
    \item If $b=0$, set
      \[
        D_0 := \{ (A, B, \V{Kex}(a, B)) \mid (a, A) \leftarrow \V{KeyGen}(1^\lambda),(b, B) \leftarrow \V{KeyGen}(1^\lambda) \}.
      \]
      Otherwise, set
      \[
        D_1 := \{ (A, B, C) \mid (a, A) \leftarrow \V{KeyGen}(1^\lambda),
           (b, B) \leftarrow \V{KeyGen}(1^\lambda),
           C \randsel \{1,\dots,2^\lambda\} \}.
      \]

    \item Return $\mathit{Exp'}_{\cal A}^{anon}(b, D_b)$

      (Modified anonymity game where the $\gamma$-th commitment in the
      refresh oracle is drawn uniformly from $D_b$ (using rewinding).  Technically, we need to
      draw from $D_b$ on withdraw for the coin secret key, write it to a table, look it up on refresh and
      use the matching tuple, so that with $b=0$ we perfectly simulate $\mathbb{G}_1$.)
  \end{enumerate}

  Depending on the coin flip $b$, we either simulate
  $\mathbb{G}_1$ or $\mathbb{G}_2$ perfectly for our adversary~$\mathcal{A}$
  against $\mathbb{G}_1$.  At the same time $b$ determines whether \prt{A}
  receives the result of the key exchange or real randomness.  Thus $\left|
  \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1} \right| = \epsilon_{KX}$ is
  exactly the advantage of $\mathbb{G}_{1 \sim 2}$.

  We observe in $\mathbb{G}_2$ that as $x_\gamma$ is uniform random and not
  learned by the adversary,  the generation of $(\V{skCoin}_\gamma,
  \V{pkCoin}_\gamma)$ and the execution of the blinding protocol is equivalent (under the PRF assumption)
  to using the randomized algorithms
  $\algo{KeyGen}_{CSK}$ and $\algo{Blind}_{BS}$.

  By the blindness of the $\textsc{BlindSign}$ scheme, the adversary is not
  able to distinguish blinded values from randomness.  Thus, the adversary is
  unable to correlate a $\algo{Sign}_{BS}$ operation in refresh or withdraw
  with the unblinded value observed during $\algo{Deposit}$.

  We conclude the success probability for $\mathbb{G}_2$ must be $1/2$ and
  hence the success probability for $\mathit{Exp}_{\cal A}^{anon}(1^\lambda,
  \kappa, b)$ is at most $1/2 + \epsilon(\lambda)$, where $\epsilon$ is a
  negligible function.
\end{proof}
% RSA ratios vs CDH in BLS below

\subsection{Conservation}

\begin{theorem}
  Assuming existential unforgeability of signatures (EUF-CMA), our instantiation satisfies conservation.
\end{theorem}

\begin{proof}

% FIXME: argue that reduction is tight when you have malleability
  In honest executions, we have $\V{withdrawn}[\V{pkCustomer}] = v_C + v_S$, i.e.
  the coins withdrawn add up to the coins still available and the coins spent
  for known transactions.

  In order to win the conservation game, the adversary must increase
  $\V{withdrawn}[\V{pkCustomer}]$ or decrease $v_C$ or $v_S$.  An adversary can
  abort withdraw operations, thus causing $\V{withdrawn}[\V{pkCustomer}]$ to increase,
  while the customer does not obtain any coins.  However, in step
  \ref{game:conserv:run}, the customer obtains coins from interrupted withdraw
  operations.  Similarly for the refresh protocol, aborted \algo{RefreshRequest} / \algo{RefreshPickup}
  operations that result in a coin's remaining value being reduced are completed
  in step \ref{game:conserv:run}.

  Thus only remaining option for the adversary to decrease $v_C$ or $v_S$ is
  with the $\ora{RefreshPickup}$ and $\ora{Deposit}$ oracles respectively.

  Since the exchange verifies signatures made by the secret key of the coin
  that is being spent/refreshed, the adversary must forge this signature or have
  access to the coin's secret key.  As we do not give the adversary access to
  the sharing oracle, it does not have direct access to any of the honest
  customer's coin secret keys.

  Thus the adversary must either compute the coin's secret key from observing
  the coin's public key (e.g. during a partial deposit operation), or forge
  signatures directly.  Both possibilities allow us to carry out a reduction
  against the unforgeability property of the $\textsc{CoinSignKx}$ scheme, by
  injecting the challenger's public key into one of the coins.

\end{proof}

\subsection{Unforgeability}

\begin{theorem}
Our instantiation satisfies {unforgeability}.
% by probabilistic polynomially time adversaries.
\end{theorem}

\begin{proof}
The adversary must have produced at least one coin that was not blindly
signed by the exchange.  %TODO: Way too fasty here, resurect the chain
In order to carry out a reduction from this adversary to a blind signature
forgery, we inject the challenger's public key into one randomly chosen
denomination.  Since we do not have access to the corresponding secret key
of the challenger, signing operations for this denomination are replaced
with calls to the challenger's signing oracle in \ora{WithdrawPickup} and
\ora{RefreshPickup}.  For $n$ denominations, an adversary against the
unforgeability game would produce a blind signature forgery with probability $1/n$.
\end{proof}

%TODO: RSA-KTI

\subsection{Income Transparency}
\begin{theorem}
Our instantiation satisfies {weak income transparency}.
\end{theorem}

\begin{proof}
  We consider the directed forest on coins induced by the refresh protocol.
  It follows from unforgeability that any coin must originate from some
  customer's withdraw in this graph.
  We may assume that all $\V{coin}_1, \dots, \V{coin}_l$ originate from
  non-corrupted users, for some $l \leq \ell$.  % So $\ell \leq w + |X|$.

  For any $i \leq l$, there is a final refresh operation $R_i$ in which
  a non-corrupted user could obtain the coin $C'$ consumed in the refresh
  via the linking protocol, but no non-corrupted user could obtain the
  coin provided by the refresh, as otherwise $\V{coin}_i$ gets marked as
  spent in step step \ref{game:income:spend}.
  Set $F := \{ R_i \mid i \leq l \}$.  %TODO: Not elegant, clean up below.

  During each $R_i \in F$, our adversary  must have submitted a blinded
  coin and transfer public key for which the linking protocol fails to
  produce the resulting coin correctly, otherwise the coin would have
  been spent in step \ref{game:income:spend}.  In this case, we consider
  several non-exclusive cases
  \begin{enumerate}
    \item the execution of the refresh protocol is incomplete,
    \item the commitment for the $\gamma$-th blinded coin and transfer
      public key is dishonest,
    \item a commitment for a blinded coin and transfer public key other
	  than the $\gamma$-th is dishonest,
  \end{enumerate}

  We show these to be exhaustive by assuming their converses all hold: As the
  commitment is signed by $\V{skCoin}_0$, our key exchange completeness
  assumption of $\textsc{CoinSignKx}$ applies to the coin public key.
  Any revealed values must match our honestly computed commitments,
  as otherwise a collision in $H$ would have been found.
  We assumed
  the revealed $\gamma$-th transfer public key is honest.  Hence our key
  exchange completeness assumption of $\textsc{CoinSignKx}$ yields
  $\algo{Kex}_{CSK}(t,C') = \algo{Kex}_{CSK}(c',T)$ where $T =
  \algo{KeyGenPub}_{CSK}(t)$ is the transfer key, thus the customer obtains the
  correct transfer secret.  We assumed the refresh concluded and all
  submissions besides the $\gamma$-th were honest, so the exchange correctly
  reveals the signed blinded coin.  We assumed the $\gamma$-th blinded coin is
  correct too, so customer now re-compute the new coin correctly, violating
  $R_i \in F$.

  We shall prove
  \begin{equation}\label{eq:income-transparency-proof}
    \Exp{{p \over b + p} \middle| F \neq \emptyset} = {1\over\kappa}
  \end{equation}
  where the expectation runs over
  any probability space used by the adversary and challenger.

  We shall now consider executions of the income transparency game with an
  optimal adversary with respect to maximizing $p \over b + p$.  Note that this
  is permissible since we are not carring out a reduction, but are interested
  in the expectation of the game's return value.

  As a reminder, if a refresh operation is initiated using a false commitment
  that is detected by the exchange, then the new coin cannot be obtained, and
  contributes to the lost coins $b := w - s$ instead of the winnings $p := L -
  w'$.  We also note $b + p$ gives the value of
  refreshes attempted with false commitments.  As these are non-negative,  $p \over b
  + p$ is undefined if and only if $p = 0$ and $b = 0$, which happens if and
  only if the adversary does not use false commitments, i.e. $F = \emptyset$.

  We may now assume for optimality that $\mathcal{A}$ submits a false
  commitment for at most one choice of $\gamma$ in any $R_i \in F$, as
  otherwise the refresh always fails.  Furthermore for an optimal adversary we
  can exclude refreshes in $F$ that are incomplete, but that would be possible
  to complete successfully, as completing such a refresh would only increase the
  adversaries winnings.

  We emphasize that an adversary that loses an $R_i$ loses the coin that would
  have resulted from it completely, while an optimal adversary who wins an
  $R_i$ should not gamble again.  Indeed, an adversary has no reason to touch
  its winnings from an $R_i$.

% There is no way to influence $p$ or $b$ through withdrawals or spends
% by corrupted users of course.  In principle, one could decrease $b$ by
%  sharing from a corrupted user to a non-corrupted users,
% but we may assume this does not occur either, again by optimality.

  For any $R_i$, there are $\kappa$ game runs identical up through the
  commitment phase of $R_i$ and exhibit different outcomes based on the
  challenger's random choice of $\gamma$.
  If $v_i$ is the financial value of the coin resulting from refresh operation
  $R_i$ then one of the possible runs adds $v_i$ to $p$, while the remaining
  $\kappa-1$ runs add $v_i$ to $b$.

  We define $p_i$ and $b_i$ to be these contributions summed over the $\kappa$ possible
  runs, i.e.
  \begin{align*}
    p_i &:= v_i\\
    b_i &= (\kappa - 1)v_i
  \end{align*}
  The adversary will succeed in $1/\kappa$ runs ($p_i=v$) and looses in
  $(\kappa-1)/\kappa$ runs ($p_i=0$). Hence:
  \begin{align*}
    \Exp{{p \over b + p} \middle| F \neq \emptyset}
        &= \frac{1}{|F|} \sum_{R_i\in F} {p_i \over b_i + p_i} \\
        &= \frac{1}{\kappa |F|} \sum_{R_i\in F} {v_i \over 0 + v_i} + \frac{\kappa-1}{\kappa |F|} \sum_{R_i \in F} {0 \over v_i + 0} \\
        &= {1\over\kappa},
  \end{align*}
  which yields the equality (\ref{eq:income-transparency-proof}).

As for $F = \emptyset$, the return value of the game must be $0$, we conclude
\begin{equation*}
  E\left[\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)\right] \le {1\over\kappa}.
\end{equation*}

\end{proof}
% https://math.stackexchange.com/questions/852890/expectation-of-random-variables-ratio
%%% $L - w' \over (L - w') + (w - s)$
% $E(b/p) + 1 = E(b/p + p/p) = E((b + p)/p) = \kappa$
% $E(b/p) = \kappa-1$
% $E(p/b) = {1 \over \kappa-1}$

%As it turns out, there is a simple hash-based solutions that provides
%post-quantum anonymity without additional assumptions though:
%% because the coin holder is encrypting to themselves:
%We extend the coin private key $c$ by a secret $m$ and extend the
%coin signing key $C$ to be a pair $(C,R)$ in which $R$ is the root
%of a Merkle tree whose $i$th leave is $H(m,i)$.
%In a refresh, the wallet first constructs the planchets from
%$H(t C', H(m,i))$ and commits to the index $i$ along with with each
%transfer public key $T$, and later when revealing $t$ also reveals
%$H(m,i)$ and the proof that it lives in the Merkle tree.
%In this scheme, our Merkle tree should be large enough to accommodate
%some fixed number of refreshes per coin, possibly just one, while
%our wallet must avoid any fragility in committing its $i$ choices to disk.

%\section{Standard Definitions}
%\begin{definition}[One-more forgery]
%For any integer $\ell$, an $(\ell, \ell + 1)$-forgery comes from
%a probabilistic polynomial time Turing machine $\mathcal{A}$ that can
%compute, after $\ell$ interactions with the signer $\Sigma$, $\ell + 1$ signatures with non-negligible
%  probability. The ``one-more forgery'' is an $(\ell, \ell + 1)$-forgery for some
%integer $\ell$.
%\end{definition}
%
%Taken from \cite{pointcheval1996provably}.  This definition applies to blind signature schemes in general.
%Intuition:  EUF-CMA is not strong enough for blind signatures,
%since attacker can choose the message (without going through a hash function before signing).
%
%\begin{definition}[RSA-KTI]
%  Game (security parameter $k$, $m : \mathbb{N} \rightarrow \mathbb{N}$,
%  $\mathcal{A}$ adversary with access to RSA inversion oracle \ora{Inv}):
%  \begin{enumerate}
%    \item $(N, e, d) \leftarrow \mathsf{KeyGen}(k)$
%    \item $y_i \leftarrow_R \mathbb{Z}_N^*$ for $i \in 1, \dots, m(k) + 1$
%    \item $(x_1, \dots, x_{m(k) + 1}) \leftarrow \mathcal{A}^{\ora{Inv}}(N, e, k, y_1, \dots, y_{m(k) + 1})$
%    \item $\mathcal{A}$ wins if it made at most $m(k)$ oracle queries and $x_i^e \equiv y_i \pmod N$
%  \end{enumerate}
%\end{definition}
%
%From \cite{bellare2003onemore}.  Assumption to prove security of RSA blind signatures.  Equivalent to RSA-CTI.




\section{Concrete Instantitation}

We now give a concrete instantiation that is used in our implementation
for the schemes \textsc{BlindSign}, \textsc{CoinSignKx} and \textsc{Sign}.

For \textsc{BlindSign}, we use RSA-FDH blind signatures~\cite{chaum1983blind}
with blinding factors produced by FD-PRF constructed from a hash
function with range the full RSA domain $[0,pq)$.  An adversary who
defeats the blindness property can recognise blinding factors,
violating this PRF assumption.  For the unforgeability property,
we require the RSA-KTI assumption as discussed in \cite{bellare2003onemore}.
%TODO: Jeff always cited multoiiple papers for RSA-KTI, but forgets why.
As the blinding step in RSA blind signatures is non-interactive, storage
and verification of the transcript is omitted in refresh and link.
We envision BLS blind signatures working equally well.

We instantiate \textsc{CoinSignKx} with signatures and key exchange operations
on elliptic curves in Edwards form, where the same key is used for signatures
and the Diffie--Hellman key exchange operations.  In practice, we use Ed25519
signatures \cite{bernstein2012high} and scalar multiplication for the Edwards
curve, which gives $\lambda=128$.  % Curve25519 \cite{bernstein2006curve25519}
We caution that some other elliptic curve key exchange implementations might
not satisfy the robustness property that we require, due to the lack of
complete addition laws.
% and that both robustness and honest key generation become tricky when ..

For \textsc{Sign}, we use elliptic-curve signatures, concretely Ed25519.


\section{Strong Income Transparency}

We characterized {\em weak income transparency} in
Section~\ref{sec:security-properties}.  We will now discuss the notion
of {\em strong income transparency}, as it might be useful for other
instantiations that provide more absolute guarantees.

\begin{definition}[Strong Income Transparency]
  We say that an e-cash scheme satisfies \emph{strong income transparency} if
  the success probability $\Prb{\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa) \ne 0}$
  for the income transparency game is negligible for any polynomial time adversary~$\mathcal{A}$.
\end{definition}

The adversary is said to win one execution of the strong income
transparency game if the game's return value is non-zero, i.e. there
was at least one successful attempt to obtain untaxed income.

Our protocol does not fulfill strong income transparency since in
practice $\kappa$ must be a small cut-and-choose parameter, as the
complexity of our cut-and-choose protocol grows linearly with
$\kappa$.  Instead we showed that our protocol satisfies weak income
transparency, which is a statement about the adversary's financial
loss when winning the game instead of the winning probability.  Here,
the return-on-investment (represented by the game's return value) is
bounded by $1/\kappa$.


\section{Endorsed E-Cash and Fair Exchange}

%\subsection{Other Properties}

% FIXME: move this to design or implementation
%\subsubsection{Fair Exchange}

% FIXME: we should mention "atomic swap" here

The Endorsed E-Cash system by Camenisch et al.~\cite{camenisch2007endorsed}
allows for fair exchange of (online or
offline) e-cash against digital goods.  The online version does not protect the
customer against loss of anonymity from linkability of aborted fair exchanges.

The refresh protocol can be used for fair exchange of online e-cash against
digital goods, without any loss of anonymity due to linkability of aborted
transactions, with the following small extension: The customer asks the
exchange to \emph{lock coins to a merchant} until a timeout.  Until the timeout
occurs, the exchange provides the merchant with a guarantee that these coins can
only be spent with this specific merchant, or not at all.  The
fair exchange exchanges the merchant's digital goods against the customer's
deposit permissions for the locked coins.  On aborted fair exchanges,
the customer refreshes to obtain unlinkable coins.



\end{document}