DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2026.35

Card-Based ZKP Protocols for Connectivity-Based Puzzles: Extending to Tree Structures with Application to Nurimeizu

Authors: Daiki Miyahara, Pascal Lafourcade, and Maxime Puys

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

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.

Cite as

Daiki Miyahara, Pascal Lafourcade, and Maxime Puys. Card-Based ZKP Protocols for Connectivity-Based Puzzles: Extending to Tree Structures with Application to Nurimeizu. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{miyahara_et_al:LIPIcs.FUN.2026.35,
  author =	{Miyahara, Daiki and Lafourcade, Pascal and Puys, Maxime},
  title =	{{Card-Based ZKP Protocols for Connectivity-Based Puzzles: Extending to Tree Structures with Application to Nurimeizu}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{35:1--35:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.35},
  URN =		{urn:nbn:de:0030-drops-257547},
  doi =		{10.4230/LIPIcs.FUN.2026.35},
  annote =	{Keywords: Card-based cryptography, Nurimeizu, Nikoli, ZKP}
}

Search Results

Documents authored by Puys, Maxime

Card-Based ZKP Protocols for Connectivity-Based Puzzles: Extending to Tree Structures with Application to Nurimeizu

Abstract

Cite as

Thanks for your feedback!

Could not send message