Search Results

Documents authored by Miyahara, Daiki

Document
DOI: 10.4230/LIPIcs.FUN.2026.33
When Locality Implies Globality: Card-Based ZKP Protocol for Shakashaka Puzzle

Authors: Daiki Miyahara, Léo Robert, Pascal Lafourcade, and Shohei Kaneko

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

Abstract
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.
Cite as

Daiki Miyahara, Léo Robert, Pascal Lafourcade, and Shohei Kaneko. When Locality Implies Globality: Card-Based ZKP Protocol for Shakashaka Puzzle. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{miyahara_et_al:LIPIcs.FUN.2026.33,
  author =	{Miyahara, Daiki and Robert, L\'{e}o and Lafourcade, Pascal and Kaneko, Shohei},
  title =	{{When Locality Implies Globality: Card-Based ZKP Protocol for Shakashaka Puzzle}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{33:1--33:16},
  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.33},
  URN =		{urn:nbn:de:0030-drops-257525},
  doi =		{10.4230/LIPIcs.FUN.2026.33},
  annote =	{Keywords: Card-based cryptography, ShakaShaka, Nikoli, ZKP}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.34
Playing President with Virtual Players: How to Play Multiple Cards of a Kind

Authors: Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki, and Kazumasa Shinagawa

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

Abstract
President is a popular card game in which players may play one to four cards of the same rank. Since it is less enjoyable with too few human players, to address this, we study the player-simulation problem for President: realizing the moves of a virtual player while keeping its hand hidden. We propose a selection protocol, which selects multiple cards of the same rank uniformly at random from a hidden virtual player’s hand, whose rank exceeds the latest played cards. Our construction reduces the task to secure sorting, so the overall efficiency is dominated by the underlying sorting protocol. To address this bottleneck, we design an efficient sorting protocol, which reduces the number of steps from O(m log m) to O(m), compared to the existing sorting protocols.
Cite as

Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki, and Kazumasa Shinagawa. Playing President with Virtual Players: How to Play Multiple Cards of a Kind. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{miyahara_et_al:LIPIcs.FUN.2026.34,
  author =	{Miyahara, Daiki and Lafourcade, Pascal and Mizuki, Takaaki and Shinagawa, Kazumasa},
  title =	{{Playing President with Virtual Players: How to Play Multiple Cards of a Kind}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{34:1--34:15},
  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.34},
  URN =		{urn:nbn:de:0030-drops-257535},
  doi =		{10.4230/LIPIcs.FUN.2026.34},
  annote =	{Keywords: Card-Based Cryptography, Player-Simulation Problem, President}
}
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}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.20
Card-Based ZKP Protocols for Takuzu and Juosan

Authors: Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, and Hideaki Sone

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0’s and 1’s under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.
Cite as

Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, and Hideaki Sone. Card-Based ZKP Protocols for Takuzu and Juosan. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{miyahara_et_al:LIPIcs.FUN.2021.20,
  author =	{Miyahara, Daiki and Robert, L\'{e}o and Lafourcade, Pascal and Takeshige, So and Mizuki, Takaaki and Shinagawa, Kazumasa and Nagao, Atsuki and Sone, Hideaki},
  title =	{{Card-Based ZKP Protocols for Takuzu and Juosan}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{20:1--20:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.20},
  URN =		{urn:nbn:de:0030-drops-127817},
  doi =		{10.4230/LIPIcs.FUN.2021.20},
  annote =	{Keywords: Zero-knowledge proof, Card-based cryptography, Takuzu, Juosan}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact