How to construct physical zero-knowledge proofs for puzzles with a “single loop” condition
How to construct physical zero-knowledge proofs for puzzles with a “single loop” condition
复制标题
如何为具有“单循环”条件的难题构建物理零知识证明
DOI：
10.1016/j.tcs.2021.07.019
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Sone Hideaki
中科院分区：
文献类型：
--
作者：
Lafourcade Pascal;Miyahara Daiki;Mizuki Takaaki;Robert Leo;Sasaki Tatsuya;Sone Hideaki
我们提出了一种技术来构建物理零知识证明（ZKP）协议的难题，需要一个单一的循环绘制功能。我们的方法是基于一个循环只有一个洞的观察，这个属性保持稳定的一些简单的变换。使用这个技巧，我们可以将一个简单的大循环（任何人都可以看到）转换为解决方案循环，方法是使用不透露任何关于解决方案的信息的转换。我们说明了我们的技术，应用它来构建物理ZKP协议的两个尼古拉难题：Slitherlink和Masyu。
We propose a technique to construct physical Zero-Knowledge Proof (ZKP) protocols for puzzles that require a single loop draw feature. Our approach is based on the observation that a loop has only one hole and this property remains stable by some simple transformations. Using this trick, we can transform a simple big loop, which is visible to anyone, into the solution loop by using transformations that do not disclose any information about the solution. We illustrate our technique by applying it to construct physical ZKP protocols for two Nikoli puzzles: Slitherlink and Masyu.