Computational Complexity

Thursday, August 03, 2006

 
Zero-Knowledge Sudoku

Posted by 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 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)¹⁵⁰ < 0.5%.

Moni Naor gives a different protocol using scratch-off cards where Paula could never cheat Victor.

3:10 PM # 14 comments

1.  D. Eppstein says:  
   
   Cute. Now how does she prove that the solution is unique?
   

   4:20 PM, August 03, 2006

2.  Bram Cohen says:  
   
   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.
   

   8:01 PM, August 03, 2006

3.  Aaron says:  
   
   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
   

   9:28 PM, August 03, 2006

4.  Anonymous says:  
   
   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?
   

   1:01 PM, August 04, 2006

5.  Aaron says:  
   
   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.
   

   1:11 PM, August 04, 2006

6.  Bram Cohen says:  
   
   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.
   

   7:30 PM, August 04, 2006

7.  Bram Cohen says:  
   
   By 'square' in that last comment, I meant 3x3 group, by the way.
   

   7:31 PM, August 04, 2006

8.  dave glasser says:  
   
   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.
   

   9:14 PM, August 04, 2006

9.  Anonymous says:  
   
   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.
   

   10:09 PM, August 04, 2006

10.  Anonymous says:  
    
    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.
    

    10:50 PM, August 04, 2006

11.  Moni Naor says:  
    
    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...
    

    7:12 AM, August 05, 2006

12.  Anonymous says:  
    
    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.
    

    8:06 PM, August 23, 2008

13.  Anonymous says:  
    
    I do not understand why sudoku would be NP.
    

    1:31 PM, August 27, 2008

14.  Anonymous says:  
    
    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.
    

    5:31 PM, October 18, 2008

Comment Feeds: This Post All