2PC ⇒ OT

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

Statement

A protocol that securely computes every polynomial-time two-party functionality against semi-honest adversaries (2PC) is, run on the functionality $((x_0,x_1),c)\mapsto (\perp ,x_c)$, a semi-honest OT protocol; the same holds against malicious adversaries — folklore.

Sketch

With empty $\mathsf{pp}$, the protocol for $f((x_0,x_1),c)=(\perp ,x_c)$ is correct as an OT, and semi-honest privacy makes the sender’s view simulatable from $(x_0,x_1)$, hence indistinguishable for $c=0$ and $c=1$ (receiver privacy), and the receiver’s view simulatable from $(c,x_c)$, hence indistinguishable for two sender pairs that agree on $x_c$ (sender privacy). Against malicious adversaries, security with abort for $f$ gives malicious OT security once the honest receiver answers an abort with the $c$-th entry of a fixed default pair: the simulator for a corrupted sender receives only $\perp$ from the trusted party, so its decision to abort does not depend on $c$ and can be replaced by submitting the default pair, and a corrupted receiver’s abort withholds only the sender’s output $\perp$ — standard.

Notes

• The converse is OT ⇒ MPC, so OT is complete for secure computation — Kil88.