Compute on Data Without Seeing It

Two millionaires want to know who’s richer. Neither wants to reveal their net worth. Can they figure it out?

Yes. This is Yao’s Millionaires’ Problem, and it’s been solvable since 1982.

The solution generalizes: any computation can be done on private data from multiple parties, with no one learning anything except the result.

How It Works

The key insight is secret sharing. Split a number into random pieces that sum to the original. Give each piece to a different party.

Secret: 42
Share 1: 17 (random)
Share 2: 25 (42 - 17)

Neither share reveals anything. Together they reconstruct the secret.

Now the clever part: you can do math on shares. If I have shares of X and you have shares of Y, we can compute shares of X + Y without either of us learning X or Y.

Multiplication is harder but possible. And addition and multiplication are enough to compute anything.

The Trade-off

Secure computation is slow. The parties need to communicate a lot. Simple operations that take nanoseconds normally can take milliseconds in secure computation.

But for some problems, it’s the only option. When the alternative is “we can’t compute this at all because no one will share their data,” slow beats impossible.

Real Applications

Private auctions: Bidders submit encrypted bids. The auction computes the winner without revealing losing bids.

Salary benchmarking: Companies learn how their salaries compare to competitors without revealing individual salaries.

Medical research: Hospitals compute statistics across combined patient data without sharing patient records.

Private machine learning: Train models on data from multiple sources without centralizing the data.

The Future

Secure computation used to be theoretical. Now it’s practical for many applications. Not all of them (the overhead still matters) but the boundary keeps moving.

The dream is a world where we get the benefits of shared data without the risks of sharing it. We’re not there yet. But we’re closer than most people realize.