No relativizing reduction from KE to TDP

Unconditional · against relativizing reductions · Rud91

Statement

There is an oracle relative to which three-message key agreement exists and injective trapdoor functions do not — Rud91 — so no relativizing, and in particular no fully-black-box, construction of trapdoor permutations or injective trapdoor functions from key agreement exists.

Notes

• Trapdoor permutations give PKE (TDP ⇒ PKE) and hence two-message key agreement, so this barrier also follows from No relativizing reduction from KE to PKE — Rud91.