10
$\begingroup$

With a trusted 3rd party, running Secret Santa is easy: The 3rd party labels each person $1,\dotsc,n$, and then randomly chooses a derangement from among all possible derangements of $n$ numbers. Person $i$ will then give a gift to the number in position $i$ of the derangement. The trusted 3rd party is responsible for keeping the derangement secure, and for telling each person whom to give a gift to.

The question is: Is there an algorithm that would allow Secret Santa to be played without a trusted 3rd party?

I thought perhaps a clever use of secret keys and a one way hash function could accomplish it, but I've failed to find an algorithm so far.

So I'm looking for a description of a valid algorithm or a (informal) proof that one does not exist.

EDIT

I believe my problem is different from the possible duplicate. I want a solution that will work for a distributed group of players. That is, you cannot assume the players are in the same room and have the ability to shuffle envelopes or notecards or anything like that.

To make this concrete, a valid solution must work across a group instant messenger or over group emails.

Also, to clarify again, it must be a random derangement and not merely a random n-cycle.

$\endgroup$
3
  • $\begingroup$ @HenningMakholm Please see my edit. If you still believe a solution from the other question can work, please clarify how. Thanks. $\endgroup$
    – Jonah
    Aug 28, 2018 at 4:04
  • $\begingroup$ The comments under the answer makes me wonder: Is it usual in Secret Santa games that everybody may learn who everybody's targets were after the game completes? (They don't really seem to be part of my cultural background). $\endgroup$ Aug 28, 2018 at 14:55
  • $\begingroup$ @HenningMakholm not required, but definitely common ime and i’d argue the most fun part of the game among close friends. you can also try to guess who the giver is for each gift and make “best guesser” a contest. $\endgroup$
    – Jonah
    Aug 28, 2018 at 15:08

3 Answers 3

5
$\begingroup$

How about this:

  1. Everybody generates a random private-public key pair.

  2. Everybody publishes their public key anonymously (see below).

  3. Collaboratively choose a random seed:

    a. Everybody chooses a random seed component.
    b. Everybody publishes a hash of their seed component openly.
    c. Everybody publishes their actual seed component openly.
    d. The seed is the sum of the components published in step (c).

  4. Use seed to derive a derangement of the public keys in a deterministic way. (Everybody can now do this for themselves).

  5. Everybody encrypts their name with their secret santa's public key and publishes the ciphertext.

  6. Everybody tries to decrypt all of the messages from the previous step with their own private key. When one of the decryptions succeed, they've found their target.

This assumes that "encrypting" with a public key uses some randomness to produces a non-deterministic result, so someone who has only the public key cannot tell whether a given cleartext and ciphertext match up or not. (This is a standard property of real public-key protocols, though not of textbook RSA).

The procedure does inherently make the cycle structure of the derangement public. In particular, everybody who is mutually santa with someone will know it. It is probably desirable to restrict oneself to "super-derangements" that don't have any $2$-cycles.

A variant that doesn't reveal the cycle structure, at the cost of not having a hard bound on the running time would be:

  1. Everybody chooses a random number and hashes it to produce a "santa ID".

  2. Everybody publishes their santa ID anonymously.

  3. Collaboratively choose a random seed.

  4. Use the seed to deterministically choose a bijection between santa IDs and target names.

  5. If anyone got themselves as target, complain openly, proving that it is so by revealing the number they hashed to get their ID. Everybody starts over from step 1 with new random numbers for everything. On average, $e$ iterations will be needed before a derangement is found.


Both of the above need a sub-algorithm for publishing things anonymously:

  1. Everybody generates a public-private key pair just for the publication sub-algorithm and publishes the public key.

  2. Everybody selects a random permutation $(K_i)_{1\le i\le n}$ of all the public keys from step 1.

  3. Everybody wraps their message in a series of encryptions: $$ M_0 = \text{the message to publish} \\ M_k = \operatorname{encypt}(K_k, M_{k-1}) \quad\text{for }1\le k\le n $$

  4. Everybody publishes their own $M_n$.

  5. Everybody tries to decrypt all the messages from the previous round. Publish all contents where decryption succeeds.

  6. After repeating the previous step $n$ times, everybody's original messages will be on the table, and nobody knows where any of them comes from (except their own).

A large enough collusion might be able to break the anonymous publishing step by traffic analysis, but if everybody except a few players collude, the game has lost much of its meaning anyway.

$\endgroup$
4
  • $\begingroup$ This is really clever and along the lines of the ideas I was unable to make work. How do you feel about the chances of an algorithm existing that doesn’t reveal cycle structure? $\endgroup$
    – Jonah
    Aug 28, 2018 at 16:25
  • $\begingroup$ Is the publishing algorithm a standard one and does it have a name? Also on 2nd reading I’m a bit unclear on the definition of “encrypt” here and how K is used within it. Could you elaborate? Thanks $\endgroup$
    – Jonah
    Aug 28, 2018 at 16:37
  • $\begingroup$ @Jonah: Edited with a variant that doesn't reveal the cycle structure. The publishing algorithm is more-or-less equivalent to what Tor does, except in one direction only. $\endgroup$ Aug 28, 2018 at 16:44
  • $\begingroup$ Encryption would be something like: Choose a random AES key, and encrypt $M_{k-1}$ with it. Encrypt the random key with the public-key primitive, using the public key $K_k$. Send out the the encrypted $M_{k-1}$ together with the encrypted AES key. $\endgroup$ Aug 28, 2018 at 16:47
4
$\begingroup$

Here's one possible strategy. Number the people $1, 2, \dots, n$. They do the following things, in order. (Whenever someone chooses a random number, I assume it's uniformly random from some fixed range $[1,N]$, say $[1,2n]$, excluding all values they've seen before.)

  1. Person $1$ picks a random number $x_1$ and passes it to person $2$.
  2. Person $2$ picks a random number $x_2$, scrambles the list $(x_1,x_2)$, and passes it to person $3$.
  3. Person $3$ picks a random number $x_3$, scrambles the list $(x_1,x_2,x_3)$, and passes it to person $4$.
  4. And so on, with person $n$ receiving a permutation of the list $(x_1, x_2, \dots, x_{n-1})$.
  5. Person $n$ picks a random number $x_n$, scrambles the list $(x_1, \dots, x_n)$, and passes that to person $1$.
  6. Person $1$ records the position of $x_1$ (that's their secret Santa target), replaces $x_1$ by a new random number $y_1$, and passes the resulting list to person $2$.
  7. Person $2$ records the position of $x_2$ (that's their secret Santa target), replaces $x_2$ by a new random number $y_2$, and passes the resulting list to person $3$.
  8. And so on, until we get to person $n$, whose target is the position of $x_n$.

This does not guarantee that the permutation is a derangement. But everyone can check if they got themselves as a target; if they complain, we can start over. (On average, we'll have to start over $e$ times.)

No information is shared about other people's targets: in steps 1 through 4, person $k$ sees the values $x_1, x_2, \dots, x_{k-1}$, which are not helpful, because in steps 5 through 8, person $k$ is given a permutation of the values $y_1, y_2, \dots, y_{k-1}, x_k, \dots, x_n$: from their perspective, these are uniformly chosen from the complement of $\{x_1,\dots, x_{k-1}\}$.

Another awkward moment, though, is that person $n$ picks the final permutation, so they get to choose their secret Santa target if they cheat and don't do it randomly. However, we can have the other people collaboratively choose a random seed for person $n$ to use (say, they send them numbers $r_1, \dots, r_{n-1}$, and then $r_1 + \dots + r_{n-1}$ has to be the seed) and then this cheating can be exposed after everyone opens their presents.

$\endgroup$
12
  • $\begingroup$ You're not - I missed that. But we can fix this problem (exactly by scrambling, although that causes some awkwardness). $\endgroup$ Aug 28, 2018 at 6:05
  • $\begingroup$ A random seed for scrambling suggests that the scrambling does not take the data into accound, so everybody would be able know where in the list person $n$ ends up. Instead, after person $n$ has deposited a copy of the list for auditing, choose and publish $r_i$s. Then person $n$ sorts the list in order of increasing $\operatorname{HASH}(x_i \Vert \sum_k x_k \Vert r_1 \Vert r_2 \Vert\cdots\Vert r_n)$. $\endgroup$ Aug 28, 2018 at 10:55
  • $\begingroup$ (The sum of $x_k$s is in all of the hashes such that nobody other than person $n$ has enough information to compute the hashes before the audit copy is made public. Otherwise they would get some information from the magnitude of the hashes of people in earlier than them, and gain some probabilistic knowledge of whether one of them is santa for person $1$ and/or $n$). $\endgroup$ Aug 28, 2018 at 10:58
  • $\begingroup$ (Perhaps exclude $r_n$ from the has computation, though. Otherwise person $n$ might be able to delay revealing his $r_n$ until everybody has revealed theirs, and he would then have the opportunity to search for a value that would put him in his desired position in the list). $\endgroup$ Aug 28, 2018 at 11:06
  • 1
    $\begingroup$ @Jonah: Sounds resonable. To protect against collusion between person $n$ and and an accomplice, everybody should wait for everybody's seed hashes to be published before they send their original seed to person $n$. $\endgroup$ Aug 28, 2018 at 14:58
1
$\begingroup$

The following suggestion is only a partial answer since requires information to be passed sequentially from one player to one specific other player, without anyone else receiving this information; e.g. as a chain of mails, without any record of previous mails in the appendix. Therefore it outright fails the concrete requirement of group mails made in the "EDIT" of the OP; but it still suitable for a distributed group of players who must know each other initially at least pairwise along the sequence of passing information, i.e. the address of player $P_k$ be known (only, or at least) to player $P_{k - 1)}$ and the address of player $P_1$ (the initiator of the round of playing the Secret Santa Game) known to player $P_n$.

My suggestion derives from this answer (the first given on this page), by @Misha Lavrov; but it attempts to avoid the "awkward moments" arising there, namely:

  • to prevent the case that some player draws herself as "Secret Santa target" (if the procedure is carried out honestly and correctly by everybody), and

  • as far as a certain procedural step involves a player having a certain choice (which is generally made secretely) then the "Secret Santa target" of this player shall not be determined (depending on the choice made) and mot become known to this player immediately by carrying out this procedureal step. (In other words: a player must not have the opportunity, nor the ensuing moral dilemma, of getting to choose his "Secret Santa target".)

To achieve this, the suggested procedure will make use of

Compatible sets of derangements

For given natural number $n \ge 2$ we have the corresponding non-empty set $\mathcal D_n$ of all derangement permutations of $n$ items.

If $n \ge 3$ then $\mathcal D_n$ has (not necessarily distinct) non-empty subsets $\mathcal S, \mathcal T \subset \mathcal D_n$ which satisfy the following "compatibility condition":

$$ \forall p \in \mathcal S, q \in \mathcal T : (q \circ p) \in \mathcal D_n. \tag{*}.$$

(For $n = 3$, one example is: $$\mathcal S = \mathcal T := \{ ~ \text{(312)} ~ \}.$$ )

If $n \ge 5$ then $\mathcal D_n$ even has subsets $\mathcal S, \mathcal T$ which are compatible in the sense of $(*)$ and which both have more than one element. This will be used to implement "random and secret shuffling". Therefore the following procedure is applicable only for cases $n \ge 5$:

The procedure

The players are identified as $P_1$, $P_2$ through $P_n$, and they shall communicate only from one to the next, in this order, or from $P_n$ to $P_1$.

  1. For the given number $n$ player $P_1$ chooses the two specific compatible derangement subsets $\mathcal S, \mathcal T \subset \mathcal D_n$; both with at least two elements. Set $\mathcal S$ will be explicitly communicated to all players except $P_n$; set $\mathcal T$ may be kept secret by $P_1$, but can perhaps uniquely be determined by those who know set $\mathcal S$.
    Accordingly, set $\mathcal S$ can be passed along up to player $P_{(n - 1)}$ at this initial step already; and all of the instructions specified in the following can be passed and agreed upon by all players outright.

  2. Based on the initial ordered list $\mathcal X_0 \equiv (1, 2, ..., (n - 1), n)$ player $P_1$ chooses and memorizes a real number $x_1$ whose value must be distinct from the values of all entries in $\mathcal X_0$, and replaces the entry of value $1$ (i.e. the first entry of list $\mathcal X_0$) with $x_1$, thereby obtaining the ordered list $\mathcal X_1 \equiv (x_1, 2, ..., (n - 1), n)$.

  3. List $\mathcal X_1$ is passed from player $P_1$ to player $P_2$, who must choose and memorize a real number $x_2$ whose value must be distinct from the values of all entries in $\mathcal X_1$,
    replace the entry of value $2$ (i.e. the second entry of list $\mathcal X_1$) with $x_2$,
    thereby obtaining the ordered list $\mathcal X_2 \equiv (x_1, x_2, ..., (n - 1), n)$.
    And so on, until ...

  4. ... player $P_{(n - 1)}$ obtains (and memorizes) list $\mathcal X_{(n - 1)} \equiv (x_1, x_2, ..., x_{(n - 1)}, n)$. Now:

  5. Player $P_{(n - 1)}$ chooses secretely one derangement $p \in \mathcal S$, applies it to list $\mathcal X_{(n - 1)}$, and passes the resulting list, $p[ ~ X_{(n - 1)} ~ ]$, to player $P_n$.

  6. Player $P_n$ must secretely choose and memorize an encoding $\mathcal C$ which is applicable (invertable) to the set of all (necessarily disinct) values of the entries in list $\mathcal X_{(n - 1)}$, i.e.

$$ \mathcal C : \{ \mathcal X_{(n - 1)} \} \longrightarrow \mathbb R $$

such that the corresponding inverse exists as well:

$$ \exists ~ \mathcal C^{(-1)} : \{ \mathcal C[ ~ \mathcal X_{(n - 1)} ~ ] \} \longrightarrow \{ \mathcal X_{(n - 1)} \}, \qquad \mathcal C^{(-1)}[ ~ \mathcal C[ ~ x ~ ] ~ ] \mapsto x,$$

and such that the encoding is effective:

$$ \{ \mathcal X_{(n - 1)} \} ~ \cup ~ \{ \mathcal C[ ~ \mathcal X_{(n - 1)} ~ ] \} = \emptyset.$$

The result of applying this encoding, entry by entry, i.e. the list $\mathcal C[ ~ p[ ~ X_{(n - 1)} ~ ] ~]$, is passed to player $P_1$.

(The described procedure has guaranteed that the list doesn't contain an entry of value $x_1$ which player $P_1$ would recognize, but only encoded entries.)

  1. Player $P_1$ chooses secretely one derangement $q \in \mathcal T$, applies it to the received list , and passes the resulting list, $q[ ~ \mathcal C[ ~ p[ ~ X_{(n - 1)} ~ ] ~] ~ ]$, is passed to player $P_2$.

  2. Player $P_2$ passes this list unchanged to player $P_3$, and so on, unitl player $P_n$ has received this list.

  3. To this list, player $P_n$ applies the decoding, $\mathcal C^{(-1)}$, entry by entry. The procedure guarantees that the resulting list contains all entries with the exact same values as in list $\mathcal X_{(n - 1)}$, but with a deranged order. Therefore player $P_n$ can recognize the unique entry of value $n$ in this resulting list; the position of this entry (which is guaranteed an integer between $1$ and $n - 1$) identifies the "Secret Santa target" of player $P_n$.
    (If player $P_n$ turns out unhappy with having to come up with a gift for exactly this "Secret Santa target" and therefore considers cheating by applying not only the decoding, $\mathcal C^{(-1)}$, but an additional permutation of the resulting list, by which to place the entry of value $n$ in a preferred position, then he runs a certain risk of being exposed eventually because some other player may subsequently find in consequence being identified as the own "Secret Santa target". This risk should at least discourage such cheating.)
    Finally, player $P_n$ replaces the entry of value $n$ with value $y_n$ (which must be distinct from all present values (which are also those of list $\mathcal X_{(n - 1)}$), thereby constructing list $\mathcal Y_{1}$ which is passed to player $P_1$.

  4. In list $\mathcal Y_{1}$, player $P_1$ can recognize the unique entry of value $x_1$; the position of this entry (which is guaranteed an integer between $2$ and $n$) identifies the "Secret Santa target" of player $P_1$.
    Player $P_1$ replaces the entry of value $x_1$ with value $y_1$ (which must be distinct from all present values, thereby constructing list $\mathcal Y_{2}$ which is passed to player $P_2$.
    (Possible cheating by player $P_1$, namely by applying some additional permutation to this list in order to identify some other _"Secret Santa target" instead of the one found by honestly following the procedure, is again risking exposure and thus discouraged.)
    And so on, until finally player $P_{(n - 1)}$ received list $\mathcal Y_{(n - 1)}$, with the only recognizable entry left the one with value $x_{(n - 1)}$, at the position identifying the "Secret Santa target" of player $P_{(n - 1)}$.

$\endgroup$
1
  • $\begingroup$ Upvoted for creative answer, though has the drawback of being too complicated, especially for non-technical people. $\endgroup$
    – Jonah
    Jan 9 at 23:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .