Interactive proofs

After a series of ego-enhancing posts it's time to get back to something better. I've read on the bus a popular paper by László Lovász. It must be shared.

Why read this. You could go ahead an read the paper I link to. Or you could continue reading this. This post contains the same ideas, is shorter, and is targeted to a (good) working programmer.

Factoring. Can you factor the integer 15? It's 3\times5. OK, that was easy. But I bet you'll find it harder to factor 2458520708919619073142040881007027206573813634042770527212029117113260478602067483 even if I tell you that it has exactly two prime factors. No one knows how to factor numbers efficiently. Yet, if I tell you that one factor is 6348726349827463298746322987643379 you can probably quickly verify that this factor is prime and figure out the other prime factor (by division). You can now even come up with a similar problem yourself, after you observe that primes are dense.

Electronic envelope. Lovász considers a scenario involving two people playing chess, Alice and Bob. It gets late and they must interrupt the game when Alice is about to announce her move. She doesn't want Bob to think about his move all night. So she wants to tell Bob her move now but put it in an envelope that Bob will be able to open only in the morning when she gives him the key. The solution is simple: Encode the move as a four digit number, find a big prime that begins with those digits, multiply it by an even bigger prime, and tell Bob the answer. Then Bob, in principle, could factor the number and look at the first four digits of the smaller prime. Fortunately, that's too much work for one night.

Hamiltonian cycle. Finding a Hamiltonian cycle in a graph is another hard problem, and we'll use it to illustrate even more magic.

Never tell your password. Really. Not even to a server to which you want to prove that you know the password. Suppose your password is a permutation of the first 1000 nonnegative integers. If two numbers are adjacent in your permutation then add the pair to an edge list. Then add more edges to the list to get a description of a bigger graph, in which your password describes a Hamiltonian cycle. Then your job is to convince the server that you know a Hamiltonian cycle in the graph (which both you and the server know) without leaking any information. Here's how it works. You choose a random permutation and apply it to your first 1000 nonnegative integers. You write down a shuffled an edge list that uses these relabeled nodes but otherwise describes the same reference graph and append at the end the permutation. You encode each edge as a big prime and also the permutation. You multiply all these big primes by other random even bigger primes and you send the resulting list to the server. Then the server asks, with equal probability, one of: (1) can you give me all the keys? or (2) can you tell me which edges are in the Hamiltonian cycle and give me the keys to those? When you answer the server will see either (1) the whole graph given in a relabeled form and the permutation describing the relabeling or (2) a cycle given using some unknown relabeling, which presumably would be a Hamiltonian cycle in the whole graph. Of course, you may get lucky even if you don't know a Hamiltonian cycle. But if you repeat this process 100 times and you can consistently answer the server's questions then, well, you just proved interactively and with zero-knowledge leaking that you know the password!

Edit. Replaced "Hamiltonian path" by "Hamiltonian cycle".