Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2021.20
URN: urn:nbn:de:0030-drops-127817
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12781/
Miyahara, Daiki ; Robert, Léo ; Lafourcade, Pascal ; Takeshige, So ; Mizuki, Takaaki ; Shinagawa, Kazumasa ; Nagao, Atsuki ; Sone, Hideaki
Card-Based ZKP Protocols for Takuzu and Juosan
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{miyahara_et_al:LIPIcs:2020:12781,
author = {Daiki Miyahara and L{\'e}o Robert and Pascal Lafourcade and So Takeshige and Takaaki Mizuki and Kazumasa Shinagawa and Atsuki Nagao and Hideaki Sone},
title = {{Card-Based ZKP Protocols for Takuzu and Juosan}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {20:1--20:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12781},
URN = {urn:nbn:de:0030-drops-127817},
doi = {10.4230/LIPIcs.FUN.2021.20},
annote = {Keywords: Zero-knowledge proof, Card-based cryptography, Takuzu, Juosan}
}
| Keywords: | Zero-knowledge proof, Card-based cryptography, Takuzu, Juosan | |
| Seminar: | 10th International Conference on Fun with Algorithms (FUN 2021) | |
| Issue date: | 2020 | |
| Date of publication: | 16.09.2020 |
