Card-Based ZKP for Connectivity: Applications to Nurikabe, Hitori, and Heyawake
Card-Based ZKP for Connectivity: Applications to Nurikabe, Hitori, and Heyawake
复制标题
基于卡的 ZKP 连接：在 Nurikabe、Hitori 和 Heyawake 中的应用
DOI：
10.1007/s00354-022-00155-5
复制
发表时间：
2022
影响因子：
2.6
通讯作者：
Mizuki Takaaki
中科院分区：
文献类型：
--
作者：
Robert Leo;Miyahara Daiki;Lafourcade Pascal;Mizuki Takaaki
在过去的几年里，针对Nikoli的谜题设计了几种基于卡的零知识证明（ZKP）协议。虽然有一些相对简单的基于卡片的ZKP协议，如数独和Kakuro，但一些谜题在设计简单协议时面临困难。例如，Slitherlink需要新颖而复杂的技术来构建协议。在本研究中，我们专注于三个尼古拉难题：Nurikabe，Hitori和Heyawake。到目前为止，还没有为这些谜题开发出基于卡片的ZKP协议，部分原因是它们有一个相对棘手的规则，即有色细胞应该形成一个连通区域（即polyomino）;这个规则有时被称为“Bundan-kin”（日语），使谜题复杂化，并在设计基于卡片的ZKP协议时遇到困难。我们解决这个具有挑战性的任务，并提出了一种方法，用于验证隐藏的彩色细胞的连通性，在ZKP的方式，这样，我们构建基于卡片的ZKP协议的三个难题。
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.