Sudoku 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 עברית
Back to: On-Line
Publications, Recent Papers