diff options
| -rw-r--r-- | comparison/comparison.tex | 16 | ||||
| -rw-r--r-- | comparison/literature.bib | 34 | ||||
| -rw-r--r-- | games/games.tex | 152 | ||||
| -rw-r--r-- | ideas.txt | 2 |
4 files changed, 179 insertions, 25 deletions
diff --git a/comparison/comparison.tex b/comparison/comparison.tex index 983eaa9..909fee7 100644 --- a/comparison/comparison.tex +++ b/comparison/comparison.tex @@ -79,7 +79,7 @@ Offline Chaum \cite{chaum1990untraceable} & \Y & $\log n$ & $\log n$ & \N & \N \\ -Tracz \cite{tracz2001} % HINDE +Tracz \cite{tracz2001fair} % HINDE & 2001 & E & \Y & \Y & ? & \N @@ -87,7 +87,7 @@ Tracz \cite{tracz2001} % HINDE & \Y & $\log n$ & $\log n$ & Onl. & \N \\ -Compact \cite{camenisch2005} +Compact \cite{camenisch2005compact} & 2005 & \N & \N & \N & ? & \N @@ -102,7 +102,7 @@ Compact \cite{camenisch2005} % & \Y & \N & W % We're guessing trustless anonymity because not trusted setup % & OFF & \N \\ -Divisible \cite{pointcheval2017} +Divisible \cite{pointcheval2017cut} & 2017 & \N & \N & \N & ? & \N @@ -173,7 +173,7 @@ Taler \item \textbf{Receipts \& Refunds.} The customer either can prove that they payed for a contract, or they can get their (unlinkable) money back, - which provides a form of fair exchange ala \cite{camenisch2007endorsed}. + which provides a form of fair exchange ala \cite{camenisch2008endorsed}. Also merchants can issue refunds for completed transactions. These operations must not introduce linkability or otherwise compromise the customer's anonymity. @@ -252,10 +252,10 @@ transactions with the same coin are linkable. Reference: \cite{schoenmakers1997security}. Has some practical aspects, including ``coinage'' (=denomination) expiration. \subsection{Electronic Cash with Change Return} -Reference: \cite{tracz2001}. Has change return, but not with the same taxability guarantees as Taler. Also has an implementation. +Reference: \cite{tracz2001fair}. Has change return, but not with the same taxability guarantees as Taler. Also has an implementation. \subsection{Compact E-Cash} -Reference: \cite{camenisch2005}. Allows to withdraw $2^\ell$ coins in $O(\ell)$. Either the whole +Reference: \cite{camenisch2005compact}. Allows to withdraw $2^\ell$ coins in $O(\ell)$. Either the whole $2^\ell$ coins must be spent at once, or all coins must be spent separately. @@ -271,12 +271,12 @@ are a side-effect of the crypto used. \subsection{Practical Divisible E-Cash with Arbitrary Wallet Size} -Reference: \cite{maertens2015} (unpublished). Parallel development to ``Divisible E-Cash Made Practical'', uses +Reference: \cite{maertens2015practical} (unpublished). Parallel development to ``Divisible E-Cash Made Practical'', uses accumulators and not the global structure (less trusted setup). Can withdraw arbitrary ``big'' amount. \subsection{Cut Down The Tree} -Reference: \cite{pointcheval2017}. Keeps some of the ideas of \cite{canard2015divisible} but removes the tree structure. +Reference: \cite{pointcheval2017cut}. Keeps some of the ideas of \cite{canard2015divisible} but removes the tree structure. Currently considered state of the art. \section{Things we don't care about} diff --git a/comparison/literature.bib b/comparison/literature.bib index 3ad7ba6..14c0144 100644 --- a/comparison/literature.bib +++ b/comparison/literature.bib @@ -1,16 +1,3 @@ -@INPROCEEDINGS{camenisch2007endorsed, - author={J. Camenisch and A. Lysyanskaya and M. Meyerovich}, - booktitle={2007 IEEE Symposium on Security and Privacy (SP '07)}, - title={Endorsed E-Cash}, - year={2007}, - pages={101-115}, - keywords={electronic money;protocols;e-cash;electronic cash scheme;fair exchange protocol;lightweight endorsement;onion routing;Authentication;Cryptographic protocols;Cryptography;Digital signatures;Explosions;Information security;Merchandise;Privacy;Routing}, - doi={10.1109/SP.2007.15}, - ISSN={1081-6011}, - month={May}, -} - - @Inbook{chaum1983blind, @@ -50,8 +37,21 @@ } +@INPROCEEDINGS{camenisch2007endorsed, + author={J. Camenisch and A. Lysyanskaya and M. Meyerovich}, + booktitle={2007 IEEE Symposium on Security and Privacy (SP '07)}, + title={Endorsed E-Cash}, + year={2007}, + pages={101-115}, + keywords={electronic money;protocols;e-cash;electronic cash scheme;fair exchange protocol;lightweight endorsement;onion routing;Authentication;Cryptographic protocols;Cryptography;Digital signatures;Explosions;Information security;Merchandise;Privacy;Routing}, + doi={10.1109/SP.2007.15}, + ISSN={1081-6011}, + month={May}, +} + + -@Inbook{pointcheval2017, +@Inbook{pointcheval2017cut, author="Pointcheval, David and Sanders, Olivier and Traor{\'e}, Jacques", @@ -90,7 +90,7 @@ -@Inbook{camenisch2005, +@Inbook{camenisch2005compact, author="Camenisch, Jan and Hohenberger, Susan and Lysyanskaya, Anna", @@ -108,7 +108,7 @@ } -@misc{maertens2015, +@misc{maertens2015practical, author = {Patrick Märtens}, title = {Practical Compact E-Cash with Arbitrary Wallet Size}, howpublished = {Cryptology ePrint Archive, Report 2015/086}, @@ -166,7 +166,7 @@ url="https://doi.org/10.1007/3-540-44750-4_35" -@inproceedings{tracz2001, +@inproceedings{tracz2001fair, author = {Tracz, Robert and Wrona, Konrad}, title = {Fair Electronic Cash Withdrawal and Change Return for Wireless Networks}, booktitle = {Proceedings of the 1st International Workshop on Mobile Commerce}, 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} diff --git a/ideas.txt b/ideas.txt new file mode 100644 index 0000000..80dca65 --- /dev/null +++ b/ideas.txt @@ -0,0 +1,2 @@ +- do some kind of simulation of spending (without any crypto) and see the cost (and maybe anonymity set?) +- assuming that all the problems with divisible e-cash are repaired, can we integrate refresh into it and have a better Taler? |