Simple explanation of weak one way function

Question

I find difficult to understand what a weak one way function is. From textbooks:

$\exists$ poly $Q$, $\forall$ PPT $\mathcal{A}$ such that: $$\Pr[x\leftarrow\{0,1\}^n; y=f(x); \mathcal{A}(1^n, f(x))=x' : f(x')=y] \leq 1 - 1/Q(n)$$

• What does this mean in practice?
• The part that I find confusing is: $1-1/Q(n)$, does this mean that we can invert all except a polynomial part which we cannot invert?

Answer 1

• The part that I find confusing is: $1-1/Q(n)$, does this mean that we can invert all except a polynomial part which we cannot invert?

This is relaxation from Strong OWF, in which, any polynomial time algorithm will succeed in inverting $f$ on random input with negligible probability.

In weak OWF, any polynomial time algorithm will fail to invert $f$ on random input with non-negligible probability.

• What does this mean in practice?

There is a theorem state as;

Theorem: If there is a weak OWF, then there is a strong OWF. In particular, given a weak OWF $f:\{0,1\}^* \to \{0,1\}^*$, a there is a fixed $m\in \mathbb{N}$ polynomial time input length $n \in \mathbb{N}$ such that $f'$

$$f'(x_1,\ldots,x_m) = (f(x_1),\cdots ,f(x_m))$$

is a strong OWF. In particular this holds for $m=2\,n\,q(n)$.

For a proof see

Therefore, in practice, we know at least one way to construct a strong OWF from weak OWFs.