The most unhelpful possible way to prove something

21 September 2013 by Julie Rehmeyer, posted in Computer Science, Mathematics

Computer science, I think, gets even more neglected by science journalists than math does. Oh, sure, the next iPhone release gets lots of media attention, but that has little to do with how most computer scientists spend their time, and the general public rarely gets much of a view of the breadth and fascination of the field. I occasionally cover stories on the mathier edge of computer science, but I’m not deeply ensconced in the field and not always tuned into the latest computer science developments. So I’m excited to talk to the computer scientists at the Heidelberg Laureate Forum next week.

I’ve been warming up by reading about the Turing Award winners who will be at the forum, and wow, they’ve done some cool stuff!

Take Shafi Goldwasser and Silvio Micali, the most recent winners of the A.M. Turing Award (both of whom will be at the forum). They observed that most mathematical proofs do a lot more than simply prove the theorem true. Say, for example, that you want to prove that a graph is Hamiltonian — that is, that it’s possible to create a path that visits each vertex of the graph exactly once. The obvious way to prove this is to simply show such a path. But Goldwasser and Micali (together with Charles Rackoff) pointed out that that conveys a lot more information than just that such a path exists — it finds some particular example. So they developed a theory to describe how much “knowledge” a particular proof conveys.

They also showed how you could prove something without conveying any extra information at all, other than that the theorem is true. At least in theory, one could use their protocol to show that, say, the Riemann Hypothesis is true, to within any degree of certainty anyone might ask, while revealing nothing about any of the details of the proof! Of course, if anyone actually did this, the mathematical community would be incensed. Knowing a theorem is true is nice, but the real reward is in the deepened understanding that a proof conveys — exactly what this protocol would conceal. In cryptography, on the other hand, carefully controlling what information is concealed and what is revealed is a pretty hand trick. That makes it not so surprising that Goldwasser and Micali’s work has had a bigger impact on computer science than on mathematical proof.

So let’s imagine that your “theorem” is simply the claim that you know the magic word that opens a door (or, say, the password for a trove of top-secret NSA documents). You’d like to demonstrate that to someone without revealing any extra information. You not only don’t want to reveal the magic word, you want to prove that you know the magic word only to one person, not to the whole world. Then Goldwasser and Micali have the solution for you!

To see how it works, imagine a peculiar, circular cave, with an entrance at one end and a magic door blocking the circle at the other, like this:

 

Wikimedia Commons CC-BY-2.5 Illustrator: Drake

 

Peggy (for “Prover”) wants to demonstrate to Victor (for “Verifier”) that she knows the magic word. So she has Victor stand outside the cave, and she travels down either side of the cave’s loop, side A or side B. Then Victor goes into the cave and calls out A or B, at random, and Peggy has to return down that side of the cave.

Let’s say that on the first round, Peggy goes down side A. If Victor calls A, she simply turns around and goes back out. If he calls B, she says the magic word, opens the magic door, and goes down A. So from Victor’s perspective, what he knows is that if she doesn’t know the magic word, she’d have had a 50% chance of succeeding.

So then Victor leaves the cave and they repeat. After two rounds, if Peggy doesn’t know the magic word, she would have only a one in four chance of having succeeded. And after twenty rounds, she’d have less than a one in a million chance of succeeding. So by that point, Victor would pretty darn convinced that Peggy’s got the magic word.

But now let’s suppose that Victor wants to convince someone else that Peggy knows the magic word. Even if he had a hidden camera, he couldn’t do it. After all, a third person couldn’t be certain that he and Peggy hadn’t agreed in advance on the order of A’s and B’s. If Peggy knew the letter Victor was going to call, she could just always go down that path. So Peggy has managed to convince Victor that she knows the magic word without revealing any extra information of any kind, to Victor or anyone else.

Hat-tip to the authors of the article “How to Explain Zero-Knowledge Protocols to Your Children," who developed this way of explaining it. The whole thing is worth reading — one of the most delightful and entertaining scientific articles ever written.

 


One Response to “The most unhelpful possible way to prove something”

  1. Han Reply | Permalink

    Thanks for this very clear explanation.

Leave a Reply


× three = 6