1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
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}
|
