Paper 2021/556

Interactive Physical ZKP for Connectivity:Applications to Nurikabe and Hitori

Leo Robert, Daiki Miyahara, Pascal Lafourcade, and Takaaki Mizuk

Abstract

During the last years, many Physical Zero-knowledge Proof(ZKP) protocols for Nikoli’s puzzles have been designed. In this paper, we propose two ZKP protocols for the two Nikoli’s puzzles called Nurikabe and Hitori. These two puzzles have some similarities, since in their rules at least one condition requires that some cells are connected to each other, horizontally or vertically. The novelty in this paper is to propose two techniques that allow us to prove such connectivity without leaking any information about a solution.

Note: Technical report.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Major revision. CiE
Keywords
Zero-knowledge proofsCard-based secure two-party protocolsPuzzleNurikabeHitori.
Contact author(s)
leo robert @ uca fr
History
2021-04-28: received
Short URL
https://ia.cr/2021/556
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/556,
      author = {Leo Robert and Daiki Miyahara and Pascal Lafourcade and Takaaki Mizuk},
      title = {Interactive Physical {ZKP} for Connectivity:Applications to Nurikabe and Hitori},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/556},
      year = {2021},
      url = {https://eprint.iacr.org/2021/556}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.