Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of
Sudoku Puzzles
Ronen Gradwohl
Moni Naor Benny Pinkas
Abstract:
We consider various cryptographic and physical zero-knowledge
proof schemes for Sudoku, a popular combinatorial puzzle. 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.
(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 .
- Moni Naor and Adi Shamir, Visual Cryptography
, Eurocrypt 94.
Postscript ,
gzipped Postscript
Back to: On-Line Publications, Recent Papers
Back Home