# Santa Claus' secret permutation

This December, $N$ friends play secret santa: they select a random permutation $\sigma$ of $N$ (without fixed point). For Santa Claus, everyone has to bring a gift to the next person in the permutation. To preserve the magical spirit of the game, each participant should only know the strict necessary (i.e. their image by $\sigma$) until the gifts are disclosed in the end of the month.

However, they cannot meet face-to-face before sharing the gifts and would like to generate a proper $\sigma$. We assume that they can communicate together using any cryptographic primitives. Besides, they have no access to a third-party to help generating $\sigma$.

Is there a distributed protocol to generate a random permutation $\sigma$ among them? Which of the following properties can be guaranteed?

• Secrecy: Each participant $i$ should only know $\sigma(i)$, and should have no other knowledge about $\sigma$ (i.e. given the messages sent and received by $i$ and $\sigma(i)$, all permutations $\mu$ with $\mu(i) = \sigma(i)$ should be equiprobable).

• Secrecy++: Each subgroup of $k < N - 1$ participants should only be able to recover their respective $\sigma(i)$ if they cheat and share information together (again, all permutations that follow these constraints should be equiprobable given their common knowledge). Note that for $k = N - 1$ the permutation is obviously recovered.

• Fairness: Each participant cannot cheat to force the value of its $\sigma(i)$, whatever messages they send. Similarly, they cannot force any other $\sigma(j)$, nor bias the distribution of $\sigma$ as a whole.

• Fairness++: Each subgroup of $k < N$ participants cannot bias the distribution of $\sigma$.

• Validity: $\sigma$ is without fixed point.

The validity property can also be replaced by other sets of permutations:

• all permutations ($S_N$)

• the alternating group ($A_N$)

• similarly, a subgroup of $S_N$

• other subsets of $S_N$.

Solution for $N = 2$ :

• With validity: there is only one choice of $\sigma$: the transposition.

• Without validity: each participant draws a number $x_i \in \{0, 1\}$ and sends it to the other using a commitment scheme. Once the messages are received, they open the values. Let $X = x_0 \oplus x_1$ (i.e. modulo 2). If $X = 0$, $\sigma$ is the identity, otherwise it is the transposition.

• Solution for N=3 is similarly easy; the three parties jointly compute a random bit, and that tells them whether the cycle is clockwise or counterclockwise. – poncho Dec 9 '15 at 12:44
• Yes the validity case for $N=3$ is easy. However, the general case (any permutation of $S_3$) seems non-trivial (if possible?). I updated the statement. – Steakfly Dec 9 '15 at 14:44
• This is a special case of secure multi-party computation. Any general-purpose MPC protocol can do this, it only suffices to write the permutation-sampling process as a boolean/arithmetic circuit. – Mikero Dec 9 '15 at 19:27