A faster cryptographer's Conspiracy Santa

DOI10.1016/J.TCS.2020.05.034zbMATH Open1453.68081arXiv2005.09244OpenAlexW3027400537MaRDI QIDQ2196567FDOQ2196567

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

Publication date: 3 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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 exist good greedy approximations. Second, we present a greedy distributed secure solution to Conspiracy Santa. This solution allows a group of n 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 to 2 $imes$ n + 1 with respect to a na{"i}ve aggregation of n $imes$ (n -- 2). 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, over Internet, using a cryptocurrency.

Full work available at URL: https://arxiv.org/abs/2005.09244

Recommendations

• A cryptographer's Conspiracy Santa
• scientific article; zbMATH DE number 1304128
• Faster Luby-Rackoff ciphers
• Crypto Santa
• Towards faster cryptosystem. II
• Towards faster cryptosystem. I
• Faster fully homomorphic encryption
• Another twist in the dining cryptographers' protocol

zbMATH Keywords

Secret Santasecure multi-party computationcryptocurrencyformal security modelsConspiracy Santaphysical cryptographyprivacy-preserving protocolssharing expenses

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cooperative games (91A12) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Privacy of data (68P27) Algorithmic game theory and complexity (91A68)

Cites Work

• Introduction to algorithms
• Title not available (Why is that?)
• The dining cryptographers problem: Unconditional sender and recipient untraceability
• Reducibility among combinatorial problems
• A cryptographer's Conspiracy Santa

Cited In (3)

• Crypto Santa
• The Secret Santa Problem
• A cryptographer's Conspiracy Santa

This page was built for publication: A faster cryptographer's Conspiracy Santa

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196567)