\documentclass[a4paper]{scrartcl}

\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{pifont}
\usepackage{url}
\usepackage[left=20mm,top=20mm]{geometry}
\usepackage{booktabs}
\usepackage{hyperref}
\usepackage{subcaption}
\usepackage{mathpazo}
\usepackage{mathtools}
\usepackage{mdframed}
% \usepackage[amsmath,thmmarks]{ntheorem}
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}

\def\Z{\mathbb{Z}}

% not amsthm
% \theoremseparator{.} % normal theorem

\title{Taler Security Proofs}
\date{\today}

\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{corollary}[lemma]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]

\begin{document}


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

% 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{\mathit{#1}}}

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

\maketitle

\section{Model and Syntax}

We consider a single exchange with many clients,
 who can acts as a merchant, a customer or both
 with no further distinction other than naming in the role.  
We prefix public and secret keys with $pk$ and $sk$,
 following standard convention.

As a rule, anonymous cash scheme consider only a single implicit
denomination in their security proofs because explicit denominations
complicate the financial games and proofs.  In fact, anonymous eCash
schemes all require protections against network, etc. failures, and
hence require a refresh operations.  If this refresh operations also
provided partial spending, which seems logical, then refreshes can be
run after spends, which invalidates assumptions in anonymity games.

As the same time, only financial games worry about the denomination
value, so even multiple denomination can be left implicit in anonymity
games.  We address compromise by leaving denominations implicit but
dropping down to a single denomination when this creates ambiguity.
We design our oracles to be modular over the accounting scheme used too. 

We track several data structures on behalf of clients : 
\begin{itemize}
\item $\V{valueWithdrawn}[\V{pkClient}]$ contains of the values
 withdrawn by each client $\V{pkClient}$,
\item $\V{wallet}[\V{pkClient}]$ contains sets of client coins records,
 which individually consist of the coin private keys and denomination signatures.
\item $\V{contractHashes}[\V{pkClient}]$ contains the sets of contracts created during deposits.
\end{itemize}
Also, our exchange implements an accounting scheme to prevent double
spending by tracking coin public keys in $\V{spent}[\V{pkCoin}]$ and
$\V{refreshed}[\V{pkCoin}]$, which record transcripts.  

We say that a coin is {\em unspent} or {\em unrefreshed} if it does
not appear in the $\V{spent}$ or $\V{refreshed}$ lists respectively.
We say that a coin is being double spent if adding a transcript to
either list would cause the total value of transcripts in both lists
to exceed the value of the denomination.
%
We may say spent but undeposited for improperly spent coins the user can
reclaim with the refresh protocol.


\subsection{Algorithms}

The Taler e-cash system is defined by the following probabilistic polynomial-time algorithms and protocols.

\begin{itemize}
  \item \algo{EKeygen}():  Algorithm executed by the exchange
    that outputs a key pair $(\V{skE}, \V{pkE})$, which contain both
    the signing key and the denomination keys for the exchange.

  \item \algo{CKeygen}():  Algorithm executed by merchants and customers
    that outputs a key pair $(\V{skU}, \V{pkU})$.

  \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU})):
    Interactive protocol between exchange and user.

    Increments $\V{valueWithdrawn}[\V{pkU}]$ appropriately,
    adds the resulting coin to the wallet $\V{wallet}[\V{pkU}]$.

  \item \algo{Spend}(contract, \V{pkClient}, \V{skCoin}, pkReceiver):
    Algorithm to produce and sign a deposit permission for a particular contract.
    Adds $\V{contract}$ to $\V{contractHashes}[pkClient]$ and
    initializes $\V{spent}[\V{pkCoin}]$.

  \item \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{M}(\V{skU}, \V{depositPermission})):
    Interactive protocol between the exchange and a customer, who acts as a merchant.

    In the deposit permission, there are coin public keys $\V{pkCoin}$
    corresponding to $\V{skCoin}$.
    If $\V{pkCoin}$ is being double spent, we return the protocol transcript
    of the previous deposits and refreshes.  

    On success, we mark $\V{pkCoin}$ spent in $\V{spent}[\V{pkCoin}]$ and
    return the exchange's signature over the request.

  \item \algo{Refresh}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin})):
    Interactive protocol between exchange and user.

    Again, there is a $\V{pkCoin}$ corresponding to $\V{skCoin}$ appearing.
    If $\V{pkCoin}$ is being double spent, then we return the protocol
    transcript of the previous deposits and refreshes. 

    Assuming otherwise, we mark $\V{pkCoin}$ as refreshed in $\V{refreshed}[\V{pkCoin}]$.
    If the user \prt{U} plays honestly, they will store the unlinkable
    change they obtain in their wallet $wallet[\V{pkU}]$.
    If \prt{U} plays dishonestly, the coin's refresh transcript
    will be marked as spent without anything in return.

  \item \algo{Link}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin})):
    Interactive protocol between exchange and user.
    If \V{skCoin} is the secret key of a coin that was refreshed, then 
    we recompute the refreshed coin and add it to to the user's wallet $wallet[\V{pkU}]$.
\end{itemize}

\subsection{Oracles}

We define the following oracles:

\begin{itemize}
  \item $\ora{AddClient}()$:
    Creates a new client, sets $valueWithdrawm$ for the client to $0$, sets $wallet[pkClient] := \{\}$.
    Returns the public key of the client.

  \item $\ora{WithdrawAsUser}(pkClient)$:  Do a withdraw from the perspective of a user.  The adversary
    controls the user, the simulator the exchange.

  \item $\ora{WithdrawAsExchange}(pkClient)$:  Do a withdraw from the perspective of a exchange.  The adversary
    controls the exchange, the user is simulated.

  \item $\ora{RefreshAsUser}$  Do a withdraw from the perspective of a user, i.e. the adversary sends messages that the user would send.

    The adversary obtains the protocol transcript from the \algo{Refresh} protocol.

  \item $\ora{RefreshAsExchange}$  Do a withdraw from the perspective of the exchange, i.e. the adversary sends messages that the exchange would send.

    The adversary obtains the protocol transcript from the \algo{Refresh} protocol.

  \item $\ora{Spend}(contractHash, pkSpender, pkCoin, pkReceiver)$
    Make a customer sign a deposit permission.  Returns the deposit permission on success, or $\bot$ if the $skSpender$ does not have enough coins.

  \item $\ora{Share}(pkSender, pkReceiver)$:

    Shares one random, previously unshared coin in the wallet of $pkSender$ with $pkReceiver$.

  \item $\ora{CorruptClient}(pkClient)$:

    Used by the adversary to corrupt a client.
    Marks the client as corrupted and gives the adversary the
    client's private key, wallet and signed contract hashes. 
    We lack an oracle to corrupt the exchange but our games may
    corrupt the exchange during the setup phase. 
\end{itemize}

\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}

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

We have two seperate security paramaters in Taler:
First, our primary security parameter $\lambda$ characterizes
 the security of all cryptographic operations.
We employ information theoretically secure blinding, but
 $\lambda$ also characterizes the ECDH used in refresh.
Second, our tiny cut-and-choose parameter $\kappa \ge 3$
 characterizes our income transperency assurances.
We shall argue later that small $\kappa$ suffice
 since cheating results in lost funds.

\subsection{Anonymity}
Intuitively, an adversary $\prt{A}$ including an exchange and merchant
win the anonymity game if they have any advnatage in linking spending
operations with the withdrawal or refresh operations that created the coin.

Let \oraSet{Anon} stand for access to the oracles
 \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
 \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}.

\bigskip
\noindent $\mathit{Exp}_{\prt{A}}^{anon}(1^\lambda, \kappa)$:
\vspace{-0.5\topsep}
\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(\V{skE}, \V{pkE}, \V{skM}, \V{pkM}) \leftarrow {\prt{A}}()$ \\
    Our adversary controls the exchange and a merchant.
    \comment{TODO: EXPLAIN: Note that this only means that $\prt{A}$ has the exchange secret key, it
    does not automatically receive transcripts and it does not have access to any exchange data structures \textit{unless} indicated by the oracles}
  \item $(\V{pkU}_0, \V{pkU}_1, \V{contract}_0, \V{contract}_1) \leftarrow {\prt{A}}^{\oraSet{Anon}}()$ \\
    Our adversary creates two users and two contract,
    along with some coins open which it calls oracles freely.
  \item Return 0 either if $\V{pkU}_1$ or $\V{pkU}_2$ are not distinct
    uncorrupted registered users, or if any coins are left in a
    unfinished unspent state without either completing the spend through
    a deposit or refreshing the coin.  
    \footnote{In general, there is lag during which coins remain in an
    unfinished spent state, but our wallet will not use those coins in
    another transaction until refreshing them.}
  \item Select unspent unrefreshed coins $\V{pkC}_0$ and $\V{pkC}_1$
    from the wallets of $\V{pkU}_0, \V{pkU}_1$, respectively.
    \footnote{In principle, we might anonymously refresh coins before
    or concurrently with spending them, but if our adversary directs a
    non-anonymous refresh then they can mark coins with it}
    Return 0 if either $\V{pkU}_0$ or $\V{pkU}_1$ has no unspent unrefreshed coin.
  \item Let $b \in \{0,1\}$ denote the result of a random coin flip, unknow to the advesary. \\
        $\V{dp_1} \leftarrow \algo{Spend}(\V{contract}_b, \V{pkU}_0, \V{pkC}_0, \V{pkM})$, \\
        $\V{dp_2} \leftarrow \algo{Spend}(\V{contract}_{(1-b)}, \V{pkU}_1, \V{pkC}_1, \V{pkM})$ \\
    Spend these two coins without revealing the customer's identity to the adversary.
  \item $r_1 \leftarrow \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\prt{A}}(dp_1))$, \\
    $r_2 \leftarrow \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), {\prt{A}}(dp_2))$ \\
    Deposit these two coins with the adversary controlled merchant.  Return 0 if $r_1$ or $r_2$ indicate a failure.
  \item $b' \leftarrow {\cal A}^{\oraSet{Anon}}()$ \\
    Our adversary makes one guess $b' \in \{0,1\}$ for $b$, which determines the mapping between users and contracts.
  \item Let $\mathcal{U} \supseteq \{ \V{pkU}_{1}, \V{pkU}_{2} \}$ consist
    of the users who know, or could learn through linking, either
    $\V{skC}_0$ or $\V{skC}_1$, aka these coin's {\em ownership set}.
    Return 0 if $\cal U$ contains either any user corrupted by $\cal A$
    or any user who ran the linking protocol.
    \footnote{We prohibit non-corrupted users form running the Linking
    protocol because it could easily violate anonymity, but corrupted
    users could employ a linking oracle.}
  \item if $b = b'$ return 1, otherwise return 0
\end{enumerate}

We have stated this game in terms of the anonymity of users to match
existing e-cash literature, but actually any user based formulation is
insufficient for any anonymous e-cash schemes because it does not
cover unlinkability between payments that the same user made.
Instead of the two users $\V{pkU}_0$ and $\V{pkU}_1$,
our adversary $\cal A$, and hence the oracles it calls, must supply
 a withdrawal (or refresh) event handle.  

In our case, planchets work well for this, but they do not exist in all scheme.
We prove the stronger anonymity game that replaces lines 2,3, and 5
with these two lines.
\begin{enumerate}
  \setlength\itemsep{0em}
  \item[2.] $(P_0, P_1, \V{contract}_0, \V{contract}_1) \leftarrow {\cal A}^{\oraSet{Anon}}()$ \\
    Our adversary invokes oracles to create users, as well as
    create and manipulate their coins.
    It singles out two coin creating invocations, either withdrawals
    or refreshes, by returning the planchets $P_0$ and $P_1$. 
    It returns two two contracts $\V{contract}_0$ and $\V{contract}_1$ as well.
  \item[3.]
    We demand that valid unspent unrefreshed coins $\V{pkC}_0$ and $\V{pkC}_1$
    have been created from the planchets $P_0$ and $P_1$ respectively.
    Also let $\V{pkU}_1$ and $\V{pkU}_2$ denote the registered users
    who obtained these respective coins coins through withdrawal or
    refresh, but note $\V{pkU}_1$ and $\V{pkU}_2$ need not be distinct.
    Return 0 either if any of these do not exist, including
    if $\V{pkC}_0$ or $\V{pkC}_1$ were spent.
  % \item[5.] 
\end{enumerate}



\paragraph{Intuition:}  Users are anonymous if there is no adversary that can win this game,
since then two users can spend money, but the adversary is not able to say who purchased what.


\begin{mdframed}
There are two kinds of games found for anonymity in the
literature, one is based in indistinguishability (between two users or coins) and
the other one on simulation.  The latter is claimed to be more powerful in \cite{izabachene2013divisible}.

Note that our game lets both users spend, which means we don't need to ``magically'' come up for
a fresh coin for the only user who just spent one.  If only one coin is spent and we don't replace it,
the adversary can exhaust wallets to see who spent.  We can avoid this, since we have contract identifiers
and can rely on those.

The ``\dots AsUser'' oracles are not given to the adversary, since they play as the exchange and thus
allowing them to talk to themselves does not make sense.
\end{mdframed}

%\subsection{Unforgeability}
%\begin{enumerate}
%  \setlength\itemsep{0em}
%  \item $(skExchange, pkExchange) \leftarrow \algo{EKeygen}()$ 
%  \item $(r_1, r_2) = {\cal A}^{\ora{*}}()$
%    \comment{Two different receipts for deposit from the exchange / relayed by merchant}
%  \item return $1$ if $r_1, r_2 \neq \bot$, $r_1 \neq r_2$ and $r_1 = S(pkExchange, pkCoin, h_1)$ but $r_2 = S(pkExchange, pkCoin, h_2)$
%    with $h_1 \neq h_2$ for some $pkCoin$.
%\end{enumerate}

%Is this the right game?  We could also base it on not being able to spend more than was withdrawn.  Note that in the game above, we only look
%at receipts and the coin doesn't even need to be valid directly.

\subsection{Fairness}

Inuitively, an adversarial merchant wins if a non-corrupted user
cannot obtain a proof-of-spending or unlinkable change, including
if the deposit receipt from the exchange is forged by the merchant. 
We have auditors to address adversarial exchanges who attempt to defraud
users, but only with weaker legal security assurances.  

Let \oraSet{Fair} stand for access to the oracles
 \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
 \ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}.

\bigskip
\noindent $\mathit{Exp}_{\cal A}^{fair}(1^\lambda, \kappa)$:
\vspace{-0.5\topsep}
\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
  \item $C_0 \leftarrow {\cal A}^{\oraSet{Fair}}(pkExchange)$
  \item If $C_0$ is not a coin public key, return 0.  Let $U$ be the user that has $C_0$ in their wallet.  If no such $U$ exists, return 0.  $C_0$ need not unspent or unrefreshed.
  \item Let $C_0, \dots, C_n$ be the coins reachable via \algo{Link} from $C_0$.
  \footnote{In particular $n=0$ if $C_0$ is unrefreshed.}
  \item If $U$ was corrupted or \ora{Share} was called with any of $C_0, \dots, C_n$, return 0.
  \item $R \leftarrow \algo{Refresh}(\prt{B}(skE, pkE), \prt{U}(U, C_n))$
  \item If $R$ indicates a successful refresh, return $0$.
    If $R$ indicates double spending with contract $h$ and $h \in contractHashes[U]$, return 0.
    Otherwise return 1.
\end{enumerate}


\subsection{Unforgability} % Exculpability?

We tentatively restrict to a single denomination here for simplicity.

Let \oraSet{Forge} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
\ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient} ???

\bigskip
\noindent $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, \kappa)$:
\vspace{-0.5\topsep}
\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
  \item $(C_0, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{Forge}}(pkExchange)$
  \item Our adversary wins if they made at most $\ell$ withdrawals
    but $C_0, \dots, C_\ell$ are all distinct valid unspent unrefreshed coins.
\end{enumerate}


\subsection{Income Transparency}
Intuition: Adversary wins if money is in exclusive control of corrupted players but the exchange has no record of withdrawal or spending for it.

We also tentatively restrict to a single denomination here for simplicity.

Let \oraSet{Income} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{Spend},
\ora{RefreshAsExchange}, \ora{Share}, \ora{CorruptClient}

\bigskip
\noindent $\mathit{Exp}_{\cal A}^{income}(1^\lambda, \kappa)$:
\vspace{-0.5\topsep}
\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
  \item $(C_1, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{Income}}(pkExchange)$
  \item Augment the wallets of all non-corrupted users with their
    transitive closure using the \algo{Link} protocol.
    Mark all coins in wallets of non-corrupted users as spent.
  \item Let $w$ denote the number of coins withdrawn by corrupted users.
    Also let $b$ denote the number of coins lost in refresh operations
    with false planchets.  Our adversary wins if $w + b < \ell$ with
    $C_1, \dots, C_\ell$ all being distinct valid unspent unrefreshed coins.
\end{enumerate}

We show only bound adversaries' probability of winning one
 Income Transparency game by $1/\kappa$, but we prove separately
that attacks cannot be profitable in the sense that
 $E[{b \over \ell - w}] \ge 1-{1\over\kappa}$ 

\subsection{Others?}
Let adversary distinguish between freshly withdrawn coin and coin obtained via refresh protocol.  Why?

Camenisch-style fair exchange and endorsements.  Should not be too much work, games are already
given in literature.

\section{Instantiation}

Let $G \in \mathbb{E}$ be the generator of the Ed25519 curve (with Edwards coordinates).  

\begin{itemize}
  \item \algo{EKeygen}():  Generate an RSA key pair of length $k$ and return it.
  \item \algo{CKeygen}():  Generate an EdDSA key pair and return it.
  \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU})):
    \begin{enumerate}
      \item \prt{U} selects blinding factor $r \randsel \Z_N^*$, coin secret $\V{skC} \randsel \Z_{|\mathbb{E}|}$, computes
        $\V{pkC} = \V{skC} \cdot G$, $\overline{M} = r \cdot H(\V{pkC})$ and sends $\overline{M}$ to $\prt{E}$.
      \item \prt{E} receives $\overline{M}$ and sends back $\overline{M}^d \bmod N$ to \prt{U}.
    \end{enumerate}

    Thus the protocol transcript is $(\overline {M}, \overline{M}^d \bmod N)$.
  \item \algo{Spend}(contract, skCoin, pkReceiver):  TODO

    The deposit permission is computed as
    \begin{equation*}
      (\V{sig}, \V{pkCoin}) = (\algo{Sign}(skCoin, (contract, pkReceiver)), \V{skCoin} \cdot G)
    \end{equation*}

    
  \item \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{M}(\V{skU}, \V{depositPermission})):
    TODO
  \item \algo{Refresh}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin})):
    The protocol transcript is 
    \begin{equation*}
      (\V{pkCoin}, sig, T_1, \dots, T_\kappa, \overline{M}_1, \dots, \overline{M}_\kappa, \gamma, \tilde{t}_1, \dots, \tilde{t}_\kappa, \overline{M}_\gamma^d \bmod N)
    \end{equation*}

    where $t_i \randsel U$, $T_i = t_i \cdot G$, $s_i = ECDH(t_i, pkCoin)$, $r_i = PRF_{pkCoin}(s_i)$, $M_i = PRF_{pkCoin+1}(s_i)$, $\overline{M}_i = r_i \cdot M_i $ 
  \item \algo{Link}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{linkSecret}, \V{skCoin})):
    TODO
\end{itemize}

\section{Proofs}

\subsection{Anonymity}



%We can describe a simple blinding game for an RSA key pair $(n,e,d)$ and
%generators $M(\cdot)$ and $B(\cdot)$ for elements of $\Z/n\Z$ whose
%parameters we need not specify: 
%We take $m_0,m_1$ from $M$ and $b_0,b_1$ from $B$ and give our adversary
%$\cal A$ the unordered pairs of withdrawals $\{ m_0^d b_0, m_1^d b_1 \}$
%and deposits $\{ m_0^d, m_1^d \}$.  $\cal A$ wins if it can correctly
%match the withdrawals and deposits.
%
%\begin{lemma}\label{RSA_blind_signatures}
%Assume adversary $\cal A$ with an advantage in this blinding game for
%some $M_0(\cdot)$ and $B_0(\cdot)$ whatever their parameters.  There is
%a machine $\cal A'$ that identifies $B_0$ as opposed to a uniform
%distribution $U(Z/nZ)$ on $Z/nZ$.
%\end{lemma}
%
%\begin{proof}
%$\cal A'$ plays the blinding game with $\cal A$ taking $M$ to be $M_0$
%and $B$ to be $X$.  $\cal A$ either guesses correctly or incorrectly.
%If $\cal A$ guesses correctly, then $\cal A'$ guesses that yes $X$ is
%$B_0$.
%
%If $X$ is $B_0$ then $\cal A$ guesses correctly with advantage $\epsilon$, meaning
%  $P[ \textrm{$\cal A$ correct} | X=B_0 ] = 1/2+\epsilon$
%and
%  $P[ \textrm{$\cal A$ correct} | X=U ] = 1/2$.
%We imagine A' is given uniform trials to guess X=F vs X=U, so that
%  $P[X=F] = 1/2$ too,
%and 
%  $P[\textrm{$\cal A$ correct}] = 1/2 + \epsilon/2$.
%Now $\cal A'$ has an advantage in guessing if $X$ is $B_0$ or uniform correctly by
%Bays rule
%  $P[ \textrm{$\cal A$ correct} | X=B_0 ] P[X=B_0] = P[ X=B_0 | \textrm{$\cal A$ correct} ] P[A correct]$
%so
%  $P[ X=F | \textrm{$\cal A$ correct} ]
%  = 1/2 (1/2+\epsilon) / (1/2 + \epsilon/2)
%  = (1/2+\epsilon) / (1+\epsilon)
%  = 1 - 1/2 / (1+\epsilon)$.
%\end{proof}
%
%\begin{lemma}\label{interleaved}
%Let $X$ and $Y$ denote generators for elements in $\Z/n\Z$, taking
%unspecified parameters.  Let $I$ denote an interleaved sequence from
%$X$ and $Y$ taking concatenated parameters.  If some adversary has
%a non-ngeligable advnatage in distinguishing $I$ from $U(Z/nZ)$
%then some adversary has a non-ngeligable advnatage in distinguishing
%$J$ from $U(Z/nZ)$ wher eitehr $J=X$ or $J=Y$.
%\end{lemma}
%
%\begin{proof}
%Exercise for the reader.
%\end{proof}
%
%\begin{lemma}\label{PRF_composed_wth_ECDH}
%...
%\end{lemma}
%
%\begin{proof}
%...
%\end{proof}
%
%\begin{theorem}
%
%... $\cal A$ ...
%\end{theorem}
%
%\newcommand\pkCoin{pkCoin}
%
%\begin{proof}[Proof-ish]
%We consider the coin $\pkCoin$ of $U_b$ selected and spent by the
%game/environment starting from line 5, as well as the coin of
%$U_{1-b}$ that was unspent unshared in line 5, denoted $\pkCoin'$.
%
%We cannot corrupt either $U_0$ or $U_1$ nor share either $\pkCoin$ or
%$\pkCoin'$.  We may however add a spend or refresh of $\pkCoin'$ if
%$\cal A$ does not do so.  It follows that an advantage for $\cal A$
%in guessing $b'$ for our anonymity game yields an advantage in the
%blinding game given by the creation of $\pkCoin$ and $\pkCoin'$ in
%line 2 together with spending them in line 6. % and their deposit in line 7 
%
%In creating each of $\pkCoin$ and $\pkCoin'$, $\cal A$ either
%(1) invokes the withdrawal oracle directly, or else (2) applies the
%refresh oracle to some previous withdrawn coin.  These invokations
%together provide the $B_0$ in Lemma \ref{RSA_blind_signatures}.
%It follows that a non-negligible advantage for $\cal A$ yields a
%non-negligible advantage for the adversary $\cal A'$ who distinguishes
%this $B_0$ from a uniform distribution $U(Z/nZ)$ on $Z/nZ$.
%We cannot know if $\cal A$ constructs $B_0$ with direct withdrawals,
%refresh operations, or both.
%
%In the direct withdrawal only case, any advantage yields an advantage
%in distinguishing the FD-PRNG used from a uniform distribution,
% in which case we are done. 
%In the refresh only case, any advantage yields an advantage
%in distinguishing from uniform the compostion of the FD-PRF and ECDH
% used, in which case we  conclude by Lemma \ref{PRF_composed_wth_ECDH}.
%In mixed cases, we obtian one of the same two conclusions,
% by Lemma \ref{interleaved}.
%\end{proof}


\begin{theorem}
  The success probability $\Prb{b \randsel \{0,1\}: \mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b) = 1}$ is neglegible for
any PPT adversary \prt{A}.
\end{theorem}

\begin{proof}
  We give a proof via a sequence of games $\mathbb{G}_1(b), \mathbb{G}_2(b), \mathbb{G}_3(b)$, where $\mathbb{G}_1(b)$ is the original
  anonymity game $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$.  Let $\epsilon_{PRF}$ and $\epsilon_{DDH}$ be the advantage
  of an adversary for the PRF game and DDH game respectively.
  
  
  In $\mathbb{G}_2$, the refresh oracle is modified so that the client responds
  with value drawn from a uniform random distribution for the the $\gamma$-th
  commitment instead of using a Diffie-Hellman function.  Since $\gamma$ is
  chosen by the adversary after seeing the commitments, the simulator first
  makes a guess $\gamma^*$ and draws a uniform random value only for the
  $\gamma^*$-th commitment.  If the $\gamma$ chosen by the adversary does not
  match $\gamma^*$, the simulator rewinds \prt{A} to the point where the
  refresh oracle was called.  Note that this succeeds with probability
  $1/\kappa + \epsilon_{DDH}$.  Since $\kappa \ll \lambda$, the runtime
  complexity of the simulator still says polynomial in $\lambda$.  Note that we
  only replace the one commitment that will not be opened to the
  adversary later.

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

  \bigskip
  \noindent $\mathbb{G}_{1 \sim 2}(b)$:
  \vspace{-0.5\topsep}
  \begin{enumerate}
    \setlength\itemsep{0em}
    \item $D = C_{ddh}(b)$
      \comment{The DDH challenger gives us a distribution that is either $(g^a, g^b, g^{ab})$ or $(g^a, g^b, g^c)$}
    \item return $\mathit{Exp'}_{\cal A}^{anon}(b, D)$
      \comment{Modified anonymity game where the $\gamma$-th commitment in the
      refresh oracle is drawn from distribution $D$ (using rewinding).  Technically we need to
      draw from $D$ on withdraw for the coin private key, write it to a table, look it up on refresh and 
      use the matching tuple.}
  \end{enumerate}
  
  We observe that depending on the coin flip $b$, we either simulate $\mathbb{G}_1$ or $\mathbb{G}_2$ perfectly for
  adversary $\cal A$ against $\mathbb{G}_1$.  At the same time $b$ determines whether \prt{A} receives $(g^a, g^b, g^{ab})$ or $(g^a, g^b, g^c)$.
  Thus $\left| \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1} \right| = \epsilon_{DDH}$ is exactly the DDH advantage of $\mathbb{G}_{1 \sim 2}$.

  In the hop between $\mathbb{G}_2$ and $\mathbb{G}_3$ we replace the PRFs with a random uniform function. \comment{Does this need a proof?
  Do we need to do this for the next step?  If so, we just use exactly the same technique as in the last hop with PRF instead of DDH.}

  The coins obtained from refresh and from withdraw have now the same distribution in $\mathbb{G}_3$.
  Since the blinding is perfect, the adversary has no information to associate a withdraw/refresh transcript
  with a spend transcript.  Thus the success probability for $\mathbb{G}_3$ is $1/2$.

  We conclude that that the success probability for $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, \kappa, b)$ is at most $1/2 + \epsilon_{DDH} + \epsilon_{PRF}$.

  \comment{The DDH game we use here is non-standard (stream of values to decide on instead of one, so maybe we need to use the number of refresh oracle invocations
  as a factor in front of $\epsilon_{DDH}$?}

\end{proof}


\begin{mdframed}
  Note that the order of the hops does matter, since it's important that we feed the PRF
  real randomness.
\end{mdframed}


\subsection{Fairness}

\begin{theorem}
If our signature scheme used for coins signing contracts is
 polynomially-secure, 
then Taler is polynomially-secure against attacks on fairness.
\end{theorem}

\begin{proof}
We required that any refresh operations were run to conclusion, 
which makes sense with our adversary $\cal A$ being a merchant
unable to control either the customer or exchange.  It follows 
that $\cal{A}$ never called the refresh oracle on $C_n$.

As the refresh $R$ must fail, $\cal A$ must have the customer
spend $C_n$, and then either deposit $C_n$, refresh $C_n$, or
spend $C_n$ with another merchant.
In any case, $\cal A$ must not return the correct receipt to
the customer, doing so concludes the transaction honestly.  

If $\cal A$ deposits $C_n$, then the customer would also obtain
the correct receipt from exchange by doing a refresh, so the
adversary must distract them with signed message from the exchange
indicating double spending or previous refresh. In either subcase,
$\cal A$ provides signatures by both $C_n$ and $\V{pkE}$.

If $\cal A$ either refreshes or spends $C_n$, then they provide
a signature by $C_n$ too.

In all cases, we discover a forged signature by $C_n$, yielding
an adversary who could attack the coin signature scheme.
\end{proof}

We have stated the game and theorem with $\cal A$ controlling only
the merchant, but even if they control the exchange as well they
still cannot forge the signature by $C_n$.  An exchange has access
to more oracles however so they can take actions like dropping the
refresh connection.  Attacks like these can only be thwarted with
the aid of authorities who can witness the attack, like our auditor.


\subsection{Unforgeability} % Exculpability?

TODO: Copy in definitions

\begin{theorem}
In the random oracle model,
if the RSA known-target inversion problem (RSA-KTI) is hard, then
Taler is polynomially-secure against one-more forgery attacks.
% by probabilistic polynomially time adversaries.
\end{theorem}

\begin{proof}
We consider a probabilistic polynomially time adversary $\cal A$ with
a non-negligible advantage for winning the unforgeability game
 $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, \kappa)$.
We describe an RSA Chosen-Target Inversion Problem (RSA-CTI)
 \cite[Definition 3]{RSA-FDH-KTIvCTI} % or \cite[DEfinition 6.1]{OneMoreInversion}.
won by $\cal A$. 

We let $C_{\ell+1}, \ldots, C_m$ denote all the spent coins arising
from the operation of $\cal A$. % Also let $C_{m+1}, ..., C_n$ denote
% the unsigned planchets used by refresh oracle call. 
% Now set $Y_i = FDA_N(C_i)$ for $0 \le i \le n$. 
% DISCUSS: We could exploit some of the power of RSA-CTI to dispose
% of these planchets.  I think this seems unnecessary, but maybe it
% might refines our usage of ROM or something.
We know $\cal A$ made at most $m$ withdrawal and refresh oracle
queries to obtain the $l+1$ RSA signatures %, aka inversions,
 on the $Y_i := FDA_N(C_i)$ with $0 \le i \le m$. 
%
It follows that $\cal A$ has produced one-more forgery in the sense
 of \cite[Definition 4 \& 5, pp. 369]{Pointcheval_n_Stern}, so
RSA-KTI cannot be hard by \cite[Theorem 12]{RSA-FDH-KTIvCTI}.
%
% So $\cal A$ wins this RSA-CTI game with its random sampling to produce
% $Y_i$ replaced by our PRF $FDA_N$, which requires nothing since we're
% already working in the stronger random oracle model anyways.
% We finally exploit the full random oracle model to apply 
% \cite[Theorem 6]{RSA-FDH-KTIvCTI} to produce an adversary who breaks
% RSA-KTI.
% DISCUSS CONTINUED: This argument directly from Theorem 6 seems wrong
% because the ROM in \cite[Lemma 13]{RSA-FDH-KTIvCTI} does not appear.
% We should figure out what's really going on.
\end{proof}


\subsection{Income Transparency}

\begin{definition}
A {\em key exchange failure} consists of two key pairs
 $A = a G$ and $B = b G$ such that $b A \neq a B$.
\comment{Find this in literature?  Is it related to contributory behavior?}
\end{definition}

\begin{theorem}
Assume Taler is polynomially-secure against
\begin{enumerate}
\item one-more forgery attacks,
\item collisions in the hash function the refresh protocol uses
 to commit to planchets, and
\item key exchange failures in the ECDH operation used in the refresh.
\end{enumerate}
Then Taler is polynomially-secure against attacks on
income transparency in the sense that
any probabilistic polynomially time adversary $\cal A$ has at best
a $1\over\kappa$ chance to win the income transparency game.

As our $\kappa$ is tiny, we also observe that 
 Taler is polynomially-secure against profitable attacks on
income transparency in the sense that
any probabilistic polynomially time adversary $\cal A$ has 
$E[{b \over l-w}] \ge 1-{1\over\kappa}$.
\end{theorem}

\begin{proof}
In our actual refresh operation, our commitment phase sends only the
hash of the planchets to reduce bandwidth.  We could however commit
to the full planchets without damaging anything else, including
unforgeability.  We may transform our our adversary $\cal A$ into
any adversary for the protocol that commits to full planchets by
rewinding $\cal A$ to try each $\gamma \in 1,\ldots,\kappa$ during
each refresh operation to obtain all planchets.  We observe a hash 
collision if this fails to provide the correct coins. 

We consider the degree one directed graph on coins induced by the
refresh protocol.  It follows from unforgeability that any coin
must originate from some user's withdraw in this graph.  
Let $X$ denote the coins from $\{C_1,\ldots,C_\ell\}$ that originate
from a non-corrupted user.  So $\ell \leq w + |X|$. 

For any $C \in X$, there is a final refresh operation $R_C$ 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 $C$ gets marked as spend. 

In each $R_C$, we know $\cal A$ must submit a planchet for which the
linking protocol fails produce $C$ correctly.  In this case, either
\begin{enumerate}
\item the planchet must be false outright, meaning either $C$ itself
 or the blinding factor does not arise form $t C'$, or else
\item  the exchange would compute the planchet correctly, but not
 users employing the linking protocol, meaning
 $t C' \neq c' T$ where $T = t G$ is the transfer key.
\end{enumerate}

In theory, our scalar multiplication should be injective, preventing
the second case where $t C' \neq c' T$.  In practice, our exchange 
might incorrectly have multiple scalar representatives $t$ yield the
same curve point $t C'$, while the user's cannonical computation of
$c' T$ yields a distinct point, like perhaps the exchange accepts and
uses an incorrectly clamped scalar $t$ without correcting the clamping itself. 

We may therefore assume the first case that $\cal A$ provides a
false planchet outright.  We may assume $\cal A$ submits a false
planchet for at most one choice of $\gamma$,
as otherwise the refresh always fails.

As our $\gamma$ are chosen randomly, any given refresh with one
false planchet has a $1-{1\over\kappa}$ chance of contributing to
 $b$ instead of $|X|$, as desired.
It now follows that
 $E[{b \over l-w}] \ge E[{b \over f}] = 1-{1\over\kappa}$
where $f \ge l-w$ denotes
 the number of refreshes attempted with false planchets.
\end{proof}

\begin{corollary}
In the random oracle model,
if the RSA known-target inversion problem (RSA-KTI) is hard, then
Taler is polynomially-secure against profitable attacks on
 income transparency.
\end{corollary}

We observe that $t C' = c' T$ provides a delicate requirement for
implementations:  An exchange might do the scalar multiplication by
the basepoint $T = t G$ differently than the arbitrary scalar
multiplication $t C'$, in curve25519 say by clearing the low bits
to multiply by the cofactor for $t G$ but not for $t C'$.  
In this case, the customer could still reclaim the coin by running
refreshes with each possible cofactor deviation.  

As using the linking protocol risks anonymity, we do not implement it
ourselves and permit taxability to rest on the threat of a customer
implementing it because a merchant asks them to use a wallet modified
for tax evasion.  We feel this threat is more credible if said
customer does not need to understand cofactors.

In this vein, there are modifications of Taler in which the customer
has no efficient algorithm to correct $t C' \neq c' T$:
 
Our blinding operation is information theoretically secure of course,
so withdrawn coins information theoretic, and hence post-quantum,
anonymity.  Refreshed coins clearly lacks post-quantum anonymity.
We lack post-quantum security for all our RSA and Ed25519 signature
schemes too of course, but this only presents problems once quantum 
computers actually exist.   

We might worry that refreshed coins might deanonymize current users
to an adversary who copies the databases of exchanges and merchants
today and only develops quantum computers in the future.  
How should we adapt Taler to defeat this adversary?  

We could extend the coin signing key $C$ to be a pair $(C,P)$ in
which $P$ is a public key for some post-quantum key exchange, but
doing so requires that the post quantum key exchange provides the
equivalent of $t C' = c' T$.  

In Ring-LWE schemes for example,
there is usually a risk that the reconciliation part of the key
exchange fails to compute the correct result.  These schemes
make this risk low, but since the income adversary known both
sides private keys they can seemingly always construct transfer
private keys that break income transparency.

There is no such problem with supersingular isogenies Diffie-Hellman
key exchange (SIDH) per se, but currently it remains about a hundred
times slower than curve25519.  As the SIDH public keys must be checked
in refresh, this adds $\kappa$ expensive SIDH operations per refresh,
which sounds unacceptable.

As it turns out, there is a simple hash-based solutions that works
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.  
% Anything about fragility?


\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 nonnegligible
  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{Questions/Todo}
\begin{itemize}
  \item We trivially get endorsed e-cash, should we add the games / definitions?
\end{itemize}


\bibliography{lit}
\bibliographystyle{alpha}

\end{document}
