Proving a function is a one way function

Question

I am trying to prove that a function is a one-way function.

The function I am working on in particular is $f'(x,y)=f(x)||f(x \oplus y)$.

For what I have understood looking at similar solved solutions (e.g. 1c), the strategy is the following:

1. Assume $f'$ is not one way, so exists an $A'$ that can invert $f'$ with non-negligible probability
2. Use $A'$ to construct $A$ that can invert $f$.
3. Show that $A$ inverts $A$ with non-negligible probability
4. Contradiction.

Based on this knowledge, I am trying to prove the given

$$f'(x,y)=f(x)||f(x \oplus y)$$

---

So, here is my attempt:

1. Assume $f'(x,y)$ is not one way function
2. So, exists a $A'$ that can invert $f'$ probability

3. Construct

   $A(z)$:

   • pick a $w \in f(x)$ (for any $x$)
   • $x,y <- A'(f(z, y)) = A'(f(x) || f(x \oplus w))$
   • we have now inverted the first half
   • ...
   • return $x,y$

However, although I understand the method I cannot find any valid way of making the construction:

• How can you build such construction?
• Is there something I am doing wrong? or am I in the right direction?

Answer 1

The easiest way to construct a probabilistic $A$ is simply, given $z$:

• Select a random $w$
• Compute $A'(z || f(w))$.
• If $A'$ succeeds, then it'll evaluate to an $(x, y)$ pair with $z = f(x)$ and $f(w) = f(x \oplus y)$.
• Discard $y$, and return $x$ as $A(z)$.

We select a random $f(w)$, rather than just inserting another copy of $z$, because it is possible that $A'$ would always fail on an input of the form $(z || z)$. As I have written, if $A'$ succeeds on a nontrivial fraction of its inputs, then $A$ will succeed on the same nontrivial fraction of its inputs.