One-Way Function

(Strongly) OWF

A function $f:\bits^* \to \bits^* $ is a (strongly) one-way function if it is polynomial-time computable and it holds that for every PPT algorithm $A$ and every positive polynomial $p(\cdot)$ and sufficiently large $n$’s:

\[Pr[f(A(y, 1^n)) = y \;|\; y = f(x); \; x \samples \bits^n] < \frac{1}{p(n)}\]

Auxiliary input

The auxiliary input $1^n$ is redundant if, given only $F(x)$, we can generate¹ $1^{|x|}$ in time polynomial in $|x|$. This auxiliary input prevents a function $f$ to be considered one-way if it only shrinks its input in such a way that, whenever we try to invert, we cannot generate the desired output in polynomial (in the size of the input!) time.

Weakly (or somewhat) OWF

In the weak variant, we only require that any algorithm trying to compute any pre-image of $f(x)$, for a random choice of $x$, fails with (any!) noticeable probability. So we come up with this definition: a polynomial-time computable function $f$ is weakly one-way if there exists a polynomial $p(\cdot)$ such that for every PPT algorithm $A$ and sufficiently large $n$’s, it holds that:

\[Pr[f(A(y)) = y \;|\; y = f(x); \; x \samples \bits^n] \le 1 - \frac{1}{p(n)}\]

Strongly vs Weakly

It is possible to show that weakly one-way functions imply the existence of strongly ones; moreover, since every OW function is also weakly OW, we claim that:

weakly OWFs exist if and only if OWFs exist.

However, it should be noticed that not all weakly one-way functions are strongly one-way too.

The other side of the moon

In the following alternative definition, we lower-bound (to $\rho$) the failure probability of all PPT algorithms trying to invert $f$.

So, a polynomial-time computable function $f$ is $\rho$-one-way if for all PPT algorithms $A$, for sufficiently large $n$’s it holds that:

\[Pr[f(A(y) \ne y \;|\; y = f(x); \; x \samples \bits^n] > \rho(n)\]

This means that:

• a weakly OW function $f$ is a $\frac{1}{p}$-one-way, for some $p$
• a (strongly) OW function $f$ is ($1-\epsilon$)-one-way, where $\epsilon$ is negligible

References

• R. Impagliazzo, M. Luby. One-way functions are essential for complexity-based cryptography. 1989