A Sudoku game is a 9x9 board partially filled out with numbers 1-9.
9
2
3
8
4
1
4
5
6
1
7
6
2
1
9
8
2
5
4
2
9
5
8
3
2
1
9
7
6
8
2
3
4
5
6
8
5
3
4
1
9
7
2
4
3
2
7
9
5
8
6
1
4
1
8
7
6
3
2
5
9
5
6
9
8
2
4
7
1
3
2
7
3
5
1
9
6
8
4
9
2
6
5
7
1
8
3
4
4
3
7
2
9
8
1
5
6
1
5
8
3
4
6
9
2
7
Paula goes to a different room than Victor and chooses a random permutation σ of {1,…,9} say σ(1)=2, σ(2)=8, σ(3)=6, σ(4)=5, σ(5)=4, σ(6)=9, σ(7)=1, σ(8)=7 and σ(9)=3. Paula then permutes the solution using σ as such.
2
3
1
9
7
8
6
5
4
9
7
4
6
5
2
3
1
8
5
6
8
1
3
4
7
9
2
5
2
7
1
9
6
8
4
3
4
9
3
7
8
5
1
2
6
8
1
6
4
2
3
9
7
5
3
8
9
4
1
2
7
6
5
5
6
1
8
3
7
2
4
9
2
4
7
6
5
9
3
8
1
Victor can make one of 28 choices.
- Choose one of the rows.
- Choose one of the columns.
- Choose one of the sub-boxes.
- See the permuted version of the original puzzle.
6
5
4
3
1
8
7
9
2
If Victor picked the last choice Paula would reveal
3
8
6
7
5
2
5
4
9
2
1
9
8
2
3
7
8
4
5
8
3
4
7
6
8
Why should Victor now be convinced that a solution exists? If there was no solution, Paula could not find a permutation that causes Victor to accept for all of his 28 choices for the permuted puzzle is just the original puzzle in disguise. If Victor makes his choice at random then he will catch a cheating Paula with probability at least 1/28.
That still gives Paula a possible 27/28 chance of cheating. So repeat the protocol 150 times, each time Paula throws away the unused lock boxes and chooses a new permutation. Paula's chance of cheating in every round is at most (27/28)150 < 0.5%.
Moni Naor gives a different protocol using scratch-off cards where Paula could never cheat Victor.
Cute. Now how does she prove that the solution is unique?
ReplyDeleteDoesn't Victor also have to have the option of having Paula reveal all of the 3's (on n's) in the original problem so he can verify that they all map to the same token? It seems that without that Paula could give any random sudoku solved position but not one which maps to the given problem and still not get busted.
ReplyDeleteBram: the third option (Of seeing a permutation of the original puzzle) serves the purpose of letting the verifier verify that the puzzle is the same. He can see that the prover has indeed presented him with a permutation of the original puzzle, and since he could have checked any of the rows, columns, or squares, can be reasonably confident that the permuted puzzle has a solution. And of course, if the permuted puzzle has a solution, so does the original one.
ReplyDelete--Aaron
Naive question: What prevents Paula from really cheating and just putting "123456789" in each lockbox and a similar trivial permutation of the original puzzle? What step am I missing?
ReplyDeleteEach square has its own lockbox, rather than there being a single lockbox for each row, column, and 3x3 group. There is a grid of lockboxes, and the verifier can choose to look at any row or column of it. So if Paula doesn't have a solution, while she could put "123456789" in any one of the rows or columns, she can't put this in all of them (since the ability to do so would constitute a solution), and the verifier might pick the one that she was unable to fill correctly.
ReplyDeleteI was thinking the same thing as the above poster until I read your reply here. The grid changes everything. Thanks for clearing that up so neatly.
DeleteThanks Aaron, I understand now.
ReplyDeleteAlthough I think efficiency could be improved a bit. Since the rows and columns are permuted randomly, when Victor asks for a complete square he could instead ask for three complete squares, as long as no two of them share a row or column.
By 'square' in that last comment, I meant 3x3 group, by the way.
ReplyDeleteBram: Not so! That would let you find out that various pairs of blank squares contain the same number, even if it doesn't tell you what number it is.
ReplyDeleteCool post! There have often been discussions on this weblog as to how we can increase the appeal of theoretical computer science, and explain to non-theorists what it is we do. Examples such as these, which will appeal even to a layperson, are perfect for that.
ReplyDeleteYes, I'm sure that would increase their belief in the practical appeal of computer science: By my calculations, it would only take about 12 hours for Paula to convince Victor that she has a solution.
ReplyDeleteThe paper on Zero Knowledge for Sudoku (with Ronen Gradwohl and Benny Pinkas) that Lance refereed to is available here:
ReplyDeletehttp://www.wisdom.weizmann.ac.il/~naor/PAPERS/sudoku_abs.html
It contains both cryptographic and "physical" protocols.
Moni
PS It is hard to imagine that a person who has no interest in privacy would be interested in this sort of stuff...
you likely to get a lot more traffic after the sciam plug. I wonder, since Paula is the one making the lockboxes, how prohibitive would it be to construct those boxes so that she could have 9 different keys for each lock, with each key producing a specific desired number? obviously there would need to be at least 81 such locks for this to work, and practically if the number of such locks were small enough, Victor could reject anything that seemed suspicious. I'm sure the presence of such manipulable locks depends on the algorithm used, but it seems like with only 3 bits of information in each box that it would be feasible for a lot of algorithms.
ReplyDeleteI do not understand why sudoku would be NP.
ReplyDeleteSudoku is an NP problem because of the reduction to graph coloring.
ReplyDeleteImagine constructing a map where each region is an entry in the puzzle and each region is connected to each region in its row and each region in its column and each of the regions inside its 3 by 3 block.
Now, if we have 9 colors (where each color is a number) we have to now color that region such that each region its connected to (which is each region in its row, column and block) has to have a different color from it (or rather a different number).
The actual reduction would have to show that if we could solve any sized sudoku in sub np that we could solve map coloring in sub np, which would offer up a contradiction. Therefore, we now need to show that we can construct a sudoku puzzle that upon solving it, could give us an answer to any map coloring problem.
I would imagine that this would involve many partially completed sudoku puzzles in order to solve.
What is confusing about this "proof" is there is an implicit trusted third party. Let's call him Charlie.
ReplyDeleteAfter solving the Sudoku puzzle, Paula needs to give Charlie her solution, ... *and* a permutation.
Victor gets to ask *one* of 28 possible questions, and Charlie gives him the (permuted) response.
When Victor wishes to ask another question, Charlie first gets another (random) permutation from Paula, and then discloses the next (differently permuted) response.
The confusion comes from some readers thinking Paula is the one telling Victor a row, column, block, etc., ... and thus perhaps she might lie or cheat.
Victor needs to be able to rely on the trusted referee who knows the solution, and all Paula is allowed to do is give (valid) permutations, ... and then Victor will be convinced. If Victor needs to rely on Paula, then Victor could save everyone a lot of work and simply ask Paula, "Have you solved this Sudoku puzzle?"
In fact, since Victor needs to be able to rely on a trustworthy third party, Victor need only ask Charlie: "Did Paula give you a valid solution?", ... again, saving everyone lots of work.
While article does talk about Victor being convinced of something (Paula solved the puzzle) with Zero-Knowledge of the specific details of the solution, ... it doesn't seem to be a useful example of how Zero-Knowledge proofs can be put to practical use in Computer Science applications.
When one says Sudoku is NP-complete, one should keep in mind that this refers only to an unusual type of Sudoku puzzle in which there might be multiple solutions.
ReplyDeletehttp://11011110.livejournal.com/23221.html