DROPS

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.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.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}
}

Search Results

Documents authored by Ruangwises, Suthee

How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku

Abstract

Cite as

Physical Zero-Knowledge Proof for Numberlink

Abstract

Cite as

Thanks for your feedback!

Could not send message