No fully-black-box reduction from length-increasing injective OWF to OWP

Unconditional · against fully-black-box reductions · MM11a

Statement

There is no fully black-box construction of a one-way permutation from a length-increasing injective one-way function, even one that stretches its input by a single bit and is adaptively one-way; as a corollary, there is none from a regular one-way function of regularity greater than $1$ — MM11a.

Notes

• Length-increasing is necessary: a one-way permutation is itself a length-preserving injective one-way function, so without the qualifier the identity construction refutes the separation — folklore.