Digital Currency

Jason Holt jason at lunkwill.org
Mon Jul 2 14:25:51 MDT 2007


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



More information about the PLUG mailing list