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

被引：0

作者：

Ronen Gradwohl

Moni Naor

Benny Pinkas

Guy N. Rothblum

机构：

[1] The Weizmann Institute of Science,Department of Computer Science and Applied Math

[2] University of Haifa,Department of Computer Science

[3] MIT,CSAIL

来源：

Theory of Computing Systems | 2009年 / 44卷

关键词：

Cryptography; Zero-knowledge proofs; Puzzles;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：245 / 268

页数：23

共 15 条

[1] Balogh J.(2003)Private computation using a PEZ dispenser Theor. Comp. Sci. 306 69-84
[2] Csirik J.A.(1996)Comparing information without leaking it Commun. ACM 39 77-85
[3] Ishai Y.(1991)Proofs that yield nothing but their validity, and a methodology of cryptographic protocol design J. Assoc. Comput. Mach. 38 691-729
[4] Kushilevitz E.(1989)The knowledge complexity of interactive proof systems SIAM J. Comput. 18 186-208
[5] Fagin R.(2006)Unwed numbers Am. Sci. 94 12-15
[6] Naor M.(1991)Bit commitment using pseudo-randomness J. Cryptol. 4 151-158
[7] Winkler P.(undefined)undefined undefined undefined undefined-undefined
[8] Goldreich O.(undefined)undefined undefined undefined undefined-undefined
[9] Micali S.(undefined)undefined undefined undefined undefined-undefined
[10] Wigderson A.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →