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$
2
  • 4
    $\begingroup$ rodrigosetti.com/cryptography/cryptographic-secret-santa $\endgroup$ 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$
    – Vodka
    Dec 18, 2017 at 20:46

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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