Proof that $g(x) = f(x) || f(f(x))$ is a OWF when $f$ is a OWF

Assume that $$f$$ is a one-way function (OWF), and let $$\mathbin\|$$ denote string concatenation.

Consider the function $$g$$ defined by $$g(x) = f(x) \mathbin\| f(f(x))$$. It is easy to prove that $$g$$ is a OWF as well, assuming that $$f$$ is length preserving (that is, $$|f(x)|=|x|$$ for all $$x$$). Here's a sample proof, taken from Lindell's final exam: Now consider the case where $$f$$ is a general OWF, not necessarily length preserving. This case is considered in Katz & Lindell book, 2nd Edition, Exercise 7.8: Q: Why Lindell's proof for length-preserving $$f$$ does not work?

A: In the proof mentioned above, $$\mathcal{A}'$$ invokes $$\mathcal{A}$$ on $$y || f(y)$$, which upon success, returns $$x'$$ such that $$f(x') \mathbin\| f(f(x')) = y \mathbin\| f(y)$$. However, this does not entail $$f(x') = y$$, as the length of $$f(x')$$ might be different from the length of $$y$$.

My question is, how to prove that that $$g(x) = f(x) \mathbin\| f(f(x))$$ is a OWF when $$f$$ is a general OWF?

/!\ the counter-example I build below is not a formal refutation of the statement, a more rigorous analysis is needed, but it gives an intuition of why I think that $$f'x\mapsto f(x)\mathbin\|f(f(x))$$ is not necessarily an OWF (thanks to Christian Matt for pointing out the necessity of a more rigorous analysis).

It seems to me that $$f': x \mapsto f(x)\mathbin\|f(f(x))$$ is not necessarily a OWF when $$f$$ is not length-preserving. Consider the following function $$f$$:

• $$h$$ is an arbitrary length-preserving OWF. $$g$$ is an arbitrary OWF that compresses its input by a factor two.
• $$f$$ is defined as follows: on input $$x$$, if $$|x|$$ is odd, then $$f(x) = 0^{|x|} \mathbin\| h(x)$$. Else, if $$|x|$$ is even, then if $$|x|/2$$ is also even and $$x$$ is of the form $$x' \mathbin\| 0^{3|x|/4}$$, return $$x' \mathbin\| 0^{|x|/4}$$. Otherwise, if $$x$$ is of the form $$x'' \mathbin\| 0^{|x|/2}$$, return $$h(x'')$$. In all other cases, return $$g(x)$$.

So, as you can see, $$f$$ maps $$n$$-bit inputs to $$n/2$$-bit outputs when $$n$$ is even, and to $$2n$$-bit outputs when $$n$$ is odd. I think that one can prove that $$f$$ is indeed an OWF by picking an appropriate function $$g$$ whose image does not intersect with $$\{0\}^n \times \{0,1\}^n$$ so that on a random input $$x$$, the probability that $$g(x)$$ is of the form $$x' \mathbin\| 0^{3|x|/4}$$ is very small (as this is the "easy to invert" case).

Now, let $$n \equiv 2 \bmod 4$$ ($$n$$ is even, and $$n/2$$ is odd). Then when you receive $$y = f(x)$$ for a random $$n$$-bit input $$x$$, it is easy to invert $$y \mathbin\| f(y)$$: with very good probability, $$x$$ is not of the form $$x'\mathbin\|0^{3|x|/4}$$, hence $$f(x) = g(x)$$ (which is of odd length $$n/2$$). In this case it holds that $$f(y) = 0^{n/2}\mathbin\|h(y)$$. But this makes inverting $$y \mathbin\| f(y)$$ trivial:

$$y\mathbin\|f(y) = y\mathbin\|(0^{n/2}\mathbin\|h(y)) = (y\mathbin\|0^{n/2})\mathbin\|h(y) = f(y\mathbin\|0^{3n/2})\mathbin\|f(f(y||0^{3n/2}))$$

Hence one can simply return $$y\mathbin\|0^{3n/2}$$ to successfully invert $$f':x \mapsto f(x)\mathbin\|f(f(x))$$. So unless I'm missing something / making a mistake, $$f': x \mapsto f(x)\mathbin\|f(f(x))$$ is not necessarily a OWF when $$f$$ is not length-preserving.

EDIT: corrected mistakes in the previous version of my counter example.

• I don't think it is so easy to show that your $f$ is one-way, even in the "obvious" case with odd $|x|$: One attempt to proving it is to give a reduction that inverts $h$. So, given $y = h(x)$, give $y' := 0^{|y|}||y$ to the algorithm $\mathcal{A}$ that inverts $f$. Now $x$ is a valid preimage that $\mathcal{A}$ could return, but $\mathcal{A}$ could also return some $x'$ with $f(x') = g(x') = y'$. In this case, you fail to invert $h$ and $g$ could actually be easy to invert for $g(x')$ of this form... Apr 7 '17 at 15:46
• @ChristianMatt: you're right, I will have to look at it carefully, but I think something along the lines of what I proposed could be made to work, by using a more carefully crafted function $g$, one whose image does not intersect with $\{0\}^n \times \{0,1\}^n$. I edited my answer and will try to build a more formal counter example when I have more time. Apr 7 '17 at 16:13
• I decided to donate the bounty to this ingenious answer, though as the OP points out, it needs a more careful analysis to prove that $g$ is actually NOT an OWF. Apr 12 '17 at 5:08