License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2021.22
URN: urn:nbn:de:0030-drops-127836
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12783/
Go to the corresponding LIPIcs Volume Portal

Ruangwises, Suthee ; Itoh, Toshiya

Physical Zero-Knowledge Proof for Numberlink

pdf-format:
LIPIcs-FUN-2021-22.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{ruangwises_et_al:LIPIcs:2020:12783,
  author =	{Suthee Ruangwises and Toshiya Itoh},
  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 =	{Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12783},
  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}
}

Keywords: Zero-knowledge proof, Card-based cryptography, Numberlink, Puzzles, Games
Collection: 10th International Conference on Fun with Algorithms (FUN 2021)
Issue Date: 2020
Date of publication: 16.09.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI