0
$\begingroup$

I have to prove that the function $f\colon \mathbb N × \mathbb N \to \mathbb N$ defined by $f(x, y) = x + y$ and $|x| = |y|$ isn't a one-way function. How do I go around doing that?

$\endgroup$
1
  • 1
    $\begingroup$ Write the definition. What would it mean for $f$ not to be a one-way function? $\endgroup$ – Yuval Filmus Jun 16 '20 at 10:28
1
$\begingroup$

A function $f$ is one-way if given $f(z)$ for random $z$, it is hard to find an input $w$ such that $f(w) = f(z)$. So in order to show that $f$ isn't one way, you need to show that given $f(z)$ for random $z$, it is not hard to find an input $w$ such that $f(w) = f(z)$. Good luck!

$\endgroup$
1
  • $\begingroup$ Thank you! I was being a bit dumb, should've thought more about the definition of a OWF. When you look at things that way, it becomes pretty easy :D Thanks again for the help! $\endgroup$ – Pedro Costa Jun 16 '20 at 10:42

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.