Decentralized Secret Santa

Secret Santa relies on a third-party arbiter to distribute a permutation of the participants involved in the exchanging of gifts. This can be done by any number of online services, but the question remains – is it possible to do this on a desert island where no one wants to sit out and arbitrate? Can we devise a peer-to-peer decentralized version of Secret Santa that will let everyone learn who they need to buy a gift for without anyone finding out anything about other people’s Santas?

Problem Statement

We wish to make a protocol with no central authority that:

• Distributes a permutation of participants to all participants involved
• Doesn’t leak any information to any participant about the permutation

We’ll make a few assumptions about the system

• The participants are honest-but-curious. No one will intentionally misbehave in the process (who wants to mess up a Secret Santa?), but given information, they will read it and do trivial computations with it
• No collusion. In addition to being honest, our participants won’t work together to calculate information, just use the information that they are privy to.
• This is a fully connected peer-to-peer network. Anyone can message anyone else, and messages between 2 parties aren’t visible to anyone else.

Real-world Inspiration

The intuition for my solution to this problem comes from the physical world “implementation” of such a problem. If you didn’t have a person sitting out from the gift exchange who was going to distribute a permutation to the participants without leaking information, how would you go about this process? A natural solution that comes to mind is the “draw names from a hat” strategy: fill a hat with everyone’s names, and pass it around with each person drawing a name from the hat. If anyone draws their own name, repeat the process.

This snag of potentially drawing your own name is a bit annoying though. It’d be nice to figure out exactly how often that happens, just to better understand our odds of the hat method succeeding. The question is one of fixed points, or values that map to themselves under the permutation. We need to make sure that the names drawn represent a permutation that has none (this is sometimes called a derangement). What is the probability of that?

A Mathematical Aside

Let’s start by enumerating the number of permutations of $n$ elements that contains at least one fixed point. To do that, we’ll use the fairly common strategy of inclusion-exclusion: Let’s count the number of permutations that have 1 as a fixed point, then 2 as a fixed point, 3 as a fixed point… We’ll annotate these as 1XXXX, X2XXX, XX3XX, etc.

How many permutations look like 1XXXX? Well, there are $n-1$ digits left to complete the permutation with no restrictions, so there are $(n-1)!$ many permuations that take this form. Given we have $n$ different potential fixed values, that gives us a value of $n(n-1)!$.

But wait, you say – what about permutations that fix 1 and 2?, i.e. 12XXX? We’ve double counted these permutations in our calculation! Let’s fix that. Since we double counted these permutations, let’s subtract off all of these groups. How many such groups are there, and how big are they? Well, 12XXX has $n-2$ freely permuted elements, so each of these groups are of size $(n-2)!$. And as for how many there are, we have a unique group for every pair of values between 1 through $n$, so there are $n \choose 2$ of them. So, we’re looking at $n(n-1)! - {n \choose 2}(n-2)!$ many terms.

Err, closer, but what about 123XX? You overcounted it 2 times, but when subtracting off all the pair groups, you removed it 3 times – once with 12XXX, once with X23XX, and once with 1X3XX. We have to add those back in…

You can visualize this process as counting the regions in a venn diagram. Add a circle for each fixed point group, and enumerate each region exactly once.

Following the overcounting-undercounting argument all the way to the permutation with all fixed points (work it out for yourselves as well), you can see that the number of permutations of $n$ elements that contains at least one fixed point is: $$ \sum_{i=1}^{n}{(-1)^{i-1} {n\choose i} (n-i)!} $$ And now, to get the number of derangements, we just subtract this from our full set: $$ n! - \sum_{i=1}^{n}{(-1)^{i-1} {n\choose i} (n-i)!} = \sum_{i=0}^{n}{(-1)^i{n \choose i}(n-i)!} $$ Let’s tweak this a bit more, by expanding the definition of combination: $$ \sum_{i=0}^{n}{(-1)^i \frac{n!}{i!(n-i)!}(n-i)!} = n!\sum_{i=0}^{n}{\frac{(-1)^i }{i!}} $$ Now, back to our initial probability question. We have how many derangements there are given by the above formula. To get the probability that a permutation is one of these, we just divide by $n!$, leaving us with a relatively satisfying: $$ \sum_{i=0}^{n}{\frac{(-1)^i }{i!}} $$ That’s nice, and it gives us a way to get the exact answer, but let’s think about this a bit more. What does this probability look like in the limit, as the size of our Secret Santa group grows? We’re looking for $$ \sum_{i=0}^{\infty}{\frac{(-1)^i }{i!}} $$ for which we can think about the formal series $$ F(x) = \sum_{i=0}^{\infty}{\frac{x^i }{i!}} $$ Now, we in particular care about $F(-1)$. Well, pulling the Taylor series rabbit from our hat, we remember that $F(x) = e^x$, and so the probability we care about is $e^{-1}$ or $\frac{1}{e}$. That gives a pretty solid intuition about how likely we are to have anyone pull their own name – it’s just a little better than 1 in 3 odds. Not great, but its nonzero – so we can repeatedly try until we succeed.

Secret Santa Protocol

On to the algorithm itself then. We’ll rely on the cryptographic primitive called the one-time pad. There are 2 distinguished roles (we’ll call them Alice and Bob) in the protocol, every other person (we’ll call them P3 through PN) has a very simple “draw name” and “reveal name” participation.

Setup

Alice Creates a Scramble

Alice first sets up a name vector $\langle N_i \rangle$, a collection of strings representing each participant’s name. Names are padded with null so that each element is of equal length $l$. Alice then generates a random permutation $\sigma_A \in S_n$, and permutes the elements of the name vector. That is, she generates: $$ \langle N_1, N_2, N_3,\dots N_n \rangle \rightarrow \langle N_{\sigma_A(1)}, N_{\sigma_A(2)}, N_{\sigma_A(3)},\dots N_{\sigma_A(n)} \rangle $$ Next, she generates her key vector $\langle a_i \rangle$, which contains $N$ random bytestrings of length $l$ each. Finally, Alice constructs a one-time padded vector, hiding the permutation she used and sending the updated vector to Bob. $$ \langle N_{\sigma_A(1)}, N_{\sigma_A(2)}, N_{\sigma_A(3)},\dots N_{\sigma_A(n)} \rangle \oplus \langle a_1, a_2, \dots a_n \rangle = \langle a_i \oplus N_{\sigma_A(i)}\rangle = \langle C_i \rangle $$

Bob Scrambles Some More

Bob receives $\langle C_i \rangle$, a vector of observably random strings, and does a little work to make sure that Alice isn’t able to learn what everyone has later down the line. He also selects a random permutation $\sigma_B \in S_n$, and permutes the $\langle C_i \rangle$ vector he received: $$ \langle C_1, C_2, \dots C_n \rangle \rightarrow \langle C_{\sigma_B(1)}, C_{\sigma_B(2)}, \dots C_{\sigma_B(n)} \rangle = \langle a_{\sigma_B(i)} \oplus N_{(\sigma_B \circ \sigma_A)(i)}\rangle $$

To make things extra hard for Alice, Bob now also applies his own key vector. $$ \langle C_{\sigma_B(1)}, C_{\sigma_B(2)}, \dots C_{\sigma_B(n)} \rangle \oplus \langle b_1, b_2, \dots b_n \rangle = \langle b_i \oplus a_{\sigma_B(i)} \oplus N_{(\sigma_B \circ \sigma_A)(i)}\rangle = \langle C^{\prime}_i \rangle $$

With this, our crytographically secure “hat” is constructed. The entries, when passed around in a circle, will be indistinguishable from each other, so “drawing name” will simply involve picking an index. Bob “draws a name out of the hat” by selecting a random index ($\beta$) from the finally constructed $\langle C_{i}^{\prime} \rangle$, and sends a vector modified with a null value in that index to the first of the “regular participants”. That is, Bob sends $$ \langle C_{1}^{\prime}, \dots C_{\beta - 1}^{\prime}, \texttt{NULL}, C_{\beta+1}^{\prime}, \dots C_{n}^{\prime} \rangle $$ to the next participant.

Generic Participant Draws a Name from the Hat

PX will start by receiving a modified $C^{\prime}$ vector, with $X - 2$ many elements replaced with null. They will each randomly “draw a name from the hat”, replace it with NULL, and send it to the next Generic Participant. PN, who will have 2 entries left in the vector, will randomly pick one and send the entry with a single non-NULL entry to Alice. The last name in the hat is Alice’s.

Reveal

Alice Sends her Key to Bob

Alice receives a single non-null value in her $C^{\prime}$ vector, and needs to learn who it is. To begin the decryption, she needs the keys, which are calculated by Bob. Alice starts by sending over her key vector to Bob.

Bob Computes the Final Unlock Keys

Bob applies $\sigma_B$ to Alice’s key vector to construct $\langle a_{\sigma_B(i)} \rangle$. Bob then $\oplus$ ’s in his own key vector $\langle b_i \rangle$ to get $K = \langle a_{\sigma_B(i)} \oplus b_i \rangle$. Note that these are precisely the keys that can be applied on $C^{\prime}$ to uncover the underlying names. In particular, he can use the key at index $\beta$ to decrypt who his Secret Santa recipient is.

Bob sends $K$ back to Alice. With $K$, Alice can decrypt her own participant name, as she knows the index (call it $\alpha$) in $C^{\prime}$ she was forced to pick at the very end. She applies $K_\alpha$ to her choice and learns who her Secret Santa recipient is.

Alice Becomes a Key Oracle

Alice now has the keys, and sends an acknowledgment to each of the remaining participants that their keys are ready. Being honest participants, they send Alice the index $i$ they chose in $C^{\prime}$, and Alice sends them $K_i$, the key that decrypts their entry. Each participant decrypts the name they drew by applying the one-time-pad. By construction, this will reveal the name in plaintext.

Example

The indices get confusing really quickly, so lets do a quick demo with 4 people: Alice, Bob, Chandrika, and Dave. For the sake of clarity, Alice will be our Alice and Bob will be our Bob. Our Name Vector is

['ALICE\0\0\0\0', 'BOB\0\0\0\0\0\0', 'CHANDRIKA', 'DAVE\0\0\0\0\0']

Setup

Alice Creates a Scramble

$\sigma_A$ is 2314. So, our scrambled name vector is:

['BOB\0\0\0\0\0\0', 'CHANDRIKA', 'ALICE\0\0\0\0', 'DAVE\0\0\0\0\0']

I always get confused about permutation notation – when someone lays out the permutation 2314, how would you apply it to the string "abcd"? We could say that 2314("abcd") = "cabd", by saying “each digit in the permutation is where you send the corresponding element index in the string. So, a (the first digit) should be sent to the second position in the resulting string. You could also say 2314("abcd") = bcad, by saying the permutation describes the former indices – b was the second index, so the new string we should place it first. Perhaps one makes more sense to you. I’m going to be going with the second option here, assuming the permutation describes which original index appears at this new spot.

$\langle a_i \rangle$ is the following random bytes:

[[0xbc, 0x29, 0x7b, 0x31, 0x8b, 0xc2, 0x73, 0xff, 0x94], 
[0x9a, 0x7f, 0x54, 0x37, 0xa3, 0x2d, 0xfb, 0xd0, 0x73],
[0x23, 0x4d, 0xf2, 0x27, 0x61, 0x64, 0xd6, 0xd5, 0xb1],
[0x35, 0x19, 0xea, 0xdd, 0xdb, 0xc2, 0x5c, 0x92, 0x1]]

So, computing $\oplus$, we get $C$

[[0xfe, 0x66, 0x39, 0x31, 0x8b, 0xc2, 0x73, 0xff, 0x94],
[0xd9, 0x37, 0x15, 0x79, 0xe7, 0x7f, 0xb2, 0x9b, 0x32],
[0x62, 0x1, 0xbb, 0x64, 0x24, 0x64, 0xd6, 0xd5, 0xb1],
[0x71, 0x58, 0xbc, 0x98, 0xdb, 0xc2, 0x5c, 0x92, 0x1]]

Alice Sends this to Bob.

Bob Scrambles Some More

Bob recieves the above $C$. $\sigma_B$ is 4213, so he applies the permutation,

[[0x71, 0x58, 0xbc, 0x98, 0xdb, 0xc2, 0x5c, 0x92, 0x1],
[0xd9, 0x37, 0x15, 0x79, 0xe7, 0x7f, 0xb2, 0x9b, 0x32],
[0xfe, 0x66, 0x39, 0x31, 0x8b, 0xc2, 0x73, 0xff, 0x94],
[0x62, 0x1, 0xbb, 0x64, 0x24, 0x64, 0xd6, 0xd5, 0xb1]]

generates $\langle b_i \rangle$,

[[0xe9, 0x66, 0x7, 0x8, 0x8, 0x43, 0x25, 0xf7, 0x81], 
[0x34, 0x95, 0xb0, 0x92, 0x58, 0x81, 0xf, 0x65, 0x81],
[0xc6, 0x15, 0x2d, 0xac, 0x8a, 0x67, 0x29, 0x8e, 0x92],
[0xe8, 0x9d, 0xcd, 0x69, 0xc6, 0x6, 0x7, 0x5e, 0xb7]]

and computes $C^{\prime}$ with another $\oplus$.

[[0x98, 0x3e, 0xbb, 0x90, 0xd3, 0x81, 0x79, 0x65, 0x80],
[0xed, 0xa2, 0xa5, 0xeb, 0xbf, 0xfe, 0xbd, 0xfe, 0xb3],
[0x38, 0x73, 0x14, 0x9d, 0x1, 0xa5, 0x5a, 0x71, 0x6],
[0x8a, 0x9c, 0x76, 0xd, 0xe2, 0x62, 0xd1, 0x8b, 0x6]]

Bob decides $^\alpha$ on the fourth element as his result, so he replaces it with NULL, and sends the modified $C^{\prime}$ to Chandrika.

[[0x98, 0x3e, 0xbb, 0x90, 0xd3, 0x81, 0x79, 0x65, 0x80],
[0xed, 0xa2, 0xa5, 0xeb, 0xbf, 0xfe, 0xbd, 0xfe, 0xb3],
[0x38, 0x73, 0x14, 0x9d, 0x1, 0xa5, 0x5a, 0x71, 0x6],
NULL]

$\alpha$. Ok, you got me. I decided for Bob to make sure we don’t hit any fixed points in the example. Normally this should be randomly generated.

Generic Participant Draws a Name from the Hat

Chandrika receives the above list, and randomly chooses the first element for herself, and sends along

[NULL,
[0xed, 0xa2, 0xa5, 0xeb, 0xbf, 0xfe, 0xbd, 0xfe, 0xb3],
[0x38, 0x73, 0x14, 0x9d, 0x1, 0xa5, 0x5a, 0x71, 0x6],
NULL]

to Dave. Dave receives that, randomly picks the second element for himself, and sends along

[NULL,
NULL,
[0x38, 0x73, 0x14, 0x9d, 0x1, 0xa5, 0x5a, 0x71, 0x6],
NULL]

to Alice.

Reveal

Alice Sends her Key to Bob

Alice sends the $\langle a_i \rangle$ from above to Bob

[[0xbc, 0x29, 0x7b, 0x31, 0x8b, 0xc2, 0x73, 0xff, 0x94], 
[0x9a, 0x7f, 0x54, 0x37, 0xa3, 0x2d, 0xfb, 0xd0, 0x73],
[0x23, 0x4d, 0xf2, 0x27, 0x61, 0x64, 0xd6, 0xd5, 0xb1],
[0x35, 0x19, 0xea, 0xdd, 0xdb, 0xc2, 0x5c, 0x92, 0x1]]

Bob Computes the Final Unlock Keys

First, Bob permutes the $\langle a_i \rangle$ using $\sigma_B$.

[[0x35, 0x19, 0xea, 0xdd, 0xdb, 0xc2, 0x5c, 0x92, 0x1],
[0x9a, 0x7f, 0x54, 0x37, 0xa3, 0x2d, 0xfb, 0xd0, 0x73],
[0xbc, 0x29, 0x7b, 0x31, 0x8b, 0xc2, 0x73, 0xff, 0x94], 
[0x23, 0x4d, 0xf2, 0x27, 0x61, 0x64, 0xd6, 0xd5, 0xb1]]

Next, he $\oplus$ s with $\langle b_i \rangle$ to get $K$.

[[0xdc, 0x7f, 0xed, 0xd5, 0xd3, 0x81, 0x79, 0x65, 0x80],
[0xae, 0xea, 0xe4, 0xa5, 0xfb, 0xac, 0xf4, 0xb5, 0xf2],
[0x7a, 0x3c, 0x56, 0x9d, 0x1, 0xa5, 0x5a, 0x71, 0x6],
[0xcb, 0xd0, 0x3f, 0x4e, 0xa7, 0x62, 0xd1, 0x8b, 0x6]]

Bob has the 4th key! He can see who he got for Secret Santa now, by $\oplus$ ing the value he chose

[0x8a, 0x9c, 0x76, 0xd, 0xe2, 0x62, 0xd1, 0x8b, 0x6]

with the 4th key.

[0xcb, 0xd0, 0x3f, 0x4e, 0xa7, 0x62, 0xd1, 0x8b, 0x6]

Given the names are of unique lengths, perhaps you can see who this is already. But if not, let’s decrpyt:

['ALICE\0\0\0\0']

Great, Bob is good to go. Note that Bob can also decrypt the full final permutation, but doesn’t know any information about who got what.

Bob sends $K$ to Alice.

Alice Becomes a Key Oracle

Ok, first things first, let’s find out who Alice got for Secret Santa. Alice, remember, got the very last entry, in the 3rd slot.

[0x38, 0x73, 0x14, 0x9d, 0x1, 0xa5, 0x5a, 0x71, 0x6]

Using the 3rd key:

[0x7a, 0x3c, 0x56, 0x9d, 0x1, 0xa5, 0x5a, 0x71, 0x6]

we can see that Alice got

['BOB\0\0\0\0\0\0']

Alice now alerts Chandrika and Dave that their keys are ready.

Chandrika sends over the fact that she needs the 1st key, and Alice replies with

[0xdc, 0x7f, 0xed, 0xd5, 0xd3, 0x81, 0x79, 0x65, 0x80]

Chandrika uses the key with the value she took from $C^{\prime}$

[0x98, 0x3e, 0xbb, 0x90, 0xd3, 0x81, 0x79, 0x65, 0x80]

Chandrika decrypts to find her Secret Santa:

['DAVE\0\0\0\0\0']

Dave does the same thing. He tells Alice he needs key number 2

[0xae, 0xea, 0xe4, 0xa5, 0xfb, 0xac, 0xf4, 0xb5, 0xf2]

and decrypts his chosen entry

[0xed, 0xa2, 0xa5, 0xeb, 0xbf, 0xfe, 0xbd, 0xfe, 0xb3]

['CHANDRIKA']

Looks like Secret Santa will involve 2 little gift exchange cycles this time!

Intuition for Information Security

Perhaps you’ve convinced yourself of the correctness of this algorithm (it basically comes down to reversing one-time pads), but are still a little unconvinced by the fact that no-one can learn more information than their own entry in the permutation. After all, Alice and Bob exchange end the protocol with access to lots of information about how to decrypt the final permutation being passed around. Let’s convince ourselves that anyone learns anything beyond what they need to.

Generic Participants

Let’s get the easy one out of the way. Because $C^{\prime}$ has been encrypted with a one-time pad, there is no way for each participant to know what has been picked and what hasn’t when they receive a partially NULL vector, nor do they have any ability to pick a specific person. Because they only get one key from Alice, there is no way for them to decrypt a different entry (well, technically they could lie to Alice, but we are assuming honest-but-curious, and if they do lie they have no way to actually successfully decrypt their own choice).

Bob

With Bob, there’s an element of timing involved. Note that during the reveal phase, Bob gets information about $\sigma_B \circ \sigma_A$, the underlying permutation that is passed around the circle. However, due to $\sigma_A$ being obscured by the one-time pad $\langle a_i \rangle$ for the first pass, Bob has no advantage in selection when pulling his entry – he is pulling from a slightly less locked down hat, but still cryptographically locked down.

Moreover, Bob goes first when pulling from the list, meaning that he has no ability to gain information about who is pulling what as he never sees the list again nor learns about what indices are being queried by whom (a responsibility that falls on Alice).

Alice

Perhaps the most surprising, given that Alice functions as an oracle with the final permutation at the last phase of the protocol. Alice’s lack of information relies on 2 components: a hidden $\sigma_B$ and receiving no information about $C^{\prime}$ except her own entry.

In particular, $\sigma_B$ is applied after Alice hands off to Bob, and by the time she receives the vector, there is only one entry left in it. So, Alice has no knowledge of the final permutation of $C^{\prime}$, meaning she can be a blind prophet – entrusting her with the knowledge of the decryption keys and the indices is completely fine because she has no knowledge of the contents of underlying permutation.

Summary

Ultimately, Alice and Bob’s inability to reconstruct the permutation relies on the division of critical information: Bob knows the underlying permutation but doesn’t know the indices that each participant chose, and Alice knows the indices with no knowledge of the permutation. As such, both can be given all the keys with no ability to gain information about any of the other participants choices.

The $\sigma_A$ Optimization

Knowing the crux of the information security allows us to simplify Alice’s first round role a little bit, and eliminate $\sigma_A$ from the picture. Instead, we can do the following:

1. Bob starts the algorithm, applying $\sigma_B$ and $\langle b_i \rangle$ exactly as Alice did in her first step. He passes this vector to P3 without choosing an entry (Otherwise, he’d have complete control of who he got!)
2. Now, Alice receives the $\langle C^{\prime} \rangle$ vector with 2 entries. She randomly selects one and passes it back to Bob. Bob instantly knows who his Secret Santa recipient is.
3. Bob now sends the keys to Alice, but redacts the key for his index. This prevents Alice from learning anything about Bob’s recipient. Alice performs her key oracle role as normal.

With these modifications, we’ve eliminated the initial tumbler that Alice creates to allow Bob to pick randomly, but we need to hide a little more information from Alice since she no longer receives the vector that’s empty except for her entry. Neat!

Conclusion + Acknowledgements

First, thanks to Michael Rosenberg for reading and providing feedback on this writeup.

I came up with this algorithm in late 2019 while tinkering with a few permutation-related problems (and the much simpler version that optimizes out $\sigma_A$ while writing this post), and in my (admittedly limited) searching, couldn’t find any literature where this algorithm is presented. If you’ve seen this elsewhere, please let me know so that I can adjust this section with some further reading.

The math problem about fixed points is a pretty standard introductory combinatorics problem, so the solution presented was just how I went about doing it – no claims of originality there.

Some problems that I’m still thinking about revolve around not needing to repeat this protocol – that is, finding a way to make sure that no one picks themselves when drawing from the hat. I’m thinking something with anonymous messages, a random ordering of the PI, and some kind of anonymous set membership detection could work, but I haven’t thought about it thoroughly enough. Please feel free to message me if you think of something! If I come up with something, I’ll revisit this in a subsequent post. In the same vein, finding a way to restrict the final permutation to an n-cycle (that is, avoiding having the final permutation devolve to gift exchange subcycles) would be nice too.

Thanks for reading this post! Hopefully next time you’re organizing Secret Santa, you’ll use this completely unnecessary cryptographically secure protocol to decide who you’re getting a gift for.