No fully-black-box reduction from iO + OWF to domain-invariant OWP

Unconditional · against fully-black-box reductions · AS16

Statement

There is no fully-black-box construction of a domain-invariant one-way permutation family, in which the permutations’ domains do not depend on the underlying primitives, from a one-way function and iO for circuits that call the function — AS16. Domain invariance allows a family’s domains to depend on the permutation index but not on the underlying primitives. A one-way permutation permutes each $\{0,1{\}}^n$, a domain independent of the underlying primitives, so every construction of one is domain-invariant and the barrier applies to it.

Notes

• Without domain invariance the barrier does not apply: sub-exponential iO + OWF ⇒ TDP gives trapdoor permutations whose domains depend on the underlying one-way function — BPW16.
• Without iO, AS16 also rule out fully-black-box constructions of a one-way permutation from a one-way function that are not domain-invariant, removing the domain restriction of Rudich’s barrier (No fully-black-box reduction from OWF to OWP) — Rud88, AS16.