Out of the Box
Renaissance mathematicians lived in the same box. They wanted to prove that they could prove something, but they didn't want rivals to know how and so claim the credit. One scheme they tried was to deposit their new proof with impartial third parties. Unfortunately, those third parties weren't always so impartial.Nor is that some ancient dilemma restricted to mathematicians and scientists. The solution is worth serious money. For instance, when one company wants to buy another, it needs someone to handle the financial and legal details of the takeover; so it hires an investment firm specializing in that sort of thing. That firm is supposed to keep its information secret, because if news of the proposed takeover leaks out, the price of the target company's stock will soar. Insiders trading on their knowledge that the takeover will definitely occur can make an awful lot of money. Which is sometimes what happens.
What we really want is a way to divulge one piece of information without having to divulge everything connected with it. Happily, we now know, at least in theory, how to prove a fact while giving away absolutely nothing else besides our knowledge of it.
Suppose, for instance, I am a Renaissance mathematician desperate to prove to a duke that I could solve some problem, say all cubic equations. However, I can't just tell him my method because then he, or his court mathematician, may steal it. Here's what I do: I tell the duke to choose any cubic equation he wants to. Once he does, I quickly give him the solution. He can easily check my answer by plugging it into the equation he originally chose.
Of course, he's still suspicious. Maybe I just made a lucky guess. So I encourage him to pick another equation---which I then briskly solve. I keep doing that until he believes that I can indeed solve any of them. He will eventually give up and believe me because I'm very unlikely to keep guessing the right answer without having the knowledge I claim to have. Best of all, even after he believes me, he still hasn't the smallest idea of how I came by my knowledge. I've convinced him that I know a secret without actually having to tell him the secret.
To make that scheme work, four things must be true. First, the duke must have a great many possible equation choices (so that I couldn't precompute every answer). Second, his question choices must be random (so I couldn't predict his next question and solve it beforehand). Third, he must have an easy way to check each answer (to avoid giving me enough time between answers to compute much). Fourth, there must be no way to deduce anything about my secret method from any number of my public answers.
If all four conditions are met, it doesn't matter if anyone overhears the proof of identity. Watching all those questions and answers whiz by is a complete and utter waste of time since each new proof of identity will consist of new answers to a new set of randomly chosen questions. The duke can't cheat me any more than I can cheat the duke.
The important thing about this sort of scheme is that I can use it as proof of my identity without having to use fixed, and forgeable, identifiers. Suppose, for example, that I want to travel to a foreign city and be kept in the lap of luxury to which I have become accustomed. I tell my duke to write to the duke in the other city telling him that I'm coming and that to prove I am who I say I am I will instantly solve any cubic equation he chooses. I'm completely safe because no one else can impersonate me---not even my own pet duke.
It's as if two spies were meeting for the first time and exchanging the usual codes and countercodes to establish their identities. The first might say ``Are the azaleas blooming today?'' and the second might reply ``Oh yes, but the midnight mail is quite strange in these parts, isn't it?'' Or some such nonsense. However, in the updated version, the second spy has no clue what the first spy will ask---beyond knowing the general topic; and the first spy has no idea what answer the second spy will give---until the first spy gives it, at which time it can be checked. Further, the seemingly senseless question-and-answer cycle can go on for millions of times, each time with a brand new question.
The spies' abilities to survive that cycle are their individual signatures, proof that they are who they say they are. Even after those signatures are used many times---and no matter how many people listen in---no one, not even the person verifying the spies' identity, can later impersonate either of them.
Of course, none of us can go through that protocol fast enough. We can, however, put the whole thing on a smartcard, a credit-card-sized computer, and have the smartcard do the work for us. The smartcard could, for instance, talk to our cellular phone company to initiate a secure call---or it could talk to our computer to initiate a secure computer session. Used this way, it would become an electronic signature and could carry all sorts of other useful information---for example, complete medical histories, eventually including even X-rays, in case of accident.
Similar protocols can protect all sorts of other information, so that we could, for example, make anonymous smartcard purchases. No one---including the bank---has to know exactly what we buy, even if we don't use cash. We could protect our medical records and other sensitive information in the same way. The computer needn't be the Big Brother that so many fear it to be. Of course, what it could be, and what it will be, are entirely different things.
Protecting Us from Ourselves