Crypto is fantastic for many things, but those who readthis blog know that I have a particular fascination for its privacy applications. Specifically, what interests me are the ways we can use cryptography to transact (securely) online, without revealing what we’re doing, or who we’re doing it with.

This is particularly relevant, since today we’re in the middle of an unprecedented social and technological experiment: moving our entire economy out of metal and paper and into the ‘net. I’ve already had to explain to my four-year old what newspapers are; I imagine he’ll have a similarly experience when his children ask why people once carried funny pieces of paper around in their wallet.

Between credit and debit cards, EFT, online banking and NFC, it seems like the days of cash are numbered. Unfortunately, all is not sunshine and roses. The combination of easy-to-search electronic records and big data seems like a death-knell for our individual privacy. Cryptography holds the promise to get some of that privacy back, if we want it.

In this post I’m going to take a very quick look at a few privacy-preserving ‘e-cash’ technologies that might help us do just that. (And yes, I’ll also talk about Bitcoin.)

Why don’t we have electronic cash today?

The simple answer is that we already have electronic money; we just don’t call it that. Right now in its mainstream incarnation, it takes the form of little plastic cards that we carry around in our wallets. If you live in a developed nation and aren’t too particular about tipping valets, you can pretty much survive without ever touching hard currency.

The problem is that credit and debit cards are not cash. They’re very good for money transfers, but they have two specific limitations: first, they require you to access an online payment network. This means that they lose their usefulness at exactly the moment when you need them most: typically, after a disaster has wiped out or severely limited your connectivity (e.g., most hurricanes in Florida, NYC the morning after 9/11, etc).

Secondly, funds transfer systems offer none of the privacy advantages of real cash. This is probably by (government) preference: untraceable cash lends itself to unsavory activities, stuff like drug dealing, arms purchases and tax evasion. Our modern banking system doesn’t necessarily stop these activities, but it’s a godsend for law enforcement: just about every transaction can be traced down to the $0.01. (And even if you aren’t a drug dealer, there are still plenty of folks who’ll pay good money for a copy of your spending history, just so they can sell you stuff.)

The genesis of private e-cash

David Chaum

Credit for the invention of true, privacy-preserving electronic cash generally goes to David Chaum. Chaum proposed his ideas in a series of papers throughout the 1980s, then made a fortune providing the world with untraceable electronic cash.

Well, actually, the statement above is not quite accurate. According to legend, Chaum turned down lucrative offers from major credit card companies in favor of starting his own e-cash venture. I don’t need to tell you how the story ends — you’ve probably already noticed that your wallet isn’t full of untraceable electronic dollars (and if it is: I’m sorry.)

There’s an important lesson here, which is that getting people to adopt electronic cash requires a lot more than just technology. Fortunately, the failure of e-cash has a silver lining, at least for the field of cryptography: Chaum went on to pioneer anonymous electronic voting and a whole mess of other useful stuff.

Like many e-cash systems since, Chaum’s earliest paper on the e-cash proposed to use digital ‘coins’, each of some fixed denomination (say, $1). A coin was simply a unique serial number, generated by the holder and digitally signed using a private key known only to the bank. When a user ‘spends’ a coin, the merchant can verify the signature and ‘deposit’ the coin with the bank — which will reject any coin that’s already been spent.

(Of course, this doesn’t prevent the merchant from re-spending your hard earned money. To deal with this, the user can replace that serial number with a freshly-generated public key for a signature scheme. The bank will sign the public key, then the user can provide the merchant with the public key — signed by the bank — and use the corresponding signing key to sign the merchant’s name and transaction info.)

However you do it, the system as described has a crucial missing element: it’s not private. The bank knows which serial numbers it signs for you, and also knows where they’re being spent. This provides a linkage between you and, say, that anarchist bookstore where you’re blowing your cash.

To address this, Chaum replaced the signing process with a novel blind signature protocol. Blind signature is exactly what it sounds like: a way for the bank to sign a message without actually seeing it. Using this technology, the user could make up a serial number and not tell the bank; the blind signature protocol would provide the necessary signature. Even if the bank was trying to track the coins, it wouldn’t be able to link them to the user.

Chaum even provided a nice real-world analogy for his idea: place a document inside of an element along with a sheet of carbon paper, then let the bank sign the outside of the envelope, conveying the signature through and onto the document. This doesn’t literally describe how blind signatures work, but the real cryptographic constructions aren’t that much worse: you can readily obtain blind versions of RSA, DSA and the Schnorr/Elgamal signatures without (mostly) breaking a sweat (see this footnote for details).

There have been quite a few developments over the past few years, but none are as dramatic as the original schemes. Still, they’re pretty cool.

One scheme that deserves a few words is the ‘Compact e-Cash‘ system of Camenisch, Hohenberger and Lysyanskaya. This system is nice because users can store millions of e-coins in a relatively small format, but also because it uses lots of neat crypto — including signatures with efficient protocols and zero-knowledge proofs.

At a very high level, when a user withdraws n coins from the bank in this system, the bank provides the user with a digital signature on the following values: the user’s public key, the number of coins n withdrawn, and a secret seed value seed that’s generated cooperatively by the bank and the user.

The bank learns the number of coins and user’s public key, but only the user learns seed. To spend the ith coin in the wallet, the user generates a ‘serial number’ SN = F(seed, i), where F is some pseudo-random function. The user also provides a non-interactive zero-knowledge proof that (a) 0 < i < n, (b) SN is correctly formed, and (c) she has a signature on seed from the bank (among other things). This zero-knowledge proof is a beautiful thing, because it does not leak any information beyond these statements, and can’t even be linked back to the user’s key in the event that she loses it. The online bank records each serial number it sees, ensuring that no coin will ever be spent twice.

This may seem pretty complicated, but the basic lesson is that we can do lots of neat things with these technologies. We can even build coins that can be spent k times for some arbitrary k, only revealing your identity if they’re used more times than that; this turns out to be useful anonymous login applications, where users want to access a resource a fixed number of times, but don’t want anyone counting their accesses.

Unfortunately, we haven’t managed to build any of this stuff and deploy it in a practical setting.

Bitcoin

Which brings us to the one widely-deployed, practical electronic cash system in the world today. What about Bitcoin?

I’m a big fan of Bitcoin (from a technical perspective), but it has a few limitations that make Bitcoins a little bit less private than real e-cash should be.

Despite the name, Bitcoin doesn’t really deal with ‘coins’: it’s actually a transaction network. Users generate blocks of a certain value then transfer quantities of currency using ECDSA public keys as identifiers. The core innovation in Bitcoin is a distributed public bulletin-board (the ‘block-chain’) that records every transaction in Bitcoin’s history. This history lets you check that any given chunk of currency has a valid pedigree.

While the Bitcoin block-chain is essential to security, it’s also Bitcoin’s privacy achilles heel. Since every transaction is public — and widely disseminated — there’s no hiding that it took place. To make up for this, Bitcoin offers pseudonymity: your public key isn’t tied to your identity in any way, and indeed, you can make as many of them as you want. You can even transfer your coins from one key to another.

Now, I’m not really complaining about this. But it should be noted that pseudonymity is to anonymity what sugar-free chocolates are to the real thing. While I don’t know of anyone who’s actively looking to de-anonymize Bitcoin transactions (scratch that, Zooko points out that some people are), there has been plenty of work on extracting (or ‘re-identifying’) pseudonymized data sets. If you don’t believe me, see this work by Narayanan and Shamtikov on de-anonymizing social network data, or this one that does the same thing for the Netflix prize dataset. And those are just two of many examples.

Many knowledgable Bitcoin users know this, and some have even developed Bitcoin ‘mixers’ that stir up large pools of Bitcoin from different users, in the hopes that this will obfuscate the transaction history. This sounds promising, but has a lot of problems — starting with the fact that none few seem to be actually online as I write this post.* Even if one was available, you’d basically be placing your privacy trust into the hands of one party who could totally screw you. (A large, distributed system like Tor could do the job, but none seems to be on the horizon). Finally, you’d need a lot of transaction volume to stay safe.

At the same time, it seems difficult to shoehorn the e-cash techniques from the previous sections into Bitcoin, because those systems rely on a centralized bank, and also assume that coins are used only once. Bitcoin has no center, and coins are used over and over again forever as they move from user to user. Any anonymous coin solution would have to break this linkage, which seems fundamentally at odds with the Bitcoin design. (Of course that doesn’t mean it isn’t possible! ;)**

In summary

This has hardly been an exhaustive summary of how e-cash works, but hopefully it gives you a flavor of the problem, along with a few pointers for further reading.

I should say that I don’t live the most interesting life, and about the only embarrassing thing you’ll see on my credit cards is the amount of money we waste on Diet Coke (which is totally sick). Still, this isn’t about me. As our society moves away from dirty, messy cash and into clean — and traceable — electronic transactions, I really do worry that we’re losing something important. Something fundamental.

This isn’t about avoiding marketers, or making it easier for people to have affairs. Privacy is something humans value instinctively even when we don’t have that much to hide. It’s the reason we have curtains on our windows. We may let go of our privacy today when we don’t realize what we’re losing, but at some point we will realize the costs of this convenience. The only question is when that will be, and what we’ll do about it when the day comes.

Notes:

* I was wrong about this: a commenter points out that Bitcoin Fog is up and running as a Tor hidden service. I’ve never tried this, so I don’t know how well it works. My conclusion still stands: mixing works well if you trust the BF operators and there’s enough transaction volume to truly mix your spending. We shouldn’t have to trust anyone.

** Some people have tried though: for example, OpenCoin tries to add Chaum-style cash to Bitcoin. Ditto Open Transactions. From what I can tell, these protocols still do Chaumian cash ‘old style’: that is, they require a trusted ‘bank’, or ‘issuer’ and don’t actually integrate into the distributed trust framework of Bitcoin. Still very nice work. h/t commenters and Stephen Gornick (who also fixed a few typos).