A Cryptographically Secret Santa

Twas about 4-6 weeks before Christmas, and all through the math department, not a creature was stirring, not even a plucky young undergrad. Cryptography professors Alice and Bob sat at the elliptically-curved conference table to plan the department’s secret Santa. Mallory, the department secretary, had been given the task of organizing last year, and somehow managed to get three gifts while leaving several people disappointed. This year’s math department thus resolved to do their secret Santa without a trusted party.

As Alice and Bob went to the blackboard to think, they began to decide on the properties of their secret Santa. They came to several conclusions:

• Math department members must be assigned to give a gift to exactly one other random person

• Math department members must not know who is buying for them

• Chuck, who only communicates by email, needs to be able to participate

• Mallory should not be able to give herself multiple gifts

• Undergrads (and theorists) should be able to participate without screwing anything up undetectably

After some research, and much to their dismay, even Matt Parker could not find such an algorithm. Nor could the kind elves of Math Stack Exchange, although they gave a valiant effort. Thus, Alice and Bob sat down to plan their own cryptographically secret Santa.

As Alice and Bob charted out the problem, it came down to three steps:

1. Creating a list of anonymous public keys to represent buyers.

2. Randomly (and trustlessly) assigning buyer keys to recipients.

3. Having recipients share their names with buyers, with a proof of identity.

Thankfully, Alice and Bob had many constructs from modern cryptography available, and they sat down at the blackboard to start each step.

Collaborative Randomness

A key building block for cryptographically secret Santa would be a collaborative process to generate a random number. Alice knew of two helpful cryptographic primitives here. The first is distributed key generation, a process through which many people contribute entropy to generate a random number together. The second is randomness beacons, such as those run by the NIST or distributed groups, that publish random bits periodically and are made to be used in processes like this one.

Alice and Bob surmised that when they needed to generate collaborative random numbers, they could give members of the department a chance to contribute to the random number generation process:

1. Announce to the participants of secret Santa that they would be generating a random number together by a given deadline.

2. Allow the participants to send any material they want to be hashed together.

3. After the deadline, hash together all of the key material that arrived in step (2), and then hash it with the output of a randomness beacon taken 10 minutes after the deadline.

That way, every member of the math department could contribute entropy to the process of random number generation, but no member of the math department could decide the outcome alone. The security of this step really came entirely from step (3), but math department members could contribute some entropy in step (2) if they were up for rolling some dice or listing some digits of pi.

Alice stood back from the blackboard with a beaming smile. Of course, Bob, ever the pragmatist, suggested that they could simply take the output of a randomness beacon without going through the first two steps. Alice retorted that they could simply pull names out of a hat, but the point of cryptographic secret Santa was to have people do some cryptography! Of course, a real shared randomness scheme would need to use something like Pedersen’s protocol.

Joining the Math Department Secret Santa

To join the department’s secret santa, Alice and Bob knew that they would need to allow math department members to anonymously publish a one-time public key to the department, but only members of the math department. It was simple enough to ask for everyone’s email when they signed up, and create a public list of names of participants.

Every participant would also be asked to generate an asymmetric key pair tied to their identity, and send out an email to the math department signing their email with their key. This key pair establishes their identity and will be used later.

Finally, all participants in the secret santa would then create a shared secret, so that future rounds could use a proof of possession of that shared secret as a method of authentication. This would be important for the next step, where participants will be sending anonymous messages.

Alice and Bob were excited to figure out a scheme for creation of a shared secret, but decided that even a generalized Diffie-Helman exchange would be too difficult for most participants, let alone a more modern protocol. Instead, they decided to use their collaborative randomness process, but forego the randomness beacon.

These steps in hand, Alice and Bob sent out the following email to the math department:

Hello everyone,

It’s that time of year again, for the department secret Santa. He’s going to be extra secret this year thanks to some cryptography. We have created a new email list this year, and it is visible to everyone: [email protected]

To sign up, send an email to the list containing your name and a public key you want Santa to use this year. Make sure to sign your email with your public key. If you need help doing this, Alice or Bob can walk you through the procedure.

The deadline to sign up is in a week, so get on the list! Ho ho ho! Happy holidays!

With the crypto-santa email list set up and sign-ups open, they came roaring in. Even the most reclusive of theorists came out to join. Once the deadline had passed, Alice sent out the next email, encrypted with everyone’s public key, to establish the shared secret:

Welcome to Secret Santa!

To start, we are going to be generating a shared secret only for people in secret santa. We’re going to do this by collecting everything you send, appending it together in the order it arrives on this list, and hashing it with SHA2-512.

The deadline to submit key material is three days from now, so get your grad students busy flipping coins or rolling dice!

Send back this material encrypted for everyone (like this message) and signed with your key so we know it came from you.

While the grad students on the list let out a collective groan, they got busy making key material as studiously as elves made toys. Three days and a flurry of emails full of random bits later, the secret was established. Alice decided to be nice and send it out as an encrypted email, even though it was not strictly necessary:

Hello Secret Santas!

Our shared secret is: [XXXXX]

Please check my math if you like. The emails are all there for everyone to see We’re now moving on to the anonymous round!

Collecting Anonymous Keys

With an email list and a shared secret, collecting anonymized keys was easy. Alice and Bob simply had everyone create an anonymous email address to share some newly-created anonymous keys. They opened up the email list to accept emails from anywhere, and filtered out any that weren’t signed with the shared secret.

A generous helping of reminder emails made sure that everyone in the math department submitted an anonymous key to the Secret Santa server. University IT staff complained at the volume of messages from random accounts that started with the text Begin GPG signed message, but they were convinced with the help of some Christmas cookies and generously-spiked eggnog.

If more anonymous keys showed up than there were participants, Alice and Bob would restart the process. A new shared secret would be created and they would do the anonymous collection phase all over again. Mallory would then only be able to delay the process, not get herself extra gifts.

Assigning Buyers to Recipients

A list of anonymized keys in hand, Alice and Bob then would have to create a derangement of that list to assign buyers to recipients. The obvious answer would be to do iterated rounds of collaborative randomness and then use that as the seed for a pseudorandom number generator used to implement a list shuffling algorithm. If anyone got themselves, they would discard the result and pick a new seed. While that would work, it would not be guaranteed to terminate and it would take, in expectation, $e$ rounds of random number generation. With Christmas rapidly approaching, this was time that Alice and Bob did not have.

Instead, Bob suggested that they randomly permute the list once, and treat that as a cyclical graph. The first person on the list buys for the second, the second for the third, and so on. This time, Alice agreed that would be a clean solution, although it would not allow all possible derangements to be in the probability space.

The next email then went out:

Hello Santas!

We are going to generate a random number again, this time to pick a permutation to generate our list of gift givers and recipients! We are so close to securely knowing who we are buying for, isn’t that exciting?

Send in your key material again, this time by midnight of December 10! It will be mixed with the NIST randomness beacon taken at 1:00 am on the 11th. At that point, we will use that number as our seed for a simple list permutation. Code will be put up on github!

After all they key material was sent in and the process was run, Alice could announce the final list:

I appreciated all the coin flips. See the attached PDF for our random number generation process. Check my math if you would like!

The final list is:

[AA] buys for [BB]

[BB] buys for [CC]

…

[ZZ] buys for [AA]

Please let your secret Santa know who you are, instructions will follow! You can even send Santa a wish list now, but if you are on the Santa side of a conversation, make sure you continue to use your anonymous identity for communication. Happy gifting!

Make sure you send this email promptly, your Santa is waiting!

The only thing left was to tell your secret santa who you were.

Communicating with your Secret Santa

Finally, the time came to tell your Secret Santa your identity and set up a communication channel with them. However, part of doing this is establishing your own identity using your anonymized and non-anonymized keys. Alice and Bob reasoned that each participant’s first email to their Santa needed to contain the following information:

• Name or email
• A signature with your anonymized key (to validate list position)
• A signature with your original non-anonymized key (to validate that they are, in fact, a secret santa participant)

And the message should be encrypted for only your Santa’s anonymized public key. At this point, your Santa can figure out who you are with proof of your identity.

Alice also knew that you and your Santa now had a communication channel open where the Santa was anonymous but the recipient was authenticated. This meant that you could even share your wishlist with your Santa or even have a conversation.

Christmas at the Math Department

The annual department Christmas party arrived. The mulled wine flowed, and the candy and cookies came out. Everyone received a gift and nobody knew who their Santa was. With the merriment and laughter, Alice stood back at the blackboard, thinking forlornly about all the simplifications and assumptions that had been involved in her algorithm. She knew that the anonymous round had big denial-of-service attacks available, and that her algorithm for generation of shared secrets was insecure and the shared random number algorithm relied on a trusted third party. Had she missed something big? Was there anywhere she could have made this simpler?

Bob came into the classroom and set down some mulled wine on the desks for Alice. “It worked. Everyone got their gifts, no one knows their Santa, not even Mallory and Eve who screw this up for everyone every year! That’s what really matters.”

Alice’s face relaxed as she took a sip of wine. “I suppose you’re right. Perfect is the enemy of good.”

“Besides,” Bob added with a wry smile, “now we have another paper to write, and that really is the miracle of the season.”

Alice and Bob clinked glasses as they turned off the classroom lights and left to join their colleagues in the fun. With the help of some cryptography, the magic of Christmas had come to the math department.