Sub-exponential iO + Sub-exponential OWF ⇒ TDP (Bitansky–Paneth–Wichs)

Free reduction · standard model · BPW16 · security loss: super-polynomial, which is why both hypotheses are assumed sub-exponentially hard

Statement

If sub-exponentially secure iO and sub-exponentially secure one-way functions exist, then trapdoor permutations exist — BPW16. These are the first trapdoor permutations not based on the hardness of factoring. The construction is not domain-invariant. Domain invariance allows a domain to depend on the permutation index, but here the domain is defined through a pseudorandom function built from the one-way function, so replacing that function changes the domain even under the same key — AS16.

Notes

• Domain dependence is unavoidable for constructions that use the obfuscator as an oracle on circuits calling the one-way function, a class containing this construction (No fully-black-box reduction from iO + OWF to domain-invariant OWP) — AS16.
• The result removes the trapdoor-permutation and injective-OWF assumptions from many earlier iO-based constructions — BPW16.