Interactive Physical ZKP for Connectivity: Applications to Nurikabe and Hitori - Université Clermont Auvergne Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Interactive Physical ZKP for Connectivity: Applications to Nurikabe and Hitori

Résumé

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.
Fichier principal
Vignette du fichier
main_long.pdf (411.95 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03209911 , version 1 (27-04-2021)

Identifiants

  • HAL Id : hal-03209911 , version 1

Citer

Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki. Interactive Physical ZKP for Connectivity: Applications to Nurikabe and Hitori. Computability in Europe: Logic and Theory of Algorithms, Jul 2021, à distance, Belgium. ⟨hal-03209911⟩
100 Consultations
169 Téléchargements

Partager

Gmail Facebook X LinkedIn More