Two-round OT ⇒ Two-round semi-honest MPC (Garg–Srinivasan, Benhamouda–Lin)

Free reduction · standard model · GS18, BL18

Statement

A two-message OT protocol secure against semi-honest adversaries (two-round OT) yields, for every $n$ and every functionality, a protocol with two rounds of broadcast that is secure against semi-honest adversaries corrupting any number of parties (two-round semi-honest MPC); for an OT in the plain model, the MPC protocol is in the plain model. The theorem is proved independently by GS18 and BL18. More generally, for every $k\ge 2$, $k$-round semi-honest OT is necessary and complete for $k$-round semi-honest MPC — BL18.

Notes

• Two rounds are optimal, and two-round OT is necessary (two-round semi-honest MPC ⇒ two-round OT) — BL18.
• Earlier two-round semi-honest protocols needed indistinguishability obfuscation, witness encryption or bilinear maps — BL18.
• The non-black-box use of the OT is necessary (no fully-black-box two-round MPC from two-round OT) — ABG+20; with three rounds, black-box use of two-round OT suffices — PS21.
• Against malicious adversaries, two-round OT secure against malicious adversaries in the common reference string model gives two-round MPC secure with abort in that model (two-round UC OT ⇒ two-round MPC) — GS18.