Card-Based Zero-Knowledge Proof for Sudoku

Authors Tatsuya Sasaki, Takaaki Mizuki, Hideaki Sone



PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.29.pdf
  • Filesize: 428 kB
  • 10 pages

Document Identifiers

Author Details

Tatsuya Sasaki
  • Graduate School of Information Sciences, Tohoku University, 6--3--09 Aramaki-Aza-Aoba, Aoba, Sendai 980--8579, Japan
Takaaki Mizuki
  • Cyberscience Center, Tohoku University, 6--3 Aramaki-Aza-Aoba, Aoba, Sendai 980--8578, Japan
Hideaki Sone
  • Cyberscience Center, Tohoku University, 6--3 Aramaki-Aza-Aoba, Aoba, Sendai 980--8578, Japan

Cite AsGet 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)
    0
    PDF Downloads

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail