8
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ toc.csail.mit.edu/node/145 $\;$ $\endgroup$ – user991 Nov 13 '14 at 3:48
  • $\begingroup$ Wow, so it certainly seems theoretically possible, although now I'm really curious HOW. $\endgroup$ – JKnight Nov 13 '14 at 4:34
  • $\begingroup$ +1 festive question :) Funny enough, this makes me think about domain parameter generation for Elliptic Curves... $\endgroup$ – Maarten Bodewes Nov 13 '14 at 14:46
  • $\begingroup$ I could think of a few mathematical solutions, but none would be verifiable by my family. I'm not sure how well educated your family is, but mine would consider it some kind of magic. In the end you'll have to trust the web interface. This is why I don't play poker online (and if I ever do, I'll make sure I'll be the "dealer"). $\endgroup$ – Maarten Bodewes Nov 13 '14 at 14:54
  • $\begingroup$ I'm okay with mathematical solutions that wouldn't necessarily be understandable/computable by my family members. I'm mostly interested in an approach that COULD be verified either by code in their client or if they spent a few years studying. After all, when's the last time any of us checked a TLS cert by hand? $\endgroup$ – JKnight Nov 13 '14 at 17:48
2
$\begingroup$

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.
    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.

$\endgroup$
  • $\begingroup$ I'm not sure I understand all of it, but wouldn't this still allow the central server to know the entire mapping? $\endgroup$ – JKnight Nov 13 '14 at 20:12
  • $\begingroup$ Not explicitly. The anonymous giver-id is only ever known by the giver themselves, they never reveal it. If connecting via a non-identified channel initially, the server has no information about the giver with a given id. $\endgroup$ – Mark Nov 13 '14 at 21:18
  • $\begingroup$ Ahh I see: The mapping from giver-ID->giftee-name is known to all, and the constraints are checked by each giver individually. So this solution requires an anonymous link to the server, and condition 2 in the question (clients could fake conflicts until they get the giftee they wanted). Cool. Now is there a way to do this without a central coordinator? ;) $\endgroup$ – JKnight Nov 13 '14 at 21:29
  • $\begingroup$ Instead of using a website, you could use a hat. Each person generates a random number and puts it in a hat. Go round a circle and each pick a number out of the hat. Reveal the number. You give to the person who has your number. To make sure no-one has their own number, each person writes on a piece of paper: X means they have their own number, O means they don't. Put the papers in the hat, shake the hat around, then reveal. If it's all O's you are good to go. If there are any X's you start again. $\endgroup$ – danxinnoble Mar 14 '17 at 2:23

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.