← Back to the Journal

Multi-party computation (MPC): the millionaire's dilemma

Multi-party computation (MPC): the millionaire's dilemma

1982. A Chinese mathematician, Andrew Yao, presents a short five-page paper at a computing conference. The first sentence poses a problem that sounds like a joke:

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth.

Two millionaires want to know who has more. Neither wants to say how much he has.

The usual solution is a notary. Both tell him their fortune, the notary compares and announces the result. It works, but now there is somebody who knows both figures. That somebody can talk, can be bribed, can have his papers stolen.

Yao proposes something else: a mathematical procedure to make the comparison without anyone, not even a notary, seeing the numbers.

That is how a field was born that today is called secure multi-party computation, or MPC. The idea is this: several parties, each holding a secret input, compute something together. At the end, each one knows the result and nothing else.

Slide: two ninja cats holding money bags, one thinking: does he have more than me?

With a deck of cards

It sounds impossible, but it can be done at a table with a deck of cards. You need clubs (♣), hearts (♥) and two people. Every card stays face down the whole time.

Slide: the ninja cat shuffling a deck on a wooden table

Let us say the largest possible fortune is 5. Alice has 3. Bob has 4.

Alice lays out a row of five cards: as many clubs as her fortune, and the rest hearts. Her row is ♣♣♣♥♥. A ramp that says “this far I go”.

Slide: the ninja cat lining up three clubs and two hearts over five face-down cards

Bob does something similar. He lays out another row of five, all clubs, but instead of filling with hearts like Alice, he puts a single heart at the position of his fortune: ♣♣♣♥♣. A pointer that says “here I am”.

Slide: Bob's row with a single heart in the fourth position

The two rows are interleaved, one card from Alice, one from Bob, always face down. Two filler cards are added at the end.

Slide: the ninja cat interleaving both rows and marking two dummy cards at the end

Then the deck is cut. Once, ten times, as many as you like. Each cut changes where the row starts, but not the order of the cards relative to each other. Now nobody knows which one is first.

Slide: the ninja cat cutting the deck in mid-air with his sword

Only Bob’s cards are turned over until his heart appears. You look at the card immediately to its left. That card is Alice’s, and it sits in the same position as Bob’s fortune.

Slide: the ninja cat with a magnifying glass looking at the card left of Bob's heart

If it is a heart, Alice’s ramp had already run out: Alice has less than Bob. If it is a club, Alice has the same or more.

Here it comes up a heart. Alice has less. Neither of them learned the other’s number.

The secret lies in the cut. If Bob could choose where to cut, he would know where the row begins and could work out Alice’s fortune. Because the cut is random, he cannot. Chance takes the notary’s place.

From cards to computers

1986. Yao publishes a second paper. Computers do not shuffle, so he proposes another way of doing the same thing: garbled circuits.

Any computation can be written as a circuit of logic gates, the smallest pieces a computer thinks with. One of the parties builds the circuit and encrypts each gate so that it works without showing what goes in or what comes out. The other party walks through it blind, gate by gate, and at the end obtains the result. Nothing else.

Slide: the ninja cat in front of a machine of pipes and safes with AND, XOR gates and valves

Forty years of improvements have been added since, but the idea is the same. And it comes with a condition: whatever you want to compute has to be writable as a circuit.

Slide: the comparison table between the card trick and the cryptographic version

The price

MPC is slow. Much slower than sending the data to a server and letting it do the maths. Every encrypted gate travels over the network, and a serious computation has millions of them.

That is why it is not used for everything. It is used when the data cannot leave, by law, by contract or out of prudence. There, the alternative to slow is not happening at all.

There are three ways to compute with someone else’s data:

How it is computedSpeedWho sees the dataHow many parties
The ordinary cloudhighthe server, all of itone
Homomorphic encryptionvery lownobodya single owner of the data
MPClownobodyseveral, connected

MPC is the only one of the three where the secret is never complete in any single place. And the only one where the parties have to be connected and agree in advance on what they are going to compute.

Denmark, 2008

MPC’s first real use was not in a bank or in the army. It was in the fields.

January 2008. The European Union reforms the sugar market, and Denmark has to redistribute its beet production contracts among its farmers. The fair way is an auction where each one bids what he wants without the others seeing his bid. Neither the sugar company nor the growers’ association wants to show its numbers to the other, and neither wants an intermediary holding every bid.

So the auction is run with MPC. The clearing price comes out. No individual bid is ever seen.

Slide: the ninja cat as a detective in a vegetable market, with a giant beet to one side

Boston, real salaries

The second case is Yao’s problem with real salaries.

In Boston, a council of working women wants to measure how much less women and people of colour are paid. It needs the salaries of many companies that compete with each other for the same people. None of them will hand over its payroll.

With Boston University they build the computation with MPC. In 2016, 69 companies take part with 112,600 employees. The salaries are never gathered into a single database. One public number comes out: the gap.

They repeat it six times between 2015 and 2023. In the last one, the sample covers 17 % of the region’s workforce.

The cat and its shadow

Slide: the ninja cat and its own shadow, with an ace of hearts on the table

«True privacy does not consist in hiding from the world, but in collaborating with it without having to hand over what is yours.»

Encrypting means hiding a piece of data so that nobody can read it. MPC does something else: it lets you use the data with others without handing it over.

It is the same idea that keeps coming back across this series. PeerDAS verifies a block without downloading it. Ğ1 verifies that someone is a person without a central registry. A stealth address gets paid without anyone being able to link payer and payee. Always the same thing: doing something with information without owning it.

Today, computing with someone else’s data is almost always done the way it was in the first scene: you hand over the data and trust the other party. It is faster, and it works as long as the other party behaves.

Yao found a third way out in 1982, with two invented millionaires and a deck of cards: not having to trust anyone.