Secure Multiparty Computation Explained: Computing on Secrets

Two hospitals want to know whether a drug works better in one patient population than another. Neither is allowed to hand the other its patient records. A naïve answer is "they can't" — privacy law forbids it. Secure multiparty computation says otherwise: the two institutions can jointly compute the comparison and learn only the answer, while each set of records never leaves its owner. The math that makes this possible is one of the strangest and most useful results in modern cryptography.

Most encryption protects data at rest or in transit. Secure multiparty computation (MPC) protects data in use. It is the cryptographic answer to a question that sounds impossible: how can a group of parties who don't trust each other compute a function of their combined private inputs, such that everyone learns the output and no one learns anyone else's input?

The problem MPC solves

The canonical illustration is Yao's Millionaires' Problem, posed by Andrew Yao in 1982. Two millionaires want to know who is richer, but neither wants to disclose their net worth. They want to compute a single bit — "is A's wealth greater than B's?" — without revealing the numbers that feed the comparison.

Generalize that and you get the whole field. Replace "who is richer" with any computable function, and replace two millionaires with any number of participants, and you have the MPC problem. The participants might be hospitals, banks, election authorities, or the components of a cryptocurrency custody system. What unites them is that they have private inputs, a shared interest in some result, and a refusal — legal, commercial, or adversarial — to pool their raw data.

How it actually works

There is no single MPC algorithm. There are several families, and real systems mix them. Three building blocks recur.

Secret sharing. A private value is split into "shares" distributed among the parties, such that any individual share reveals nothing, but a sufficient subset can reconstruct the value. Shamir's secret sharing is the classic scheme — the same primitive used to split a master key into recovery fragments. In MPC, the parties don't reconstruct the secret; they perform arithmetic directly on the shares. Adding two secret-shared numbers is as simple as each party adding its local shares; multiplication is harder and requires interaction, which is where most of the protocol complexity and network cost live.

Garbled circuits. Yao's other great contribution. One party ("the garbler") expresses the function as a Boolean circuit and encrypts — "garbles" — every gate so its truth table is scrambled. The other party ("the evaluator") runs the garbled circuit without ever learning the intermediate wire values. To feed in its own inputs, the evaluator uses oblivious transfer, a protocol that lets it retrieve exactly the encryption keys corresponding to its input bits without the garbler learning which ones it chose.

Oblivious transfer (OT). The quiet workhorse. In 1-out-of-2 OT, a sender holds two messages and a receiver picks one; the receiver gets only its chosen message and the sender never learns which was chosen. OT turns out to be sufficient to build all of MPC, and modern "OT extension" techniques generate millions of transfers cheaply from a small number of expensive base ones — the single biggest reason MPC went from theoretical curiosity to deployable system.

Threat models: who are you protecting against?

MPC security comes in flavors that matter enormously in practice. The cheap version assumes semi-honest (also called "honest-but-curious") adversaries: parties that follow the protocol correctly but try to learn what they can from the messages they see. The expensive version defends against malicious adversaries that deviate arbitrarily — sending malformed shares, lying about computations, aborting to leak information.

Many real deployments quietly assume semi-honest behavior because the participants have reputational or legal incentives not to cheat. That is a perfectly defensible engineering choice — but it is a choice, and it should be stated, not buried. A semi-honest protocol gives no protection against a party that actively manipulates its messages.

Where MPC is already running

MPC stopped being purely academic more than fifteen years ago. The first large-scale practical deployment was a 2008 Danish sugar-beet auction, where farmers and the sole buyer used MPC to clear a market price without any party — including the auctioneer — seeing individual bids.

In 2017, the City of Boston worked with researchers to compute aggregate gender and racial pay gaps across participating employers using MPC, so that no company had to expose its individual payroll data to a regulator or to competitors. The same shape — pooled statistics without pooled data — drives privacy-preserving analytics across healthcare and finance today.

The fastest-growing use is key custody. "MPC wallets" split a private signing key into shares held by different devices or parties, so that signing a transaction is itself an MPC: the signature is produced without the full key ever existing in one place. This is closely related to Shamir's secret sharing, but stronger — with threshold signatures the key is never reassembled even momentarily.

"The dream of MPC is to make data useful without making it exposed. That is also, almost word for word, the dream of privacy engineering."

How MPC relates to its cryptographic cousins

MPC is often confused with two adjacent technologies. Homomorphic encryption lets a single party compute on data that stays encrypted the whole time — no interaction needed, but historically far slower. MPC distributes the computation across parties and uses interaction instead of heavy single-party crypto, which often makes it faster for real workloads. Zero-knowledge proofs let one party convince another that a statement is true without revealing why; MPC computes a joint output rather than proving a fact. The three are complementary, and modern privacy systems frequently combine all three.

The honest limitations

MPC is not magic, and three caveats deserve to be stated plainly. First, it is communication-heavy: multiplication and malicious-secure variants require rounds of network interaction, so latency and bandwidth — not CPU — are usually the bottleneck. Second, it protects inputs, not outputs: a carelessly chosen function can leak almost everything through its result. Third, it assumes a threshold of honest participants; collusion above that threshold breaks the guarantee, which is why who holds the shares is as important as the cryptography.

None of this diminishes the achievement. MPC takes a problem that intuition says is unsolvable — useful computation on data you're not allowed to see — and makes it routine enough to clear auctions and custody billions in assets. As regulation tightens around data sharing, the ability to collaborate on results without surrendering raw data stops being a luxury and becomes infrastructure.