Semi-honest 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 (semi-honest 2PC) is, run on the functionality $((x_0,x_1),c)\mapsto (\perp ,x_c)$, a semi-honest OT protocol — folklore.

Sketch

With $\mathsf{pp}$ the protocol’s reference string, empty in the plain model, the protocol for $f((x_0,x_1),c)=(\perp ,x_c)$ is correct as an OT, and semi-honest security 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) — standard.

Notes

• Against malicious adversaries the same construction gives maliciously secure OT (2PC ⇒ malicious OT) — folklore.
• Conversely, semi-honest OT and a garbling scheme give semi-honest 2PC (Yao’s protocol) — Yao86 — and ideal OT gives 2PC secure against malicious parties unconditionally (ideal OT ⇒ 2PC) — Kil88.