summaryrefslogtreecommitdiff
path: root/comparison/comparison.tex
blob: df6c4b5b3a5b7fbe33de5c1f5e84705775bcad4e (plain)
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
\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{adjustbox}
\usepackage{array}

\newcolumntype{R}[2]{%
    >{\adjustbox{angle=#1,lap=\width-(#2)}\bgroup}%
    l%
    <{\egroup}%
}
\newcommand*\rot{\multicolumn{1}{R{45}{1em}}}% no optional argument here, please!

\newcolumntype{H}{>{\setbox0=\hbox\bgroup}c<{\egroup}@{}}


\title{E-Cash Comparison}
\date{\today}

\begin{document}

\maketitle

\newcommand\Y{\ding{51}} % {\checkmark}
\newcommand\N{\ding{55}}

\begin{tabular}{r|cccccHHcccccc}
&
\rot{Year} &
\rot{Implementation} &
%
\rot{Instant enforcement} &
\rot{Robust anonymity} &
\rot{Key expiration} &
%
&% \rot{Traceability} &
&% \rot{Transferability} &
\rot{Taxability} &
%
% \rot{Withdrawal cost} & \rot{Deposit cost} &
\rot{Trustless anonymity} &
\rot{Realistic exchange storage} &
\rot{Cryptographic batching} &
%
\rot{Change/Divisibility} &
\rot{Receipts \& Refunds}
\\ \hline
Digicash \cite{chaum1983,schoenmakers1997security}
& 1983 & P
&  \Y & \Y & \Y
&  \N &  S & \N
% &  $\log n$ & $\log n$ 
&  \Y & \Y & \N 
&  \N & \N
\\
Offline Chaum \cite{chaum1990}
& 1990 & ?
&  \N & \N & %?
&  \N &  S & \N
% &  $\log n$ & $\log n$ 
&  \Y & \Y & \N
&  \N & \N
\\
Tracz \cite{tracz2001} % HINDE
& 2001 & E
&  \Y & \Y & %?
&  \N  &  S & \N
% &  $\log n$ & $\log n$ 
&  \Y & \Y & \N 
&  ON & \N
\\
Compact \cite{camenisch2005}
& 2005 & \N
&  \N & \N & %?
&  \N &  S & \N
% &  $\log n$ & $\log n$ 
&  \Y & \N & W % We're guessing trustless anonymity because not trusted setup
& OFF & \N
% \\
% Martens \cite{maertens2015}
% & 2015 & \N
% &  \N & \N & %?
% &  \N &  S & \N
% % &  $\log n$ & $\log n$ 
% &  \Y & \N & W % We're guessing trustless anonymity because not trusted setup
% & OFF & \N
\\
Divisible \cite{pointcheval2017}
& 2017 & \N
&  \N & \N & %?
&  \N &  S & \N
% &  $\log n$ & $\log n$ 
&  \N & \N & WD
& OFF & \N
\\
Taler
& 2017 & FS
&  \Y & \Y & \Y
&  \N &  S & \Y
% &  $\log n$ & $\log n$ 
&  \Y & \Y & \N 
&  ON & \Y
% \\
% Compact Taler & \N
% &  \Y & \Y & \Y
% &  \N &  S & \Y
% % &  $\log n$ & $\log n$ 
% &  \Y & \Y & W
% &  ON & \Y
% \\
% Divisible Taler & \N
% &  \Y & \Y & \Y
% &  \N &  S & \Y
% % &  $\log n$ & $\log n$ 
% &  \N & \Y & WD
% &  ON & \Y
\\ \hline
\end{tabular}

\section{Criteria}

\begin{itemize}
  \item \textbf{Implementation.}
    Is there an implementation?  Is it proprietary (P), experimental (E), or Free Software (FS).
  \item \textbf{Instant enforcement.}
    Is double spending detected immediately during spending?
    In the past, payment schemes needed to function even when neither
    party had connectivity, which complicates double spending detection.  
    To address this, anonymous payment schemes were designed to
    deanonymize the customer who double spent, but this approach makes
    anonymity extremely brittle and requires expensive debt collection
    operations.  Such schemes are only of academic interest today.
  \item \textbf{Robust anonymity.}
    Is anonymity preserved preserved in the presence of interrupted 
    operations or restoration from backups?
    % Required for good operational security.
    Inherently conflicts with offline double spending detection.
    % Exculpability under ...
  \item \textbf{Key expiration.}
    Can the exchange rotate key material without disrupting the operation
    of customers' wallets?  There are many schemes that do not address this
    directly and adding it may require larger changes to the protocol.
  \item \textbf{Taxability.}
    Is income transparent to the exchange?  Do transfers among 
    distrusting parties require that the exchange record the transaction?
    % TODO: Expand definition and cite the successor papers to Zerocash/BOLT
    % that handle regulation?
  \item \textbf{Trustless anonymity.}
    At present, divisible e-cash schemes entrust anonymity properties
    to a trusted setup phase.  Users cannot easily participate in this
    trusted setup, so they must entrust some party with their anonymity,
    and instantiating such schemes becomes difficult.
    By comparison, blind signatures normally provide information theoretic security.
  \item \textbf{Realistic exchange storage requirements.}
    Is it possible for the exchange to detect double spending
    without having to expand a divisible coin into parts of the smallest possible
    size and store one or more records for each part?
  \item \textbf{Cryptographic batching.}
    Does the scheme save bandwidth through batching?
    Compact e-cash schemes provide withdrawal operations that extract 
    many coins with one single withdrawal (W), reducing overall bandwidth
    for fixed denomination values, but not computation.  %% VERIFY
    Divisible e-cash schemes batch both withdrawal and deposit operations (WD),
    providing greater bandwidth reduction, and possibly computation
    reduction.  There is a trade off between these savings and the exchange's
    storage requirements, and the divisible schemes depend upon trusted setup
    for their anonymity properties. 
  \item \textbf{Change/Divisibility.}
    Can customers pay without possessing exact change?  If so, is it handled
    by giving change online (ON) or by divisible coins that support offline
    operation (OFF)?
  \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}.
    Also merchants can issue refunds for completed transactions.
    These operations must not introduce linkability or otherwise
    compromise the customer's anonymity.
\end{itemize}


These are discussion items that do not necessarily need to appear in the table.

\begin{itemize}
  \item \textbf{Traceability.}
    A threshold of authorities can deanonymize a customer. % if required (e.g. to catch a criminal).
    Also makes anonymity brittle.
    % TODO: Should this be Untraceability?
  \item \textbf{Transferability.}
    Ability to transfer a coin from one user to another.
    None/Sharing/Transfer.

  \item \textbf{Withdrawal cost.}
    Asymptotic time and storage costs for the wallet during and after withdrawal.
    Also frequently bandwidth costs for the withdrawal operation.  %TODO: Details?
    FIXME: Do we have a rigorous definition for this?  Literature
    only uses big-O for batched withdrawal/deposit.
  \item \textbf{Deposit costs.}
    Asymptotic time and storage costs for the exchange's double spending
    protections required during deposit.   
    Frequently ignored, especially in ``constant time'' schemes.
    FIXME: Do we have a rigorous definition for this?  Literature
    only uses big-O for batched withdrawal/deposit.
  \item \textbf{Robustness under network failures.} 
    Protocol aborts, including network failures, cannot compromise any party's
    financial security or the customer's anonymity.

  \item \textbf{Security proofs}. % {Cryptographic assumptions.}
    Do some security proofs require the random oracle model (ROM)?
    At present, any schemes with security proofs in the standard model
    do still require strong assumptions for pairing-based cryptography
    (I/II/III).  % so give the pairing type required.
% Notes: Taler uses ROM for the mint's security in the proof of security
% for FDH against one-more forgery attacks, but this could be removed by
% adapting it to some standard model blind signature scheme.  We expect
% Taler also uses ROM for the user's anonymity in the proof of security
% around the FD-PRF in the refresh protocol.
  \item \textbf{Software.} 
    Can the scheme be implemented purely in software?
    Some schemes require hardware security modules, including
    ``Untraceable Off-line Cash in Wallet with Observers''.  % replace with \cite{}
\end{itemize}


\section{Misc.}
\textbf{Blind signatures under aborts.}  The idea here is that the customer could abort before the exchange
credits the account/reserve.  Before aborting, the customer obtains some intermediate values from the exchange, which they
could re-combine into a valid signature when repeating this many times.  This is especially relevent since there's a proof
that in the Standard Model, blind signature schemes need to have $>3$ moves.


\section{Literature Survey}
\subsection{Chaum Blind Signatures}
Reference: \cite{chaum1983}.  Only defines blind signatures and their application to ``untraceable`` payments.

\subsection{Chaum with Offline Spending}
Reference: \cite{chaum1990}.  Introduces offline double spending detection.

\subsection{HINDE}
Reference:  Unpublished, there used to be some references on a mailing list, but they seem to be gone.

\subsection{Brands}
Reference: \cite{brands1993efficient}.  Variations of e-cash based on the representation problem.
In these schemes, divisibility leads to linkability.

\subsection{Okamoto's Divisible E-Cash}
Reference: \cite{okamoto1995efficient}.  Efficient construction for divisible E-Cash, but multiple independent
transactions with the same coin are linkable.

\subsection{DigiCash's ecash}
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.

\subsection{Compact E-Cash}
Reference: \cite{camenisch2005}.  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.


\subsection{Divisible E-Cash Made Practical}
Reference: \cite{canard2015divisible}.  Introduces a different coin structure
where there is one global tree and all coins are put on that skeleton.
Requires trusted setup that endangers anonymity.

\subsection{Scalable Divisible E-Cash}
Reference: \cite{canard2015scalable}.  Improves the spending protocol of ``Divisible E-Cash Made Practical'', so that the
bank only has to store serial numbers of coins that are actually spent and not ``fake'' serial numbers that
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
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.
Currently considered state of the art.

\section{Things we don't care about}

Offline spending:  Introduces brittleness (when backing up), since users might accidentally double spend.
Enforcement is hard to guarantee.  Some schemes even disclose all transaction of a user on double spending.

Transferability:  Means that coins can be exchanged safely without being recorded in the exchange,
goes against income transparency.

``Fairness'': Means that a threshold of authorities can de-anonymize a user.  Too much potential for abuse.




\bibliography{literature}
\bibliographystyle{alpha}

\end{document}