XOR of one-way function

Question

Considering the top answer to the question “If xor-ing a one way function with different input, is it still a one way function?”…

The function is no longer one-way.

we build a counter example 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.

Wouldn't this counter-example imply that we've inverted $f$?

Consider the reduction where we take in $f(x_1)$ and $f(x_2)$: then we could compute $f(x_1) \oplus f(x_2)$, invert this to $x_1x_2$, and then we have inverted $f$ as well.

Is the quoted answer correct? If so, why, given my considerations outlined above?

Answer 1

There are two reasons that counter-example wouldn't "imply that we've inverted".

(a)

Despite that answer's (probably-not-necessarily-correct) opening sentence,
it's only a counterexample to "$h$ is necessarily one-way", not to "$h$ is one-way".


(b)

That answer's attack does not require inverting ​ $\hspace{.04 in}f(x_1) \oplus f(x_2)$ ​ "to $x_1x_2$",
it just involves finding a preimage of ​ $\hspace{.04 in}f(x_1) \oplus f(x_2)$ ​ under $h$.

Answer 2

The question there asks:

"If $f()$ is one way, is it true that $h(x_1,x_2)=f(x_1)\oplus f(x_2)$ is also one way."

This claim is incorrect. There exists some $f$ whose respective $h$ is not one way anymore.

However, the above doesn't apply to all $f$'s. It is possible that there exists some one-way $f$ whose respective $h$ remains one-way. But it needs not happen, as the example in that answer proves.

moreover, inverting $h$ means finding two inputs $x'_1, x'_2$ whose XOR after $f$ is given. this doesn't mean you get the same $x_1$ you started with.

In better words: say you are given $y=f(x)$. now you try to invert it. So you pick some value $x'$ compute $y'=f(x')$ and invert $y \oplus y'$. Say after inverting, you get values $u,v$. All you know is that $f(u) \oplus f(v) = f(x) \oplus f(x')$, but there needs not be any relation between $f(x)$ and $f(u)$. Specifically, it is possible that $u\ne x$ and even $f(u) \ne f(x)$, etc.