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$ to $V$, $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
problem 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 two well-known NP-complete problems: the
Hamiltonian cycle problem and a logic puzzle called Bridges.

Go to Source of this post
Author Of this post: <a href="http://arxiv.org/find/cs/1/au:+Ruangwises_S/0/1/0/all/0/1">Suthee Ruangwises</a>, <a href="http://arxiv.org/find/cs/1/au:+Itoh_T/0/1/0/all/0/1">Toshiya Itoh</a>

By admin