Loading ...
Sorry, an error occurred while loading the content.
 

[Computational Complexity] Zero-Knowledge Sudoku

Expand Messages
  • Lance
    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
    Message 1 of 1 , Aug 3, 2006
      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.

      > 
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      >4
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >4
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      > 

      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
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >5
      >6
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >2
      >4
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >1
      >4
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >9
      >5
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >3
      >2
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >4
      >9
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >4
      >4
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >6
      >1
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >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
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >4
      >9
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >8
      >5
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >2
      >5
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >3
      >4
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >6
      >8
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >5
      >3
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >5
      >5
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >9
      >2
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >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

      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >4
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >8
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      >2
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 

      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

      > 
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >5
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      >5
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >1
      class="sudokuSquare"
      >9
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >2
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >5
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      >3
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >4
      class="sudokuSquare"
      > 
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >7
      class="sudokuSquare"
      >6
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      > 
      class="sudokuSquare"
      >8
      class="sudokuSquare"
      > 

      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.

      --
      Posted by Lance to Computational Complexity at 8/03/2006 03:10:00 PM

    Your message has been successfully submitted and would be delivered to recipients shortly.