diff options
Diffstat (limited to 'games/games.tex')
| -rw-r--r-- | games/games.tex | 152 |
1 files changed, 152 insertions, 0 deletions
diff --git a/games/games.tex b/games/games.tex new file mode 100644 index 0000000..9b9094f --- /dev/null +++ b/games/games.tex @@ -0,0 +1,152 @@ +\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} + +\title{Taler Provable Security} +\date{\today} + + +\begin{document} + +%\newcommand{randsel}{\ensuremath{\xrightarrow[\text{world}]{\text{hello}}}} +\newcommand{\randsel}[0]{\ensuremath{\xleftarrow{\text{\$}}}} + +\maketitle + +\section{Model and Syntax} + +Signature over message $m$ with public key is denoted by $S(m, p)$. For notational convenience, includes +both the signature and the message. By convention, private keys begin with $pk$ and secret keys with $sk$. + +The exchange is one entity, there is only one exchange (reason?!), 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). + +We track $balanceDeposit[pkClient]$ and $balanceWithdraw[pkClient]$ separately. The withdraw balance starts at $0$ and +can become negative. The withdrawn coins are tracked in $wallet[pkClient]$. Contracts are tracked created during deposit +are tracked as $contractHashes[pkClient]$. The exchange keeps track of $spent[pkCoin]$. + +Simplification: No partial spending (reasonable?) + +\begin{itemize} + \item $\mathrm{Setup}(1^\lambda, \kappa)$ + + Generates and distributes denomination public kets + to all participants. + \item $\mathrm{ExchangeKeygen} \mapsto (skExchange, pkExchange)$ + \item $\mathcal{O}\mathrm{AddClient} \mapsto pkClient$ + + Sets $balanceDeposit$ and $balanceWithdraw$ for the client to $0$, sets $wallet[pkClient] := \{\}$. + + \item $\mathcal{O}\mathrm{Withdraw}(pkClient, pkDenomList) \mapsto \{ S(pkDenom_i, pkCoin_i) \mid 0 \le i < n \}$ + + Decreases $balanceWithdraw[pkClient]$ by one, adds the resulting keys to the wallet. + \item $\mathcal{O}\mathrm{Refresh}(honest, S(pkDenomOld, pkCoinOld), targetCustomer) \mapsto (linkSecret, newCoins)$ + + When $honest = \bot$, then with probability $1/\kappa$ the target customer obtains completely unlinkable change + and thus $linkSecret = \bot$. + + Sets $spent[pkCoinOld] := 1$. + + \item $\mathcal{O}\mathrm{Link}(linkSecret, skCoinOld) \mapsto coins$ + + Returns blinded signatures for refreshed coin if $linkSecret$ was produced by the refresh + oracle and is not $\bot$. + + \item $\mathcal{O}\mathrm{Spend}(contractHash, pkSpender, pkCoin, pkReceiver) \mapsto S(pkCoin, contractHash, pkReceiver)$ + + Signs a ``deposit permission``. An oracle since it accesses the coin's private key to produce the signature. + Allows the adversary to force customers to spend coins without corrupting them. + + Also adds $contractHash$ to $contractHashes[pkSpender]$. + + \item $\mathcal{O}\mathrm{Share}(pkCoin, pkReceiver) \mapsto skCoin$ + + Adds the coin to the receiver's wallet and reveals the coin secret key. + + \item $\mathcal{O}\mathrm{Deposit}(S(pkCoin, contractHash, pkReceiver)) \mapsto S(pkExchange, pkCoin, contractHash) = receipt$ + + If a coin is double-spend (by spending it on a different $contractHash$) then $receipt = \bot$. Sets $spent[pkCoin] := 1$. + + \item $\mathcal{O}\mathrm{CorruptClient}(pkClient) \mapsto skClient$ + + Used by the adversary to corrupt a client. Marks the client as corrupted and gives the adversary the + client's private key. +\end{itemize} + +\section{Games} + + +\subsection{Anonymity} +Intuition: Same as offline e-cash, but we might add something more complicated to have refresh be part of it. + +\begin{enumerate} + \item $b \randsel{} \{0,1\}$ + \item $pkExchange \leftarrow \mathcal{A}()$ + \item adversary registers two users ($u_0$ and $u_1$) and one merchant, selects amount + \item the adversary must have registered users and withdraw amount or adversary loses + \item $u_b$ spends money with adversary-controlled merchant + \item $b \leftarrow \mathcal{A}()$ + \item if adversary corrupts $u_1$ or $u_0$ the adversary loses + \item if adversary used sharing oracle with $u_1$ or $u_0$ the lose +\end{enumerate} + +\subsection{Unforgeability} +Intuition: Offline e-cash has the double spender traceability game, which implies unforgeability. We need to have +it separately here. + +\begin{enumerate} + \item $(skExchange, pkExchange) \leftarrow \mathrm{ExchangeKeygen}()$ + \item $(r_1, r_2) = \mathcal{A}()$ + \item return $1$ if $r_1, r_2 \neq \bot$, $r_1 \neq r_2$ and $r_1 = (pkExchange, pkCoin, h1)$ but $r_2 = (pkExchange, pkCoin, h2)$ + with $h1 \neq h2$ 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. + +\subsection{Fairness} +Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spending or unlinkable change. + + +\begin{enumerate} + \item adversary gets all oracles, does not control the exchange + \item if there is a non-corrupted user $u$ that has a coin in $wallet[pkCustomer]$ that can't be + successfully refreshed and was not spent for and contract hash generated by the user $contractHashes[pkCustomer]$, the + adversary wins. +\end{enumerate} + +FIXME: this does not cover that the change needs to be unlinkable to original coins. + + +\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} + \item adversary gets all oracles, no control over exchange + \item adversary produces $(skCoin, S(pkDenom, pkCoin))$ + \item non-corrupted players refresh and spend their whole wallet + \item let $V_r$ be the value of coins still spendable by the adversary and $V_w$ the coins withdrawn by the adversary. + \item adversary wins if $V_r \ge V_w/\kappa$. +\end{enumerate} + +FIXME: this does not explicitly consider the amount ``burned`` during refresh. Necessary/better? + +\subsection{Others?} +Let adversary distinguish between freshly withdrawn coin and coin obtained via refresh protocol. Why? + +\section{Instantiation} + +\section{Proofs} + + + +\end{document} |