Skip to Main content Skip to Navigation
Journal articles

Physical Zero-Knowledge Proof and NP-completeness Proof of Suguru Puzzle ⋆

Abstract : Suguru is a paper and pencil puzzle invented by Naoki Inaba. The goal of the game is to fill a grid with numbers between 1 and 5 while respecting three simple constraints. We first prove the NP-completeness of Suguru puzzle. For this we design gadgets to encode the PLANAR-CIRCUIT-SAT in a Suguru grid. We then design a physical Zero-Knowledge Proof (ZKP) protocol for Suguru. This ZKP protocol allows a prover to prove that he knows a solution of a Suguru grid to a verifier without leaking any information on the solution. To construct such a physical ZKP protocol, we only rely on a few physical cards and adapted encoding. For a Suguru grid with n cells, we only use 5n + 5 cards. Moreover, we prove the three classical security properties of a ZKP: completeness, extractability, and zero-knowledge.
Document type :
Journal articles
Complete list of metadata
Contributor : Léo Robert Connect in order to contact the contributor
Submitted on : Tuesday, January 25, 2022 - 1:21:53 PM
Last modification on : Thursday, February 10, 2022 - 3:34:51 AM
Long-term archiving on: : Tuesday, April 26, 2022 - 6:54:28 PM


Files produced by the author(s)



Léo Robert, Daiki Miyahara, Pascal Lafourcade, Luc Libralesso, Takaaki Mizuki. Physical Zero-Knowledge Proof and NP-completeness Proof of Suguru Puzzle ⋆. Information and Computation, Elsevier, In press, ⟨10.1016/j.ic.2021.104858⟩. ⟨hal-03542495⟩



Record views


Files downloads