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
- Draw random names
- Keeping the first valid assignment
- 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.