From 629d44aa0e8bb90954f6ec086d590239fff67006 Mon Sep 17 00:00:00 2001 From: Florian Dold Date: Fri, 10 Nov 2017 02:52:08 +0100 Subject: fixes --- games/games.tex | 92 +++++++++++++++++++++++++++++++++------------------------ 1 file changed, 53 insertions(+), 39 deletions(-) (limited to 'games') diff --git a/games/games.tex b/games/games.tex index a9c40dc..22dd209 100644 --- a/games/games.tex +++ b/games/games.tex @@ -47,14 +47,11 @@ 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. -Signature over message $m$ with public key $p$ is denoted by $S(m, p)$. For notational convenience, includes -both the signature and the message. By convention, names for private keys begin with $pk$ and $sk$ for secret keys. - -We track $countDeposit[pkClient]$ and $countWithdraw[pkClient]$ separately for -each client. The private keys of coins certainly known by clients are stored as -$wallet[pkClient]$. Contracts are tracked created during deposit are tracked -as $contractHashes[pkClient]$. The exchange keeps track of $spent[pkCoin]$ and $refreshCommit[pkCoin]$ and $refreshFail[pkCoin]$. +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. @@ -64,22 +61,29 @@ 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{skExchange}, \V{pkExchange})$. + \item \algo{CKeygen}(): Probabilistic algorithm executed by customers, outputs a key pair $(\V{sk}, \V{pk})$. \item \algo{Withdraw}(\prt{E}(\V{skE}, \V{pkE}, \prt{U}(\V{skU}, \V{pkU})): Interactive protocol between exchange and user. - \item \algo{Spend}(contract, skCoin, pkReceiver): Probabilistic algorithm. Signs a deposit permission for a particular contract. + + 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). - On double-spending, return the protocol transcript of the deposit/refresh. + 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{c})): - Interactive protocol between exchange and user. + 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. \item \algo{RefreshReveal}(\prt{E}(\V{skE}, \V{pkE}), \prt{U}(\V{skU}, \V{pkU}, \V{skCoin}, \V{r})): - Interactive protocol between exchange and user. + 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. + 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} @@ -88,40 +92,43 @@ We define the following oracles: \begin{itemize} \item $\ora{AddClient}()$: - Creates a new client, sets $balanceDeposit$ and $balanceWithdraw$ for the client to $0$, sets $wallet[pkClient] := \{\}$. + Creates a new client, sets $countWithdraw$ for the client to $0$, sets $wallet[pkClient] := \{\}$. + Returns the public key of the client. - \item $\ora{Withdraw}(pkClient)$: + \item $\ora{WithdrawAsUser}(pkClient)$: Do a withdraw from the perspective of a user. The adversary + controls the user, the simulator the bank. - Decreases $balanceWithdraw[pkClient]$ by one, adds the resulting coin to the wallet. + \item $\ora{WithdrawAsBank}(pkClient)$: Do a withdraw from the perspective of a bank. The adversary + controls the bank, 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 handle to the refresh session if the client has at least one coin, or $\bot$ otherwise. + 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, handle, 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) \mapsto S(pkCoin, contractHash, pkReceiver)$ - Make a customer sign a deposit permission. + \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. - Also adds $contractHash$ to $contractHashes[pkSpender]$. + \item $\ora{Share}(pkSender, pkReceiver)$: - \item $\ora{Share}(pkCoin, pkReceiver)$: + Shares one random, previously unshared coin in the wallet of $pkSender$ with $pkReceiver$. - Adds the coin to the receiver's wallet and reveals the coin secret key. - - \item $\ora{Deposit}(S(pkCoin, contractHash, pkReceiver))$: - - If a coin is double-spent (by spending it on a different $contractHash$) then $receipt = \bot$. Sets $spent[pkCoin] := 1$. + \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 and wallet. + client's private key, wallet and signed contract hashes. \end{itemize} \section{Games} @@ -131,7 +138,7 @@ We define the following oracles: \subsection{Anonymity} Anonymity game with adversary $\prt{A}$, where $\ora{*}$ means access to all -oracles (\ora{AddClient}, \ora{Withdraw}, \ora{Deposit}, \ora{Spend}, +oracles (\ora{AddClient}, \ora{WithdrawAsBank}, \ora{WithdrawAsUser}, \ora{Deposit}, \ora{Spend}, \ora{RefreshCommit}, \ora{RefreshReveal}, \ora{Share}, \ora{CorruptClient}). \begin{enumerate} @@ -144,7 +151,7 @@ oracles (\ora{AddClient}, \ora{Withdraw}, \ora{Deposit}, \ora{Spend}, \item $b \randsel{} \{0,1\}$ \comment{Random bit selected by challenger} \item select unspent coin $pkCoin$ from wallet of $\V{pkU}_b$. - \item $\V{dp} \leftarrow \algo{Spend}(\V{contract}, \V{pkCoin}, \V{pkM})$ + \item $\V{dp} \leftarrow \algo{Spend}(\V{contract}, \V{pkU}_b \V{pkCoin}, \V{pkM})$ \item $\algo{Deposit}(\prt{E}(\V{skE}, \V{pkE}), \prt{A}())$ \comment{Role of merchant is played by adversary} \item sign a fresh coin and add it to the wallet of $\V{pkU}_b$ @@ -169,8 +176,8 @@ the other one on simulation. The latter is claimed to be more powerful in \cite % 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. +%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. @@ -179,12 +186,14 @@ Intuition: Adversary wins if a non-corrupted user can't obtain a proof-of-spendi \begin{enumerate} \setlength\itemsep{0em} \item $(skExchange, pkExchange) \leftarrow \mathrm{EKeygen}()$ - \item $C \leftarrow \prt{A}^{\ora{*}}(pkExchange)$ - \item Let $U$ be the user that has $C$ in their wallet. If no such $U$ exists, return 0. - \item If $U$ was corrupted or \ora{Share} was called with $C$, return 0. - \item $R \rightarrow \algo{Refresh}(\prt{B}(skExchange, pkExchange), \prt{U}(U, C))$ + \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. + If $R$ indicates double spending with contract $h$ and $h \in contractHashes[U_n]$, return 0. Otherwise return 1. \end{enumerate} @@ -237,9 +246,13 @@ given in literature. 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{Unforgeability} -\paragraph{``Proof sketch''.} Relatively straigt reduction to RSA-KTI and unforgeability of EdDSA. Either -the exchange must have accepted the coin, and the co + +\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 coins that are not in the wallet of any non-corrupted user. @@ -292,6 +305,7 @@ From \cite{bellare2003onemore}. Assumption to prove security of RSA blind signa \section{Questions/Todo} \begin{itemize} \item Some authors first present the protocol and then oracles, others directly use the protocol syntax as oracles. What should we do? + \item We trivially get endorsed e-cash, should we add the games / definitions? \end{itemize} \bibliography{lit} -- cgit v1.2.3