Secret Santa algorithm that does not rely on a trusted 3rd party?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

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

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

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

10. 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)}$.