Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Card-Based ZKP for Connectivity: Applications to Nurikabe, Hitori, and Heyawake *

Abstract : During the last years, several card-based Zero-Knowledge Proof (ZKP) protocols for Nikoli's puzzles have been designed. Although there are relatively simple card-based ZKP protocols for a number of puzzles, such as Sudoku and Kakuro, some puzzles face difficulties in designing simple protocols. For example, Slitherlink requires novel and elaborate techniques to construct a protocol. In this study, we focus on three Nikoli puzzles: Nurikabe, Hitori, and Heyawake. To date, no cardbased ZKP protocol for these puzzles has been developed, partially because they have a relatively tricky rule that colored cells should form a connected area (namely, a polyomino); this rule, sometimes referred to as "Bundan-kin" (in Japanese), complicates the puzzles, as well as facilitating difficulties in designing card-based ZKP protocols.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Léo Robert Connect in order to contact the contributor
Submitted on : Tuesday, January 25, 2022 - 1:08:22 PM
Last modification on : Thursday, February 10, 2022 - 3:34:52 AM
Long-term archiving on: : Tuesday, April 26, 2022 - 6:54:25 PM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-08-09

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License


  • HAL Id : hal-03542477, version 1


Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki. Card-Based ZKP for Connectivity: Applications to Nurikabe, Hitori, and Heyawake *. In press. ⟨hal-03542477⟩



Record views