论文标题
更快的密码学家的阴谋圣诞老人
A Faster Cryptographer's Conspiracy Santa
论文作者
论文摘要
在Secret Santa的一种串谋圣诞老人中，一群人互相提供圣诞节礼物，该小组的每个成员都从小组的其他成员那里收到礼物。为此，小组成员形成阴谋，决定适当的礼物，并通常将每个礼物的成本分配给该阴谋的所有参与者。这需要解决每个阴谋的共同费用，因此阴谋圣诞老人实际上可以看作是几个共享费用问题的汇总。首先，我们表明，在Setting共享费用确定时，找到最小数量的交易数量的问题是NP完成。尽管如此，仍然存在良好的贪婪近似值。其次，我们为阴谋圣诞老人提供了贪婪的分布式解决方案。该解决方案允许一群n人分享礼物的费用，以至于没有参与者了解他的礼物价格，但同时尤其将交易数量减少到2 $ \ times $ n + 1，相对于na { ^ ation n $ \ \ \ \ \ \ \ \ \ \ \ \ \ times $（n- 2）。此外，我们的解决方案不需要值得信赖的第三方，并且可以进行身体实施（参与者在同一房间里，并使用信封交换资金），或者通过互联网使用加密货币。
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 $\times$ n + 1 with respect to a na{ï}ve aggregation of n $\times$ (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.
