Cryptographic and Physical Zero-Knowledge
Proof Systems for Solutions of Sudoku Puzzles
Ronen Gradwohl Moni Naor
Benny Pinkas
Guy Rothblum
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 עברית
(Somewhat) Related On-Line Papers:
- Tal Moran and Moni Naor, Polling with Physical
Envelopes: A Rigorous Analysis of a Human-Centric Protocol, Eurocrypt 2006, Abstract
, Postscript , gzipped Postscript , PDF .
- Tal Moran and Moni Naor, Basing Cryptographic
Protocols on Tamper-Evident Seals, Abstract
, Postscript
, gzipped Postscript , PDF
- Moni Naor, Yael Naor and Omer Reingold, Applied Kid
Cryptography or How to convince your children you are not cheating,
August 98 Abstract
, Postscript
, gzipped Postscript , PDF
Also see: The Puzzler page. - Ron Fagin, Moni Naor and Peter Winkler, Comparing
Information without Leaking it, Communications of the ACM, May
1996, pp. 77-85. Abstract,
Postscript,
gzipped Postscript.
- Moni Naor and Adi Shamir, Visual
Cryptography, Eurocrypt 94. Postscript
, gzipped Postscript
Back to: On-Line
Publications, Recent Papers