GC + OT ⇒ Two-party computation (2PC)

Fully-black-box reduction · standard model · Yao86, LP09 · security loss: additive: the garbling-privacy advantage plus, by a hybrid over the evaluator’s $n$ input bits, $n$ times the OT simulation advantage

Statement

A garbling scheme and OT yield a protocol, with the round complexity of the OT plus at most one message, for two-party computation of any polynomial-size circuit against semi-honest adversaries: the garbler sends the garbled circuit with the labels of its own input, and the evaluator obtains the labels of its input by OT and evaluates — Yao86. The first complete description and security proof is LP09.

Sketch

The evaluator’s view is simulated from a simulated garbled circuit and input labels that reveal only the output (garbling privacy), together with simulated OT transcripts; the garbler’s view is simulated from OT receiver privacy. A hybrid argument turns any distinguisher of the real and simulated views into an adversary against the garbling or OT games.

Notes

• Garbling schemes were later formalized as a standalone primitive whose privacy notion is the one the evaluator’s simulator uses — BHR12.
• Efficiency: the garbled circuit has four ciphertexts of $O(\lambda )$ bits per gate, the OTs run in parallel, so the protocol is constant-round given a constant-round OT, and the evaluator needs one OT per bit of its own input and, with point-and-permute, one decryption per gate — standard.