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

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 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.

arXiv commentThis paper has appeared at UCNC 2021

References in corpus (2)

• Physical Zero-Knowledge Proof for Numberlink Puzzle and $k$ Vertex-Disjoint Paths Problem
• Secure Grouping Protocol Using a Deck of Cards

Cited by in corpus (8)

• Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku
• Physical Zero-Knowledge Proof for Ripple Effect
• Physical ZKP for Makaro Using a Standard Deck of Cards
• An Improved Physical ZKP for Nonogram and Nonogram Color
• Physical Zero-Knowledge Proof for Ball Sort Puzzle
• Using Five Cards to Encode Each Integer in $\mathbb{Z}/6\mathbb{Z}$
• Printing Protocol: Physical ZKPs for Decomposition Puzzles
• Verifying the First Nonzero Term: Physical ZKPs for ABC End View, Goishi Hiroi, and Toichika