Is there a protocol for conducting a Secret Santa without a central authority? Precisely, we want to sample uniformly a permutation that has no one-cycles and reveal to each member his or her successor without revealing any other part of the permutation. Alternatively, we can uniformly sample an $n$-cycle, where $n$ is the number of participants in the Secret Santa.
2
-
4$\begingroup$ rodrigosetti.com/cryptography/cryptographic-secret-santa $\endgroup$– Carlo BeenakkerCommented Dec 18, 2017 at 20:39
-
$\begingroup$ This is precisely what I wanted! I have a followup question. Is there a protocol that doesn't rely on encryption? Preferably one that could be used in person without a computer, like the protocol for secure addition. $\endgroup$– VodkaCommented Dec 18, 2017 at 20:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Cryptographic Protocols with Everyday Objects (section 5)
Typical cryptographic Secret Santa protocols require a fully homomorphic encryption system. These protocols are thus suitable for those with some planning, some expertise and access to computational assistance, but not to a group of friends without access to computers. Here we present an alternative solution, which does not lower the security requirements, and does not require anything beyond card, envelopes and pens.
answered Dec 18, 2017 at 21:04
-
$\begingroup$ math.stackexchange.com/a/1054676/30836 gives an equivalent protocol which may be physically slicker. $\endgroup$– MicahCommented Dec 18, 2017 at 21:51
-
1$\begingroup$ @Micah: Personally, I find the envelope-based solution quite a bit more practical than anything that involves cutting up cards and stapling them together (not to mention trying to shuffle the stapled-up cards). But I guess that's a matter of taste. $\endgroup$ Commented Dec 18, 2017 at 22:10