Secure Multi-Party Computation (MPC)

Introduction

Secure Multi-Party Computation (MPC) allows a set of parties, each holding private inputs, to jointly compute a function over those inputs without revealing anything beyond the output.
No single party learns another party's input, and no coalition of parties (below a defined threshold) can extract private data from the protocol's messages.

The problem was first formalized by Andrew Yao in 1982 for the two-party case and later generalized to the multi-party setting by Goldreich, Micali, and Wigderson.
The foundational result is striking: any function that can be computed by a trusted third party can also be computed securely by the parties themselves, assuming appropriate cryptographic primitives exist.
This means MPC is not limited to specific functions.
It is a general-purpose framework.

MPC has moved from theoretical curiosity to production deployment.
Real-world applications include privacy-preserving auctions, threshold key management, confidential benchmarking (e.g., comparing salaries without disclosure), federated analytics, and private set intersection for ad measurement.
Understanding MPC's core protocols, threat models, and performance trade-offs is increasingly relevant for engineers building systems that handle sensitive data across organizational boundaries.

Threat Models

MPC protocols are designed against two primary adversary models.

Semi-Honest (Honest-but-Curious)

All parties follow the protocol specification exactly, but may attempt to infer additional information from the messages they receive.
Protocols secure in this model are simpler and faster, but they assume no party deviates from the prescribed steps.
This model is appropriate when parties are institutionally trusted to follow the protocol (e.g., divisions within the same organization) but should not see each other's raw data.

Malicious

Corrupted parties may deviate arbitrarily from the protocol, sending incorrect values, aborting early, or colluding.
Security in this model requires additional machinery such as zero-knowledge proofs, commitment schemes, or authenticated secret sharing.
The overhead relative to semi-honest protocols was historically very large (orders of magnitude), but recent protocols (e.g., SPDZ variants, authenticated garbling) have substantially narrowed this gap, with practical overheads often in the range of 10x–100x depending on the protocol and circuit structure.

A key parameter is the corruption threshold t.
For n parties, protocols typically guarantee security when fewer than t parties are corrupted.
Common thresholds are t < n/2 (honest majority) and t < n (dishonest majority).
Honest majority protocols can achieve information-theoretic security (no computational assumptions), while dishonest majority protocols require cryptographic assumptions such as the hardness of discrete logarithms or the existence of oblivious transfer.

Core Techniques

Garbled Circuits (Yao's Protocol)

Yao's garbled circuits protocol handles the two-party case.
One party (the "garbler") encodes a Boolean circuit representing the target function.
Each wire in the circuit is assigned two random cryptographic labels, one for bit 0 and one for bit 1.
Each gate is encrypted so that given the labels on its input wires, only the correct output label can be recovered.
The other party (the "evaluator") obtains the labels corresponding to its input bits via oblivious transfer (OT), evaluates the garbled circuit gate-by-gate, and decodes the final output.

The garbled circuit reveals nothing beyond the output because the evaluator only ever sees one label per wire and cannot determine whether that label represents 0 or 1 (except for the output wires, where a decoding table is provided).

Secret Sharing (GMW and BGW)

For the multi-party setting, secret sharing is the dominant paradigm.
Each party splits its input into shares distributed among all parties.
Linear operations (addition, scalar multiplication) on shared values are free: each party performs the operation locally on its share.
Multiplication requires interaction, as it involves a degree-reduction step.

The BGW protocol, for example, uses Shamir secret sharing over a finite field.
With n parties and threshold t < n/2, it achieves information-theoretic security.
Each multiplication gate requires one round of communication among all parties.

Oblivious Transfer (OT)

Oblivious transfer is a fundamental two-party primitive.
In 1-out-of-2 OT, a sender holds two messages (m_0, m_1) and a receiver holds a choice bit b.
The receiver learns m_b and nothing about m_{1-b}.
The sender learns nothing about b.
OT is both necessary (in the sense that any protocol for non-trivial secure two-party computation can be used to implement OT) and sufficient (any function can be computed using OT as a building block) for general two-party secure computation under computational assumptions.
Efficient OT extension protocols allow generating millions of OTs from a small number of base OTs using only symmetric-key operations.

Walkthrough

The following walkthrough illustrates the BGW protocol for three parties computing the product of their private inputs using Shamir secret sharing with threshold t = 1.

Setup

• Three parties: P1, P2, and P3 with private inputs x1, x2, x3 in a finite field F_p.
• Goal: compute f(x1, x2, x3) = x1 * x2 * x3 without any party learning another's input.
• Shamir threshold: t = 1 (any single party's shares alone reveal nothing about the secret).

Step 1: Input Sharing

Each party Pi shares its input xi using a degree-1 polynomial:

Pi picks random ai ∈ F_p
Pi defines fi(z) = xi + ai * z
Pi sends fi(j) to each party Pj for j ∈ {1, 2, 3}
Pi retains fi(i) as its own share

After this step, each party Pj holds shares f1(j), f2(j), f3(j).

Aside: Local Addition

Before describing multiplication, note that Shamir sharing is linear, so addition requires no communication.

Pj computes its share of (x1 + x2 + x3) as f1(j) + f2(j) + f3(j)

This is not needed for the product computation below, but illustrates an important property: linear operations on secretly shared values are free.

Step 2: First Multiplication (Computing x1 * x2)

Multiplication is where interaction is necessary.
Each party Pj locally multiplies its shares of x1 and x2:

Pj computes hj = f1(j) * f2(j)

The values h1, h2, h3 lie on a degree-2 polynomial (the product of two degree-1 polynomials).
To reduce back to degree-1 (so further operations remain possible), the parties run a degree-reduction sub-protocol:

Each Pj treats hj as its "input" and re-shares it:
  Pj picks random bj ∈ F_p
  Pj defines gj(z) = hj + bj * z
  Pj sends gj(k) to each Pk

Each Pk computes its new degree-1 share of (x1 * x2) as:
  prod12_k = μ1 * g1(k) + μ2 * g2(k) + μ3 * g3(k)
  where μ1, μ2, μ3 are Lagrange recombination coefficients
  evaluated at z = 0 for points {1, 2, 3}

The Lagrange coefficients μ1, μ2, μ3 are public constants determined by the evaluation points.
After this step, each party holds a degree-1 share of x1 * x2.

Step 3: Second Multiplication (Computing x1 * x2 * x3)

Repeat Step 2 using the degree-1 shares of (x1 * x2) and the degree-1 shares of x3 (from Step 1) to obtain degree-1 shares of x1 * x2 * x3.

Step 4: Output Reconstruction

Each party sends its final share to all other parties.
Given three shares of a degree-1 polynomial, any party can reconstruct the result via Lagrange interpolation:

result = λ1 * share_1 + λ2 * share_2 + λ3 * share_3

where λ1, λ2, λ3 are the standard Lagrange basis coefficients for reconstruction at z = 0 from evaluation points {1, 2, 3}.
This yields x1 * x2 * x3 without any party having learned another's input.

Performance Considerations

MPC protocols involve fundamental trade-offs that engineers must evaluate for production use.

Communication complexity. The dominant cost in most MPC protocols is network communication, not computation.
Each multiplication gate in a circuit-based protocol requires at least one round of communication.
For deep circuits, round complexity becomes the bottleneck, especially over wide-area networks with high latency.

Circuit representation. Functions must be expressed as arithmetic or Boolean circuits.
The efficiency of an MPC protocol depends heavily on circuit size and depth.
A function that admits a small arithmetic circuit (e.g., inner products, polynomial evaluation) will be far cheaper to compute via MPC than one requiring a large Boolean circuit (e.g., comparisons, bit decompositions).

Preprocessing models. Many modern protocols (SPDZ, MASCOT, Overdrive) split execution into an offline phase and an online phase.
The offline phase generates correlated randomness (multiplication triples, authenticated shares) independent of the inputs.
The online phase, which depends on inputs, becomes very fast because it consumes precomputed material.
This amortizes the expensive cryptographic work.

Concrete costs. As a rough practical reference: private set intersection between two parties, each holding 1 million items, can run in under 5 seconds on a fast LAN using modern OT-based protocols.
Garbled-circuit-based two-party computation in the semi-honest setting can evaluate many millions of AND gates per second with OT extension, though exact throughput depends heavily on hardware, network bandwidth and latency, and implementation.
Engineers should benchmark against their specific circuit and deployment environment rather than relying on published headline numbers.

Practical Deployment Patterns

In production systems, MPC is often combined with other privacy-enhancing technologies.
Threshold signature schemes use MPC to distribute private key operations across multiple servers, so no single server holds the full key.
Privacy-preserving machine learning uses MPC for inference on encrypted inputs.
Private set intersection (PSI), a specialized MPC protocol, sees wide deployment in ad conversion measurement and contact discovery.

Engineers deploying MPC should be aware of several operational concerns.
Abort handling matters: in the dishonest majority setting, a malicious party can always force the protocol to abort (guaranteed output delivery is impossible without honest majority).
Network topology affects performance: point-to-point links scale as O(n²) and become costly beyond a few dozen parties.
And the choice of finite field or ring affects both the circuit representation and the underlying arithmetic efficiency.

Key Points

• MPC enables joint computation over private inputs without revealing those inputs, achieving the functionality of a trusted third party through cryptographic protocols.
• The two foundational approaches are garbled circuits (primarily two-party) and secret-sharing-based protocols (multi-party), each with distinct performance profiles.
• Security guarantees depend on the adversary model (semi-honest vs. malicious) and the corruption threshold relative to the number of participants.
• Multiplication gates require interactive communication, making circuit depth and multiplication count the primary cost drivers in practice.
• Preprocessing (offline/online) models like SPDZ dramatically improve online-phase performance by generating correlated randomness before inputs are known.
• Oblivious transfer is both a necessary and sufficient primitive for general two-party secure computation under computational assumptions, and scales efficiently through OT extension.
• Production deployments commonly use MPC for threshold cryptography, private set intersection, and confidential analytics, rather than general-purpose computation.

References

Yao, A. C. "Protocols for Secure Computations." Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), 1982, pp. 160–164.

Goldreich, O., Micali, S., and Wigderson, A. "How to Play Any Mental Game." Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), 1987, pp. 218–229.

Ben-Or, M., Goldwasser, S., and Wigderson, A. "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation." Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), 1988, pp. 1–10.

Damgård, I., Pastro, V., Smart, N. P., and Zakarias, S. "Multiparty Computation from Somewhat Homomorphic Encryption." Advances in Cryptology (CRYPTO), Springer LNCS vol. 7417, 2012, pp. 643–662.

Evans, D., Kolesnikov, V., and Rosulek, M. "A Pragmatic Introduction to Secure Multi-Party Computation." Foundations and Trends in Privacy and Security, vol. 2, no. 2–3, 2018. https://doi.org/10.1561/3300000019