# Simple explanation of weak one way function

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?

• 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.

• can you break out what in practice means to have 1-1/Q(n)? Does this mean that the adversary succeeds on a polynomial fraction of the inputs? Jan 8 '19 at 9:04
• @graphtheory92 negligible amount of failure! Jan 8 '19 at 12:54
• does 1-1/Q(n) mean negl(n)? Jan 12 '19 at 9:37
• no, the failure is $1/Q(n)$ you subtract from 1. Jan 12 '19 at 9:40