Zero knowledge proof for Sudoku solution
I occasionally listen to a podcast called Computational Complexity. They recently had an interesting blog post explaining a zero-knowledge proof for a Sudoku puzzle.
A zero-knowledge proof is an interesting beast. It involves two parties, the Prover (who knows something) and the Skeptic (who doesn’t). The Prover has to convince the Skeptic that they know something, without revealing what they know.
The example given on the linked article is of a pair of sudoku players. One of them (the Prover, who we shall call Pam) has solved the puzzle. The other (the Skeptic, Sam) is convinced that there is no solution. How can Pam convince Sam that there is a solution without giving him solution?
This is the purpose of a zero-knowledge proof. For a sudoku, the Prover has to take the solved puzzle and permute all the numbers. So the features of the puzzle is identical, but the particular symbols in each grid square are different. For example, if the top-left square and the middle square of the original both contained a 7, then in the permuted puzzle they would both contain an identical, but different value.
So let us say that Pam has taken her solved puzzle, and produced an identical but mixed-up version. How does she prove that to Sam? She writes each digit on a small card and arranges them face-down on a table. Sam then has a choice:
- See a single row
- See a single column
- See a 3x3 block
She then turns over the row, column or group he wants to see. If she has a real solution he can confirm that the digits 1-9 only appear once. This information doesn’t help him solve his own puzzle, since there’s no evidence that the cards he has seen are actually permutations of his own puzzle.
So Pam could have cheated. She may just be pretending to have solved the puzzle and be revealing small sets of numbers from a much easier puzzle. Which is why Sam also has a fourth choice - he can ask that Pam turn over the cards which correspond to the starting numbers for his original puzzle. These allow him to confirm that her solution, whatever it is, had the same unique starting point as his own.
The problem is that all Sam has to do is ask to see two 3x3 groups and the starting combination and then he can solve his own puzzle. Which is what we’re trying to prevent. The way round it is simple - Sam can only make one choice from the selection 1-4. Once he has made his choice and confirmed that Pam wasn’t lying in some way, she sweeps all her cards off the table and starts again. She makes a different permutation from the original solution, and allows him to make another choice.
Each time he chooses, he has a choice of 28 options: one each of 9 rows, 9 columns and 9 groups or the opening state of the board. If she’s lying he can only catch her out with probability of 1/28. She has 27 ways to cheat him for every go! But according to the post, if they repeat the game 150 times:
Paula’s chance of cheating in every round is at most (27/28)150 < 0.5%.
So while it might not be actually feasible for a couple of people fighting over an “impossible” sudoku it demonstrates the principle marvellously. And in reality, it shouldn’t take long to convince someone.