Interactive physical ZKP for connectivity: applications to Nurikabe and Hitori
Conference on Computability in Europe, 2021•Springer
During the last years, many Physical Zero-knowledge Proof (ZKP) protocols for Nikoli's
puzzles have been designed. In this paper, we propose two ZKP protocols for the two
Nikoli's puzzles called Nurikabe and Hitori. These two puzzles have some similarities, since
in their rules at least one condition requires that some cells are connected to each other,
horizontally or vertically. The novelty in this paper is to propose two techniques that allow us
to prove such connectivity without leaking any information about a solution.
puzzles have been designed. In this paper, we propose two ZKP protocols for the two
Nikoli's puzzles called Nurikabe and Hitori. These two puzzles have some similarities, since
in their rules at least one condition requires that some cells are connected to each other,
horizontally or vertically. The novelty in this paper is to propose two techniques that allow us
to prove such connectivity without leaking any information about a solution.
Abstract
During the last years, many Physical Zero-knowledge Proof (ZKP) protocols for Nikoli’s puzzles have been designed. In this paper, we propose two ZKP protocols for the two Nikoli’s puzzles called Nurikabe and Hitori. These two puzzles have some similarities, since in their rules at least one condition requires that some cells are connected to each other, horizontally or vertically. The novelty in this paper is to propose two techniques that allow us to prove such connectivity without leaking any information about a solution.
Springer