Physical Zero-Knowledge Proof for Numberlink Puzzle and $k$ Vertex-Disjoint Paths Problem
This work addresses the need for secure, non-revealing verification in logic puzzles and graph theory problems, but it is incremental as it adapts existing zero-knowledge proof concepts to a physical card-based implementation.
The paper tackles the problem of verifying solutions to Numberlink puzzles and the k vertex-disjoint paths problem without revealing the solution details, by developing a physical zero-knowledge proof protocol using a deck of cards that allows a prover to demonstrate knowledge of a solution while keeping it secret.
Numberlink is a logic puzzle with an objective to connect all pairs of cells with the same number by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a prover to convince a verifier that he/she knows a solution without revealing it. In particular, the protocol shows how to physically count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Finally, we show that our protocol can be modified to verify a solution of the well-known $k$ vertex-disjoint paths problem, both the undirected and directed settings.