2026-07-24T03:13:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15979 2024-03-06T10:56:59Z ddc:004 open_access

Zero-Knowledge Proof of Knowledge for Peg Solitaire Bultel, Xavier Zero-Knowledge Proof Peg Solitaire 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xavier Bultel 2022 Is Part Of LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2022.9 urn:nbn:de:0030-drops-159798 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.9 eng https://creativecommons.org/licenses/by/4.0/legalcode