10
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ rodrigosetti.com/cryptography/cryptographic-secret-santa $\endgroup$ – Carlo Beenakker Dec 18 '17 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$ – Vodka Dec 18 '17 at 20:46
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ math.stackexchange.com/a/1054676/30836 gives an equivalent protocol which may be physically slicker. $\endgroup$ – Micah Dec 18 '17 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$ – Ilmari Karonen Dec 18 '17 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.