Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles

Ronen Gradwohl, Moni Naor, Benny Pinkas*, Guy N. Rothblum

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

Abstract

We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can 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 to the verifier. In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols 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 physical protocols utilize items such as scratch-off cards, similar to those used in lotteries, or even just simple playing cards. The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by "lay-people" and implementable without the use of computers.

Original languageEnglish (US)
Pages (from-to)245-268
Number of pages24
JournalTheory of Computing Systems
Volume44
Issue number2
DOIs
StatePublished - Feb 2009

Funding

Research of R. Gradwohl was supported by US-Israel Binational Science Foundation Grant 2002246. Research of M. Naor was supported in part by a grant from the Israel Science Foundation. Research of B. Pinkas was supported in part by the Israel Science Foundation (grant number 860/06). Research of G.N. Rothblum was supported by NSF grant CNS-0430450 and NSF grant CFF-0635297.

Keywords

  • Cryptography
  • Puzzles
  • Zero-knowledge proofs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles'. Together they form a unique fingerprint.

Cite this