Mental poker

Mental poker is the problem of dealing a fair hand of cards between players who don't trust each other and only talk over a network, with no dealer and no physical deck. Adi Shamir, Ron Rivest and Leonard Adleman, the three letters in RSA, solved it in 1979 with encryption that can be applied and removed in any order. The same trick gives a Secret Santa draw that no single person controls, and it's also the reason ours doesn't work that way.

The question Floyd asked

Robert W. Floyd put it to them: can two players who don't trust each other play a fair game of poker over the phone, without cards? Their technical report, Mental Poker (MIT/LCS/TM-125, February 1979), opens with a surprise. It first proves the job can't be done, then shows how to do it anyway.

The proof is about information. Suppose Alice and Bob end up with different hands, and everything they said to each other is on the record. If the transcript fixes which cards Bob holds, Alice, who saw all of it, could work out his hand. If it doesn't, Bob can't be sure which cards he holds either. With unlimited computing power, one of them always wins that argument. The escape is to give up on unlimited power. If working out the other player's hand would take longer than the universe has left, the game is fair in every sense that matters. That shift, from "impossible to know" to "infeasible to compute", is what almost all modern cryptography rests on.

Locks you can take off in any order

The tool they used is a commutative cipher: encrypting with Alice's key and then Bob's gives exactly the same result as Bob's and then Alice's, so either of them can remove their own layer first. It's the padlock trick from the treasure chest puzzle, and the cipher that does it is the one in the three-pass protocol: raise the message to a secret power modulo a shared prime p. Alice's lock is x ↦ x^a mod p, Bob's is x ↦ x^b mod p, and since (x^a)^b = (x^b)^a, the layers commute.

Dealing with it goes like this:

1. Write the 52 cards as 52 numbers. Alice locks every one with her key, shuffles the 52 locked cards, and sends them to Bob. Bob sees 52 meaningless numbers in an order he didn't choose.
2. Bob picks five for Alice and sends them back. She removes her lock and reads her hand. Bob doesn't know what he gave her.
3. Bob picks five more for himself, adds his own lock, and sends them to Alice. She removes her layer (allowed, because the locks commute) and sends them back, now under Bob's lock alone. Bob removes it and reads his hand. Alice never saw his cards unlocked.
4. At the end of the game both reveal their keys, so each can check the other dealt honestly.

Nobody acted as dealer, and nobody could steer the deal. Alice shuffled, but blind to what Bob would pick. Bob picked, but blind to what the cards were.

The leak, and what it taught

There was a flaw, and Richard Lipton pointed it out in How to cheat at mental poker. Raising to a power modulo p keeps one property of a number visible: whether it's a perfect square modulo p (a quadratic residue). If the card numbers aren't chosen with care, a player can sort the locked cards into two piles and tell, say, which locked cards are hearts. It isn't the whole hand, but in poker even one bit is cheating. Fixes followed, and the bigger lesson stuck: a protocol can be secure against what you meant to hide and still leak something you didn't think of. Shafi Goldwasser and Silvio Micali's 1982 paper on probabilistic encryption, which hides every partial fact about a message, was titled in part How to Play Mental Poker Keeping Secret All Partial Information.

A Secret Santa nobody controls

A Secret Santa draw is a shuffled deck where every player is also a card. Mental poker says a group can deal it with no organizer at all. Here's one way to do it, simplified from the kind of protocol Sjouke Mauw, Saša Radomirović and Peter Ryan presented in 2010 (theirs also handles cheating and the case where a loop isn't wanted):

1. Each person makes a fresh, anonymous key pair, never linked to their name, and puts the public key in an envelope. All the envelopes go in a pile.
2. The pile goes round the group. Each person, in turn, adds a commutative layer of their own to every envelope and shuffles the pile. Then it goes round again and everyone takes their layer off. Each person saw only their own shuffle, so nobody can say which envelope came from whom.
3. The keys are laid out in their final order, in a circle. Everyone can see the list, but each person recognizes only their own key.
4. Each person encrypts their own name under the key just before theirs in the circle and posts it. Only the holder of that key, their Santa, can read it. Because it's a circle, nobody can land on themselves, and the result is always one big loop.

Nobody, the organizer included, ever learns more than their own assignment. It works.

Why our Secret Santa doesn't do this

Look at step 2 again. Everyone has to take a turn, in order, and the pile can't move on until they do. Then everyone has to take a second turn. In practice that means the whole family online at the same time, or a draw that waits days for the uncle who checks his phone once a week. And if anyone vanishes mid-protocol, the draw stalls for everyone.

Ours makes a different trade. Our Secret Santa lets one browser, the organizer's, draw for about a second, seal every person's result into their own encrypted card, and forget the pairing. The server stores only ciphertext. The organizer never sees a pair on screen, a card shows its owner whether anyone opened it before them, and after Forget the links the organizer's page can't open a card at all.

What's left is exactly one gap: an organizer who opens developer tools and stops the code during that second could read the draw. We say so on the page itself. For an office party it's a gap nobody will use. If your group really needs no trusted person at all, the protocol above is the answer, and it's worth the coordination.

Common questions