Thursday, August 03, 2006

Zero-Knowledge Sudoku

Victor has tried and failed to solve the latest Sudoku game and exclaims no solutions exists. His wife Paula has already solved the game. How does Paula convince Victor that a solution exists without giving the solution away?
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
The goal is to fill out the rest of the board with numbers 1-9 such that every row, column and the 3x3 sub-boxes all have exactly one of each digit in them.
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
Sudoku is an NP problem so Paula and Victor could reduce the problem to graph coloring and use the original zero-knowledge protocol for coloring. Or you can view Sudoku as a graph coloring problem. Here is a way for Paula can do a zero-knowledge proof on Sudoku directly, loosely based on the graph coloring protocol.
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
Paula then puts each entry into a lockbox (which can be implemented using cryptographic assumptions) and gives the lockboxes to Victor.
Victor can make one of 28 choices.
  1. Choose one of the rows.
  2. Choose one of the columns.
  3. Choose one of the sub-boxes.
  4. See the permuted version of the original puzzle.
Paula then unlocks the appropriate boxes. If say Victor picked the third row Paula would reveal
6
5
4
3
1
8
7
9
2
Victor will accept if all of the digits in the row appear exactly once. Note that every possible permutation in the row will occur with equal probability over the choice of σ, so Victor learns nothing about the solution from this question.
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
Victor accepts if this is really a permutation of the original problem. Since the permutation σ is chosen at random again Victor learns nothing about the solution from this question.
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.

17 comments:

  1. Cute. Now how does she prove that the solution is unique?

    ReplyDelete
  2. Doesn'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.

    ReplyDelete
  3. Bram: 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.

    --Aaron

    ReplyDelete
  4. 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?

    ReplyDelete
  5. Each 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.

    ReplyDelete
    Replies
    1. I 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.

      Delete
  6. Thanks Aaron, I understand now.

    Although 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.

    ReplyDelete
  7. By 'square' in that last comment, I meant 3x3 group, by the way.

    ReplyDelete
  8. Bram: 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.

    ReplyDelete
  9. Cool 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.

    ReplyDelete
  10. Yes, 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.

    ReplyDelete
  11. The paper on Zero Knowledge for Sudoku (with Ronen Gradwohl and Benny Pinkas) that Lance refereed to is available here:
    http://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...

    ReplyDelete
  12. 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.

    ReplyDelete
  13. I do not understand why sudoku would be NP.

    ReplyDelete
  14. Sudoku is an NP problem because of the reduction to graph coloring.
    Imagine 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.

    ReplyDelete
  15. What is confusing about this "proof" is there is an implicit trusted third party. Let's call him Charlie.

    After 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.

    ReplyDelete
  16. 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.

    http://11011110.livejournal.com/23221.html

    ReplyDelete