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

• Published in: New generation computing 2022-04, Vol.40 (1), p.149-171
• Main Authors: Robert, Léo, Miyahara, Daiki, Lafourcade, Pascal, Mizuki, Takaaki
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Computer Hardware; Computer Science; Computer Systems Organization and Communication Networks; Cryptography and Security; Software Engineering/Programming and Operating Systems
• ISSN: 0288-3635; 1882-7055
• DOI: 10.1007/s00354-022-00155-5

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 card-based 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. We address this challenging task and propose a method for verifying the connectivity of hidden colored cells in a ZKP manner, such that we construct card-based ZKP protocols for the three puzzles.