TY - GEN
T1 - Card-based ZKP protocols for takuzu and juosan
AU - Miyahara, Daiki
AU - Robert, Léo
AU - Lafourcade, Pascal
AU - Takeshige, So
AU - Mizuki, Takaaki
AU - Shinagawa, Kazumasa
AU - Nagao, Atsuki
AU - Sone, Hideaki
N1 - Funding Information:
Funding Daiki Miyahara: This work was supported by JSPS KAKENHI Grant Number JP19J21153. Léo Robert: This work was partially supported by the French project ANR-18-CE39-0019 (MobiS5). Pascal Lafourcade: This work was partially supported by the project ANR-18-CE39-0019 (MobiS5). Takaaki Mizuki: This work was supported by JSPS KAKENHI Grant Number JP17K00001. Kazumasa Shinagawa: This work was supported by JSPS KAKENHI Grant Number JP17J01169.
Publisher Copyright:
© Licensed under Creative Commons License CC-BY 10th International Conference on Fun with Algorithms (FUN 2021).
PY - 2020/9/1
Y1 - 2020/9/1
N2 - Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0's and 1's under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.
AB - Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0's and 1's under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.
KW - Card-based cryptography
KW - Juosan
KW - Takuzu
KW - Zero-knowledge proof
UR - http://www.scopus.com/inward/record.url?scp=85091410868&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85091410868&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.FUN.2021.20
DO - 10.4230/LIPIcs.FUN.2021.20
M3 - Conference contribution
AN - SCOPUS:85091410868
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 10th International Conference on Fun with Algorithms, FUN 2021
A2 - Farach-Colton, Martin
A2 - Prencipe, Giuseppe
A2 - Uehara, Ryuhei
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 10th International Conference on Fun with Algorithms, FUN 2021
Y2 - 30 May 2021 through 1 June 2021
ER -