Physical Zero-Knowledge Proof for Numberlink Puzzle and $k$ Vertex-Disjoint Paths Problem

Abstract

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.

A preliminary version of this paper has appeared in the proceedings of FUN 2021

Cited by in corpus (11)

• Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku
• Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems
• Physical Zero-Knowledge Proof for Ripple Effect
• Physical ZKP for Makaro Using a Standard Deck of Cards
• Physical Zero-Knowledge Proof for Ball Sort Puzzle
• An Improved Physical ZKP for Nonogram and Nonogram Color
• 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
• NP-Completeness and Physical Zero-Knowledge Proofs for Zeiger
• Tatami Printer: Physical ZKPs for Tatami Puzzles