From: "Joseph M. Reagle Jr." <reagle@rpcp.mit.edu>
Date: Sat, 10 Aug 1996 08:45:27 +0800
To: cypherpunks@toad.com
Subject: Electronic Cash System Based On The Representation
Message-ID: <199608092225.SAA26589@mccannerick-bh.mccann.com>
MIME-Version: 1.0
Content-Type: text/plain


Interesting paper I had not heard of, but was recently referred to...

http://www.cwi.nl/~brands/cash.html

Electronic Cash System Based On The Representation 
Problem Stefan Brands CWI 
P.O. Box 4079, 1009 AB Amsterdam 
The Netherlands e-mail: brands@cwi.nl 

Abstract: We present a new on-line electronic cash system based on a
problem, called the representation problem, of which little use has been
made in literature thus far. Our system is the first to be based entirely on
discrete logarithms. Using the representation problem as a basic concept,
some techniques are introduced that enable us to construct protocols for
withdrawal and payment that do not use the cut and choose methodology of
earlier systems. As a consequence, our cash system is much more efficient in
both computation and communication complexity than previously proposed
systems. Another important aspect of our system concerns its provability .
Contrary to previously proposed systems, its correctness can be
mathematically proven to a very great extent. Specifically , if we make one
plausible assumption concerning a single hash-function, the ability to break
the system seems to imply that one can break the Diffie-Hellman problem. Our
system offers a number of extensions that are hard to achieve in previously
known systems. In our opinion the most interesting of these is that the
entire cash system (including all the extensions) can be incorporated
straight forwardly in a setting based on wallets with observers, which has
the important advantage that double- spending can be prevented in the
\014rst place, rather than detecting the identity of a double-spender after
the fact. In particular, it can be incorporated even under the most
stringent requirements conceivable about the privacy of the user, which
seems to b e impossible to do with previously proposed systems. Another
benefit of our system is that framing attempts by a bank have negligible
probability of success (independent of computing power) by a simple
mechanism from within the system, which is something that p previous
solutions lack entirely . Furthermore, the basic cash system can be extended
to checks, multi-show cash and divisibility , while retaining its
computational efficiency. Although in this paper we only make use of the
representation problem in groups of prime order, similar intractable
problems hold in RSA-groups (with computational equivalence to facto ring
and computing RSA- roots). We discuss how one can use these problems to
construct an efficient cash system with security related to factoring or
computation of RSA-roots, in an analogous way to the discrete log based
system. Finally , we discuss a decision problem (the decision variant of the
Diffie-Hellman problem) that is strongly related to undeniable signatures,
which to our knowledge has never been stated in literature and of which we
do not know whether it is in BPP. A p roof of its status would be of
interest to discrete log based cryptography in general. Using the
representation problem, we show in the appendix how to batch the
confirmation protocol of undeniable signatures such that polynomially many
undeniable signatures can be verified in four moves. 

AMS Subject Classification (1991) : 94A60 
CR Subject Classification (1991) : D.4.6 
Keywords and Phrases : Cryptography , 
Electronic Cash, Representation Problem 
_______________________
Regards,            It is not because things are difficult that we do not dare; 
                    it is because we do not dare that they are difficult.
-Seneca
Joseph  Reagle      http://rpcp.mit.edu/~reagle/home.html
reagle@mit.edu      E0 D5 B2 05 B6 12 DA 65  BE 4D E3 C1 6A 66 25 4E