We want to show that weakly one-way $\not\Rightarrow$ strongly one-way.
The short answer
In order to prove the above statement, it is sufficient to give an example of a weakly one-way function that is not strongly one-way.
Let $f: \bits^n \to \bits^n$ be a weakly one-way function and let $g: \bits^{n+1} \to \bits^{n+1}$ be the following:
\[g(b, x) := \begin{cases} (b, f(x)) \mbox{ if } b = 1 \\ (b, x) \mbox{ if } b = 0 \\ \end{cases}\]A few details
Independently of whether $f$ is one-way or not, it is clear that $g$ cannot be a strongly one-way function: indeed, for a random bit $b$ and a random choice of $x \in \bits^n$, the probability that $g$ coincides with the identity function is $\frac{1}{2}$.
However, if $f$ is weakly one-way, we can prove that $g$ is weakly one-way too.1
A simple reduction
Let assume that $g$ is not weakly one-way: this means that forall polynomial $p(\cdot)$ there exists an algorithm $A$ able to invert $g$ with probability $w > 1 - \frac{1}{p(n+1)}$. If this is the case we construct $A’$ as follows: $A’(\cdot)$, on input a string $y = f(x)$, for some $x \samples \bits^n$, runs $(z_1, z_2) \samples A(1||y)$.
If $f(z_2) \ne y$, $A’$ aborts. Otherwise, it returns $z_2$.
The winning probability is $w’ \ge (1 - \frac{2}{p(n+1)})$
Conditional winning
In order to justify the previous result, we can think that $w$ as the weighted sum of two components (disjoint events): the first one is the winning probability when $b=0$, the second one for $b=1$.
Expressed in formulas this reduces to:
\[\begin{aligned} w &:= Pr[f(A(y)) = y] \\ &=Pr[b=0] \cdot Pr[f(A(y)) = y \;|\; b = 0] + Pr[b=1] \cdot Pr[f(A(y)) = y \;|\; b = 1] \\ &=\frac{1}{2} + \frac{1}{2}Pr[f(A(y)) = y \;|\; b = 1] \\ \end{aligned}\]It means that $Pr[f(A(y)) = y \;|\; b = 1] > 1 - \frac{2}{p}$.
Beyond a single bit
The schema presented above can be generalized. Let $l$ be $\log_2{n}$ and $g(s, x) := (s, f(x))$, when $s$ starts with at least $l$ zeros; otherwise $g$ is the identity function defined over $2n$-bits strings.
It easy to see that such a construction provides in all but $\frac{1}{n}$ of the overall cases the identity function.
The previous reduction can be adapted2 to show that we can attack $f$ with a winning probability of at least $1 - \frac{n}{p(2n)}$.
References
- O. Goldreich. Foundations of Cryptography. 2001