Secure multi-party computation

Secure multi-party computation (MPC) allows $n$ parties, each holding a private input $x_i$, to jointly compute a function $f(x_1,\dots ,x_n)$ such that each party learns only its designated output and nothing else about the other parties’ inputs. The fundamental question of whether this is possible was raised by Yao — Yao82.

Syntax

An $n$-party MPC protocol is a collection of $n$ interactive algorithms $({\Pi }_1,\dots ,{\Pi }_n)$ where party $i$ runs ${\Pi }_i$ with input $x_i$ and random coins $r_i$. Security is formalized via the real/ideal paradigm: the real execution of $({\Pi }_1,\dots ,{\Pi }_n)$ is indistinguishable from an ideal execution in which a trusted third party receives all inputs, computes $f$, and returns the outputs.

Properties

Correctness

All honest parties output the correct value $f(x_1,\dots ,x_n)$ with overwhelming probability.

Privacy (semi-honest)

In the semi-honest (or honest-but-curious) model, corrupted parties follow the protocol faithfully but try to learn extra information. Privacy requires that the view of any subset of semi-honest corrupted parties is simulatable from their inputs and outputs alone.

Security (malicious)

In the malicious model, corrupted parties may deviate arbitrarily from the protocol. Full security requires simulation-based security against any such adversary, typically with guaranteed output delivery or fairness conditions.

Variations

Two-party computation (2PC)

The special case $n=2$ studied by Yao. Two-party protocols are typically built from oblivious transfer (OT) and garbled circuits.

Honest majority ($t<n/3$ or $t<n/2$)

When fewer than a threshold fraction of parties are corrupt, information-theoretic (unconditional) security is achievable. For $t<n/3$, perfect security against malicious adversaries is achievable; for $t<n/2$, statistical security is achievable with broadcast — BGW88.

Dishonest majority (threshold up to $n-1$)

With $n-1$ malicious parties, computational assumptions are necessary. OT is sufficient and complete for this setting.

MPC with preprocessing (SPDZ, etc.)

A correlated randomness or “preprocessing” phase generates reusable correlated randomness offline; the online phase is highly efficient. Preprocessing can be instantiated from OT extension or homomorphic encryption.

Universal composability (UC)

The UC framework by Canetti provides a strong composable security notion for MPC — Can01.

Other results

• MPC with perfect security for any function when fewer than $n/3$ parties are corrupt (no cryptographic assumptions) — BGW88
• MPC with computational security for any function from OT — GMW87, Yao82
• OT is complete for (dishonest-majority) MPC — Kil88
• OT extension: $O(1)$ base OTs suffice to generate polynomially many OTs efficiently — IKNP03
• MPC implies OT in a black-box way for certain non-trivial functionalities — BH26
• COM is complete for two-party computation in the semi-honest model — GMW87
• Doubly-efficient RAM-MPC (computation sublinear in the database size) from LWE — LMW24
• Communication lower bounds for two-party differential privacy — HMST22