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$
$\endgroup$
5
-
$\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$– Sasho NikolovCommented 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$– Gilles 'SO- stop being evil'Commented Mar 13, 2013 at 20:11
-
$\begingroup$ How do you define $h(x)$ when $|x|$ is odd? $\endgroup$– Gilles 'SO- stop being evil'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$– fraflCommented Mar 15, 2013 at 11:01
-
$\begingroup$ @frafl probably it doesn't matter. $\endgroup$– Ran G.Commented Mar 18, 2013 at 1:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$– fraflCommented 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$– fraflCommented Mar 25, 2013 at 19:11