Skip to Main content Skip to Navigation
Conference papers

Interactive Physical ZKP for Connectivity: Applications to Nurikabe and Hitori

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.
Document type :
Conference papers
Complete list of metadata

https://hal.uca.fr/hal-03209911
Contributor : Léo Robert <>
Submitted on : Tuesday, April 27, 2021 - 3:25:29 PM
Last modification on : Wednesday, May 5, 2021 - 10:05:14 AM

File

main_long.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03209911, version 1

Collections

Citation

Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki. Interactive Physical ZKP for Connectivity: Applications to Nurikabe and Hitori. CiE, Jul 2021, à distance, Belgium. ⟨hal-03209911⟩

Share

Metrics

Record views

50

Files downloads

20