.-""-.._
 /,.._____\
() { _____ }
  ( /-O-O-\ )
  { `--^--' }
  {   `o'   } Encrypt everything!
   {       }
    `-----'

Description:

During Christmas 2019, I implemented this simple secret santa program ¹ that was able generate a random permutation of a set of parties and send each party an email indicating the person to whom that party should give a x-mas present 🎄🎁. I actually used that program to play secret santa with my cousins that year! (See the image below 🥰).

Although that program worked very well back then, I realised that the permutation me and my cousins used was secret to them, but not to me since I had run the program myself, as a trusted third party (TTP) and I wondered whether there was a protocol that would allow us to do this without any TTPs!. Apart from from it being an interesting problem in this context, I also thought it could be thought of as a more general coordination problem that might have applications in other fields 🤔 ².

I stopped thinking about that problem soon after, but recently I saw this tweet that grabbed my attention:

Hey crypto (as in cryptography) folks - is there a way to do a secret Santa (that is, generate a random permutation) such that everyone knows only the person they're assigned, with nobody knowing the complete mapping?

— nick.eth (@nicksdjohnson) October 12, 2021

To which, of course, I replied:

omg! I've been wondering about this since xmas 2019!

— np (@nph4rd) October 13, 2021

There were a bunch of replies by @LindellYehuda that made me think about this again. Specifically, I found this one really interesting:

With semi honest security, it should be quite easy. I’d generate a shared ElGamal key pair and encrypt each number separately. Then, in turn, each party permutes the ciphertexts and rerandomizes them. Finally, each party gets one ciphertext and distributed decryption is run. >>

— Yehuda Lindell (@LindellYehuda) October 13, 2021

It seemed to me that this problem could be solved with a fairly simple protocol and I made the decision to implement it for this (2021) Christmas, at least as POC program that simulates the parties and their interactions, while omitting everything else around the protocol, such as the secure communication channels, the clients, etc. In what follows I will describe the protocol in a little more detail, provide some more information about the actual work behind this (that is, the previous research work by other people who actually designed some protocols to solve this) and share some details about my implementation and how to use it.

Background

Secret Santa is actually a very popular tradition in the West, as pointed out in its Wikipedia entry. Traditionally (at least in my family) people would get together and write the names of the participants on pieces of paper, that would then be placed in some sort of container (bag, hat, or whatever). The container would then be passed around among the participants, and each would draw one piece of paper. If the paper they drew has their own name on it then, of course, he/she would show it to the rest of the participants, place the paper back into the recipient and draw another one. This step is repeated until that person has a paper that does not have their own name on it, and, thus, a random mapping is created, which is not known to any of the participants. This is beatiful, of course, and it’s the trivial solution to what we seek, but we want to be able to replicate something like this for the case where the participants can’t meet in person! The following is a description of one solution to this problem, but it is possible to do this in a number of different ways.

Before going into details about the protocol (at least in my own words) I should credit the people who actually worked on this problem, so first things first:

The actual work

Although I did not make a very thorough search for previous work (after all, I’m only doing this for fun), I did find three very interesting articles/papers about crypto santa ³:

The first one was an open-access paper from 2010 by Sjouke Mauw, Sasa Radomirovic, and Peter Ryan, in which the authors offer a decentralised solution using the ElGamal cryptosystem (which will be outlined in the next section). The protocol they describe is similar to the one outlined by Yehuda Lindell in the tweet above, except for the fact that they include a derangement test to assure that the resulting permutation is a derangement (i.e. has no fixed-points), and a commitment step so as to make the protocol verifiable (i.e. to detect cheaters! 🕵️). Presumbly, the idea to have a shared ElGamal key-pair is so that it can be used as a threshold cryptosystem. Although this is really cool, I think it is unnecessary, as we will see in the following work.

The second paper I found was a subsequent work by Peter Ryan, that can be found as a chapter to a book from 2016 that is unfortunately behind a paywall ⁴. The protocol described here is very elegant and is actually the main basis of my implementation. I will describe it in a little more detail below. For now it suffices to say that one of the main differences is that in this protocol each party has their own key-pair, instead of having a shared key-pair with which all encryptions are done, as in the one outlined in the tweet or in the previous 2010 paper.

The last paper I found was an older (2007), perhaps more general solution to this same problem. This paper by Chris Studholme and Ian Blake proposes a protocol that (much like the paper that was just mentioned) depends on each player deriving a key-pair with the ElGamal cryptosystem. The protocol is pretty much the same as the one described in 2016 “Crypto Santa”, although some of the details in each of the steps differ. For instance, in the former there is a last step where each of the participants share one of their two secret keys with the rest of the participants, whereas in the latter each participant \(i\) relays a shared value \(g^{\hat{s}_i}\), where \(\hat{s}_i\) is recursively defined as \(\hat{s}_i = \hat{s}_{i-1} \cdot s_i\). That is, each participant relays the previous shared value raised to a specific re-encryption value determined by the participant in turn.

In order for us to better understand why this can be done, let’s have a look at what the ElGamal cryptosystem is.

ElGamal

The ElGamal cryptosystem depends on the computational difficulty of solving discrete logarithms in certain groups, such as the multiplicative group of integers modulo n, which is cyclic if \(n\) is \(1, 2, 4, p^k, 2p^k\), where \(p\) is an odd prime (see this for more info). Since cyclic groups have a generator, \(g\), this means that for any \(x \in \{1, n-1\}\) it is unfeasible to compute \(x\) from knowledge of only \(g^x\), whenever \(n\) is a “large enough” prime ⁵. From now on, we will assume we use a group, \(G\), with the characteristics that we just mentioned, and we will denote with \(q\) the “large enough” prime for the group (which is also its order).

The key generation process for ElGamal is simple: Once the group \(G\) has been established with the characteristics mentioned above, each party can generate a private key by randomly choosing an integer \(x \in \{1, ... , q - 1\}\). We can then compute the value: \(h = g^x\), which is needed to construct the full public key: \((G, q, g, h)\).

Under this scheme, encryption consists on the following: a party uses the public key, \((G, q, g, h)\), to encrypt a message \(M\) by mapping \(M\) to an element, \(m\), of \(G\) and choosing a random element \(s \in \{1, ... , q - 1\}\). The value \(s\) is then used to compute a shared secret: \(r = h^s\). With this, the ciphertext (which consists of two values) can be constructed: \((c_1, c_2) = (g^s, m \cdot r)\).

Now, decryption is as follows: the owner of the private key, \(x\) corresponding to public key \((G, q, g, h)\) can recover \(m\) with the following steps:

1. Compute \(c_{1}^{x}\), which is \(g^{xs} = h^s = r\), thus recovering the shared secret.
2. Compute the inverse of the shared secret, \(r^{-1}\) ⁶.
3. Compute \(m = c_{2} \cdot r^{-1}\).
4. Map \(m\) back to the plaintext \(M\).

Note:

A useful property of the ElGamal cryptosystem is that it allows for re-encryptions. In particular, we will use a seemingly pointless property that is, however, very important to the protocol implementation, which is that if \(m = e\) (that is, \(m\) is the group identity) then whoever generates another value \(s'\) can compute a new ciphertext given by: \((c_1^{s'}, c_2^{s'})\). For a normal application this is useless because it only works for a pretty specific case that would imply knowing the message in the first place! However, as we will see soon, this is key in our protocol.

The protocol

Now that we know how ElGamal works and we know a little bit more about the previous work on the development of the protocol, we can outline the protocol that will be used in the implementation.

Suppose a set of \(N\) players want to organize a decentralised secret 🎅 and that they’ve agreed on using a group \(G\) with the wanted characteristics above. That is, assume they’ve chosen a large prime \(q\) and they’ve constructed the multiplicative group of integers modulo \(q\). They can all generate a key pair: \((x_i, pk_i)\), with \(pk_i = (G, q, g, h_i) = (G, q, g, g^{x_i})\) and broadcast their public key ⁷ so as to form the vector:

The first player can now re-encrypt/re-randomise (see the note above) and shuffle the vector with her own encryption value, \(s_1\). Thus, the vector becomes:

This first player can now forward (through a secure channel) the new vector, along with the shared value \(g^{s_1}\), to a second player. The process is repeated for the arbitrary player \(i\). This player also applies a re-encryption and a random shuffle to the vector she receives with a random value \(s_i\). The vector becomes:

Where:

And the permutation \(\hat{\pi}_i: \{1, ..., N\} \rightarrow \{1, ..., N\}\) is the composition of the permutations of all the players that have participated so far. That is:

Again, player \(i\) shares the new vector and the shared value, \(g^{\hat{s}_i}\), with the next player. Finally, we reach player \(N\), who repeats the process and broadcasts the final vector to the rest of the players, along with the shared value. With it, each player only needs to raise the shared value, \(g^{\hat{s}_N}\), to its private key value, \(x_i\), and find its match in the vector. For example, if player \(1\) does this and finds a match in position \(3\), then player \(1\) has to give out a present to player \(3\) and only player \(1\) knows this! ⁸

Note:

This construction is in some ways similar to a mix network, which is used in protocols, such as TOR ⁹.

The implementation

The Rust implementation of this protocol can be found in this repo. Notice that it is only a simple demo of the protocol! That is, it does not include many of the (very important) details that the protocol would need to work properly. Most importantly, it is not an implementation of the clients/peers that would participate in the protocol. Instead, it’s just a script that runs the protocol in one centralised program.

Another important note about the implementation is that it uses this implementation of ElGamal in Rust. The only extra function that we use is the rerandomise function, which is as follows:

/// Function that rerandomises a ciphertext. Note that this only works
/// when the message `m` is the identity.
fn rerandomise(c: &ElGamalCiphertext, y: &BigInt) -> Result<ElGamalCiphertext, ElGamalError> {
    let c1 = BigInt::mod_pow(&c.c1, &y, &c.pp.p);
    let c2 = BigInt::mod_pow(&c.c2, &y, &c.pp.p);
    Ok(ElGamalCiphertext {
        c1,
        c2,
        pp: c.pp.clone(),
    })
}

The program has two main structs:

// This represents a single player.
#[derive(Debug)]
struct Player {
    /// The id of the player.
    id: u8,
    /// Who this player gives a present to.
    gives_to: Option<u8>,
    /// Key-pair in the ElGamal cryptosystem.
    key_pair: Option<ElGamalKeyPair>,
}

/// This struct represents an instance of
/// a secret santa that will be played out.
#[derive(Debug)]
struct SecretSanta {
    /// The vector of players that
    /// will participate.
    players: Vec<Player>,
}

The SecretSanta struct has a function assign:

/// Function that "triggers" the protocol
/// creating the random permutation of players
/// in a "decentralised" way.
pub fn assign(&mut self) {

This function takes care of running the protocol on a SecretSanta instance. I will show this, step-by-step.

The first step is to generate the ElGamal instance:

// Build new ElGamal instance
let group_id = SupportedGroups::FFDHE2048;
let pp = ElGamalPP::generate_from_rfc7919(group_id);

In order for the players to be able to announce whenever they have been self-assigned in the secret santa, we use a flag:

// Use this as a flag whenever a player
// finds that she has been self-assigned.
let mut finished = false;

So… the rest of the code for this function runs within a while loop that finishes once a derangement has been found:

while !finished {
    ...
}

Within the loop we have 3 main steps. First:

// We instantiate the vector of ElGamal
// ciphertexts.
let mut vec: Vec<ElGamalCiphertext> = Vec::new();
// This first step consists of each player
// adding an encryption of the identity,
// with "randomness" 1. That is, each player
// adds its public-key `g^x`.
for p in &mut self.players {
    p.key_pair = Some(ElGamalKeyPair::generate(&pp));
    let m = BigInt::from(1);
    let y = BigInt::from(1);
    let c = ElGamal::encrypt_from_predefined_randomness(
        &m,
        &p.key_pair.as_ref().unwrap().pk,
        &y,
    )
    .unwrap();
    vec.push(c)
}

Then:

// Each player randomly permutes the vector
// and reandomises each entry.
for _ in &self.players {
    let slice: &mut [ElGamalCiphertext] = &mut vec;
    let mut rng = thread_rng();
    slice.shuffle(&mut rng);
    vec = slice.to_vec();
    let y = BigInt::sample_below(&pp.q);
    vec = vec.iter().map(|x| rerandomise(&x, &y).unwrap()).collect();
}

And, finally:

// The vector is broadcasted to every player and
// now each can find out who they give a present
// to, but only that.
for p in &mut self.players {
    // Each player can get the shared value, `g^\hat{s}`
    // from any of the ciphertexts (c1).
    let shared_value = &vec.get(0).unwrap().c1;
    // Each player now finds their assignment by
    // raising the shared value to her secret key `x`.
    let target_value =
        BigInt::mod_pow(&shared_value, &p.key_pair.as_ref().unwrap().sk.x, &pp.p);
    p.gives_to = Some(vec.iter().position(|x| x.c2 == target_value).unwrap() as u8 + 1);
    // If the player finds out that she has
    // been self assigned, then she "announces"
    // this and the assignment starts over again.
    if p.id == p.gives_to.unwrap() {
        finished = false;
        break; // No point in continuing.
    }
}

With all this, we can run something like the following, for a 10-person secret santa:

// Instantiate a new SecretSanta with 10 players.
let mut ss = SecretSanta::new(10);
// Run the protocol.
ss.assign();
// Find out the assignment:
for p in &ss.players {
    println!("{:?} gives 🎁 to: {:?}", p.id, p.gives_to.unwrap());
}

The above results in something like this:

New secret 🎅 among 10 players!
1 gives 🎁 to: 2
2 gives 🎁 to: 4
3 gives 🎁 to: 9
4 gives 🎁 to: 1
5 gives 🎁 to: 8
6 gives 🎁 to: 5
7 gives 🎁 to: 3
8 gives 🎁 to: 6
9 gives 🎁 to: 7

With this, we’ve managed to decentralise Christmas! 🎄

🍀