UC-secure OT ⇒ MPC

Fully-black-box reduction · CRS model · Kil88, IPS08, Can01

Statement

OT is complete for MPC: in the OT-hybrid model every two-party functionality can be computed with unconditional security against malicious parties — Kil88. In the OT-hybrid model, every $n$-party functionality can be computed with statistical security with abort against a malicious adversary corrupting any number of parties — IPS08. An OT protocol that UC-realizes OT against malicious adversaries instantiates the hybrid, by the composition theorem — Can01.

Sketch

Parties hold XOR shares of every wire; XOR gates are local, and each AND gate costs one 1-out-of-4 OT per pair of parties. This suffices against semi-honest parties. A zero-knowledge proof cannot certify the inputs a party gives an ideal OT, so against malicious parties Kil88 builds commitments from OT and makes each transfer consistent with committed inputs — Kil88.

Notes

• Constant-rate two-party computation in the OT-hybrid model, statistically UC-secure against malicious adversaries, with communication $O(s)+\mathrm{poly}(\lambda ,d,\log s)$ for a circuit of size $s$ and depth $d$, extending to any constant number of parties, via a compiler that uses an honest-majority protocol as a black box — IPS08.
• The converse holds: OT is itself a two-party functionality, so MPC for every functionality gives OT — standard.
• Semi-honest OT gives maliciously secure OT through OT ⇒ malicious OT — Hai08 — and stand-alone maliciously secure MPC through semi-honest OT ⇒ MPC — HIKLP10.
• Efficiency: the number of rounds of the GMW protocol grows with the multiplicative depth of the circuit, while Yao’s garbled-circuit protocol has a constant number — standard.