Anonymous e-cash

I once interviewed at a place called NTRU Cryptosystems. They have a very fast public key algorithm suitable for implementation in slow, memory-limited embedded systems. One of the interesting aspects of their algorithm is that creating public/private key pairs is a very quick operation. If you've used PGP or GPG, you've probably noticed that with traditional RSA, the key generation process is annoyingly slow. Recalling that cryptography's version of a person's identity is a private key, this made me think about what might be possible if key generation were a very inexpensive operation, and what you get is a kind of anonymity that could make electronic cash work really well. But you don't really need fast key generation. You can set up your home computer to generate many key pairs overnight, and save them all on a USB flash drive for use the following day.

How do you get from plentiful key pairs to anonymity? You start a bank that accepts public keys as proofs of identity, and therefore associates accounts with public keys. The bank does not ask a client for any identification other than a public key. The bank allows the money to be withdrawn by any party who can prove ownership of the public key by using the corresponding private key to sign documents, which signatures the bank can verify using the public key. The bank will transfer the money to the ownership of a different public key, given a digitally signed transfer request from the original holder. The transfer document could be presented in email, which could be routed through any number of anonymous remailers.

If I wish to transfer anonymously, I can send the bank a series of emails transferring the money from one identity to another, each identity represented by one of the key pairs I generated last night. Going through several anonymous identities provides plausible deniability that I still have the money.

All it takes to create such a bank is to set up a database that associates public keys with cash balances, and a website that performs redemptions and transfers as discussed above. One would want to locate the bank in a country or region with a favorable tax and regulatory climate.