Verifiable, Distributed Secret Santa Assignments

Question

My family was planning a secret santa and I thought about how I might write a little web app to dole out these secret assignments. But the downsides to this approach are obvious: there's no way for the users to know that I'm a) generating the results randomly and b) not snooping on the (secret) assignments myself.

In the real secret santa, there's no central authority giving out pieces of the assignment. Rather, there's a process by which each user draws names out of a hat and is trusted to redraw if they pick up a name violating one of the constraints (themselves or sometimes a spouse). While drawing, each user is trusted/observed to not be peeking into the hat and only redrawing under invalid conditions.

So my question is: under a message-passing framework, what scheme requires the minimal amount of trust, but produces a valid game where nobody knows the other assignments?

The closest I've been able to achieve is a ring system where a arbitrary starting client draws a random, valid assignment for themselves and then sends that assignment to the next one in the ring. Then this user randomly draws a valid assignment which is not in conflict with the previous assignment, ORs those two together and then sends it off to the next client. This could be repeated until a valid total assignment is generated (some assignments become invalid towards the end eg: the user at the end receives only one name: their own).

This is pretty sub-optimal though as the first and last assignments can be computed by the second and second-to-last users respectively. In addition, each user must be trusted to

1. Draw random names
2. Keeping the first valid assignment
3. OR-ing their assignment with the previous assignments and sending it off

I'd say the 2nd and 3rd are shared with the physical game (you're trusted not to throw multiple names in, take multiple names out etc...) but it's the 1st condition which I can't seem to eliminate (or verify).

Forgive me if this is a silly question, but I had fun pondering this while laying in bed for a few minutes and wondered if someone else might have any insights.

Thanks!

Answer 1

Reform the problem. Instead of each participant picking their givee (which they give to), have them select a giver (which they receive from).

1. Each participant randomly generates a number (appropriately large) and anonymously submits it (e.g., via the tor network) to the site. This number represents them as giver.
2. After all participants have entered, the site publishes the list and participants (1 at a time, in no particular order) select (and remove) a random number from the list, linking it with their public name as a recipient to the giver-id.
3. After all participants have selected a giver-id for themselves, the validity criteria is evaluated: Each participant observes the specific co-participants with whom they conflict (i.e. immediate family members). If a conflicting co-participant possesses the observer's giver-id, that observer anonymously (via same channel as in step 1) registers a conflict.
4. 1. If no conflicts occur, each participant now knows to whom a gift should be given: the co-participant possessing their giver-id.
   2. If one or more conflicts occur, start over at step 2 with the restriction that participants cannot chose the same giver-id as before.
   3. If all combinations are exhausted, start over at step 1 by re-choosing giver-ids.

The probability of success and/or expected iteration count is left as an exercise for the reader.