Secure multi-party computation

A secure multi-party computation (MPC) protocol lets $n$ parties, party $P_i$ holding an input $x_i$, compute $f(x_1,\dots ,x_n)$ so that an adversary corrupting some of the parties achieves nothing beyond what it could in an ideal execution, in which a trusted party receives the inputs and hands each party its output. The notion is due to Yao82b for two parties and to GMW87 for $n$ parties.

Syntax

An $n$-party functionality is a possibly randomized map $f:(\{0,1{\}}^{\ast }{)}^n\to (\{0,1{\}}^{\ast }{)}^n$ computed by a polynomial-size circuit; party $P_i$ is to learn the $i$-th output $y_i$.

An $n$-party protocol is a tuple $\Pi =(\mathsf{Setup},P_1,\dots ,P_n)$ of efficient algorithms:

• $\mathsf{Setup}(1^{\lambda })\to \mathsf{pp}$, a common reference string; in the plain model $\mathsf{Setup}$ is trivial and $\mathsf{pp}=1^{\lambda }$.
• $P_i(\mathsf{pp},x_i)$, an interactive algorithm with private random coins that outputs $y_i$ or $\perp$.

The parties run in synchronous rounds over authenticated point-to-point channels between every pair and a broadcast channel. The adversary $\mathcal{A}$ corrupts a set $T\subseteq [n]$ fixed before the execution (static corruption), reads every message, and is rushing: it chooses the corrupted parties’ round-$r$ messages after seeing the honest parties’ round-$r$ messages. A protocol may in addition use secure channels, correlated randomness or an ideal functionality such as ideal OT; it is then secure in that model.

Each notion below is achieved if for every $n$ and every $n$-party functionality $f$ there is a protocol for $f$, running in time polynomial in $\lambda$, $n$ and the circuit size of $f$, that meets the notion.

Properties

Correctness

If no party is corrupted, the parties’ outputs $(y_1,\dots ,y_n)$ are distributed as $f(x_1,\dots ,x_n)$, up to negligible statistical distance.

Security with abort

The game compares the real execution (world $0$) with an ideal execution run by a trusted party (world $1$). The distinguisher $\mathcal{D}$ sees the reference string, chooses the inputs and the adversary’s auxiliary input $z$, and then sees the adversary’s output together with the honest parties’ outputs.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{mpc}}_{\Pi,f,\calA,\Sim,\calD}(\secpar)$}
\begin{algorithmic}
\State $b \getsr \bits$; $\pp_0 \gets \Setup(1^\secpar)$; $\pp_1 \gets \Sim(1^\secpar)$
\Comment{$\calA$ corrupts a fixed set $T \subseteq [n]$; $\Sim$ is stateful}
\State $(x_1, \ldots, x_n, z, \st) \gets \calD(1^\secpar, \pp_b)$
\State Run $\Pi$ with $P_i(\pp_0, x_i)$ for $i \notin T$ and $\calA(\pp_0, (x_i)_{i \in T}, z)$ controlling $(P_i)_{i \in T}$
\State $\mathit{out}_0 := (\text{output of } \calA, (y_i)_{i \notin T})$
\State $\mathit{out}_1 \gets \mathrm{Ideal}^{\mathrm{abort}}_{f,T}(x_1, \ldots, x_n, z)$
\State $b' \gets \calD(\st, \mathit{out}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\mathrm{Ideal}^{\mathrm{abort}}_{f,T}(x_1, \ldots, x_n, z)$}
\begin{algorithmic}
\State $(x_i')_{i \in T} \gets \Sim((x_i)_{i \in T}, z)$
\Comment{$\Sim$ may replace the corrupted parties' inputs}
\State $x_i' := x_i$ for $i \notin T$; $(y_1, \ldots, y_n) \gets f(x_1', \ldots, x_n')$
\State $d \gets \Sim((y_i)_{i \in T})$
\Comment{$\Sim$ sees the corrupted parties' outputs first}
\If{$d = \mathsf{abort}$}
\State $y_i := \bot$ for every $i \notin T$
\EndIf
\Return $(\text{output of } \Sim, (y_i)_{i \notin T})$
\end{algorithmic}
\end{algorithm}

A protocol $\Pi$ securely computes $f$ with abort against $t$ corruptions if for all efficient $\mathcal{A}$ corrupting a set $T$ of at most $t$ parties there is an efficient $\mathcal{S}$ such that for all efficient $\mathcal{D}$,

$${\mathbf{Adv}}_{\Pi ,f,\mathcal{A},\mathcal{S},\mathcal{D}}^{\mathrm{mpc}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,f,\mathcal{A},\mathcal{S},\mathcal{D}}^{\mathrm{mpc}}(\lambda )=1\right]-1\right|$$

is negligible. In world $1$ the simulator also produces the reference string, which $\mathcal{D}$ sees before choosing the inputs; in the plain model $\mathsf{pp}=1^{\lambda }$ and the order is immaterial. Up to that order, this is the stand-alone definition of Gol04. Statistical and perfect security require, for all possibly unbounded $\mathcal{A}$ and $\mathcal{D}$, a negligible and a zero advantage respectively. MPC is achieved when every functionality has a protocol that securely computes it with abort against $t=n-1$ corruptions, that is, against any number of corrupted parties. The abort is unanimous: every honest party outputs $\perp$, or every honest party outputs its value.

Semi-honest security

The corrupted parties run $\Pi$ honestly on their inputs, and $\mathcal{A}$ outputs their joint view. As above, $\mathcal{D}$ chooses the inputs after seeing the reference string, which $\mathcal{S}$ produces in world $1$. In world $1$ the trusted party computes $(y_1,\dots ,y_n)\leftarrow f(x_1,\dots ,x_n)$, the simulator receives $(x_i,y_i{)}_{i\in T}$ and can neither replace inputs nor abort, and the game outputs the simulator’s output together with $(y_i{)}_{i\notin T}$. A protocol is secure against semi-honest adversaries corrupting at most $t$ parties if for every such $T$ there is an efficient $\mathcal{S}$ such that for all efficient $\mathcal{D}$ the advantage, defined as above, is negligible. The notion is achieved when every functionality has such a protocol for $t=n-1$.

Neither this notion nor security with abort implies the other. A protocol secure against malicious adversaries is secure against augmented semi-honest adversaries, which may replace their inputs before the execution — Gol04 — but not in general against semi-honest adversaries, because the malicious-model simulator may replace the corrupted parties’ inputs and the semi-honest ideal execution forbids it — HL10.

Variations

Each notion below changes one component of security with abort or of semi-honest security: the number of parties, the corruption threshold, what the ideal execution guarantees the honest parties, the composition setting, the number of rounds, or the simulator’s running time. At a fixed threshold, guaranteed output delivery implies fairness and fairness implies security with abort, since each ideal execution is a restriction of the next; security against $t$ corruptions implies security against $t^{\prime }<t$; and a notion achieved for every $n$ is achieved for $n=2$ — folklore. UC security implies stand-alone security — Can01.

Two-party computation (2PC)

Security with abort for $n=2$: the adversary corrupts one party, receives that party’s output first, and may then make the other party output $\perp$. MPC gives it by taking $n=2$ — folklore.

Five-round 2PC

Two-party computation with expected polynomial-time simulation in the plain model ($\mathsf{pp}=1^{\lambda }$) by a protocol of five rounds, in each of which only one party sends a message, with a black-box simulator: an oracle algorithm $\mathcal{S}$, running in expected polynomial time, such that for every efficient $\mathcal{A}$ the simulator ${\mathcal{S}}^{\mathcal{A}}$, which runs $\mathcal{A}$ only as an oracle and may rewind it, meets the definition. It implies 2PC with expected polynomial-time simulation by the identity map (five-round 2PC ⇒ 2PC with expected-time simulation) — folklore. Every two-party functionality, each party receiving its own output, has such a protocol from certified trapdoor permutations (certified TDP ⇒ five-round 2PC) — KO04. Five rounds are necessary for a black-box proof of security: unconditionally, no four-round protocol of this kind securely computes the coin-tossing functionality for a super-logarithmic number of coins with a black-box proof — KO04. When only one party receives output, four rounds suffice — KO04 — also from enhanced trapdoor permutations used as a black box (enhanced TDP ⇒ 2PC with expected-time simulation) — ORS15.

Semi-honest two-party computation

Semi-honest security for $n=2$, which semi-honest security gives by taking $n=2$ — folklore. A two-party protocol secure with abort need not be semi-honest secure, for the reason above — HL10.

Fairness

Security with complete fairness against $t=n-1$ corruptions. The ideal execution lets $\mathcal{S}$ abort only before the trusted party computes $f$, in which case every party outputs $\perp$; otherwise every party receives its output. A fair protocol securely computes $f$ with abort, since the simulator can emulate an early abort by submitting arbitrary inputs and aborting once it has the outputs — folklore. When at least half of the parties may be corrupted, fairness is impossible for some functionalities: every $r$-round coin-flipping protocol can be biased by $\Omega (1/r)$ by an adversary that only aborts early — Cle86. A completely fair protocol for Boolean XOR, run on uniform inputs, would be a coin flip with negligible bias, so XOR has no completely fair two-party protocol over authenticated channels without setup and the notion is not achieved (no reduction from authenticated channels to fair MPC) — Cle86.

Complete fairness is ruled out for XOR, not for every function. Under standard cryptographic assumptions, every two-party function over polynomial-size domains without an embedded XOR, including Boolean AND and OR and Yao’s millionaires’ problem, has a completely fair protocol; some functions with an embedded XOR do too, but every completely fair protocol for them needs a number of rounds super-logarithmic in the security parameter — GHKL08.

Guaranteed output delivery

Full security, or guaranteed output delivery, removes the abort: in the ideal execution $\mathcal{S}$ may replace the corrupted parties’ inputs, a corrupted party that submits none is assigned a default input, and every honest party receives its output. It implies fairness against the same corruptions, being the fair ideal execution in which $\mathcal{S}$ never aborts — folklore. With $t\ge n/2$ it would give a fair coin flip, which does not exist — Cle86. The broadcast channel can be emulated over the point-to-point channels when $t<n/3$ (Lamport–Shostak–Pease), and cannot be without a setup when $t\ge n/3$ (no broadcast from authenticated channels) — LSP82; the emulation runs in time polynomial in $n$ — GM93.

Honest majority ($t<n/3$)

Guaranteed output delivery against a malicious adversary corrupting at most $t<n/3$ parties. The $t<n/2$ notion below implies it, its adversaries including these — folklore.

Honest majority ($t<n/2$)

Guaranteed output delivery against a malicious adversary corrupting at most $t<n/2$ parties, over the network with its broadcast channel.

Honest majority with abort ($t<n/2$)

Security with abort against a malicious adversary corrupting at most $t<n/2$ parties, over the network with its broadcast channel. The ideal execution is ${\mathrm{Ideal}}_{f,T}^{\mathrm{abort}}$, except that after receiving the corrupted parties’ outputs $\mathcal{S}$ chooses, for each honest party separately, whether that party receives its output or $\perp$ (selective abort). A protocol with unanimous abort meets the notion, and one final round in which every party broadcasts whether it aborted makes a selective-abort protocol unanimous — folklore. Guaranteed output delivery against $t<n/2$ and security with abort against $t=n-1$ each imply it, by the identity map — folklore.

Semi-honest, honest majority ($t<n/2$)

Semi-honest security against at most $t<n/2$ corrupted parties. Semi-honest security against $t=n-1$ implies it — folklore. Over secure channels it is achieved with perfect security (BGW) — BGW88.

With information-theoretic privacy, $\lceil n/2\rceil$ corruptions already force the trivial case for Boolean functions: a Boolean function is either $n$-private, or $\lfloor (n-1)/2\rfloor$-private and not $\lceil n/2\rceil$-private, and the $n$-private ones are exactly those of the form $f_1(x_1)\oplus \cdots \oplus f_n(x_n)$ — CK89. The two-argument functions computable with perfect privacy are characterized combinatorially — Kus89. Given semi-honest OT, every functionality has a protocol secure against semi-honest adversaries corrupting any number of parties (semi-honest OT ⇒ semi-honest MPC) — GMW87, Gol04.

Universal composability (UC)

Security with abort against $t=n-1$ static corruptions in the UC framework: the protocol UC-realizes the ideal functionality ${\mathcal{F}}_f$, which computes $f$, hands the adversary the corrupted parties’ outputs first and lets it withhold the output of any honest party — Can01. The distinguisher is an environment $\mathcal{Z}$ that chooses the inputs, reads the outputs and interacts with $\mathcal{A}$ throughout the execution. UC security implies stand-alone security, the game above being an environment that only supplies inputs and reads outputs — Can01; one more round in which every party broadcasts whether it received its output turns the per-party abort into the unanimous abort of security with abort — folklore.

With an honest majority no setup is needed — Can01. With $t=n-1$ a setup is necessary: UC commitments do not exist in the plain model — CF01 — and neither do UC protocols for a large class of two-party functionalities, whatever the assumption (no UC MPC from authenticated channels) — CKL03. In the common reference string model every functionality has a UC protocol against static corruptions from enhanced trapdoor permutations (enhanced TDP ⇒ UC MPC) — CLOS02; in the OT-hybrid model a PRG used as a black box suffices, with a constant number of rounds (ideal OT + PRG ⇒ UC MPC) — IPS08.

MPC with preprocessing

Security with abort against $t=n-1$ corruptions, by a protocol in two phases. An offline phase, which depends neither on the inputs nor on $f$ beyond its number of gates of each type, gives the parties correlated randomness; an online phase evaluates $f$ using it and is statistically secure in the hybrid model where an ideal dealer supplies that correlated randomness, together, in some protocols, with ideal commitments. Multiplication triples, one consumed per multiplication gate, are the standard correlation, as in the online phases of BDOZ11 and DPSZ12. They descend from Beaver’s circuit randomization, which sets every input of every gate at random and then corrects it, replacing each secret multiplication in a secret-sharing-based protocol by reconstructions of shared values that need only broadcast, not Byzantine agreement; there the random values are prepared within the protocol, not by a dealer — Bea91. Given a dealer of such triples, the BDOZ online phase is UC-secure with abort against $t=n-1$ (correlated randomness ⇒ UC MPC) — BDOZ11. The notion implies MPC, which ignores the split into phases — folklore.

Two-round MPC

Security with abort against $t=n-1$ corruptions by a protocol with two rounds of communication. It implies MPC — folklore. In the common reference string model it follows from two-round malicious OT (two-round UC OT ⇒ two-round MPC) — GS18 — and from LWE with NIZK arguments (LWE + NIZK ⇒ two-round MPC) — MW16; the round complexity of MPC without that setup is under Other results.

Two-round semi-honest MPC

Semi-honest security against $t=n-1$ corruptions by a protocol with two rounds of communication. It implies semi-honest security — folklore. Two-round semi-honest OT is necessary and sufficient for it (two-round OT ⇒ two-round semi-honest MPC) — GS18, BL18 — but not with black-box use of the OT (no fully-black-box reduction) — ABG+20.

Expected polynomial-time simulation

Security with abort in which, for every efficient $\mathcal{A}$, the simulator $\mathcal{S}$ need only run in expected polynomial time, with $\mathcal{A}$ and $\mathcal{D}$ efficient as before. MPC with expected polynomial-time simulation is achieved when every functionality has a protocol secure in this sense against $t=n-1$ corruptions. MPC implies it by the identity map (MPC ⇒ MPC with expected-time simulation) — folklore. The converse is not an identity: truncating an expected polynomial-time simulator at a fixed polynomial can change its output distribution by an inverse-polynomial amount — standard. Constant-round plain-model protocols with black-box simulators need the relaxation: a constant-round plain-model protocol that securely computes the zero-knowledge functionality with a strict polynomial-time black-box simulator is a constant-round zero-knowledge argument with one — standard — and in the plain model such arguments exist only for languages in $\mathbf{BPP}$ — BL02. With a reference string the relaxation is not needed: NIZK arguments in the common reference string model have straight-line simulators running in strict polynomial time — standard.

2PC with expected polynomial-time simulation

2PC with a simulator that need only run in expected polynomial time, the case $n=2$ of expected polynomial-time simulation. 2PC implies it by the identity map (2PC ⇒ 2PC with expected-time simulation) — folklore.

Four-round MPC

Security with selective abort against $t=n-1$ corruptions, the ideal execution of honest majority with abort in which $\mathcal{S}$ chooses for each honest party separately whether it receives its output or $\perp$, with expected polynomial-time simulation in the plain model ($\mathsf{pp}=1^{\lambda }$), by a protocol of four rounds over the network of the syntax, in each of which every party may send, with a black-box simulator as in five-round 2PC. It implies MPC with expected polynomial-time simulation: one more round, in which every party broadcasts whether it aborted, makes the abort unanimous (four-round MPC ⇒ MPC with expected-time simulation) — folklore. With a black-box proof of security, MPC in the plain model needs at least four rounds — GMPP16. Four rounds suffice under polynomially hard DDH (DDH ⇒ four-round MPC), QR (QR ⇒ four-round MPC) or $N$-th residuosity (DCR ⇒ four-round MPC) — BGJ+18 — and from four-round OT (four-round OT ⇒ four-round MPC) — CCG+20. Earlier four-round protocols rested on super-polynomial hardness: one-way permutations with sub-exponentially hard DDH — ACJ17 — and sub-exponentially hard LWE with a slightly super-polynomial modulus-to-noise ratio together with adaptively secure commitments — BHP17.

Other results

• OT extension: $O(\lambda )$ base OTs suffice to generate polynomially many OTs efficiently — IKNP03
• Communication lower bounds for two-party differential privacy — HMST22
• Round complexity in the plain model with black-box proofs of security: five rounds for 2PC when one party sends per round (Five-round 2PC) — KO04 — and four for MPC (Four-round MPC) — GMPP16, BGJ+18; with a simultaneous-message channel, four rounds suffice for 2PC from trapdoor permutations — COSV17.
• Two-round MPC in the common reference string model: from indistinguishability obfuscation, UC-secure with abort against static malicious adversaries, with communication proportional to the input and output size and independent of the circuit size — GGHR14; from LWE and NIZK arguments — MW16; and from two-round malicious OT — GS18 (Two-round MPC).
• 2PC from malicious OT by cut-and-choose over garbled circuits, with $O(1)$ OTs per input bit as its only public-key operations (malicious OT ⇒ 2PC) — LP07.
• Functions that a RAM computes in sublinear time have secure two-party computation in amortized sublinear time, by generic secure two-party computation run on top of an ORAM — GKK+12

Participates in

Builds on Secure multi-party computation

• Fair MPC ⇒ MPC (via Fairness)
• Five-round 2PC ⇒ 2PC with expected-time simulation (via Five-round 2PC)
• Four-round MPC ⇒ MPC with expected-time simulation (via Four-round MPC)
• MPC with honest majority ($t<n/2$) ⇒ MPC with honest majority ($t<n/3$) (via Honest majority ($t<n/2$))
• MPC with honest majority ($t<n/2$) ⇒ MPC with abort and honest majority ($t<n/2$) (via Honest majority ($t<n/2$))
• MPC ⇒ MPC with abort and honest majority ($t<n/2$)
• MPC ⇒ MPC with expected-time simulation
• MPC ⇒ 2PC
• MPC with preprocessing ⇒ MPC (via MPC with preprocessing)
• Semi-honest MPC + OWF ⇒ MPC (GMW compiler) (via Semi-honest security)
• Semi-honest MPC ⇒ Semi-honest MPC with honest majority (via Semi-honest security)
• Semi-honest MPC ⇒ Semi-honest 2PC (via Semi-honest security)
• 2PC ⇒ Malicious OT (via Two-party computation (2PC))
• Semi-honest 2PC ⇒ OT (via Semi-honest two-party computation)
• 2PC ⇒ 2PC with expected-time simulation (via Two-party computation (2PC))
• Two-round MPC ⇒ MPC (via Two-round MPC)
• Two-round semi-honest MPC ⇒ Semi-honest MPC (via Two-round semi-honest MPC)
• Two-round semi-honest MPC ⇒ Two-round OT (via Two-round semi-honest MPC)
• UC MPC ⇒ MPC (via Universal composability (UC))

Produces Secure multi-party computation

• Correlated randomness ⇒ UC MPC (BDOZ online phase) (via Universal composability (UC))
• DCR ⇒ Four-round MPC (Badrinarayanan–Goyal–Jain–Kalai–Khurana–Sahai) (via Four-round MPC)
• DDH ⇒ Four-round MPC (Badrinarayanan–Goyal–Jain–Kalai–Khurana–Sahai) (via Four-round MPC)
• Doubly enhanced certified TDP ⇒ Five-round 2PC (Katz–Ostrovsky) (via Five-round 2PC)
• Enhanced TDP ⇒ MPC with honest majority ($t<n/2$) (GMW) (via Honest majority ($t<n/2$))
• Enhanced TDP ⇒ 2PC with expected-time simulation (Ostrovsky–Richelson–Scafuro) (via 2PC with expected polynomial-time simulation)
• Enhanced TDP ⇒ UC MPC in the CRS model (CLOS) (via Universal composability (UC))
• Fair MPC ⇒ MPC
• Five-round 2PC ⇒ 2PC with expected-time simulation (via 2PC with expected polynomial-time simulation)
• Four-round MPC ⇒ MPC with expected-time simulation (via Expected polynomial-time simulation)
• Four-round OT ⇒ Four-round MPC (Choudhuri–Ciampi–Goyal–Jain–Ostrovsky) (via Four-round MPC)
• GC + OT ⇒ Semi-honest 2PC (Yao) (via Semi-honest two-party computation)
• SHE + correlated randomness ⇒ MPC with preprocessing (SPDZ) (via MPC with preprocessing)
• MPC with honest majority ($t<n/2$) ⇒ MPC with honest majority ($t<n/3$) (via Honest majority ($t<n/3$))
• MPC with honest majority ($t<n/2$) ⇒ MPC with abort and honest majority ($t<n/2$) (via Honest majority with abort ($t<n/2$))
• Ideal OT + PRG ⇒ UC MPC (IPS) (via Universal composability (UC))
• Ideal OT ⇒ 2PC (Kilian) (via Two-party computation (2PC))
• Malicious OT ⇒ 2PC by cut-and-choose (Lindell–Pinkas) (via Two-party computation (2PC))
• MPC ⇒ MPC with abort and honest majority ($t<n/2$) (via Honest majority with abort ($t<n/2$))
• MPC ⇒ MPC with expected-time simulation (via Expected polynomial-time simulation)
• MPC ⇒ 2PC (via Two-party computation (2PC))
• MPC with preprocessing ⇒ MPC
• OT Extension ⇒ MPC with preprocessing (SPDZ, etc.) (via MPC with preprocessing)
• Semi-honest OT ⇒ MPC (HIKLP)
• Semi-honest OT ⇒ Semi-honest MPC (GMW) (via Semi-honest security)
• QR ⇒ Four-round MPC (Badrinarayanan–Goyal–Jain–Kalai–Khurana–Sahai) (via Four-round MPC)
• Secure channels ⇒ MPC with honest majority ($t<n/2$) (Rabin–Ben-Or) (via Honest majority ($t<n/2$))
• Secure channels ⇒ MPC with honest majority ($t<n/3$) (BGW) (via Honest majority ($t<n/3$))
• Secure channels ⇒ MPC with honest majority ($t<n/3$) with linear communication (Beerliová-Trubíniová–Hirt) (via Honest majority ($t<n/3$))
• Secure channels ⇒ MPC with honest majority ($t<n/3$) (Chaum–Crépeau–Damgård) (via Honest majority ($t<n/3$))
• Secure channels ⇒ MPC with honest majority ($t<n/3$) from linear secret sharing (Cramer–Damgård–Maurer) (via Honest majority ($t<n/3$))
• Secure channels ⇒ MPC with abort and honest majority ($t<n/2$) (CGH+18) (via Honest majority with abort ($t<n/2$))
• Secure channels ⇒ Semi-honest MPC with honest majority ($t<n/2$) (BGW) (via Semi-honest, honest majority ($t<n/2$))
• Semi-homomorphic encryption ⇒ MPC with preprocessing (BDOZ) (via MPC with preprocessing)
• Semi-honest MPC + OWF ⇒ MPC (GMW compiler)
• Semi-honest MPC ⇒ Semi-honest MPC with honest majority (via Semi-honest, honest majority ($t<n/2$))
• Semi-honest MPC ⇒ Semi-honest 2PC (via Semi-honest two-party computation)
• LWE + NIZK ⇒ Two-round MPC in the CRS model (Mukherjee–Wichs) (via Two-round MPC)
• 2PC ⇒ 2PC with expected-time simulation (via 2PC with expected polynomial-time simulation)
• Two-round MPC ⇒ MPC
• Two-round OT ⇒ Two-round semi-honest MPC (Garg–Srinivasan, Benhamouda–Lin) (via Two-round semi-honest MPC)
• Two-round semi-honest MPC ⇒ Semi-honest MPC (via Semi-honest security)
• Two-round UC OT ⇒ Two-round MPC in the CRS model (Garg–Srinivasan) (via Two-round MPC)
• UC MPC ⇒ MPC

Barriers

• No reduction from authenticated channels to fair MPC (via Fairness)
• No reduction from authenticated channels to UC MPC (via Universal composability (UC)) — circumvented by Enhanced TDP ⇒ UC MPC in the CRS model (CLOS), Ideal OT + PRG ⇒ UC MPC (IPS), Correlated randomness ⇒ UC MPC (BDOZ online phase)
• No fully-black-box reduction from two-round OT to two-round semi-honest MPC (via Two-round semi-honest MPC) — circumvented by Two-round OT ⇒ Two-round semi-honest MPC (Garg–Srinivasan, Benhamouda–Lin)