License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.9
URN: urn:nbn:de:0030-drops-159798
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15979/
Go to the corresponding LIPIcs Volume Portal

Bultel, Xavier

Zero-Knowledge Proof of Knowledge for Peg Solitaire

pdf-format:
LIPIcs-FUN-2022-9.pdf (0.8 MB)

Abstract

Peg solitaire is a very popular traditional single-player board game, known to be NP-complete. In this paper, we present a zero-knowledge proof of knowledge for solutions of peg solitaire instances. Our proof is straightforward, in the sense that it does not use any reduction to another NP-complete problem, and uses the standard design of sigma protocols. Our construction relies on cryptographic commitments, which can be replaced by envelopes to make the protocol physical. As a side contribution, we introduce the notion of isomorphisms for peg solitaire, which is the key tool of our protocol.

BibTeX - Entry

@InProceedings{bultel:LIPIcs.FUN.2022.9,
  author =	{Bultel, Xavier},
  title =	{{Zero-Knowledge Proof of Knowledge for Peg Solitaire}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{9:1--9:17},
  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/opus/volltexte/2022/15979},
  URN =		{urn:nbn:de:0030-drops-159798},
  doi =		{10.4230/LIPIcs.FUN.2022.9},
  annote =	{Keywords: Zero-Knowledge Proof, Peg Solitaire}
}

Keywords: Zero-Knowledge Proof, Peg Solitaire
Collection: 11th International Conference on Fun with Algorithms (FUN 2022)
Issue Date: 2022
Date of publication: 23.05.2022

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