2026-07-22T20:50:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25754 2026-05-15T05:43:01Z ddc:004 open_access

Card-Based ZKP Protocols for Connectivity-Based Puzzles: Extending to Tree Structures with Application to Nurimeizu Miyahara, Daiki Lafourcade, Pascal Puys, Maxime Card-based cryptography Nurimeizu Nikoli ZKP Card-based zero-knowledge proof (ZKP) protocols allow a prover to convince a verifier that it knows a witness of a given statement, without revealing any information, using a physical deck of playing cards. Previous studies have focused on puzzles with a specific connected component, such as a simple cycle and a polyomino. In this study, we propose a unified approach to handle a family of connected components, including a tree, path, cycle, and polyomino. This approach achieves this verification in O(mn) steps relative to a given grid size m × n. Using this approach, we construct a card-based ZKP protocol for Nurimeizu, where the goal is to find the shortest path on a given grid. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daiki Miyahara and Pascal Lafourcade and Maxime Puys 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.35 urn:nbn:de:0030-drops-257547 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.35 eng https://creativecommons.org/licenses/by/4.0/legalcode