Card-based zero-knowledge proof for Sudoku

Tatsuya Sasaki, Takaaki Mizuki, Hideaki Sone

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

14 Citations (Scopus)


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.

Original languageEnglish
Title of host publication9th International Conference on Fun with Algorithms, FUN 2018
EditorsGiuseppe Prencipe, Hiro Ito, Stefano Leonardi, Linda Pagli
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages2620
ISBN (Electronic)9783959770675
Publication statusPublished - 2018 Jun 1
Event9th International Conference on Fun with Algorithms, FUN 2018 - La Maddalena Island, Italy
Duration: 2018 Jun 132018 Jun 15

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference9th International Conference on Fun with Algorithms, FUN 2018
CityLa Maddalena Island


  • Card-based cryptography
  • Sudoku
  • Zero-knowledge proof


Dive into the research topics of 'Card-based zero-knowledge proof for Sudoku'. Together they form a unique fingerprint.

Cite this