On Sun, 1 Jul 2007, Daniel C. wrote:
I just finished reading Cryptonomicon for the third or fourth time,
and it's got me wondering (again) about how digital currency would be
possible. He talks a lot about how "strong crypto" can enable you to
have digital currency that is unforgeable, but I've thought and
thought about it and I just don't see how it's possible to issue a
digital, transferable document that you couldn't just make a copy of,
thereby doubling the amount of this currency that you own. Is digital
currency really possible, or is it purely a product of Neal
Stephenson's imagination?
Secure, anonymous digital cash is indeed real, and in fact it's one of the
things that got me into cryptography years ago. It's mathe-magical!
As others have pointed out, online, trusted third party (TTP) systems are an
easy way to solve lots of security problems. Tamper-resistant devices are
another "easy out". But in this case, there's a purely mathematical solution.
We have two goals: anonymous cash, and cash that prevents double-spending
without an on-line authority.
Anonymity: an anonymous coin is one which you can withdraw from the bank, but
which the bank can't link to you when you spend it. Sounds impossible,
doesn't it? Blind signatures to the rescue. They allow the bank to sign the
banknote using its private key without seeing the contents of what it's
signing. Here's how blind signatures work in RSA:
In ordinary RSA, e is the public exponent, d is the private exponent, and
m^(ed) = m (modulo n, the signer's modulus) for all suitable messages m.
A signature on m can be computed as m^d (mod n).
If I want you to sign m without knowing what it is, I pick a random r and
compute r^e. I send you m*r^e and you sign it, returning (m*r^e)^d =
m^d*r^(ed) = m^d*r. I divide out r and am left with m^d, the signature for m.
You don't know r, so you have no idea what m is.
Now, if the bank only uses d to sign, say, $1 coins, then it doesn't care what
I chose for m, so it doesn't mind signing it blindly. m just becomes the
serial number for the bill, and I pick it randomly each time. Now, I'm
perfectly free to repeate a value of m, but the only person that hurts is me,
since I'm just left with two copies of the signed bill.
When I want to spend the bill, I present m and m^d to the merchant, who
verifies that it was indeed signed by the bank. He sends it to the bank while
Alice waits, and they record the serial number to prevent double spending, but
they have no way to link m with the value m*r^e they signed earlier.
So there's anonymity. Now, to show off, we'll remove the need for the online
double-spending check.
m now gets fancier. It becomes a structured bit string having an encrypted
message saying "Alice, account number: #123456789" and some other special
fields. The 256-bit key k for encrypting the message is split into 2 128-bit
keys k1 and k2. The special fields are sha1(k1) and sha1(k2). That is, they
don't reveal what k1 and k2 are (because you can't reverse sha1), but they let
you know when you've seen k1 or k2, since you can compute sha1(k1) and
compare.
Alice creates, say, 1024 different versions of m that we'll call m0..m1023.
Each has a unique k. She blinds each m with its own blinding factor b and
sends them all to the bank. Each is called a "share".
Now we do what's called "cut and choose". The bank picks half of the shares
at random and tells Alice to provide the blinding factors and keys for each
share. She does, and the bank verifies that each one decrypts properly,
revealing Alice's name and account number.
Satisfied that she's not cheating (by putting a bogus name/account), the bank
multiplies the unrevealed shares together and signs them (assuming the bank
didn't ask to see m0, m3, m4, ...):
((m0*b0^e)*(m3*b1^e)*(m4*b2^e)...)^d (mod n)
= m0^d * b0^ed * m3^d * b3^ed ...
As before, each b^ed = b, and she divides out the b values, leaving:
(m0*m3*m4...)^d
That is, the signature on the product of all the m values.
Still with me? Alice now has a signature on a bunch of glommed-together
shares, and the decryption keys for each share. The bank's signature is
valid, but the bank has never seen the unblinded value and thus won't
recognize it as coming from Alice when it sees it later.
Alice goes to spend her $1 coin. She gives the signature to Bob the merchant,
along with the shares m0,m3,m4... that make up the signed coin. Bob
multiplies them together and checks the signature on their product. So far so
good. Now, for each m, Bob picks at random and demands to see either k1 or k2
-- that is, half the key decrypting the message which would identify her.
She complies, knowing that he has only half the key for any given message, so
her identity is still safe. He checks that sha1(k1) or sha1(k2) matches
what's in each m to make sure she isn't making up k values. Satisfied, he
accepts the coin, and later, at his leisure, sends the day's spent coins to
the bank. Alice securely deletes all the k values and goes on her way.
Now, what happens if she tries to double-spend? She gives the same signature
and m values to the other merchant, and he now demands to see one half-key or
the other for each of the m values. With overwhelming probability, he asks to
see the *other* half key for one of the m values the first merchant requested.
Call that share m'. Later, when he sends the spent coin to the bank, the bank
will see that it's identical to the earlier coin, and use the two key halves
of m' to decrypt the message incriminating Alice.
Neat, huh? I simplified a lot, so if you want to get all the details, look up
"Untraceable Electronic Cash" by Chaum, Fiat and Naor. Chaum actually put a
fancier version of his system into practice, and I remember around 1995
downloading a Digicash "wallet" and $100 in play money to spend online in a
trial run. He also had real vending machines and bus passes (iirc) in the
Netherlands, but ultimately Digicash went broke for the same reason I moved
away from security: very few people actually care enough about security and
privacy to pay even a little for it (and big companies like Visa have
everything to lose if we have to shift to new ways of doing things).
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
