Malicious OT ⇒ 2PC by cut-and-choose (Lindell–Pinkas)

Fully-black-box reduction · standard model · LP07 · security loss: statistical error at most $2^{-s/17}$ for $s$ garbled circuits, plus the advantages against the OT and against the garbling’s encryption

Statement

Run Yao’s protocol with cut-and-choose over $s$ garbled circuits and checks that the parties’ inputs are consistent across the circuits. Given an OT protocol with malicious security for strings of the garbling’s key length, the protocol securely computes every two-party functionality with abort against a malicious adversary (2PC), with a proof in the standard model and no random oracle or common reference string; it is a black-box reduction of 2PC to OT, and it is constant-round given also perfectly hiding commitments — LP07. The adversary cheats with probability at most $2^{-s/17}$, so $s=\omega (\log \lambda )$ makes the protocol secure — LP07, as quantified by LP11.

Notes

• Efficiency: the only public-key operations are $O(1)$ OTs per input bit, or per bit of the statistical parameter $s$ if that is larger — LP07. The protocol garbles $s$ circuits, and the error $2^{-s/17}$ means 680 circuits for error $2^{-40}$ — LP11; with four ciphertexts of $O(\lambda )$ bits per gate, the garbled circuits take $O(s\cdot |C|\cdot \lambda )$ bits for a circuit $C$ — standard.
• Rounds: from OT alone the reduction takes a number of rounds linear in $s$, while Kilian’s OT-only reduction takes a number of rounds linear in the circuit’s depth (ideal OT ⇒ 2PC) — LP07.
• Constant-round parallel coin tossing and trapdoor commitments that use a one-way function only as a black box give, as a corollary, a constant-round black-box construction of 2PC from semi-honest OT — PW09.
• Fewer circuits: cut-and-choose OT under DDH brings the error to $2^{-0.311s}$ — LP11. Where the best earlier protocols sent between 125 and 128 circuits for error $2^{-40}$, error $2^{-s}$ with $s$ circuits brings this to 40 circuits, with some additional overhead — Lin13.