No fully-black-box reduction from OWF to OWP

Unconditional · against fully-black-box reductions · Rud88, KSS11

Statement

There is no fully-black-box construction of a one-way permutation from a one-way function in which the permutation’s domain does not depend on the function. Rud88 reduces the separation to a combinatorial conjecture on families of terms over Boolean variables, which KSS11 prove through an inequality dual to the van den Berg–Kesten–Reimer inequality.

Notes

• Injectivity does not help: there is no fully-black-box construction of a one-way permutation from a length-increasing injective one-way function either (No fully-black-box reduction from injective OWF to OWP) — MM11a.
• The converse holds trivially: OWP ⇒ OWF — folklore.