Physical Zero-Knowledge Proof for Numberlink Puzzle and k Vertex-Disjoint Paths Problem
- PDF / 1,066,566 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 190 Views
Physical Zero‑Knowledge Proof for Numberlink Puzzle and k Vertex‑Disjoint Paths Problem Suthee Ruangwises1 · Toshiya Itoh1 Received: 5 May 2020 / Accepted: 6 October 2020 © Ohmsha, Ltd. and Springer Japan KK, part of Springer Nature 2020
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. Keywords Card-based cryptography · Zero-knowledge proof · Numberlink · Puzzle · Vertex-disjoint paths · Graph
Introduction Numberlink is a logic puzzle developed by a Japanese company Nikoli, which is famous for creating many popular logic puzzles including Sudoku, Kakuro, Shikaku, and Hashiwokakero. Recently, the puzzle has become increasingly popular, and a large number of Numberlink mobile apps with different names have been developed [9].
A preliminary version of this paper [21] has appeared in the proceedings of FUN 2021. * Suthee Ruangwises [email protected] Toshiya Itoh [email protected] 1
Department of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan
123
Vol.:(0123456789)
New Generation Computing
4 3
1
2
3 4
2
4 3
1
2
1
2
3 4
1
Fig. 1 An example of a Numberlink puzzle (left) and its solution (right)
A Numberlink puzzle consists of a rectangular grid with some cells containing a number. Each number appears exactly twice in the grid. The objective of this puzzle is to connect every pair of cells with the same number by a path that can go from a cell to its horizontally or vertically adjacent cell. Paths cannot cross or share a cell with one another. In the official rule [19], it is not required that all cells in the grid have to be covered by paths. However, a puzzle is generally considered to be well-designed if it has a unique solution, and all cells are covered by paths in that solution. Suppose that Alice, an expert in Numberlink, created a difficult Numberlink puzzle and challenged her friend Bob to solve it. After several tries, Bob could not solve her puzzle. He then claimed that the puzzle does not have a solution and refused to try it anymore. In order to convince Bob that her puzzle actually has a solution without revealing it to him (which would render the challenge pointless), Alice needs some kind of a zero-knowledge proof. Zero‑Knowledge Proof A zero-knowledge proof is an interactive proof between a prover P an
Data Loading...
