No fully-black-box reduction from PKE to TDP

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

Statement

There is no fully-black-box construction of a trapdoor permutation from a trapdoor predicate, i.e. single-bit PKE, by an oracle separation 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 a trapdoor permutation from multi-bit PKE would compose into one from trapdoor predicates, and none exists.

Notes

• The converse holds: a trapdoor permutation with a hard-core predicate gives semantically secure PKE (TDP ⇒ PKE) — GM84.
• OT does not give trapdoor permutations either: No fully-black-box reduction from OT to TDP — GKM+00.