DROPS

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}
}

Document

DOI: 10.4230/DagSemProc.06271.3

Adaptive Triangular System Solving

Authors: Jean-Guillaume Dumas, Clément Pernet, and Jean-Louis Roch

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract

Large-scale applications and software systems are getting increasingly complex. To deal with this complexity, those systems must manage themselves in accordance with high-level guidance from humans. Adaptive and hybrid algorithms enable this self-management of resources and structured inputs. In this talk, we first propose a classification of the different notions of adaptivity. For us, an algorithm is adaptive (or a poly-algorithm) when there is a choice at a high level between at least two distinct algorithms, each of which could solve the same problem. The choice is strategic, not tactical. It is motivated by an increase of the performance of the execution, depending on both input/output data and computing resources. Then we propose a new adaptive algorithm for the exact simultaneous resolution of several triangular systems over finite fields. The resolution of such systems is e.g. one of the two main operations in block Gaussian elimination. For solving triangular systems over finite fields, the block algorithm reduces to matrix multiplication and achieves the best known algebraic complexity. Exact matrix multiplication, together with matrix factorizations, over finite fields can now be performed at the speed of the highly optimized numerical BLAS routines. This has been established by the FFLAS and FFPACK libraries. In this talk we propose several practicable variants solving these systems: a pure recursive version, a reduction to the numerical dtrsm routine and a delaying of the modulus operation. Then a cascading scheme is proposed to merge these variants into an adaptive sequential algorithm. We then propose a parallelization of this resolution. The adaptive sequential algorithm is not the best parallel algorithm since its recursion induces a dependancy. A better parallel algorithm would be to first invert the matrix and then to multiply this inverse by the right hand side. Unfortunately the latter requires more total operations than the adaptive algorithm. We thus propose a coupling of the sequential algorithm and of the parallel one in order to get the best performances on any number of processors. The resulting cascading is then an adaptation to resources. This shows that the same process has been used both for adaptation to data and to resources. We thus propose a generic framework for the automatic adaptation of algorithms using recursive cascading.

Cite as

Jean-Guillaume Dumas, Clément Pernet, and Jean-Louis Roch. Adaptive Triangular System Solving. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{dumas_et_al:DagSemProc.06271.3,
  author =	{Dumas, Jean-Guillaume and Pernet, Cl\'{e}ment and Roch, Jean-Louis},
  title =	{{Adaptive Triangular System Solving}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.3},
  URN =		{urn:nbn:de:0030-drops-7704},
  doi =		{10.4230/DagSemProc.06271.3},
  annote =	{Keywords: Adaptive and hybrid algorithms; triangular system solving; parallel and sequential degenerations}
}

Search Results

Documents authored by Dumas, Jean-Guillaume

A Cryptographer's Conspiracy Santa

Abstract

Cite as

Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and KenKen

Abstract

Cite as

Adaptive Triangular System Solving

Abstract

Cite as

Thanks for your feedback!

Could not send message