Re: Detecting double-spending (long)

[nobody@alumni.cco.caltech.edu]

For those of you who slogged through my description last week of Chaum's
"simple" digital cash which detects double-spending, I've realized on
further thought that a simplification is possible.  Writing that long
essay improved my own understanding of his system.

Recall that the double-spending cash is the product, for i from 0 to
k/2, of f(xi,yi)^(1/3), mod the bank's public modulus.  f() is a one-way
function, one which can't be inverted.  xi and yi were a little complicated,
and here is where my simplification comes in.

Let xi be g(ai), where ai is a random number and g is a one-way function.
Let yi be g(ai xor <info>), where <info> is Alice's identifying information,
her account number.  Normally the ai "blinds" that since it is random
and it is xor'd onto it.  But if ever both ai and ai xor <info> are known,
<info> is revealed and Alice's goose is cooked.

Everything else works as Chaum suggested; I have just eliminated his ci
and di random numbers.  In his proposal, g took two arguments, and ci and
di were appended for the xi and yi cases.  But I'm convinced now that
these are unnecessary for our purposes.

The purpose for ci and di are to provide "unconditional" anonymity to
Alice if she doesn't cheat.  Look what happens with my simpler system.
She tells Bob ai and yi for certain i's.  Now, g is a one-way function,
but suppose Bob had a big enough computer to try all possible arguments
to g.  Sooner or later he'd find a value Z for which g(Z) was yi.  So
then he could figure that Z equals ai xor <info>, and he knows ai, so
he could find <info>.  This means that in my simplified system Alice
is depending on Bob (and everyone else) being unable to crack g() in
order to stay anonymous.

Chaum's system is better.  By having a g with two arguments he creates
a huge number of solutions to g(Z1,Z2) = yi.  There is no way for Bob to
tell which one is right, so even with infinite computing resources he
can't crack Alice's anonymity.

My thought is, unconditional anonymity is really no better than
computational anonymity in the real world.  Eric Hughes often says
"all cryptograpy is economics".  In practice, beyond a certain point,
anonymity would not be broken by a direct computational attack, but rather
by other means - bribery, theft, etc.  In the real world there is no such
thing as "unconditional" anonymity.  In practice, computational anonymity
is enough.

So my feeling is that for implementation purposes the ci and di in Chaum's
system can be removed, simplifying the protocols somewhat, at the cost
of reducing Alice's anonymity from unconditional to computational.

Hal Finney
hfinney@shell.portal.com