Detecting double-spending

[nobody@alumni.cco.caltech.edu]

Wonderer asks about Alice guessing the bank's random choices of the
blinded f()'s that she creates.  Certainly this would let her cheat.
The bank would probably use a quantum-based hardware random number
generator (as a seed, at least) to make this impossible.

To take cube roots, the bank must find a d such that d*3 = 1 mod
(p-1)(q-1), where p and q are the secret primes in its RSA system.
Finding such a d is a simple application of Euclid's algorithm.  It
has the property that (m^d)^3 = (m^3)^d = m.  In other words, taking
a number to the power of d produces its cube root.  This is the basic
mathematics behind the RSA public-key cryptosystem.

Marc Horowitz asks about collusion between Bob and Charlier to pick the
same 1's and 0's.  It is true that this would defeat the scheme.  However,
the chances of this happening randomly are so low that the bank would
know that at least one of them was cheating, although it would not know
which.

Chaum discusses this threat in his paper.  He suggests that each merchant
in the system would have a unique ID number.  The 1's and 0's that the
merchant uses in the payment protocol would be partially random choices
as I described and partially based on the unique ID.  Since all ID's are
different this would guarantee that any two merchants would use different
patterns of 1's and 0's even if they were cheating.

Hal Finney
hfinney@shell.portal.com