# If xor-ing a one way function with different input, is it still a one way function?

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$
• 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? – Sasho Nikolov Mar 11 '13 at 23:47
• @SashoNikolov I agree with you: the hypotheses are pretty different. In such cases, please vote to reopen. – Gilles 'SO- stop being evil' Mar 13 '13 at 20:11
• How do you define $h(x)$ when $|x|$ is odd? – Gilles 'SO- stop being evil' Mar 13 '13 at 20:17
• 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? – frafl Mar 15 '13 at 11:01
• @frafl probably it doesn't matter. – Ran G. Mar 18 '13 at 1:14

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.
• 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. – frafl Mar 25 '13 at 14:52
• @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)$. – Ran G. Mar 25 '13 at 18:29
• @RanG: How obvious $f^{-1}(xx)$. Thanks! – frafl Mar 25 '13 at 19:11