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

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 2

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

Answer 4

Yes there is. I've been puzzeling over this one for years and after reading the answers her I think I've figured it out.

The approach involves two steps like @hmalcom left over monica's work above, and depends on a couple of primitives that we'll assume exist as well as a public communication channel.

Primitives

random number selection.

The goal is for each person to contribute randomness but in a way that cannot be manipulated to their benefit later.

First each person generates a random number, Second, they compute a cryptographic hash of that number and post the hash publicly. Later, then the random number is required, each person posts the underlying random number and participants validate that the random numbers do generate the hashes posted earlier. Any thay don't match are discarded. The remainimg are xor'ed together as binary numbers to get a random seed. I'll refer to these as the randumom number(s) amd their precommits.

public/private key encryption

This is the standard sets of public/private keypairs, with the requirement that their format doesn't contain any identifying information.

a public communication channel

Each participant needs read/write permissions in this channel.

Algorithm

The basic version will take three public/private keypairs per person, two precommits for random number, and the public communication channel.

Establish identities

First, each participant publishes one of their public keys and the two random number preecommits. Thes public keys will be used to encrypt communication between participants while the random numbers associated with the precommits will be used to sort some lists.

create an anonomous list of public keys.

Now we must create an ordered list of participants, and then randomize the list using the random numbers associated with the first precommits provided.

This list will determine the order in which participants submit information.

The first participant encrypts their second public key with the communication key of the second perwon and sends them the message.

Each remaining participant does the following:

• Decrypt the message they are sent
• add their own second public key to the list of public keys
• reorder the list randomly
• encrypt and send it to the next participant in the list.

When it reaches the last participant in the list, they do the same as above, sending it to the first participant.

It is of utmost importance that all of these communications be encrypted. Once the first participant recieves the message from the last, they will:

• decrypt the message
• replace their second public key with the third public key.
• randomly shuffles the list of public keys. (this is the last permanent shuffle)
• make a copy of this shuffled list, encrypted with the second participant's public key, and send it to them.
• use the random number from the second set of precommits, and shuffle the list using the agreed upon random number as the seed.
• they then takes the order of this list, finds theirself on it, and grabs the public key. immediately following their own. This who will be who will send them a present.
• They then encrypt a message to this person with their name, contact details (if mailimg presents), and critical information such as allergies and religious prohibitions thay might apply.
• they then publish this encrypted message, ensuring that it does not include any information on the public/private key pair that it is destined for.
• they delete their copy list of participants they created.

Each participant after will follow a similar pattern.

• decrypt
• replace their key
• DO NOT SHUFFLE THE LIST
• make a copy of the list
• encrypt the original list and send it to the next participant.
• shuffle the list based on the random number given by the second set of precommits.
• find the person who's public key follows theirs
• encrypt their identifying information with that public key and post it to the communication channel.

As these encrypted messages are posted, each participant tries to decrypt them with both of the keys they have provided. When they decrypt one, it will contain the information of the person they are buying for.

how this works

Consider the information each participant has during each of their turns.

During the first round, each participant can identify which participants came before them, and thus could identify who came after if they obtain a plaintext copy of the list. For example, the second and penultimate participants can associate the keys of the first and last participants to their identities. The shuffling step during each participant's turn eliminates the possibility of associating keys to participants through order information.

During the second round, participants lose the positional information they may have gathered. For each participant, when it gets to them, they see the (previously unobserved) keys from those after them and the updated keys of those before them. As these are both previously unobserved, the participamt cannot tell between them, as long as nobody else leaks their view.

There is a bit to say about potential attacks and the impact of leaking informatiom, but I'll do that when I have something other than my phone to type on.

Answer 5

I have devised a secret santa scheme that I suspect is either flawless or just as bad as random draws with redraws. You and $n-1$ participants need a billboard for public information and each participant needs a box to draw from and $n-1$ pieces of paper. If you do it digitally, you can use public text files for the boxes and disregard the paper.

1. Each participant chooses a large, random secret number

2. (Optional) Participants agree on a method to choose unique secret numbers (e.g. by defining an order on the participants and doing some prime number or polynomial tomfoolery with a chosen secret seed or some such. I don't consider this a real issue but let me know if I have overlooked something).

3. Each participant writes their secret number $n-1$ times on their slips of paper and puts one in each of the other participants’ boxes (or: They simply write their secret number in all the public text files except their own).

4. An order is imposed on the participants, and the first participant in this order draws a piece of paper from their box, writes their name on it, and posts it to the billboard as public information (or: The first participant chooses a number randomly from their text file and writes the drawn number to the billboard along with their name.)

5. Following the order, each participant (except the first) now does the following:

• Draw a piece of paper from their respective box (or: Choose a random number from their text file).
• Check the billboard: If the number is already there, discard the drawn number and draw again.
• When the participant has a new unique number, they draw their name on the piece of paper and post it to the billboard (or: They write the drawn number to the billboard along with their name).

6. When the last participant has had the unpleasant task of going through up to $n-2$ pieces of paper before they discover the last unique number, everyone may check the billboard at their leisure.
7. A participant simply locates the slip of paper with their private number on the billboard and remembers which name is written on it, and that will be who they buy a gift for (or: Find the pair of your secret number and a name in the billboard file).

It could be a fun extra challenge to build a small website to house the boxes and billboard, making it even harder to look over each other's shoulders and cheat.

A positive of this method is that, aside from choosing a private number, the method is straightforward and seems pretty foolproof to me --- but I am probably wrong.