Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles

Ronen Gradwohl        Moni Naor        Benny Pinkas        Guy Rothblum


Description: Sudoku in NewspaperSudoku is a combinatorial puzzle that has swept the world in 2005 (especially via newspapers, where it appears next to crossword puzzles), following the lead of Japan (see Sudoku Wikipedia entry or the American Scientist article). In a Sudoku puzzle the challenge is a 9 x 9 grid subdivided into nine 3 x 3 subgrids. Some of the cells are already set with values in the range 1 through 9 and the goal is to fill out the remaining cells with numbers 1 through 9 so that each number appears exactly once in each row, column and subgrid.

A natural issue, at least for cryptographers, is how to convince someone that you have solved a Sudoku puzzle without revealing the solution. The questions of interest here are how can a prover who knows the solution show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution?

In this paper we consider several methods for doing just that. Broadly speaking, the methods are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our protocols utilize playing cards, scissors and scratch-off cards, similar to those used in lotteries.

The cryptographic protocols are direct and efficient, and the physical protocols are meant to be understood by ``lay-people" and implementable without the use of computers.

Paper: Postscript , gzipped Postscript , PDF.
Pictorial Demonstration of one of the protocols: Demo.
Slides from Talks: English, Hebrew עברית  

(Somewhat) Related On-Line Papers:

Back to: On-Line PublicationsRecent Papers

Back Home