论文标题
物理零知识证明波纹效果
Physical Zero-Knowledge Proof for Ripple Effect
论文作者
论文摘要
纹波效应是一个逻辑难题，玩家必须在矩形网格中填充数字中的数字。网格分为房间，每个房间必须包含连续的整数，从1到它的大小。同样，如果同一行或列中的两个单元格包含相同的数字$ x $，则必须至少有一个分隔两个单元格的$ x $单元。在本文中，我们使用一张卡片来为波纹效应拼图开发物理零知识证明，这使供者能够说服验证者，他/她知道解决方案而不揭示解决方案。特别是，给定一个秘密数字$ x $和数字列表，我们的协议可以实际验证$ x $在列表中的第一个$ x $数字中没有出现，而不会显示$ x $或列表中的任何数字。
Ripple Effect is a logic puzzle where the player has to fill numbers into empty cells in a rectangular grid. The grid is divided into rooms, and each room must contain consecutive integers starting from 1 to its size. Also, if two cells in the same row or column contain the same number $x$, there must be a space of at least $x$ cells separating the two cells. In this paper, we develop a physical zero-knowledge proof for the Ripple Effect puzzle using a deck of cards, which allows a prover to convince a verifier that he/she knows a solution without revealing it. In particular, given a secret number $x$ and a list of numbers, our protocol can physically verify that $x$ does not appear among the first $x$ numbers in the list without revealing $x$ or any number in the list.
