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.

Let’s say Peggy (the “prover”) and Victor (the “verifier”) share a Sudoku puzzle, which is to say a 9-by-9 grid with several (but not all) boxes filled in with numbers between 1 and 9. Peggy wants to convince Victor that she has a solution to this puzzle. In other words, she knows a way of filling all the boxes in the grid with integers between 1 and 9; the restriction is that every row, column, and each of the nine 3-by-3 squares the grid naturally splits into contains all the numbers from 1 to 9, each exactly once. Moreover, the solution should extend the partial filling-in given at the outset. However, Victor should not learn of the actual solution.

To carry this out, Peggy makes a 9-by-9 array of cards with each card containing the appropriate component of the solution, face down. The face that is visible, facing up, contains a number from 1 to 81 expressing the position of that card in the grid. Victor is taken to the table containing the cards, and asks for the cards in the fixed places — that is, those given by the puzzle — to be revealed; Peggy does that, to show Victor that the constraints of the puzzle are met. Next, for each row, Peggy picks up the cards in that row, and places them into a box. She pulls out the cards from the box, showing Victor the other face only: that is, the face containing an integer between 1 and 9. By doing this, Peggy convinces Victor that the row in question contains exactly the integers between 1 and 9. However, Victor does not see the original side (which contains the position in the grid), and learns absolutely nothing that he did not already know about the actual positions of the cards in the grid.

The rest of the protocol is clear: Peggy does the same for each column, and for each of the nine 3-by-3 square the grid naturally decomposes into. When Peggy finishes one round (e.g. one row), she puts back the cards facing in the original direction. Since the cards contain a marker indicating their position in the grid on the back face, Victor can be convinced that Peggy has not altered the arrangement of the cards during the interaction. Moreover, he can be convinced that the putative solution satisfies the requirements: that each row, column, and 3-by-3 subsquare contains all the integers between 1 and 9, each exactly once. However, Victor has not learned anything other than precisely the last claim, which gives no information about the solution (other than that it is a solution).

I was amused by the extreme simplicity of this argument; there is no probability, not even any mathematics whatsoever, involved. I wonder why it isn’t more popular in introductions to zero-knowledge proofs.

Advertisements