2026-07-23T03:56:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8820 2024-03-06T10:42:44Z ddc:004 open_access

Card-Based Zero-Knowledge Proof for Sudoku Sasaki, Tatsuya Mizuki, Takaaki Sone, Hideaki Zero-knowledge proof Card-based cryptography Sudoku 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatsuya Sasaki and Takaaki Mizuki and Hideaki Sone 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.29 urn:nbn:de:0030-drops-88207 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.29 eng https://creativecommons.org/licenses/by/3.0/legalcode