OT + OWF ⇒ OT extension (Beaver)

Free reduction · standard model · Bea96 · security loss: polynomial

Statement

Given $\lambda$ oblivious transfers and a one-way function, any polynomial number $m$ of oblivious transfers can be generated — Bea96. This is OT extension.

Sketch

The parties use the $\lambda$ base transfers to run a constant-round secure computation, such as Yao’s protocol, of the functionality that expands short seeds of both parties with a PRG into the inputs and outputs of $m$ random transfers; random OT then gives chosen-input transfers. The number of base transfers is the evaluator’s input length, the length of its seed, independent of $m$ — Bea96.

Notes

• The garbled circuit computes the generator’s whole output, costing $\mathrm{poly}(\lambda )$ garbled gates per extended transfer; a construction using a constant number of hash evaluations per transfer is IKNP OT extension — IKNP03.