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 — Yao82b.

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. Security with abort requires simulation-based security against any such adversary in an ideal model where the adversary receives its output first and may then deny the honest parties theirs; full security additionally guarantees output delivery, which a dishonest majority cannot achieve for every functionality — Cle86.

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

When fewer than a threshold fraction of parties are corrupt, information-theoretic (unconditional) security is achievable.

Honest majority ($t<n/3$)

For $t<n/3$, perfect security against malicious adversaries is achievable — BGW88.

Honest majority ($t<n/2$)

For $t<n/2$, statistical security against malicious adversaries is achievable with broadcast — RB89.

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

• Honest majority ($t<n/3$) ⇒ MPC
• Honest majority ($t<n/2$) ⇒ MPC
• UC-secure OT ⇒ MPC
• Semi-honest OT ⇒ MPC (HIKLP)
• OT extension: $O(\lambda )$ base OTs suffice to generate polynomially many OTs efficiently — IKNP03
• Ring-LWE ⇒ DE-RAM-MPC
• Communication lower bounds for two-party differential privacy — HMST22

Participates in

Builds on Secure multi-party computation

• Honest majority ($t<n/2$) ⇒ MPC (via Honest majority ($t<n/2$))
• Honest majority ($t<n/3$) ⇒ MPC (via Honest majority ($t<n/3$))
• Semi-honest MPC + OWF ⇒ MPC (GMW compiler) (via Privacy (semi-honest))
• 2PC ⇒ OT (via Two-party computation (2PC))

Produces Secure multi-party computation

• Additively homomorphic encryption ⇒ MPC with preprocessing (BDOZ) (via MPC with preprocessing (SPDZ, etc.))
• GC + OT ⇒ Two-party computation (2PC) (via Two-party computation (2PC))
• SHE ⇒ MPC with preprocessing (SPDZ) (via MPC with preprocessing (SPDZ, etc.))
• Honest majority ($t<n/2$) ⇒ MPC
• Honest majority ($t<n/3$) ⇒ MPC
• OT Extension ⇒ MPC with preprocessing (SPDZ, etc.) (via MPC with preprocessing (SPDZ, etc.))
• Semi-honest OT ⇒ MPC (HIKLP)
• UC-secure OT ⇒ MPC
• Semi-honest MPC + OWF ⇒ MPC (GMW compiler)