No relativizing reduction from OWF to OT

Unconditional · against relativizing reductions · IR89

Statement

No relativizing, and in particular no fully-black-box, construction of oblivious transfer from a one-way function exists: relative to a random permutation together with a $\mathbf{PSPACE}$-complete oracle, one-way functions exist and no key-agreement protocol is secure — IR89 — and OT yields key agreement by a construction that relativizes — folklore.

Notes

• A semi-honest secure protocol for the OT functionality is an OT protocol, so the same oracle rules out relativizing constructions of semi-honest secure two-party computation from one-way functions — folklore.
• The direct separation is No relativizing reduction from OWP to KE — IR89.