Semi-honest OT ⇒ Semi-honest MPC (GMW)

Fully-black-box reduction · standard model · GMW87, Gol04 · security loss: polynomial: a hybrid over the OT invocations, $n(n-1)$ per AND gate; in the OT-hybrid model the protocol is perfectly secure

Statement

If a semi-honest OT protocol exists, every polynomial-time $n$-party functionality has a protocol that is secure against semi-honest adversaries corrupting any $t\le n-1$ parties — GMW87. The full proof is in Gol04: in the OT-hybrid model the protocol is perfectly secure against semi-honest adversaries, and the composition theorem for the semi-honest model replaces each ideal call by the OT protocol — Gol04.

Sketch

The parties XOR-share every wire, so XOR gates are local. For an AND gate with $a={⨁}_i{a}_i$ and $b={⨁}_i{b}_i$, for each ordered pair $i\ne j$ party $P_i$ picks a uniform bit $r$ and acts as OT sender on $(r,r\oplus a_i)$ while $P_j$ selects with $b_j$, so the two hold XOR shares $r$ and $r\oplus a_i{b}_j$ of $a_i{b}_j$; each party XORs $a_i{b}_i$ with its shares of the cross terms, and output shares are sent to the output parties — standard.

Notes

• Efficiency: each AND gate costs $n(n-1)$ 1-out-of-2 OTs on bits, or equivalently $n(n-1)/2$ 1-out-of-4 OTs on bits, and XOR gates are free; the AND gates of one layer run in parallel, so the protocol has $O(d)$ rounds for AND-depth $d$ given a constant-round OT — standard.
• Security with abort against malicious adversaries does not imply semi-honest security in general — HL10 — so semi-honest OT ⇒ MPC — HIKLP10 — does not give this result.
• With one-way functions, the GMW compiler turns these protocols into protocols secure with abort against malicious adversaries (semi-honest MPC + OWF ⇒ MPC) — GMW87.