Secret Santa Protocols

Some friends and I are kicking off the holiday season early this year! Along with Jason Kealey and Etienne Tremblay of LavaBlast Software, as well as their better halves, I've arranged to rent a rather nice cottage in mid-December. We decided to hold a Secret Santa gift exchange over there, which brings us to this post.

How do you arrange a randomly-assigned Secret Santa event when the participants are geographically distributed?

Assignment of giver/recipient pairs is usually handled by drawing strips of paper from a hat, an approach that obviously won't work here, when planning over email. So I started to think about how one could do this without relying on a trusted third-party. Is it possible for a group of peers, communicating only through email, to each choose a random recipient and guarantee uniqueness of picks, while ensuring picks are not revealed to others, and no one ends up picking themselves? [My father, over dinner the other day, helpfully pointed out that this is known as a derangement problem.]

The real-world pragmatic approach

We ended up going with the very pragmatic approach of relying on a trusted third-party (in this case a simple computer program). I wrote a Java program that took the list (L) of 5 email addresses, shuffled it (using Collections.shuffle()), then sent an email to address L[i] containing address L[(i+1) % 5], all without printing to the screen what it was doing, or logging anything. Once the program exited, there was no way for anyone to recover who got what address, and it guarantees that the final assignment is a derangement: no person in the initial list gets themselves.

Now, this is all well and good, but it's a boring solution because of its reliance on software. Is this doable with only five people talking over email? (Yes, it's a mostly academic exercise.) I've had some ideas that go in the right direction, but haven't solved the problem of ensuring the final mapping is a derangement, other than running the process for multiple rounds, until no one declares they received themselves as an assignment.

Primitive: mapping IDs to gift recipients

The first primitive our protocol needs is a method of mapping an abstract identifier (say, a number) to an actual name. This is because since participants need to pick one of the 5 identifiers unsupervised, they must not know in advance which person this identifier will represent.

This is the easy part: have everyone pick a unique value i from the pool of identifiers [0-4] (randomly or not) and remember it without disclosing it. Your assigned name is then L[(i+d) % 5], where d is the integer part of the TSX composite index at market close the following day. The offset value d is the same for everyone, is not known in advance, and when we all exchange gifts we can audit that no one cheated and changed their chosen ID after knowing d.

Independently choosing IDs

The above relies on everyone having independently picked a unique value for i, and this is where things get interesting.

• There are 3125 [5^5] sets of picks when done independently with no knowledge of the others.
• Of those, only 120 [5!] contain unique, unduplicated, choices, or 3.84%.
• Of those, only 44 are derangements, where no one ends up with themselves (1.408% of the total)

First approach: anonymous broadcast

If a means of anonymously broadcasting a message to the whole list is available, we can rapidly constrain picks to the 120 cases where there are no duplicates. We'll then have a 36.7% chance [44/120] of having a derangement in each round, so we should be able to settle on a solution in very few rounds.

• We declare the round started, and the pool of legal choices to be {0, 1, 2, 3, 4}.
• Everyone picks a random delay d in [0; 3599] (with 5 participants, collisions are unlikely).
• After d seconds, pick a value in the pool of legal choices, and anonymously broadcast "n has been picked", everyone removes n from the pool. (You can also just always choose the first available number, that works equally well.)

Second approach: no anonymous broadcast

OK, so you don't have an anonymous remailer. No problem!

I've devised a method to ensure the picks are independent, but it can take many rounds to work, as the expected success rate is only 120/3125. (And after that you still have the problem of restarting if you don't have a derangement.)

I think the following should work, but YMMV, I haven't proven it:

• We publish the list of 5 participants. Their order is unimportant.

• We publish 5 IDs. Let's use 5 prime numbers {3, 5, 7, 11, 13}. I don't think they need to be prime, but they must be picked to ensure that their product, known by all (in this case, P=15015) can only be achieved if you pick EXACTLY one of each number, and this is easy to ensure if you take primes [I think].

• Everyone independently picks an ID i from the list, keeping it secret.

• I'm first on the list. I choose a random large integer s. I compute P' = i * s * P.

• I hand off this product (P') to the second person on the list. The number she receives from me is evenly divisible by 3, 5, 7, 11, 13 and P, so she has no way of knowing what my chosen i is, or what value of s I picked (there are 5 equiprobable possible values for s, which tells her nothing).

• She multiplies P' by her own chosen i, and gives that to the third person on the list, and so on.

• The list wraps around and I'm sent a value from the 5th person on the list. If everyone picked a unique value for i, I get s * i0 * i1 * i2 * i3 * i4 * P or, succinctly, s * P². If I get anything else, then I know there's a duplicate.

• I announce whether or not there was a duplicate. (I, or anyone else, can always lie, but then when gifts are exchanged we'd know someone lied - in the spirit of the holidays, the participants in this protocol are honest.)

Phew. Each round has a 1.408% chance of working, so it could take a while. I have yet to find a much better approach, so I think our little 30-line Java program was appropriate in this situation.