Re: Chaumian ecash without RSA
At 08:10 AM 3/31/96 -0800, David Wagner wrote:
The bank picks a secret value k, and publishes g^k.
To withdraw a coin, Alice picks an x, sets y = x | hash(x), [ | is concatenation ] chosen so that y is in G. Alice chooses a random secret blinding factor b, sends to the bank A->B: y g^b, and the bank returns B->A: (y g^b)^k, debiting Alice's account.
Note that this is a (blinded) Diffie-Hellman key exchange with public exponentials g^k and y g^b; the bank returns the exchanged "secret".
Alice unblinds this value, computing z = (y g^b)^k (g^k)^{-b} and now c = (x,z) is a coin in the digital cash system. Note z = y^k.
We use the traditional online clearing protocol; to deposit the coin, a shop S sends S->B: x, z. The bank checks to make sure the coin hasn't already been spent, and then computes y = x | MD5(x), checking whether y^k = z.
Two irritations with this protocol: 1: A coin is almost twice the size of a coin in the RSA protocol 2: Nobody except the bank can verify that a coin has face validity. The second point is more serious than you might think, as most of us want to see a world where everyone is his own bank and his own credit rating agency, as well as his own publisher. It will obstruct contracts of the form "Anne promises to provide numbers with certain cryptographic properties, provided Bob provides numbers with certain cryptographic properties." With RSA crypto cash, Anne can construct a blinded unsigned coin, and ask Bob to have it signed. For this to be reasonably convenient and practical, we need to have locally verifiable signatures. For computer mediated management of contracts, transactions, and credit ratings, we need contracts such that all intermediate transactions can be reduced to locally verifiable cryptographic protocols. --------------------------------------------------------------------- | We have the right to defend ourselves | http://www.jim.com/jamesd/ and our property, because of the kind | of animals that we are. True law | James A. Donald derives from this right, not from the | arbitrary power of the state. | jamesd@echeque.com
1: A coin is almost twice the size of a coin in the RSA protocol
Nah, it can be the same size as in the RSA-based Digicash protocol. (Pick x to be 128 bits, and repeatedly iterate SHA to get a 1024 bit y value, like Digicash does in their RSA-based Chaumian protocol.)
2: Nobody except the bank can verify that a coin has face validity.
So your comment makes me glad I posted the scheme (even if it turns out to be only of academic interest :-). I claim that statement 2 is also true of Digicash's protocol as well. Recall that Digicash is using an *online clearing* protocol-- so you can't tell whether a coin is valid without consulting the bank. Consulting the bank is absolutely necessary to prevent double spending. So if you ever wrote an application which made a security-critical decision based on whether the RSA signature verified correctly in the Digicash protocol, and you didn't consult the bank re: double spending, you'd be 100% vulnerable to a simple double spending attack. In particular, I claim that the only reason the bank needs to publish its RSA public exponent e is to allow you to blind the RSA signature: it's specifically *not* intended for you to verify coin validity. Everyone, feel free to jump in correct me if you disagree.
For computer mediated management of contracts, transactions, and credit ratings, we need contracts such that all intermediate transactions can be reduced to locally verifiable cryptographic protocols.
Well, if that's what you want, no currently shipping protocol gives you that. The current Digicash protocol does *not* let you do offline clearing. I don't claim to be able to solve the offline clearing problem; I just hoped to point out that there is/(seems to be) nothing special about RSA. (Indeed, one researcher has kindly emailed me to point out that several well-known digital cash schemes use a El Gamal-based protocol.)
participants (2)
-
D.A. Wagner -
jamesd＠echeque.com