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:
- Assume $f'$ is not one way, so exists an $A'$ that can invert $f'$ with non-negligible probability
- Use $A'$ to construct $A$ that can invert $f$.
- Show that $A$ inverts $A$ with non-negligible probability
- 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:
- Assume $f'(x,y)$ is not one way function
- So, exists a $A'$ that can invert $f'$ probability
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?