TY - GEN
T1 - Card-based zero-knowledge proof for Sudoku
AU - Sasaki, Tatsuya
AU - Mizuki, Takaaki
AU - Sone, Hideaki
N1 - Funding Information:
This work was supported by JSPS KAKENHI Grant Number JP17K00001.
Publisher Copyright:
© Tatsuya Sasaki, Takaaki Mizuki, and Hideaki Sone; licensed under Creative Commons License CC-BY 9th International Conference on Fun with Algorithms (FUN 2018).
PY - 2018/6/1
Y1 - 2018/6/1
N2 - 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.
AB - 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.
KW - Card-based cryptography
KW - Sudoku
KW - Zero-knowledge proof
UR - http://www.scopus.com/inward/record.url?scp=85048954170&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048954170&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FUN.2018.29
DO - 10.4230/LIPIcs.FUN.2018.29
M3 - Conference contribution
AN - SCOPUS:85048954170
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 291
EP - 2910
BT - 9th International Conference on Fun with Algorithms, FUN 2018
A2 - Prencipe, Giuseppe
A2 - Ito, Hiro
A2 - Leonardi, Stefano
A2 - Pagli, Linda
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 9th International Conference on Fun with Algorithms, FUN 2018
Y2 - 13 June 2018 through 15 June 2018
ER -