Detecting double-spending (long)

[Marc Horowitz]

Great description!  One question, which struck me when I heard Chaum
present this material at IETF Amsterdam:

>> Now, suppose Alice cheats.  She spends the money again somewhere else, 
>> at Charlie's.  Charlie goes through the same procedure as Bob, choosing 
>> 0 or 1 at random for each value of i.  Here is the catch.  Since he is 
>> choosing at random, it would be very unlikely that he will choose 
>> exactly the same 0's and 1's that Bob chose.  (Here is where the size of 
>> k matters - making it bigger makes it less likely that Charlie and Bob 
>> will choose the same pattern of 0's and 1's.  But it makes the 
>> calculations take longer.)  That means for one or more values of i, 
>> Charlie will probably choose a 0 where Bob chose a 1, or vice versa.

What if Alice, Bob, and Charlie are all colluding, and Bob and Charlie
present the same 1's and 0's to Alice?  The bank would know the same
bill was spent twice once it got it, but wouldn't be able to determine
that Alice was the spender.  Bob and Charlie could both claim "What a
cooincidence!"  and say they wanted their money.

I suppose the bank could just write the scenario down, and hand the
money to Bob and Charlie (who give their cut to Alice, in anonymous
digicash, of course).  If it happens again, the bank says "yeah,
right" and invokes the clause in their contract which allows the bank
to terminate its relationship with Bob and Charlie.  Assuming the
digicash economy is strong enough that people won't cut off the
relationship with the bank so easily, most people won't try this.  But
it will cause the bank to want to put an upper limit on transaction
size.

		Marc