论文标题

跨越子图的连接的物理ZKP:桥梁难题的应用程序和其他问题

Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems

论文作者

Ruangwises, Suthee, Itoh, Toshiya

论文摘要

称者$ p $和验证者$ v $都知道一个无向图$ g $,但只有$ p $知道$ g $的子图$ h $。如果没有透露有关$ h $的任何信息,$ p $要说服$ v $ $ h $是$ g $的连接子图,即连接$ h $,并包含所有$ g $的顶点。在本文中,我们使用物理卡片提出了一种非常规的零知识证明协议,这使$ p $可以物理地表明$ h $可以满足该条件而没有透露条件。我们还展示了该协议的应用,以验证三个众所周知的NP完整问题的解决方案:汉密尔顿周期问题,最大的叶子生成树问题以及一个流行的逻辑难题,称为桥梁。

An undirected graph $G$ is known to both the prover $P$ and the verifier $V$, but only $P$ knows a subgraph $H$ of $G$. Without revealing any information about $H$, $P$ wants to convince $V$ that $H$ is a connected spanning subgraph of $G$, i.e. $H$ is connected and contains all vertices of $G$. In this paper, we propose an unconventional zero-knowledge proof protocol using a physical deck of cards, which enables $P$ to physically show that $H$ satisfies the condition without revealing it. We also show applications of this protocol to verify solutions of three well-known NP-complete problems: the Hamiltonian cycle problem, the maximum leaf spanning tree problem, and a popular logic puzzle called Bridges.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源