10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – poncho Dec 9 '15 at 12:44
  • $\begingroup$ 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. $\endgroup$ – Steakfly Dec 9 '15 at 14:44
  • 3
    $\begingroup$ 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. $\endgroup$ – Mikero Dec 9 '15 at 19:27
2
$\begingroup$

A solution is given by Peter Ryan, Crypto Santa. In The New Codebreakers, vol. 9100 of Lecture Notes in Computer Science, pp. 543-549, Springer, 2016. http://dx.doi.org/10.1007/978-3-662-49301-4_33

An earlier version (with Sjouke Mauw and Sasa Radomirovic) can be found at http://hdl.handle.net/10993/25936 (Open access), Security protocols for Secret Santa.

$\endgroup$

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.