A Truly Secret Santa Algorithm

What is a Truly Secret Santa?

Secret Santa is a gifting tradition, where names are pulled out of a hat in secret, and one gifts the person whose name they pulled. Normally, if you pull out your own name, you'll put it back in the hat. This method is good enough for most people. However, if you are a mathematician (and/or a particularly annoying friend - in the best way) then this will not suffice. You can use observations about who put their name back in order to deduce who is gifting whom.

A truly secret Secret Santa algorithm is one where there is no possible way of deducing the identity of the gifters. Normally this makes use of a trusted third party; someone not in the group handles the pairing. But what if you have nobody to trust? And you happen to be in a situation where you can't use a trusted computer? Well I think you have bigger problems, but that is beside the point.

I (believe) I have found a truly secret Secret Santa algorithm which does not rely on a third party or central authority. I will first explain the original idea, then the slightly more fun one. They share the final step in common, and are very similar.

The Algorithm (using computers)

This algorithm is based on using a blockchain as the cycle. Mining is the process used to generate the cycle in a random order.

• Every person will generate a public/private keypair.

• Everyone will agree on some sort of purpose-built proof-of-work blockchain, along with all the practicalities of it (such as binary format and messaging protocols).

• A block is 'mined' by a person ('miner') when they have completed the proof-of-work (e.g. N-length prefix of 0's in the previous block's hash).

• Each block must contain the necessary proof-of-work, previous block's hash, the miner's public key.

• Each person will only generate one block.

• Upon mining a block, it is broadcast to all remaining miners immediately, who will begin mining the next block.

• Once everybody has mined a block, the cycle is complete. The miner of block N is to be the person who gifts the miner of block N+1. The miner of the last block will gift the miner of the first block.

• In order to get the identity of the giftees, everybody will sign their name using the public key of the miner who is going to give them a gift, and broadcasts this cyphertext

• The gifters will then decrypt the relevant broadcasted name using their private key, in order to obtain the name of the person they will give a gift to.

As far as I can tell, this algorithm will work. That said, it relies on two things: (1) the security of the keypair; and (2) a method of privately broadcasting information. For (1), this is not much of an issue, there are even post-quantum keypair algorithms that should work fine. However, (2) is more debatable. If you are implementing this on the internet, then IP addresses may not be private enough for you. After all, now you're relying on a third party: your ISP. Even if you are using TOR to hide your IP address, you're still relying on the trustworthiness of TOR (which is pretty good, but not perfect). If you believe this isn't a true no-third-party algorithm, then the next idea is for you.

The Algorithm (using word games)

For this algorithm, we will still construct a blockchain, but we will perform mining in a turn-based manner. This one will be based around Boggle, a word game where players find as many words as they can from a set of random letters within a time limit. You can change this to almost any game as long as there is some sort of proof-of-work. It's also designed to work offline. Here's how it works:

• There is a ballot box in the room, along with a timer, and a Boggle grid.

• Each person will have a slip of paper to write their answers on (anonymously). This will also contain their public key (Yes, not convenient to do in-person. Too bad.)

• Play a round of Boggle. Once the timer is up, everyone will fold their paper and place it into the ballot box.

• Everyone will open the ballot box together. Whichever slip of paper has the most words on will be the 'block' for this round. If there are several winners, you can do a vote or something, it doesn't actually matter, as long as you all agree and it stays anonymous.

• If your slip was already in the chain, submit a blank piece of paper

• Repeat until you have the full chain of blocks.

• Sign your name with the public key of the person before you in the chain. They will decrypt it with their private key to get your name.

Now as far as I can tell, this really works. I don't think you can argue that there is a central authority here or any third party, and as far as I know there is no way to deduce who will get who. You also won't end up with your own name, same as the previous algorithm. Again, you can replace the scoring system any way you want, but this was the first thing I thought of (aside from Countdown, but I figured too many people would get the same answers).

Merry Christmas (and happy holidays)

Please let me know if you can think of any flaws in this (email: hannah at spanner dot codes)! I'm sure someone has probably beaten me to this (For the record, I thought of this at approximately 14:17 UTC, 24th December 2024). This was sparked by Matt Parker's video on the topic, with Hannah Fry's Secret Santa algorithm as inspiration for the anonymous cycle idea. In the unlikely event that I have actually invented something new, would anyone care to tell me how to write a paper? Merry Christmas :)