The millionaires' problem (Yao, 1982)

Imagine two millionaires meeting at a dinner party. Each is curious: which of the two is richer? But neither wants to reveal the exact amount of their fortune. This little puzzle, posed by Andrew Yao in 1982, founded an entire field of cryptography.

The millionaires' problem

Alice has a fortune a, Bob a fortune b. They want to know the outcome of the comparison — whether a > b, a < b or a = b — without Alice learning b, or Bob learning a.

The naive solution would be to entrust the two figures to a trusted third party who would make the comparison and announce the winner. But such an arbiter does not always exist: they would have to be completely trusted, and they would then know both fortunes. Yao showed that this arbiter can be dispensed with.

From the special case to the general case

The millionaires' problem is just one example. Its generalization is called secure multiparty computation (often abbreviated MPC).

Several parties, say P1, P2, ..., Pn, each hold a private input x1, x2, ..., xn. They want to jointly compute a common function:

resultat = f(x1, x2, ..., xn)

The guarantee sought is twofold:

• Correctness: the computed result really is f(x1, ..., xn), the true value.
• Confidentiality: each party learns only the result, and nothing more about the others' inputs than what the result itself reveals.

The central idea in one picture

   x1 (privé)  x2 (privé)  x3 (privé)
      \           |           /
       \          |          /
        +---------+---------+
        |  protocole MPC    |   <- personne ne voit x1, x2, x3
        +---------+---------+
                  |
                  v
             f(x1,x2,x3)          <- seul le résultat sort

The inputs enter on one side, encrypted or split up; only the result comes out. No party, and no observer, has access to the individual inputs.

What is it good for?

The applications are numerous whenever actors want to cooperate without trusting one another:

• Sealed-bid auctions: determine the highest bidder without disclosing the losing bids.
• Salary statistics: compute the average salary of a group without any employee revealing their own.
• Cross-hospital medical analyses: combine patient data across institutions for research, without sharing individual records.

In each case, the aggregate value is useful to everyone, but the raw data must remain private. MPC makes exactly this possible.

In summary

MPC lets several parties compute a function of their private inputs so that each learns only the result, never the others' inputs. Yao's millionaires' problem (1982) is the founding example; auctions, statistics and medical analyses are concrete uses.