LIPIcs.FUN.2018.29.pdf
- Filesize: 428 kB
- 10 pages
Document
Card-Based Zero-Knowledge Proof for Sudoku
Authors
-
Part of:
Volume:
9th International Conference on Fun with Algorithms (FUN 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
Cite As Get BibTex
Tatsuya Sasaki, Takaaki Mizuki, and Hideaki Sone. Card-Based Zero-Knowledge Proof for Sudoku. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 29:1-29:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FUN.2018.29
Abstract
In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and that he/she knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have a soundness error with a non-zero probability or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof for Sudoku that use a normal deck of playing cards and have no soundness error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
Subject Classification
ACM Subject Classification
- Security and privacy → Information-theoretic techniques
Keywords
- Zero-knowledge proof
- Card-based cryptography
- Sudoku
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, and Pascal Lafourcade. Physical zero-knowledge proofs for akari, takuzu, kakuro and kenken. In Erik D. Demaine and Fabrizio Grandoni, editors, 8th International Conference on Fun with Algorithms, FUN 2016, June 8-10, 2016, La Maddalena, Italy, volume 49 of LIPIcs, pages 8:1-8:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.FUN.2016.8.
- Yu-Feng Chien and Wing-Kai Hon. Cryptographic and physical zero-knowledge proof: From sudoku to nonogram. In Paolo Boldi and Luisa Gargano, editors, Fun with Algorithms, 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings, volume 6099 of Lecture Notes in Computer Science, pages 102-112. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-13122-6_12.
- Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):691-729, 1991. URL: http://dx.doi.org/10.1145/116825.116852.
- Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186-208, 1989. URL: http://dx.doi.org/10.1137/0218012.
- Ronen Gradwohl, Moni Naor, Benny Pinkas, and Guy N. Rothblum. Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. Theory Comput. Syst., 44(2):245-268, 2009. URL: http://dx.doi.org/10.1007/s00224-008-9119-9.
- Yuji Hashimoto, Kazumasa Shinagawa, Koji Nuida, Masaki Inamura, and Goichiro Hanaoka. Secure grouping protocol using a deck of cards. In Junji Shikata, editor, Information Theoretic Security - 10th International Conference, ICITS 2017, Hong Kong, China, November 29 - December 2, 2017, Proceedings, volume 10681 of Lecture Notes in Computer Science, pages 135-152. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-72089-0_8.
- Rie Ishikawa, Eikoh Chida, and Takaaki Mizuki. Efficient card-based protocols for generating a hidden random permutation without fixed points. In Cristian S. Calude and Michael J. Dinneen, editors, Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Auckland, New Zealand, August 30 - September 3, 2015, Proceedings, volume 9252 of Lecture Notes in Computer Science, pages 215-226. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21819-9_16.
- Takaaki Mizuki and Hiroki Shizuya. Practical card-based cryptography. In Alfredo Ferro, Fabrizio Luccio, and Peter Widmayer, editors, Fun with Algorithms - 7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings, volume 8496 of Lecture Notes in Computer Science, pages 313-324. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-07890-8_27.
-
Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions, 86-A(5):1052-1060, 2003.
