Say Victor has a Sudoku problem written on a paper but doesn’t know how to solve it. Peter knows the solution. If there is a double-sided photocopier, how can Peter convince Victor that he really knows the solution without leaking any information about the solution?
If there is a protocol that satisfies this requirement, then we call it a zero-knowledge proof for the Sudoku problem, because the verifier Victor doesn’t learn anything about the solution from the proof.
The protocol is as follows:
- Peter writes the solution on the backside of the paper so that Victor cannot see it.
- Victor chooses a row, a column or a submatrix.
- Peter cuts off the row, column or submatrix from the paper, and further cuts it into 9 grids, shuffles them, and gives them to Victor.
- Victor verifies they are indeed a permutation of 1 to 9.
Note that Victor doesn’t learn anything about the solution in this protocol.
If there is a solution and Peter really knows it, Victor will always get a permutation of 1 to 9 in Step 4. So Victor will always believe Peter knows the solution.
But if there isn’t a solution, it’s still possible for Peter to cheat Victor, because it’s possible for Peter to just ‘guess right’. Here’s when the photocopier comes. After Step 1, Victor can photocopy the paper into 27 copies, so all 9 row, 9 columns and 9 submatrices will be verified.
Furthermore, Victor can verify the initial numbers are the same on both sides of the paper on-the-fly. Thus if there isn’t a solution, then it’s impossible for Peter to cheat Victor.