digital receipts and cash

Digital cash protocols are starting to look like they could become very
popular and useful.

But under current proposals, there's one thing you don't get when you
spend digital cash: a digital receipt.

(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?

ObCypherpunks relevance: digital receipts seem (IMHO) important to the
emergence of fair and robust reputation markets.  Discuss.

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?

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>