Secure Multi-Party Computation: The Protocol That Lets Strangers Compute Together

In 2008, the Danish sugar beet industry faced a problem that no conventional technology could solve. Sugar beet farmers needed to determine the market-clearing price for their crop, which required each farmer to submit their production costs and capacities. But no farmer would reveal their private cost data to competitors, the industry association, or any central authority. The information was too commercially sensitive. Yet without it, the market could not function efficiently.

The solution was a secure multi-party computation protocol deployed by researchers at the University of Aarhus. Each farmer submitted their data in encrypted shares distributed across three independent computation servers. The servers jointly computed the market-clearing price – performing additions, comparisons, and optimizations on the encrypted data – without any single server ever seeing any farmer’s private input. The result was a correct, optimal price computed from data that no one could see.

This was MPC’s first large-scale real-world deployment. By 2025, MPC was securing over $50 billion in cryptocurrency assets through threshold wallets (Fireblocks, Coinbase, BitGo), enabling privacy-preserving medical research across hospital networks, and powering sealed-bid auctions for government spectrum licenses. The $1.2 billion MPC market is projected to exceed $5 billion by 2030.

The Core Problem

Secure multi-party computation addresses a deceptively simple question: can n parties, each holding a private input x_i, jointly compute a function f(x_1, x_2, …, x_n) such that each party learns the output but nothing about any other party’s input beyond what is revealed by the output itself?

The trivial solution – send all inputs to a trusted third party who computes f and returns the result – works perfectly if such a party exists. MPC exists because it does not. In practice, no party is trusted. Every party is a potential adversary. The protocol must guarantee correctness and privacy even when some participants actively try to cheat.

The theoretical foundations were established by Andrew Yao in 1982 (for two parties) and Goldreich, Micali, and Wigderson in 1987 (for multiple parties). Their results proved that any function computable by a Turing machine can be computed securely in the multi-party setting. This is a completeness result – it means MPC can, in principle, replace any trusted third party for any computation.

Secret Sharing: The Building Block

Shamir’s Secret Sharing

The most fundamental MPC technique is Shamir’s Secret Sharing (1979). It splits a secret value s into n shares such that:

• Any t shares (the threshold) can reconstruct the secret
• Fewer than t shares reveal absolutely nothing about the secret (information-theoretically secure)

The mechanism uses polynomial interpolation over a finite field:

1. Choose a random polynomial p(x) of degree t-1 where p(0) = s (the secret is the constant term)
2. Evaluate the polynomial at n distinct points: share_i = p(i) for i = 1, 2, …, n
3. Distribute share_i to party i

To reconstruct, collect any t shares and use Lagrange interpolation to recover p(0) = s.

Example: To share the secret s = 42 with n = 5 parties and threshold t = 3, choose a random quadratic polynomial: p(x) = 42 + 17x + 8x² (where 17 and 8 are random coefficients). The shares are p(1) = 67, p(2) = 108, p(3) = 165, p(4) = 238, p(5) = 327. Any three shares reconstruct the polynomial and recover 42. Any two shares are consistent with every possible secret value.

Why Sharing Enables Computation

The critical insight is that Shamir shares are additively homomorphic. If party i holds a share of secret a and a share of secret b, they can locally compute a share of (a + b) by simply adding their two shares. No communication required.

Multiplication is harder. Computing shares of (a × b) from shares of a and shares of b requires an interactive protocol (such as Beaver triples or the BGW protocol) where parties exchange carefully constructed messages. This multiplication protocol is the bottleneck of most MPC systems.

An MPC computation proceeds as:

1. Each party secret-shares their input among all parties
2. Parties jointly evaluate the function gate by gate:
   • Addition gates: local computation (no communication)
   • Multiplication gates: interactive protocol (requires message exchange)
3. Parties reconstruct only the output by pooling their output shares

At every intermediate step, each party holds only random-looking shares that reveal nothing about the actual intermediate values. Privacy is maintained throughout the computation.

Garbled Circuits: Yao’s Protocol

An alternative approach to MPC, specifically optimized for the two-party case, is Yao’s Garbled Circuits protocol.

How Garbled Circuits Work

1. Circuit representation. The function to be computed is expressed as a Boolean circuit of AND, OR, XOR, and NOT gates.

2. Garbling. One party (the “garbler”) assigns random cryptographic labels to each wire in the circuit – two labels per wire, one representing 0 and one representing 1. For each gate, the garbler creates an encrypted truth table: four ciphertexts, one for each input combination, each encrypting the output label corresponding to that combination under the two input labels.

3. Transmission. The garbler sends the entire garbled circuit (all encrypted truth tables) to the evaluator, along with the labels corresponding to the garbler’s own input.

4. Oblivious Transfer (OT). The evaluator needs the labels corresponding to their own input, but the garbler must not learn which labels the evaluator selected (that would reveal the evaluator’s input). This is solved by oblivious transfer – a cryptographic protocol where the evaluator obtains exactly one of two values from the garbler without the garbler learning which one was selected.

5. Evaluation. The evaluator, holding one label per input wire, evaluates the circuit gate by gate. At each gate, they decrypt the one truth table entry that corresponds to their pair of input labels, obtaining the output label. They cannot decrypt the other three entries (and thus learn nothing about other input combinations).

6. Output. The final output wire labels are decoded to reveal the function’s output.

Performance

Garbled circuits require communication proportional to the circuit size. A modern garbled circuit for AES-128 evaluation contains approximately 6,800 AND gates and requires transmitting approximately 50 KB of garbled tables. With optimizations (free XOR, half-gates, point-and-permute), practical garbled circuit systems achieve throughput of millions of gates per second.

Oblivious Transfer: The MPC Primitive

Oblivious Transfer (OT) is a fundamental cryptographic primitive used in both garbled circuits and share-based MPC. In its simplest form (1-out-of-2 OT):

• The sender holds two values (m_0, m_1)
• The receiver holds a choice bit b
• After the protocol:
  • The receiver learns m_b (and nothing about m_{1-b})
  • The sender learns nothing about b

OT was proven by Kilian (1988) to be complete for secure computation – any MPC protocol can be constructed from OT alone. This makes OT the atomic primitive of the field.

OT Extension (Ishai et al., 2003) allows a small number of expensive “base OTs” (using public-key cryptography) to be extended into millions of cheap OTs using only symmetric-key operations. This technique reduced the cost of OT by 2-3 orders of magnitude and made large-scale garbled circuit computations practical.

Security Models: Honest-but-Curious vs. Malicious

MPC protocols are analyzed under two adversary models:

Semi-Honest (Honest-but-Curious)

Parties follow the protocol correctly but attempt to learn additional information from the messages they receive. This is the easier model to achieve and is sufficient when parties have economic incentives to follow the protocol (e.g., regulated financial institutions, consortium members).

Malicious

Parties can deviate from the protocol arbitrarily – sending incorrect messages, aborting early, or colluding. Security against malicious adversaries requires additional mechanisms:

• Zero-knowledge proofs to verify that each party’s messages are consistent with some valid input (ZKPs compose naturally with MPC)
• Commitment schemes to prevent parties from changing their input mid-protocol
• Authenticated secret sharing to detect corrupted shares

Malicious-secure protocols are typically 10-100x slower than semi-honest protocols. The SPDZ protocol (Damgard et al., 2012), widely used in practice, achieves malicious security with an offline preprocessing phase (which can be amortized) and an online phase that runs at near-semi-honest speeds.

Real-World Deployments

Cryptocurrency Custody (Threshold Wallets)

The largest commercial deployment of MPC is in cryptocurrency custody. A threshold wallet splits a private key into n shares held by different parties or devices. Signing a transaction requires t-of-n parties to participate in an MPC signing protocol – producing a valid signature without ever reconstructing the private key.

Fireblocks ($8 billion valuation as of 2023) secures over $50 billion in digital assets using MPC-based wallets. Their protocol uses a 2-of-3 or 3-of-4 threshold scheme where shares are distributed across the customer, Fireblocks, and a third-party cosigner.

Coinbase migrated its institutional custody to MPC wallets in 2023, replacing hardware security modules (HSMs) for key management. The advantage: MPC wallets have no single point of compromise. Even if one share is stolen, the attacker cannot sign transactions without the threshold number of shares.

This is a paradigm shift from traditional key management. In the HSM model, the private key exists as a complete, vulnerable object inside specialized hardware. In the MPC model, the complete private key never exists – not during generation, not during signing, not ever.

Salary Comparison

One of the most intuitive MPC applications: a group of employees wants to compute their average salary without any individual revealing their salary to anyone else.

The protocol is straightforward with additive secret sharing:

1. Each employee splits their salary into n random shares that sum to their salary
2. Each employee sends one share to each other employee (keeping one)
3. Each employee sums all shares they received
4. These partial sums are combined to compute the total
5. Divide by n for the average

No individual learns anything beyond the average. Companies like Blind (workplace transparency app) have used variants of this approach for anonymous salary comparison.

Medical Research

The Boston Women’s Workforce Council has used MPC since 2015 to analyze gender pay gaps across 150+ employers in the Boston area. Each company submits encrypted payroll data. The MPC protocol computes aggregate statistics (average salary by gender, role, and seniority) without any company seeing another’s data and without the researchers seeing individual-level data.

In healthcare, the Swiss SMPC consortium (2023) deployed MPC protocols to analyze patient data across 12 hospitals for cancer research. Each hospital retained custody of its patient records. The MPC protocol computed statistical models – survival curves, treatment efficacy comparisons – on the joint dataset without any hospital sharing raw patient data with any other hospital or with the researchers.

Sealed-Bid Auctions

The 2008 Danish sugar beet auction was the first, but the most economically significant deployment is in government spectrum auctions. Ofcom (UK telecommunications regulator) has evaluated MPC-based sealed-bid auctions where bidders submit encrypted bids, and the winner is determined through an MPC protocol without revealing any losing bid amounts.

The advantages over traditional sealed-bid auctions:

• No trusted auctioneer required (the auctioneer cannot see the bids)
• Bid manipulation is cryptographically prevented
• Losing bidders are protected from information leakage (competitors cannot learn their valuation)

Privacy-Preserving Machine Learning

MPC is increasingly used for privacy-preserving ML inference. The protocol:

1. The model owner secret-shares the model weights
2. The data owner secret-shares their input
3. Parties jointly compute the inference (matrix multiplications, activations) using MPC
4. Only the output (prediction) is revealed to the data owner

Cape Privacy, Opaque Systems, and Inpher have built commercial platforms for MPC-based ML. The overhead is significant – MPC inference on a ResNet-50 image classifier takes approximately 10 seconds compared to 10 milliseconds for plaintext inference (a 1,000x slowdown). For applications where privacy justifies latency – medical diagnosis, financial fraud detection, classified intelligence analysis – this trade-off is acceptable.

MPC vs. Other Privacy Technologies

MPC occupies a specific niche in the privacy-enhancing technologies landscape:

MPC’s unique advantage is its flexible trust model. Unlike FHE (which requires trusting the client to hold the key) or TEEs (which require trusting the hardware manufacturer), MPC distributes trust across multiple independent parties. As long as fewer than t parties are corrupted, security holds. This makes MPC particularly suited to consortium settings – multiple organizations that need to collaborate but do not trust each other.

Limitations

Communication complexity. MPC requires parties to exchange messages proportional to the circuit size. For complex functions, this means gigabytes of data exchange. WAN latency (50-200 ms round trips) compounds multiplicatively with circuit depth.

Party scaling. Most practical MPC protocols work with 2-10 parties. Scaling to hundreds or thousands of parties introduces quadratic communication overhead and coordination challenges.

Availability. MPC protocols typically require all parties (or at least the threshold number) to be online simultaneously. If parties are unavailable or unresponsive, the computation stalls.

Abort attacks. In many MPC protocols, a malicious party can cause the computation to abort after learning the output but before other parties receive it. Achieving “guaranteed output delivery” against malicious adversaries is possible but expensive.

The Stealth Cloud Perspective

Secure multi-party computation eliminates the need for a trusted central party – a principle that aligns directly with Stealth Cloud’s zero-trust architecture. Where traditional cloud services demand that users trust the provider, MPC distributes computation so that no single entity can access the complete data. For operations that require coordination between Stealth Cloud’s edge nodes – key management, aggregate analytics, model selection – MPC provides the mathematical guarantee that collaboration does not require compromising the zero-knowledge principle.