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.
September 1, 2011 at 7:53 pm
Write a computer program that will verify that a given file contains a valid solution to the problem (and does not display/store any other info). Peggy and Victor both look over the code, watches it compile & run, and watches as Peggy inserts a disk with her supposed solution file, points the program to the file, gets the “Verified!” output, and deletes all traces of the file.
More to the point: Some mechanisms (like watching your hands to make sure you don’t cheat) can work in a physical setting but do not translate well into a context where you are reduced to communicating back and forth with pure data over some wires.
September 2, 2011 at 8:59 am
Yes, this example is primarily allegorical and intended for motivation. I understand that there are techniques for ensuring that Peggy can’t play games (even during a digital interaction), but I am not familiar with the details (so I’m taking this course!).
September 28, 2011 at 3:09 am
I think that there is some hidden probability in the protocol: when Peggy places the cards into the box, she has to do so in a random order or, alternatively, reveal them to Victor in a random order (but then Victor must not know how they are placed in the box). Otherwise, Victor would gain some information on the position of each card in the grid.