Creative Commons Attribution 4.0 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/
Bultel, Xavier
Zero-Knowledge Proof of Knowledge for Peg Solitaire
| pdf-format: |
|
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 | |
| Seminar: | 11th International Conference on Fun with Algorithms (FUN 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 23.05.2022 |
