Suppose $f(x)$ is a one way function. What about $h(x)=f(x_1) \, \oplus \,f(x_2)$, where $x=x_1 || x_2$ and $\lvert x_1 \rvert = \lvert x_2\rvert$?

  • $\oplus$ is exclusive disjunction (xor)
  • $||$ is concatenation
  • $|u|$ is the length of $u$
  • $\begingroup$ why is a question whether $f(x_1) \oplus f(x_2)$ is one-way assuming that $f$ is one-way a duplicate of the question whether $f(x) \oplus x$ is one-way when $f$ is one-way? $\endgroup$ Commented Mar 11, 2013 at 23:47
  • $\begingroup$ @SashoNikolov I agree with you: the hypotheses are pretty different. In such cases, please vote to reopen. $\endgroup$ Commented Mar 13, 2013 at 20:11
  • $\begingroup$ How do you define $h(x)$ when $|x|$ is odd? $\endgroup$ Commented Mar 13, 2013 at 20:17
  • $\begingroup$ Is $f(x)$ a one-way permutation on $\{0,1\}^{|x|}$ or is it possible that the length of $f(x_1)$ and $f(x_2)$ differ? $\endgroup$
    – frafl
    Commented Mar 15, 2013 at 11:01
  • $\begingroup$ @frafl probably it doesn't matter. $\endgroup$
    – Ran G.
    Commented Mar 18, 2013 at 1:14

1 Answer 1


The function $h$ may not be one-way anymore.

We construct a counter example—a specific one way $f$ whose $h$ is not one-way anymore—in the following way. Assume $g$ is a one-way function that preserves size, and define $f$ on input $w=bx_1x_2$ in the following way, $$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$$ (assuming $b\in\{0,1\}$ and $|x_1|=|x_2|$.) It is easy to see that $f$ is also one-way — to invert it, you need to either invert $g$ on the first half or invert $g$ on the second half.

Now we show how to invert $h$. Assume you are given $h(u,v)=Z$, we write it as $h(u,v)= z_1z_2$ with $|z_1|=|z_2|=n$. Then a possible preimage of $Z$ is $$u=0 \,0^n \,\langle g(0^n)\oplus z_2\rangle$$ $$v=1 \, \langle g(0^n)\oplus z_1\rangle \, 0^n$$

because $f(u) = g(0^n)\, \langle g(0^n)\oplus z_2\rangle$ and $f(v) = \langle g(0^n)\oplus z_1\rangle \, g(0^n)$ thus their XOR gives exactly $z_1\,z_2$ as required.

  • $\begingroup$ Could you add more details about inverting $g$? Given some $x$, you concatenate a random $x_1$ or $x_2$ and then compute $f^{-1}(xx_2)$ and/or $f^{-1}(x_1x)$. But the result could yield $g^{-1}(x_1)$ and $g^{-1}(x_2)$. You have to assure that this doesn't happen in to many cases. Given that you need two positive examples to construct a negative one this should be possible, but it is not as obvious (to me) as you claim. $\endgroup$
    – frafl
    Commented Mar 25, 2013 at 14:52
  • $\begingroup$ @frafl are you asking why $f$ is one way? Assume you have $A$ that inverts it, and use it to invert $g(x)$ by querying $A$ on $g(x)g(x)$. $\endgroup$
    – Ran G.
    Commented Mar 25, 2013 at 18:29
  • $\begingroup$ @RanG: How obvious $f^{-1}(xx)$. Thanks! $\endgroup$
    – frafl
    Commented Mar 25, 2013 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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