path: root/games/games.tex

\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}
\newtheorem{theorem}{Theorem}

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

\begin{document}


%\newcommand{randsel}{\ensuremath{\xrightarrow[\text{world}]{\text{hello}}}}
\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}}}

\maketitle

\section{Model and Syntax}

The exchange is one entity, there is only one exchange, there are many clients
and a client can act as a merchant, a customer or both (no further distinction other than naming in the role).
By convention, names for private keys begin with $pk$ and $sk$ for secret keys.

We track $\V{countWithdraw}[\V{pkClient}]$ for each client.  The private keys of coins given to clients are stored as
$\V{wallet}[\V{pkClient}]$.  Contracts are created during deposit are tracked
as $\V{contractHashes}[\V{pkClient}]$.  The exchange keeps track of $\V{spent}[\V{pkCoin}]$ and $\V{refreshCommit}[\V{pkCoin}]$ and $\V{refreshFail}[\V{pkCoin}]$.


Simplification:  No partial spending, only one denomination.

\subsection{Algorithms}
The Taler e-cash system is defined by the following algorithms.

\begin{itemize}
  \item \algo{EKeygen}():  Probabilistic algorithm executed by the exchange, outputs a key pair $(\V{skE}, \V{pkE})$.

  \item \algo{CKeygen}():  Probabilistic algorithm executed by customers, 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.

    Increases $countWithdraw[pkU]$ by one, adds the resulting coin to the wallet $wallet[pkU]$.
  \item \algo{Spend}(contract, pkClient, skCoin, pkReceiver):  Probabilistic algorithm. Signs a deposit permission for a particular contract.
    Adds $contract$ to $contractHashes[pkClient]$.
  \item \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{M}(\V{skU}, \V{depositPermission})):
  Interactive protocol between the exchange and a customer (acting as merchant).

  Marks the coin with public key $pkCoin$ in the deposit permission as $spent[pkCoin] := 1$.

  On double-spending, return the protocol transcript of the deposit/refresh.  On success, returns exchange's signature over the request.
  \item \algo{RefreshCommit}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{commitData})):
  Interactive protocol between exchange and user.  Marks the coin with secret key $skCoin$ as spent and uses $c$ as commitment.

  If the refresh would be double spending, return the protocol transcript of the deposit/refresh.
  On success, returns $\gamma$, the index of the commitment that should not be revealed.
  \item \algo{RefreshReveal}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{revealData})):
  Interactive protocol between exchange and user.  If revealed value $r$ does not match commitment or the coin marked as previously failed in $refreshFail$, return
  protocol transcript of prior refresh.  Otherwise, return fresh coin.
  \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, adds a coin that resulted from the refresh to the user's wallet.
\end{itemize}

\subsection{Oracles}

We define the following oracles:

\begin{itemize}
  \item $\ora{AddClient}()$:
    Creates a new client, sets $countWithdraw$ 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{RefreshCommit}(pkClient, blindedNewCoins, commitData)$
    Forces the client to execute the refresh protocol, with data provided by
    the adversary.  Returns a the index to be revealed and a handle to the
    refresh session if the client has at least one coin, or $\bot$ otherwise.

  \item $\ora{RefreshReveal}(pkClient, refresHandle, revealData)$

    Force a client to do a reveal.
    
    Returns the new coin, or transcript of double spending / wrong commit on failure.

    Note that the handle is necessary so the adversary
    can make clients refresh without seeing the actual coins.

  \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{Deposit}(depositPermission)$:
    Give a deposit permission to the exchange.  Returns the exchange's response.

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

All algorithms need to be polynomial time, but this is already implied by the
definition of the adversary and simulator.
\end{mdframed}



\section{Games}

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


\subsection{Anonymity}
Anonymity game with adversary $\prt{A}$.
Let \oraSet{Anon} stand for access to the oracles \ora{AddClient}, \ora{WithdrawAsExchange}, \ora{WithdrawAsUser}, \ora{Deposit}, \ora{Spend},
\ora{RefreshCommit}, \ora{RefreshReveal}, \ora{Share}, \ora{CorruptClient}

\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(\V{skE}, \V{pkE}) \leftarrow \prt{A}()$
    \comment{``Adversary controls the exchange.''  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{skM}, \V{pkM}, \V{contract_0}, \V{contract_1}) \leftarrow \prt{A}^{\oraSet{Anon}}()$
    \comment{Adversary must create two users, a merchant and two contract identifiers}
  \item if $\V{pkU}_1$ or $\V{pkU}_2$ are not registered as distinct users, return 0
  \item $b \randsel{} \{0,1\}$
    \comment{Random bit selected by challenger}
  \item select unspent coins $pkC_0, pkC_1$, from wallets of $\V{pkU}_0, \V{pkU}_1$ respectively.
  \item $\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})$
  \item $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{A}(dp_1))$, \\
        $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{A}(dp_2))$
    \comment{Role of merchant is played by adversary}
  \item $b' \leftarrow \prt{A}^{\oraSet{Anon}}()$
    \comment{Ask adversary to find out mapping between users and contracts as determined by $b$}
  \item if $\V{pkU}_1$ or $\V{pkU}_2$ were corrupted by \prt{A}, return 0
  \item if \ora{Share} was used with $\V{pkU}_1$ or $\V{pkU}_2$ as source, return 0
  \item if $b = b'$ return 1, otherwise return 0
\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.

\paragraph{Todo:}  Show that/how in our model, this also implies that anonymous purchases are independent from \emph{each other}.

\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 spend 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.
\end{mdframed}

%\subsection{Unforgeability}
%\begin{enumerate}
%  \setlength\itemsep{0em}
%  \item $(skExchange, pkExchange) \leftarrow \algo{EKeygen}()$ 
%  \item $(r_1, r_2) = \prt{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}
Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spending or unlinkable change.


\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(skE, pkE) \leftarrow \mathrm{EKeygen}()$ 
  \item $C_0 \leftarrow \prt{A}^{\ora{*}}(pkExchange)$
  \item Let $U$ be the user that has $C_0$ in their wallet.  If no such $U$ exists, return 0.
  \item Let $C_0, \dots, C_n$ be the coins reachable via \algo{Link} from $C_0$.
    \comment{When $C_0$ was not refreshed, $n=0$ and $C_n = C_0$}
  \item If $U$ was corrupted or \ora{Share} was called with any of $C_0, \dots, C_n$, return 0.
  \item $R \rightarrow \algo{Refresh}(\prt{B}(skExchange, pkExchange), \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}

\paragraph{Note:}  This also covers the case where the deposit receipt from the exchange is forged by the merchant.


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

\begin{enumerate}
  \setlength\itemsep{0em}
  \item $(skExchange, pkExchange) \leftarrow \mathrm{EKeygen}()$ 
  \item $(C_1, \dots, C_\ell) \leftarrow \mathcal{A}^{\ora{Withdraw}}(pkExchange)$
  \item wallets of all non-corrupted users are augmented with their transitive closure via the \algo{Link} protocol
  \item all coins from wallets of non-corrupted users are marked as spent
  \item let $V_r$ be the number of valid non-spent coins in $(C_1, \dots, C_\ell)$  and $V_w$ the number of coins withdrawn by corrupted users
  \item adversary wins if $V_r > V_w$.
\end{enumerate}

Income transparency implies unforgeability.

Note that we want to show in the end that the probability of winning one Income Transparency game is at most $1/\kappa$.
This is why $\kappa$ does not appear directly in the proof.

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

\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})):
    TODO
  \item \algo{Spend}(contract, skCoin, pkReceiver):  TODO
  \item \algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{M}(\V{skU}, \V{depositPermission})):
    TODO
  \item \algo{RefreshCommit}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{c})):
    TODO
  \item \algo{RefreshReveal}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{r})):
    TODO
  \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-negligable advantage for $\cal A$ yields a
non-negligable 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}





\paragraph{``Proof sketch''.}  Proof by looking at withdraw/deposit/refresh transcripts seen by the adversary.  Do game hopping, replace
everything that's not random by something random (with computationally indistinguishable distribution) until everything that the adversary
could see in a game has the same probability, and he must win with probability $1/2$.


\subsection{Fairness}
\paragraph{``Proof sketch''.}  We enumerate all things that can lead to a failure in the refresh step.
\begin{itemize}
  \item double-spending with different contract hash $\Rightarrow$ merchant can forge/modify deposit permission
  \item double-spending with refresh $\Rightarrow$ linking protocol must be broken
\end{itemize}

\subsection{Income Transparency}
To win the game, the adversary must produce enough coins that are not in the wallet of any non-corrupted user, but withdraw little
coins via corrupted users.

\begin{lemma}
  The signatures on $C_1, \dots, C_\ell$ must have been obtained by using either \ora{Withdraw}, \ora{RefreshReveal} or \ora{Link}.
\end{lemma}

\begin{lemma}
  \ora{Link} can not be used to get a coin from a non-corrupted peer.
\end{lemma}

\begin{lemma}
  To win the Income Transparency game, the adversary must call $\ora{RefreshReveal}$ at least $(\kappa V_r - V_w) > 0$ times
  in a way that causes the linking step to fail.  (This implies unforgeability.)
\end{lemma}

\begin{lemma}
  The probability to successfully use \ora{RefreshCommit} and \ora{RefreshReveal} in a way that causes \algo{Link} to return $\bot$ is at most $1/\kappa$.
\end{lemma}

\begin{theorem}
  The adversary wins the Income Transparency game with with probability at most $1 / \kappa$.
\end{theorem}

FIXME:  We should also include what the expected ``untaxed'' money for the adversary is for each won game, vs. the money wasted.

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