1
$\begingroup$

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?
$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ this is not enough though, we have to show that A' is non-negligible for the contraddiction $\endgroup$ Feb 20, 2016 at 21:56
  • $\begingroup$ @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'$). $\endgroup$
    – fkraiem
    Feb 21, 2016 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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