8
$\begingroup$

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:

Lindell's proof

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:

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?

$\endgroup$
3
+50
$\begingroup$

/!\ 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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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... $\endgroup$ – Christian Matt Apr 7 '17 at 15:46
  • $\begingroup$ @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. $\endgroup$ – Geoffroy Couteau Apr 7 '17 at 16:13
  • $\begingroup$ 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. $\endgroup$ – M.S. Dousti Apr 12 '17 at 5:08

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.