From: sneal@muskwa.ucs.ualberta.ca (Sneal)
Date: Wed, 26 May 93 15:00:53 PDT
To: cypherpunks@toad.com
Subject: Digital cash issuess...
Message-ID: <9305262158.AA28845@muskwa.ucs.ualberta.ca>
MIME-Version: 1.0
Content-Type: text/plain


     There's an interesting paper on offline cash systems by Stefan
Brands, who I believe is/was a student of David Chaum.  The abstract
reads:
 
"We present a new off-line electronic cash system based on a problem,
called the representation problem, of which little use has been made
in the literature thus far.  Our system is the first to be entirely
based 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 import 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
systems 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 straightforwardly in a setting based on wallets
with observers, which has the important advantage that
double-spending can be prevented in the first place, rather than
detecting the identity of a double-spender after the fact.  In
particular, in can be incorporated even under the most stringent
requirements conceivable about the privacy of the user, which seems
to be 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 conputing power) by
a simple mechanism from within the system, which is something that
previous solutions lack entirely.  Furthermore, the basic cash system
can be extended to checks, multi-show cash and divisibility, while
retaining its computation efficiency."
 
[...some stuff elided...]
 
"...Using the representation problem, we show in the appendix how to
batch the confirmation protoocol of undeniable signatures such that
polynomially many undeniable signatures can be verified in four
moves."
 
The paper can be found at
 
 ftp.cwi.nl  /pub/CWIreports/AA/CS-R9323.ps.Z
 

   -- Steve