License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2018.13
URN: urn:nbn:de:0030-drops-88047
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8804/
Go to the corresponding LIPIcs Volume Portal

Bultel, Xavier ; Dreier, Jannik ; Dumas, Jean-Guillaume ; Lafourcade, Pascal

A Cryptographer's Conspiracy Santa

pdf-format:
LIPIcs-FUN-2018-13.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{bultel_et_al:LIPIcs:2018:8804,
  author =	{Xavier Bultel and Jannik Dreier and Jean-Guillaume Dumas and Pascal Lafourcade},
  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 =	{Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8804},
  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}
}

Keywords: Secret Santa, Conspiracy Santa, Secure Multi-Party Computation, Cryptocurrency, Physical Cryptography
Collection: 9th International Conference on Fun with Algorithms (FUN 2018)
Issue Date: 2018
Date of publication: 04.06.2018

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