No fully-black-box reduction from PKE to OT

Unconditional · against fully-black-box reductions · GKM+00

Statement

There is no fully-black-box construction of OT from a trapdoor predicate, i.e. single-bit PKE: the two primitives are incomparable under black-box reductions, by oracle separations following IR89 — GKM+00. Bitwise encryption under a trapdoor predicate is a semantically secure multi-bit PKE — GM84 — so a fully-black-box construction of OT from multi-bit PKE would compose into one from trapdoor predicates, and none exists.

Notes

• A restricted, strengthened form of each primitive does imply the other — GKM+00.
• The converse separation: OT ⇏ PKE — GKM+00.