4
$\begingroup$

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?
$\endgroup$
4
$\begingroup$
  • 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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – graphtheory92 Jan 8 at 9:04
  • 1
    $\begingroup$ @graphtheory92 negligible amount of failure! $\endgroup$ – kelalaka Jan 8 at 12:54
  • $\begingroup$ does 1-1/Q(n) mean negl(n)? $\endgroup$ – graphtheory92 Jan 12 at 9:37
  • $\begingroup$ no, the failure is $1/Q(n)$ you subtract from 1. $\endgroup$ – kelalaka Jan 12 at 9:40

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.