2 Search Results for "Ruangwises, Suthee"

Document
DOI: 10.4230/LIPIcs.FUN.2022.24
How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku

Authors: Suthee Ruangwises and Toshiya Itoh

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.
Cite as

Suthee Ruangwises and Toshiya Itoh. How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ruangwises_et_al:LIPIcs.FUN.2022.24,
  author =	{Ruangwises, Suthee and Itoh, Toshiya},
  title =	{{How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{24:1--24:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.24},
  URN =		{urn:nbn:de:0030-drops-159947},
  doi =		{10.4230/LIPIcs.FUN.2022.24},
  annote =	{Keywords: Zero-knowledge proof, Card-based cryptography, Shikaku, Puzzles, Games}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.22
Physical Zero-Knowledge Proof for Numberlink

Authors: Suthee Ruangwises and Toshiya Itoh

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

Abstract
Numberlink is a logic puzzle for which the player has to connect all pairs of cells with the same numbers by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a player to physically show that he/she knows a solution without revealing it. In particular, we develop a physical protocol to count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Our protocol can also be applied to verify the existence of vertex-disjoint paths connecting all given pairs of endpoints in any undirected graph.
Cite as

Suthee Ruangwises and Toshiya Itoh. Physical Zero-Knowledge Proof for Numberlink. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 22:1-22:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ruangwises_et_al:LIPIcs.FUN.2021.22,
  author =	{Ruangwises, Suthee and Itoh, Toshiya},
  title =	{{Physical Zero-Knowledge Proof for Numberlink}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{22:1--22:11},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.22},
  URN =		{urn:nbn:de:0030-drops-127836},
  doi =		{10.4230/LIPIcs.FUN.2021.22},
  annote =	{Keywords: Zero-knowledge proof, Card-based cryptography, Numberlink, Puzzles, Games}
}
  • Refine by Author
  • 2 Itoh, Toshiya
  • 2 Ruangwises, Suthee

  • Refine by Classification
  • 2 Security and privacy → Information-theoretic techniques
  • 2 Theory of computation → Cryptographic protocols

  • Refine by Keyword
  • 2 Card-based cryptography
  • 2 Games
  • 2 Puzzles
  • 2 Zero-knowledge proof
  • 1 Numberlink
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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