7
$\begingroup$

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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