Log in

No account? Create an account

Previous Entry | Next Entry

Cryptographers are clever people

So, I've been reading about David Chaum's digital cash protocols, which allow two people to perform a bank transaction without the bank being able to connect the two participants—as if one of them had withdrawn cash and given it to the other to deposit, except there aren't even usable serial numbers for the bank to connect.

As you might expect, it's exceedingly clever.

First of all, you need to know one of the unusual properties of RSA: You can make a "blind signature". Essentially, you add a random value to the message you want signed, sign the combination, and then remove the random value from the signature. (Obviously, the random value has to be added in just the right way.) The result is a valid signature for the original message. The cool part is that a third party can do the signing step, in which case he has no idea what the real message said.

(Other applications of this include elections—you can blind an electronic ballot, bring it to a machine that will only sign it if you're on the roll of registered voters, then unblind the signature; when counting ballots, the signature verifies that the voter was registered, but can't be linked to a specific voter.)
RSA_encrypt(plaintext) = plaintexte (mod N)
RSA_decrypt(ciphertext) = ciphertextd (mod N)

# RSA has this lovely property:
RSA_verify(signature) = RSA_encrypt(signature)
RSA_sign(message) = RSA_decrypt(message)

RSA_blind(message, factor) = message * RSA_encrypt(factor) (mod N)
RSA_unblind(signature, factor) = signature / factor (mod N)

m contains the message to be signed. N, e, and d are as in standard RSA; that is, N is the modulus, e is the public (encrypt/verify) exponent, and d is the private (decrypt/sign) exponent.
  1. Generate a random number factor which has a particular relationship to N. (Specifically, factor and N can't have any common divisors except 1.)
  2. m' ← RSA_blind(m, factor)
  3. s' ← RSA_sign(m')
  4. s ← RSA_unblind(s', factor)
  5. RSA_verify(public key, s) == m.
(I've omitted padding, which I believe you would use in a real system, although not to the encrypt-blinding-factor part.)

The magic here is that step 3, the only part that requires the signer's private key, uses only m', not m or factor. Thus, m' can be sent to a remote computer, which can perform the RSA_sign and return s', which the local machine can turn into s. Essentially, the remote computer can sign m without having any idea of its contents (or even a hash of its contents). Without knowing what the blinding factor is, it's impossible for the remote computer to determine the original contents.
This can be turned into an electronic cash system, i.e. one that allows anonymous transactions.
Alice wants to pay Bob $1 for a widget. Both of them have accounts established with Mickey, who runs a bank with a cryptographic mint.

Alice generates m, a randomly-chosen token number. (If that number is sufficiently large, like 256 bits, the chances of a collision are astronomical.) Alice then blinds that number, signs it with her private key, and sends it to Mickey.

Mickey must now perform several steps.
  1. He verifies Alice's signature.
  2. He notes the blinded number in a table of used numbers so it can't be redeemed in blinded form.
  3. He debits $1 from Alice's account.
  4. He removes Alice's signature and affixes his own, which indicates that the (unblinded) number can be redeemed for $1.
  5. He sends the new signature, and a signed debit slip back to Alice.
Alice receives the signature and unblinds it, getting a signature for m. m and the unblinded signature form a token worth $1.

All of these steps can be performed ahead of time and even in bulk; the tokens can then be, say, put on a smart card (or even a USB key, really) for offline use. If Alice's smart card is stolen but she has backup copies of the tokens, she can pay herself with the copies before the thief can (and she can report them stolen so that when the thief tries to redeem them, he can be arrested).

To pay Bob, Alice gives the token to Bob. Bob signs it with his private key, then sends it to Mickey.

Again, Mickey must perform several steps:
  1. He verifies and removes Bob's signature.
  2. He unpacks the token into the number and signature, then verifies his own signature.
  3. He checks if the number is in the table of used numbers. If it appears in the table, then either Bob is trying to redeem the same number twice, or Alice has given the same number to two merchants; either way, the transaction should be rejected. (Note that the blinded version of the number was inserted when Alice asked him to mint it, not the unblinded version.) If it doesn't appear in the table, insert it.
  4. He credits $1 to Bob's account.
  5. He sends a signed receipt and a signed credit slip back to Bob.
Finally, Bob gives Alice her widget and (a copy of) the receipt.

Although Mickey knows the number and signature he got from Bob are valid, he can't connect them to Alice, because Alice only gave him a blinded version of the number.

These folks are fucking geniuses. It's too bad no bank wants to do this—they prefer to be able to see who the money is coming from. (And the government prefers them to see it, too, so it can be subpoenated.)