OWP ⇒ Size-verifiable OWF

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

A one-way permutation $f$ is a size-verifiable one-way function, with the same inversion advantage for every adversary: $f$ permutes each $\{0,1{\}}^n$, so $|f^{-1}(y)|=1$ for every $y$, and the preimage-size problem $\{(y,s):|f^{-1}(y)|=s\}=\{(y,1):y\in \{0,1{\}}^{\ast }\}$ lies in $\mathbf{P}\subseteq \mathbf{AM}$ — folklore.