License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12781/
Go to the corresponding LIPIcs Volume Portal

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:
LIPIcs-FUN-2021-20.pdf (0.7 MB)

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
Collection: 10th International Conference on Fun with Algorithms (FUN 2021)
Issue Date: 2020
Date of publication: 16.09.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI