Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems
Preprint
Abstract
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 a physical protocol of zero-knowledge proof for this condition using a 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 logic puzzle called Bridges.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Interactive Physical ZKP for Connectivity: Applications to Nurikabe and Hitori2021
- Physical Zero-Knowledge Proof for Numberlink Puzzle and k Vertex-Disjoint Paths ProblemNew Generation Computing, 2020
- Proofs that yield nothing but their validity and a methodology of cryptographic protocol design2019
- Card-Based Physical Zero-Knowledge Proof for KakuroIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2019
- Secure implementations of a random bisection cutInternational Journal of Information Security, 2019
- Card-Based Protocols Using Regular Polygon CardsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2017
- Hashiwokakero is NP-completeInformation Processing Letters, 2009
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989