\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|ccccccccccc}
&
\rot{Year} &
\rot{Implementation} &
%
\rot{Instant enforcement} &
\rot{Robust anonymity} &
\rot{Key expiration} &
%
\rot{Taxability} &
%
% \rot{Withdrawal cost} & \rot{Deposit cost} &
\rot{Trustless anonymity} &
\rot{Storage for wallet} &
\rot{Storage for exchange} &
%
\rot{Change/Divisibility} &
\rot{Receipts \& Refunds}
\\ \hline
Chaum \cite{chaum1983}
& 1983 & P
&  \Y & \Y & \Y
& \Y
% &  $\log n$ & $\log n$ 
&  \Y & $\log n$ & $\log n$
&  \N & \N
\\
DigiCash \cite{schoenmakers1997security}
& 1990 & P
&  \Y & \Y & \Y
& \N
&  \Y & $\log n$ & $\log n$
&  \N & \N
\\
Offline Chaum \cite{chaum1990}
& 1990 & ?
&  \N & \N & ?
& \N
% &  $\log n$ & $\log n$ 
&  \Y & $\log n$ & $\log n$
&  \N & \N
\\
Tracz \cite{tracz2001} % HINDE
& 2001 & E
&  \Y & \Y & ?
& \N
% &  $\log n$ & $\log n$ 
&  \Y & $\log n$ & $\log n$
&  Onl. & \N
\\
Compact \cite{camenisch2005}
& 2005 & \N
&  \N & \N & ?
&  \N
&  \Y & $\log n$ & $n$ % 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
&  \N & $1$ & $n$
& Off. & \N
\\
Taler
& 2017 & FS
&  \Y & \Y & \Y
&  \Y
% &  $\log n$ & $\log n$ 
&  \Y & $\log n$ & $\log n$
&  Onl. & \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.  
    Divisible e-cash schemes batch both withdrawal and deposit operations (WD),
    providing greater bandwidth 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 (Onl.) 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}
