The millionaires' problem

Two millionaires want to know which of them is richer. Neither is willing to say how much they have, not to each other and not to anyone else. Can they find out anyway? The answer is yes, and the techniques behind it let any group compute almost anything from private data that nobody ever reveals.

The puzzle

Andrew Yao posed the millionaires' problem in 1982, and it launched a whole field called secure multi-party computation, or MPC. Yao later won the Turing Award, partly for this work.

The general version goes like this. Several people each hold a private input. They want to compute some function of all the inputs together: a total, an average, a comparison, the winner of an auction, the overlap between two customer lists. Everyone should learn the result, and nothing else. Not the other inputs, not partial results, nothing.

It sounds like it must be impossible, because computing something seems to require seeing the data. It isn't.

The perfectly trusted friend

There's an easy solution if you have a friend both millionaires trust completely. Each whispers their wealth to the friend, the friend announces “Alice is richer”, and then the friend forgets everything forever.

MPC uses this imaginary friend as its definition of success. A protocol is secure if it gives every participant exactly what they'd get from the trusted friend, and nothing more, even though no such friend exists. The participants simulate the friend among themselves, by exchanging carefully constructed messages that look like random noise.

Adding secrets you can't see

Start with an easier problem than comparing. Four colleagues, Ana, Ben, Cara and Dev, want to know their average salary without anyone revealing their own. The trick is called additive secret sharing.

1. Split Each person splits their salary into four random-looking numbers, called shares, that add up to the salary. Three shares are chosen at random; the fourth is whatever makes the total work. The arithmetic wraps around at ten million, like a clock, so the shares look like pure noise.
2. Hand out Each person keeps one share and gives one to each colleague. A single share, or even three of the four, reveals nothing about the salary.
3. Add up locally Each person adds up the four shares they're holding, one from everyone, and announces that sum.
4. Combine The four announced sums add up to the total of all salaries. Divide by four for the average.

Pick any one person's view. Everything they receive is a share that looks completely random, and the only meaningful numbers they see are their own salary and the announced sums. Even if three people pool what they hold, the fourth person's shares still look random. Their combined knowledge is the total, minus their own salaries.

Comparing is harder

Addition worked because adding shares adds the hidden values. Comparison doesn't work like that: there's no way to add up shares and get “who's bigger”. Yao needed a new ingredient.

Here's a physical version of the idea, for wealth between £1 million and £10 million. Bob takes ten envelopes, labelled 1 to 10. In each one he seals a card saying what the answer would be if Alice had that many millions: “Bob is richer”, “Equal” or “Alice is richer”. He hands Alice the envelopes. Alice opens only the envelope matching her own wealth, reads the answer, and shreds the rest unopened.

That works, but only if two things hold. Bob mustn't see which envelope Alice opened, and Alice mustn't peek inside any others. In the physical world you'd need a referee. Cryptography replaces the referee with a protocol called oblivious transfer.

Oblivious transfer: the magic trick

In an oblivious transfer, a sender holds several messages, and a receiver gets exactly one of them, of their choice. The sender doesn't learn which one was taken, and the receiver learns nothing about the others. Michael Rabin introduced the idea in 1981. The version below, built from RSA, is from Shimon Even, Oded Goldreich and Abraham Lempel in 1985, extended here from two envelopes to ten.

It's a short exchange of three messages. Step through it and watch what each side actually sees. If you haven't met RSA yet, the public-key cryptography lesson builds one by hand.

Why Bob learns nothing: the number Alice sends is her chosen envelope's random number plus k^e, and k is a fresh random number only she knows. That sum is equally likely to be any value, whichever envelope she chose. Bob dutifully unlocks all ten envelopes with his private key, which gives ten keys that all look random to him.

Why Alice learns only one answer: exactly one of Bob's ten keys equals her k. That's the one she can remove. Undoing the others would mean reversing RSA without Bob's private key.

Computing anything: garbled circuits

Ten envelopes work for ten possible values. Real fortunes need millions of envelopes, and real computations are far more complicated than one comparison. In 1986, Yao showed how to handle any function at all, using garbled circuits.

Any computation can be written as a circuit of simple logic gates like AND, OR and XOR, the same way a computer chip works. Comparing two 30-bit numbers takes a few dozen gates. The idea is to scramble every gate so that it can be evaluated without anyone seeing the values flowing through it.

1. Replace bits with random labels The garbler, say Bob, picks two random labels for every wire in the circuit: one stands for 0, the other for 1. Only Bob knows which is which.
2. Encrypt each gate's truth table For each of a gate's four input combinations, Bob encrypts the correct output label using the two input labels as the key. Then he shuffles the four rows.
3. Hand over the right labels Bob sends the scrambled circuit and the labels for his own input bits. Alice gets the labels for her bits through oblivious transfer, so Bob never learns her bits.
4. Evaluate blind Holding one label per input wire, Alice can decrypt exactly one row of each gate, giving one output label. She works through the whole circuit seeing only random labels, and only the final output's meaning is revealed.

Alice sees four rows of noise, two labels that mean nothing to her, and exactly one row that decrypts. She never learns which input combination that row stood for, so she never learns Bob's bit. Chain enough of these gates together and two parties can compare fortunes, run an auction or match medical records, with every intermediate value hidden.

What the answer gives away

Remember the trusted friend: MPC promises nothing beyond what the answer itself reveals. Sometimes the answer reveals a lot. Test your intuition.

This is why designing an MPC system starts with a question that has nothing to do with cryptography: what's safe to reveal as the output? Real systems often only release results over large groups, or add deliberate noise, a technique called differential privacy.

It's used for real

For decades MPC was considered too slow to be practical. Faster protocols and computers have changed that.

The cost is communication. Every gate of a garbled circuit is sent across the network, so large computations can mean gigabytes of traffic. Much current research is about cutting that down.

Why this matters

• You can compute on data nobody shows you. A group can learn the result of a function of their private inputs, and nothing else.
• The trusted friend is the benchmark. A secure protocol gives everyone exactly what an imaginary, perfectly trustworthy third party would.
• A few building blocks do the work. Secret sharing for sums, oblivious transfer for choosing without revealing, and garbled circuits for everything else.
• The output always leaks something. Deciding what's safe to reveal is part of the design, not an afterthought.