Ideal OT ⇒ 2PC (Kilian)

Free reduction · standard model · Kil88

Statement

OT is complete for secure two-party computation: in the OT-hybrid model, where the two parties may call an ideal OT functionality any number of times, every two-party functionality has a protocol that is statistically secure with abort against a malicious adversary corrupting either party (2PC), with no complexity assumption — Kil88.

Sketch

The parties hold XOR shares of every wire; XOR gates are local, and each AND gate costs one 1-out-of-4 OT on bits, which suffices against semi-honest parties — standard. 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

• Kil88 works with Rabin’s OT, which is information-theoretically equivalent to 1-out-of-2 OT (Rabin OT ⇔ OT) — Cre87.
• Calling a protocol that UC-realizes OT in place of the ideal functionality preserves security, by the composition theorem, in the common reference string model — Can01.
• Efficiency: in the OT-hybrid model there is a statistically UC-secure two-party protocol with communication $O(s)+\mathrm{poly}(\lambda ,d,\log s)$ and $O(d)$ rounds for a circuit of size $s$ and depth $d$, which extends to any constant number of parties; the compiler uses an honest-majority protocol and a semi-honest OT-hybrid protocol as black boxes, and with a PRG it gives constant-round UC MPC for any number of parties (ideal OT + PRG ⇒ UC MPC) — IPS08.
• Rounds: Kilian’s reduction uses OT alone, with a number of rounds linear in the circuit’s depth; Yao-based cut-and-choose gives a black-box reduction to OT with rounds linear in a statistical parameter, and a constant-round one given also perfectly hiding commitments (malicious OT ⇒ 2PC) — LP07.
• The converse holds: OT is a two-party functionality, so 2PC gives maliciously secure OT (2PC ⇒ malicious OT) — folklore.
• From computational OT: semi-honest OT gives maliciously secure OT through OT ⇒ malicious OT — Hai08 — and stand-alone maliciously secure MPC through semi-honest OT ⇒ MPC — HIKLP10.