Search Results

Documents authored by Bultel, Xavier

Document
DOI: 10.4230/LIPIcs.FUN.2022.9
Zero-Knowledge Proof of Knowledge for Peg Solitaire

Authors: Xavier Bultel

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

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.
Cite as

Xavier Bultel. Zero-Knowledge Proof of Knowledge for Peg Solitaire. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 9:1-9:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.FUN.2022.9},
  URN =		{urn:nbn:de:0030-drops-159798},
  doi =		{10.4230/LIPIcs.FUN.2022.9},
  annote =	{Keywords: Zero-Knowledge Proof, Peg Solitaire}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.13
A Cryptographer's Conspiracy Santa

Authors: Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, and Pascal Lafourcade

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
In Conspiracy Santa, a variant of Secret Santa, a group of people offer each other Christmas gifts, where each member of the group receives a gift from the other members of the group. To that end, the members of the group form conspiracies, to decide on appropriate gifts, and usually divide the cost of each gift among all participants of that conspiracy. This requires to settle the shared expenses per conspiracy, so Conspiracy Santa can actually be seen as an aggregation of several shared expenses problems. First, we show that the problem of finding a minimal number of transaction when settling shared expenses is NP-complete. Still, there exists good greedy approximations. Second, we present a greedy distributed secure solution to Conspiracy Santa. This solution allows a group of people to share the expenses for the gifts in such a way that no participant learns the price of his gift, but at the same time notably reduces the number of transactions with respect to a naive aggregation. Furthermore, our solution does not require a trusted third party, and can either be implemented physically (the participants are in the same room and exchange money using envelopes) or, virtually, using a cryptocurrency.
Cite as

Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, and Pascal Lafourcade. A Cryptographer's Conspiracy Santa. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 13:1-13:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bultel_et_al:LIPIcs.FUN.2018.13,
  author =	{Bultel, Xavier and Dreier, Jannik and Dumas, Jean-Guillaume and Lafourcade, Pascal},
  title =	{{A Cryptographer's Conspiracy Santa}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.13},
  URN =		{urn:nbn:de:0030-drops-88047},
  doi =		{10.4230/LIPIcs.FUN.2018.13},
  annote =	{Keywords: Secret Santa, Conspiracy Santa, Secure Multi-Party Computation, Cryptocurrency, Physical Cryptography}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.8
Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and KenKen

Authors: Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, and Pascal Lafourcade

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a grid has to be filled with 0's and 1's, while respecting certain constraints. In Kakuro a grid has to be filled with numbers such that the sums per row and column match given values; similarly in KenKen a grid has to be filled with numbers such that in given areas the product, sum, difference or quotient equals a given value. We give physical algorithms to realize zero-knowledge proofs for these games which allow a player to show that he knows a solution without revealing it. These interactive proofs can be realized with simple office material as they only rely on cards and envelopes. Moreover, we formalize our algorithms and prove their security.
Cite as

Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas, and Pascal Lafourcade. Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and KenKen. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 8:1-8:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bultel_et_al:LIPIcs.FUN.2016.8,
  author =	{Bultel, Xavier and Dreier, Jannik and Dumas, Jean-Guillaume and Lafourcade, Pascal},
  title =	{{Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and  KenKen}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.8},
  URN =		{urn:nbn:de:0030-drops-58693},
  doi =		{10.4230/LIPIcs.FUN.2016.8},
  annote =	{Keywords: Physical Cryptography, ZKP, Games, Akari, Kakuro, KenKen, Takuzu}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact