Cryptology ePrint Archive: Report 2021/556

Interactive Physical ZKP for Connectivity:Applications to Nurikabe and Hitori

Leo Robert and Daiki Miyahara and 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.

Category / Keywords: applications / Zero-knowledge proofs, Card-based secure two-party protocols, Puzzle, Nurikabe, Hitori.

Original Publication (with major differences): CiE

Date: received 27 Apr 2021

Contact author: leo robert at uca fr

Available format(s): PDF | BibTeX Citation

Note: Technical report.

Version: 20210428:075558 (All versions of this report)

Short URL: ia.cr/2021/556


[ Cryptology ePrint archive ]