Mild average-case hardness of Kᵗ ⇔ OWF

Equivalence · standard model · LP20

Statement

For every polynomial $t(n)\ge (1+\epsilon )n$ with a constant $\epsilon >0$, one-way functions exist if and only if $K^t$ is mildly hard on average: there is a polynomial $p$ such that for every PPT algorithm $\mathcal{A}$ and all sufficiently large $n$, ${\mathrm{Pr}}_{x\stackrel{\$}{\leftarrow }\{0,1{\}}^n}[\mathcal{A}(x)=K^t(x)]<1-1/p(n)$ — LP20.

Notes

• Both directions hold for every such $t$, so mild average-case hardness of $K^t$ for one polynomial $t(n)\ge (1+\epsilon )n$ gives it for all of them — LP20.