2026-09-22T21:02:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25752 2026-09-05T19:26:05Z ddc:004 open_access

When Locality Implies Globality: Card-Based ZKP Protocol for Shakashaka Puzzle Miyahara, Daiki Robert, Léo Lafourcade, Pascal Kaneko, Shohei Card-based cryptography ShakaShaka Nikoli ZKP Shakashaka is an NP-complete Nikoli puzzle that requires to draw white rectangles by filling a grid with black triangles. Verifying that there are only rectangles drawn in the solution was an open problem for card-based ZKP protocols designers. In this paper, we construct a card-based ZKP protocol to show that a prover can prove to a verifier that he knows a solution of this puzzle without revealing any information. For doing this we prove a local property on all possible 2 × 2 subgrids drawn according to the rules of the game and such configurations are possible valid shapes for rectangles. This local property implies a global property on the shape of the constructed areas. Thanks to this local result for all 2 × 2 subgrids, we are able to establish that the only possible shape in the global grid are rectangles. We also verify other classical rules of Shakashaka. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daiki Miyahara and Léo Robert and Pascal Lafourcade and Shohei Kaneko 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.33 urn:nbn:de:0030-drops-257525 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.33 eng https://creativecommons.org/licenses/by/4.0/legalcode