by Daniel Ranard
The fact that anything happens securely on the web should be mind-boggling. In some ways, the internet is like a group of people shouting at each other across an open field. How can you hold a secret conversation when anyone might be listening? How do you prevent imposters, when you can’t always see the face behind the shout?
Imagine trying to establish, say, paperless currency. How do I pay you? Maybe I just yell that I’m giving you ten (invisible) dollars. But you won’t be sure that it’s really me, or that I really have the money. And when you try to spend it later, how will anyone know I gave it to you?
One solution is for everyone to place their trust in some individual or organization. When we have a private message to deliver, we whisper it to our trusted messenger, who passes it along in secret. Likewise, when I want to pay you, I tell a trusted organization – the bank. They check it’s really me, then subtract money from my virtual balance, notifying you that you’ve been “paid.”
Most of us prefer not to trust strangers unless we need to. So how can we conduct ourselves on the internet, without ceding power to any one group?
No, I’m not about to start preaching bitcoin or other cryptocurrencies. I just want to share some satisfyingly clever ideas from cryptography, which accomplish the seemingly impossible.
Let’s start with the task of telling secrets in public. How do I shout a message that only you can understand? The answer might seem obvious: use a secret code. But if we’ve never met before, and everyone can hear our conversation, how do we decide on a code? I can’t shout, “Hello, nice to meet you! I’m about to tell you a secret message using that particular code – you know, the one where you shift all the letters by a few spots in the alphabet?”
We might try a mechanical solution instead. Say I send a courier with a locked box that contains my message. No one can open the box, sure. But how do I send you the key? The courier might steal it or make a duplicate.
There’s actually a very clever way to solve this problem using ordinary locks and keys. Think about it for a minute, if you want. To make it an honest brainteaser, let’s establish the ground-rules. I want to send you a secret message, but we’ve never met. Although I can communicate by sending envelopes and packages, I don’t trust the courier. For instance, the courier might steal the package. (We’ll need to assume that ultimately, we can find a courier who actually delivers the package, even if any particular courier might tamper with the contents. The hypothetical postal system may be insecure, but it can’t be useless.) How do we manage to exchange secret messages with guaranteed privacy?
I don’t know who came up with this idea, but here’s how it goes. Say I want to send you a message. First, you forge a secret key and padlock; your padlock only opens with your key. Then you charge a courier to deliver me the padlock, with the lock left carefully open. I write you a message, put it in a box, and lock it using your lock. Of course, I can’t re-open the box at this point, but neither can anyone else – except you. Finally, I send you back the locked message, knowing it’s secure.
If the courier tries to steal your open padlock, so be it. You’ll just hire another courier and send another copy of the padlock. Your padlock is called your “public key” (though it’s really more of a lock than a key). Having a copy of your public key doesn’t actually help someone read your secret messages. The only thing someone can do with a public key – the unlocked padlock – is send you secret messages, by locking them with the padlock. Meanwhile, the actual key you forged is your “private key,” which you never show anyone.
This mechanical scheme provides a somewhat faithful analogy to electronic “public-key protocols.” The particular mathematics used requires some background, but the essential ideas are over 100 years old. The protocols don’t rely on computers or electricity in any crucial way. Hypothetically, they could even be carried out by the crowd shouting across the field, if they were good with mental math. The procedure would go roughly like this. First, you do some arithmetic to come up with a pair of random but related numbers. The first number acts as your public key (like the open padlock in the mechanical example), which others will use to send you secret messages. The second number acts as your private key (like the private mechanical key you forged), which you’ll use to decode others’ messages. You announce your public key to the world: “Hi everyone, send me secret messages using the number 2407724!” If I then want to send you a message, I do some arithmetic involving both my intended message and the number 2407724. That arithmetic produces some other number, say 99938, which I shout back to you. Finally, you use your private key to do some more arithmetic and calculate my original message. In a good encryption scheme, the arithmetic is sufficiently complicated that anyone else hearing my spoken message “99938” won’t be able to reverse-engineer my original message or your private key, just like it’s hard to reverse-engineer the mechanical key that fits a given padlock.
It baffles intuition. You could put three strangers in a room, where everyone can hear everyone else. But using these mathematical tricks, any two of them could still carry out a secret conversation. The third person would hear everything from start to finish, but they couldn’t decipher the meaning.
These protocols were fully imagined already in the 1970s, and they’re just one step toward establishing trustworthy communication online. For instance, you’d also like to develop a “digital signature”: some method of modifying an electronic document such that only you could have made that modification, analogous to signing it in your own handwriting. Meanwhile, timestamping provides another interesting challenge. How do you prove a document was produced at a certain time, say before some other document? When you communicate about sending money, or signing contracts, it’s important to know who said what when.
The new ideas behind cryptocurrencies like bitcoin are an important addition to this body of techniques, with applications far beyond electronic money. On one hand, communicating on the internet really is like shouting in public. On the other hand, we’ve devised some very clever ways of shouting.
[In a future post, I’ll talk about the tricky art of timestamping and reaching consensus.]