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.)