Digital cash issuess...

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

>As a consequence, our
>cash system is much more efficient in both computation and
>communication complexity than previously proposed systems."

I take this with a grain of salt; see below.

>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, 

I am not surprised that they find this interesting; David Chaum has
patented all the observer protocols.

Having read these protocols in the original, I can say this is not
much of an advantage.  The observer protocols are tremendously
expensive computationally.  Anything you build on top of it won't be
any faster.

Eric

Eric Hughes says:
> >As a consequence, our
> >cash system is much more efficient in both computation and
> >communication complexity than previously proposed systems."
> 
> I take this with a grain of salt; see below.
> 
> >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, 
> 
> I am not surprised that they find this interesting; David Chaum has
> patented all the observer protocols.
> 
> Having read these protocols in the original, I can say this is not
> much of an advantage.  The observer protocols are tremendously
> expensive computationally.  Anything you build on top of it won't be
> any faster.

As I understand it, "observers" are built in to supposedly uncrackable
hardware built into a smart card -- and I'm not a big fan of the
notion that you can make hardware non-reverse engineerable...

Perry