How can two millionaires learn who is richer without revealing their fortunes?
Two rich people want to know who has more money, and neither will say how much. A 1982 puzzle turned into a whole branch of cryptography.
▶ Start the storySecure multi-party computation, or MPC, lets several parties jointly compute something from their private inputs while keeping those inputs private. Its classic puzzle is Yao's Millionaires' problem, introduced in 1982 by Andrew Yao: two millionaires, Alice and Bob, want to know which of them is richer without revealing their actual wealth.
The usual way to explain the goal is with a trusted friend. Suppose Alice, Bob and Charlie want to find the highest of their three salaries. A mutual friend, Tony, who can keep a secret, could hear all three and announce the maximum. MPC aims for a where, by exchanging messages only with each other, the three learn the same result without revealing who makes what and without relying on Tony. They should learn no more than they would from an incorruptible, perfectly trustworthy Tony.
A trusted friend
- Everyone tells Tony their salary
- Tony announces the maximum
- Everyone must trust Tony
MPC
- Parties only exchange messages with each other
- Everyone learns the result
- Nobody learns more than the result
How can that work? The building block is secret sharing. Each party splits its input into shares, random values that add up to the input, and any incomplete set of shares looks randomly distributed. Yao's own approach for two parties was to a , hiding its structure so that the two learn the output of the circuit and nothing else. The extension to many parties was later built on secret sharing of all the inputs.
It is no longer only a puzzle. MPC is now considered a practical solution for distributed voting, private bidding and auctions, sharing of signature or decryption functions, and private information retrieval. The first large-scale practical use was an electronic , the Danish Sugar Beet Auction, in January 2008. The catch is cheating: security against active adversaries typically costs efficiency.
Quiz me
0/3
Recap
MPC aims to teach the parties no more than a perfectly trustworthy outside friend would, using shares in place of that friend.
💡 A trick to remember it · Swap secret pieces, add what you hold, announce your sum: the answer appears and Tony was never needed.
Surprising fact · Yao posed the millionaires' puzzle in 1982, yet the first large-scale practical use came only in 2008, in a Danish sugar beet auction.
Connects to
- 🧩 How can a secret be split so that no single person holds it?
- 📈 How can any 3 of 5 people unlock a secret with a curve drawn through points?
- 🔏 How can three of five devices sign a transaction without the key ever existing in one place?
- 🔨 Why would an auction make the winner pay only the second-highest bid?
- 🏛️ What does "democracy" actually mean?
Sources (2)
No source, no claim. Every fact in this lesson (15 claims) cites at least one of these.