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?
$\begingroup$
$\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
Add a comment
|
$\begingroup$
$\endgroup$
1
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!
answered Jun 16 '20 at 10:30
-
$\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
