No fully-black-box reduction from PKE to injective TDF

Unconditional · against fully-black-box reductions · GMR01

Statement

There is no fully-black-box construction of an injective trapdoor function, or even of a trapdoor function with polynomially many preimages per image, from a trapdoor predicate, i.e. single-bit PKE — GMR01. A multi-bit scheme encrypts bit by bit under a trapdoor predicate — GM84 — so none exists from multi-bit PKE either.

Notes

• Trapdoor permutations and injective trapdoor functions give PKE through the Goldreich–Levin predicate (TDP ⇒ PKE) — GL89 — so injective trapdoor functions are strictly stronger than PKE with respect to fully-black-box constructions — GMR01.
• The permutation case is No fully-black-box reduction from PKE to TDP — GKM+00.