Two-round semi-honest MPC ⇒ Two-round OT

Fully-black-box reduction · standard model · BL18 · security loss: none

Statement

Run, for $n=2$, a protocol that computes every functionality in two rounds with semi-honest security (two-round semi-honest MPC) on $((x_0,x_1),c)\mapsto (\perp ,x_c)$. This gives a two-message semi-honest OT: the receiver sends its first-round message; the sender’s first-round message does not depend on the receiver’s, so the sender replies with both of its messages; and the receiver’s second-round message is never sent, because the sender has no output. Hence $k$-round semi-honest OT is necessary for $k$-round semi-honest MPC, here with $k=2$ — BL18.

Sketch

In the OT protocol the sender’s view is a sub-view of its view in the MPC protocol, and the receiver’s view equals its MPC view, since it can recompute its own unsent second message. The MPC simulators therefore give receiver privacy, the sender’s view being simulatable without $c$, and sender privacy, the receiver’s view being simulatable from $(c,x_c)$ — standard.

Notes

• With a common reference string the argument is unchanged: in the MPC security definition the distinguisher chooses the inputs after seeing the reference string, as the adversary does in the OT privacy games — folklore.
• GS18 call two-round OT the minimal assumption for two-round MPC, and the converse holds by their construction (two-round OT ⇒ two-round semi-honest MPC) — GS18.
• The same construction with any number of rounds gives semi-honest OT from semi-honest 2PC (semi-honest 2PC ⇒ OT) — folklore.