Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems
This provides a novel physical verification method for graph theory problems, with potential applications in puzzles and educational tools, but it is incremental as it adapts existing card-based ZKP techniques to a new graph condition.
The paper tackles the problem of proving that a hidden subgraph is a connected spanning subgraph without revealing it, by proposing a physical zero-knowledge proof protocol using a deck of cards, and applies it to verify solutions for NP-complete problems like Hamiltonian cycle and Bridges puzzle.
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.