path: root/comparison
diff options
authorFlorian Dold <>2017-08-21 00:08:49 +0200
committerFlorian Dold <>2017-08-21 00:08:49 +0200
commit7ff357a2bc763b83c43cadf557f66838241a7b0b (patch)
tree6061ea36318a19f3e8d950a4505601793dbf8f4e /comparison
parentd6926e46b6d5ff8d7b5e804984fed45a4b95073c (diff)
Diffstat (limited to 'comparison')
2 files changed, 165 insertions, 0 deletions
diff --git a/comparison/comparison.tex b/comparison/comparison.tex
index ab7f6d6..cbe3c7c 100644
--- a/comparison/comparison.tex
+++ b/comparison/comparison.tex
@@ -226,7 +226,48 @@ 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.
+Reference: Unpublished, there used to be some references on a mailing list, but they seem to be gone.
+\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}
+Reference: \cite{maertens2015} (unpublished). Parallel development to ``Divisible E-Cash Made Practical'', uses
+accumulators and not the global structure (less trusted setup).
+\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.
diff --git a/comparison/literature.bib b/comparison/literature.bib
index 06944aa..dd74588 100644
--- a/comparison/literature.bib
+++ b/comparison/literature.bib
@@ -13,3 +13,127 @@
+ author="Chaum, David",
+ editor="Chaum, David
+ and Rivest, Ronald L.
+ and Sherman, Alan T.",
+ title="Blind Signatures for Untraceable Payments",
+ bookTitle="Advances in Cryptology: Proceedings of Crypto 82",
+ year="1983",
+ publisher="Springer US",
+ address="Boston, MA",
+ pages="199--203",
+ abstract="Automation of the way we pay for goods and services is already underway, as can be seen by the variety and growth of electronic banking services available to consumers. The ultimate structure of the new electronic payments system may have a substantial impact on personal privacy as well as on the nature and extent of criminal use of payments. Ideally a new payments system should address both of these seemingly conflicting sets of concerns.",
+ isbn="978-1-4757-0602-4",
+ doi="10.1007/978-1-4757-0602-4_18",
+ url=""
+ author="Chaum, David
+ and Fiat, Amos
+ and Naor, Moni",
+ editor="Goldwasser, Shafi",
+ title="Untraceable Electronic Cash",
+ bookTitle="Advances in Cryptology --- CRYPTO' 88: Proceedings",
+ year="1990",
+ publisher="Springer New York",
+ address="New York, NY",
+ pages="319--327",
+ abstract="The use of credit cards today is an act of faith on the part of all concerned. Each party is vulnerable to fraud by the others, and the cardholder in particular has no protection against surveillance.",
+ isbn="978-0-387-34799-8",
+ doi="10.1007/0-387-34799-2_25",
+ url=""
+ author="Pointcheval, David
+ and Sanders, Olivier
+ and Traor{\'e}, Jacques",
+ editor="Fehr, Serge",
+ title="Cut Down the Tree to Achieve Constant Complexity in Divisible E-cash",
+ bookTitle="Public-Key Cryptography -- PKC 2017: 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28-31, 2017, Proceedings, Part I",
+ year="2017",
+ publisher="Springer Berlin Heidelberg",
+ address="Berlin, Heidelberg",
+ pages="61--90",
+ abstract="Divisible e-cash, proposed in 1991 by Okamoto and Ohta, addresses a practical concern of electronic money, the problem of paying the exact amount. Users of such systems can indeed withdraw coins of a large value N and then divide it into many pieces of any desired values {\$}{\$}V{\backslash}le N{\$}{\$} . Such a primitive therefore allows to avoid the use of several denominations or change issues. Since its introduction, many constructions have been proposed but all of them make use of the same framework: they associate each coin with a binary tree, which implies, at least, a logarithmic complexity for the spendings.",
+ isbn="978-3-662-54365-8",
+ doi="10.1007/978-3-662-54365-8_4",
+ url=""
+ author="Canard, S{\'e}bastien
+ and Pointcheval, David
+ and Sanders, Olivier
+ and Traor{\'e}, Jacques",
+ editor="Katz, Jonathan",
+ title="Divisible E-Cash Made Practical",
+ bookTitle="Public-Key Cryptography -- PKC 2015: 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 -- April 1, 2015, Proceedings",
+ year="2015",
+ publisher="Springer Berlin Heidelberg",
+ address="Berlin, Heidelberg",
+ pages="77--100",
+ abstract="Divisible E-cash systems allow users to withdraw a unique coin of value {\$}{\$}2^n{\$}{\$} from a bank, but then to spend it in several times to distinct merchants. In such a system, whereas users want anonymity of their transactions, the bank wants to prevent, or at least detect, double-spending, and trace the defrauders. While this primitive was introduced two decades ago, quite a few (really) anonymous constructions have been introduced. In addition, all but one were just proven secure in the random oracle model, but still with either weak security models or quite complex settings and thus costly constructions. The unique proposal, secure in the standard model, appeared recently and is unpractical. As evidence, the authors left the construction of an efficient scheme secure in this model as an open problem.",
+ isbn="978-3-662-46447-2",
+ doi="10.1007/978-3-662-46447-2_4",
+ url=""
+ author="Camenisch, Jan
+ and Hohenberger, Susan
+ and Lysyanskaya, Anna",
+ editor="Cramer, Ronald",
+ title="Compact E-Cash",
+ bookTitle="Advances in Cryptology -- EUROCRYPT 2005: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005. Proceedings",
+ year="2005",
+ publisher="Springer Berlin Heidelberg",
+ address="Berlin, Heidelberg",
+ pages="302--321",
+ abstract="This paper presents efficient off-line anonymous e-cash schemes where a user can withdraw a wallet containing 2ℓ coins each of which she can spend unlinkably. Our first result is a scheme, secure under the strong RSA and the y-DDHI assumptions, where the complexity of the withdrawal and spend operations is {\$}{\{}{\backslash}mathcal O{\}}({\backslash}ell + k){\$} and the user's wallet can be stored using {\$}{\{}{\backslash}mathcal O{\}}({\backslash}ell + k){\$} bits, where k is a security parameter. The best previously known schemes require at least one of these complexities to be {\$}{\{}{\backslash}mathcal O{\}}(2^{\{}{\backslash}rm {\backslash}ell{\}}{\backslash}cdot k){\$} . In fact, compared to previous e-cash schemes, our whole wallet of 2ℓ coins has about the same size as one coin in these schemes. Our scheme also offers exculpability of users, that is, the bank can prove to third parties that a user has double-spent. We then extend our scheme to our second result, the first e-cash scheme that provides traceable coins without a trusted third party. That is, once a user has double spent one of the 2ℓ coins in her wallet, all her spendings of these coins can be traced. However, the price for this is that the complexity of the spending and of the withdrawal protocols becomes {\$}{\{}{\backslash}mathcal O{\}}({\backslash}ell {\backslash}cdot k){\$} and {\$}{\{}{\backslash}mathcal O{\}}({\backslash}ell {\backslash}cdot k+k^{\{}2{\}}){\$} bits, respectively, and wallets take {\$}{\{}{\backslash}mathcal O{\}}({\backslash}ell {\backslash}cdot k){\$} bits of storage. All our schemes are secure in the random oracle model.",
+ isbn="978-3-540-32055-5",
+ doi="10.1007/11426639_18",
+ url=""
+ author = {Patrick Märtens},
+ title = {Practical Divisible E-Cash},
+ howpublished = {Cryptology ePrint Archive, Report 2015/318},
+ year = {2015},
+ note = {\url{}},
+author="Canard, S{\'e}bastien
+and Pointcheval, David
+and Sanders, Olivier
+and Traor{\'e}, Jacques",
+editor="Malkin, Tal
+and Kolesnikov, Vladimir
+and Lewko, Allison Bishop
+and Polychronakis, Michalis",
+title="Scalable Divisible E-cash",
+bookTitle="Applied Cryptography and Network Security: 13th International Conference, ACNS 2015, New York, NY, USA, June 2-5, 2015, Revised Selected Papers",
+publisher="Springer International Publishing",
+abstract="Divisible E-cash has been introduced twenty years ago but no construction is both fully secure in the standard model and efficiently scalable. In this paper, we fill this gap by providing an anonymous divisible E-cash construction with constant-time withdrawal and spending protocols. Moreover, the deposit protocol is constant-time for the merchant, whatever the spent value is. It just has to compute and store {\$}{\$}2^l{\$}{\$} serial numbers when a value {\$}{\$}2^l{\$}{\$} is deposited, compared to {\$}{\$}2^n{\$}{\$} serial numbers whatever the spent amount (where {\$}{\$}2^n{\$}{\$} is the global value of the coin) in the recent state-of-the-art paper. This makes a very huge difference when coins are spent in several times.",