GC + OT ⇒ Semi-honest 2PC (Yao)

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, and any PRF gives a projective private garbling scheme (PRF ⇒ garbled circuits) — 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.
• Free XOR: XOR gates need no garbled table and no cryptographic operation, with security proved in the random oracle model — KS08.
• Half gates: AND gates take two ciphertexts ($2\lambda$ bits) and XOR gates stay free, and the evaluator performs two cryptographic operations per AND gate; two ciphertexts are optimal among a large class of garbling schemes that covers all known practical techniques — ZRE15.
• Three halves: slicing wire labels in half brings AND gates to $1.5\lambda +5$ bits with free XOR, below the half-gates bound, from a circular correlation-robust hash — RR21.