论文标题
物理零知识证明数字链接拼图和$ k $ vertex-disshixexhient路径问题
Physical Zero-Knowledge Proof for Numberlink Puzzle and $k$ Vertex-Disjoint Paths Problem
论文作者
论文摘要
NumberLink是一个逻辑难题，其目标是通过在矩形网格中的非交叉路径连接所有与数字相同的单元格。在本文中，我们提出了使用一张牌牌的零知识证明的物理协议，这使供者能够说服一个验证者，他/她知道解决方案而不揭示了解决方案。特别是，该协议显示了如何物理计算列表中等于给定秘密值的元素数量，而不揭示该值，列表中元素的位置与之等于它或列表中任何其他元素的值。最后，我们证明可以修改我们的协议以验证众所周知的$ K $ VERTEX-DISEXEXEXEXENEXEXENEXEXENEXENEXEXENEX路径问题，无论是未指向和有向设置的问题。
Numberlink is a logic puzzle with an objective to connect all pairs of cells with the same number by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a prover to convince a verifier that he/she knows a solution without revealing it. In particular, the protocol shows how to physically count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Finally, we show that our protocol can be modified to verify a solution of the well-known $k$ vertex-disjoint paths problem, both the undirected and directed settings.
