# Proving a function is a one way function

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

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?

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.
• @graphtheory92 The key observation is that if $x$ and $y$ are uniformly and independently distributed, then so are $x$ and $x \oplus y$, so since $w$ is chosen independently of $x$, $f(x)||f(w)$ is identically distributed to $f(x)||f(x\oplus y)$, and so the success probability of $A'$ is at least that of $A$ (because if $A$ succeeds, so does $A'$). – fkraiem Feb 21 '16 at 0:30