Re: digital receipts and cash

[futplex@pseudonym.com (Futplex)]

David Wagner writes:
> (Later, if the vendor reneges on the transaction, you'd have the digital
> receipt to prove that you paid & the vendor is cheating you.)
> 
> This seems like it would be a really useful feature.  Does anyone know
> if there are any *practical* protocols to do this?
[...]
> ObCrypto relevance: I've looked through _Applied Cryptography_, but the
> protocols listed there aren't practical -- they require something like
> 100 rounds of interaction!  Can this be improved?

The Even/Goldreich/Lempel protocol (ACv1, pp.101-103) requires O(k) fairly
expensive operations (i.e. key generations, encryptions, network 
transmissions) to guarantee honesty with probability p = 2^k. k = 100 is
suggested. Perhaps this protocol would be useful in many applications with
k << 100. It might be argued that k need only be about 
O(lg(value(transaction))). I think k = 10 or 20 would be suitable for many
relatively low-value digital cash transactions. Waiting a bit longer to
arrange the purchase of a car over the net sounds tolerable to me.

I suppose you could precompute heaps of keys for use in unspecified future
transactions, which helps a bit.

It's hard to imagine circumventing the basic need for incremental increases
in trust, with a nontrivial cryptographic operation at each end in each
round. But hey, I certainly don't expect to prove that anytime soon.... :) 

-Futplex <futplex@pseudonym.com>