The semester has just begun here, and my rate of posting will likely taper off. I do hope to finish the story I started earlier on exponential sums. In the meantime, I would like to explain a fun topic discussed in cryptography class today.

There are a lot of situations in which one party wants to prove to another that something is true, for instance that they have a certain bit of information (say, a solution to a computationally intractable problem, such as a Hamiltonian path in a large graph). However, either because the second party is not trustworthy, or because the transmission medium may be insecure, it may be ideal to make “proof” zero-knowledge. In other words, the second party needs to be convinced that the first party possesses the valuable information, but without actually learning what this information is (e.g. in the earlier example, the second party shouldn’t find out the Hamiltonian cycle).

There are a bunch of parables to illustrate the idea of a zero-knowledge proof. For instance, the Wikipedia article describes an example of a zero-knowledge proof that a graph has a Hamiltonian cycle. This protocol relies essentially on randomness, however — without it, a dishonest “prover” claiming to possess a Hamiltonian cycle could fool the verifier.

But there is a simple example of a zero-knowledge proof that does not use randomness in any way. This is a protocol to convince another party that one has a solution to a Sudoku puzzle. (more…)