XOR of one-way function - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:52:04Z https://cs.stackexchange.com/feeds/question/52249 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/52249 1 XOR of one-way function vrume21 https://cs.stackexchange.com/users/0 2016-01-24T22:53:44Z 2016-01-25T00:29:07Z <p>Considering the top answer to the question “<a href="https://cs.stackexchange.com/a/10418">If xor-ing a one way function with different input, is it still a one way function?</a>”…</p> <blockquote> <p>The function is no longer one-way.</p> <p>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 &amp; b=0 \\ x_1\, g(x_2) &amp; 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.</p> <p>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$$</p> <p>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.</p> </blockquote> <p>Wouldn't this counter-example imply that we've inverted $f$?</p> <p>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.</p> <p>Is the quoted answer correct? If so, <em>why</em>, given my considerations outlined above?</p> https://cs.stackexchange.com/questions/52249/-/52250#52250 1 Answer by user12859 for XOR of one-way function user12859 https://cs.stackexchange.com/users/0 2016-01-25T00:17:25Z 2016-01-25T00:17:25Z <p>There are two reasons that counter-example wouldn't "imply that we've inverted".</p> <p><br></p> <p>(a)</p> <p>Despite that answer's (probably-not-necessarily-correct) opening sentence, <br> it's only a counterexample to "$h$ is <em>necessarily</em> one-way", not to "$h$ is one-way". <br><br><br> (b)</p> <p>That answer's attack does not require inverting ​ $\hspace{.04 in}f(x_1) \oplus f(x_2)$ ​ "to $x_1x_2$", <br> it just involves finding a <a href="https://en.wikipedia.org/wiki/Preimage_attack" rel="nofollow">preimage</a> of ​ $\hspace{.04 in}f(x_1) \oplus f(x_2)$ ​ under $h$.</p> https://cs.stackexchange.com/questions/52249/-/52251#52251 1 Answer by Ran G. for XOR of one-way function Ran G. https://cs.stackexchange.com/users/157 2016-01-25T00:26:44Z 2016-01-25T00:26:44Z <p>The question there asks:</p> <blockquote> <p>"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."</p> </blockquote> <p>This claim is incorrect. There exists some $f$ whose respective $h$ is not one way anymore.</p> <p>However, the above doesn't apply to <em>all</em> $f$'s. It is possible that there exists <em>some</em> one-way $f$ whose respective $h$ remains one-way. But it needs not happen, as the example in that answer proves.</p> <p><br> 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. </p> <p>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.</p>