-1
$\begingroup$

I read a book about one-way function. In this book, I saw 2 exercises that I can't understand and don't know how to solve. Can anyone help me to solve these?

  1. Is $f(x,y)=x+y$ a one way function?
  2. Is $f(x)=x^2$ a one way function?
$\endgroup$
  • 2
    $\begingroup$ What is the name and chapter/page of the book? What did you try? $\endgroup$ – kelalaka Dec 9 '18 at 14:46
  • $\begingroup$ Please edit your question to contain answers to kelalaka's questions and please also state the definition of "one way function" from said book. $\endgroup$ – SEJPM Dec 9 '18 at 15:55
  • 4
    $\begingroup$ Are those functions defined over the integers or some other structure? $\endgroup$ – Maeher Dec 9 '18 at 16:38
  • 4
    $\begingroup$ Well, what's the context of those exercises? You need to give us something to work with. $\endgroup$ – Maeher Dec 9 '18 at 19:52
  • 2
    $\begingroup$ @john You have to find out whether or not these functions are defined over integers or not (e.g. are done $\bmod N$), because it will completely determine the answer to the question. $\endgroup$ – Ella Rose Dec 9 '18 at 23:43
2
$\begingroup$

First lets clarify what a one-way function is. Informally a one-way function is a function that is easy to compute but hard to invert.

More formally a function $f : \{0,1\}^* \to \{0,1\}^*$ is one-way, if

  1. There exists a polynomial time algorithm $M_f$ that computes $f$, i.e., for all $x$, $M_f(x)=f(x)$.

  2. For every probabilistic polynomial time algorithm $\mathcal{A}$, there exists a negligible function $\epsilon$, such that $$\Pr\big[x\gets \{0,1\}^n,\ y:= f(x),\ x'\gets\mathcal{A}(1^n,y) : f(x')=y\big] \leq \epsilon(n).$$

Now do the two functions you're asking about conforming to these definitions?

First, let me note that we cannot give an affirmative answer to that question without making assumptions. The reason being, that is is unknown whether one-way functions exist. Presenting an unconditional one-way function would resolve among other things the famous open question whether $\mathsf{P}=\mathsf{NP}$.

An additional problem is that given the information you gave us, we do not really know which structure the functions are defined over. If we assume that the functions are defined over the integers, then neither function is one-way.

Both are easy to compute, however they are also easy to invert.

  1. Lets first consider the function $f(x,y) = x+y$. Given $z := x+y$, an algorithm $\mathcal{A}$ can simply output $(x',y')=(z,0)$. This is obviously polynomial time and according to regular integer arithmetic $z+0 = z$ and thus $\mathcal{A}$ is successful with probability $1$.

    More generally this attack works over any structure with an additive identity, be that a field, ring, group, or even a monoid.

  2. For the function $f(x) = x^2$ things are a bit less clear. Over the integers, $f$ is also easy to invert. There are efficient algorithms for computing the square root of perfect squares over the integers.

    However, as hinted by Ella Rose, this is not known to be true over some structures. Specifically, if we define the function over the integers modulo $N$, where $N$ is a large semiprime with two distinct, equal length but unknown prime factors, then finding a square root is equivalent to factoring $N$, a problem that is believed to be hard. In fact, the Rabin cryptosystem is based on the hardness of this problem.

$\endgroup$
0
$\begingroup$

You can wiki the definition of a one way function yourself so I won't repeat it, other than to hint that being lossy /compressive is not sufficient to formally qualify . So,

  1. Clearly there are infinite preimages ($x,y$ pairs) that can replicate any output from $f$. Therefore not formally a one way function.

  2. $\sqrt f$ only has a maximum of four possible solutions for $x$ (depending on whether you go complex or not). So no too.

$\endgroup$
  • 3
    $\begingroup$ This answer assumes context that is not specified in the question. If $f(x) = x^2$ is done $\bmod N$, then the ability to compute square roots is as hard as factoring $N$, and so if factoring is hard and the factors of $N$ are not known, then $f(x) = x^2 \bmod N$ behaves like a one-way function. $\endgroup$ – Ella Rose Dec 9 '18 at 23:41
  • $\begingroup$ @EllaRose Well you're right for your $f$, but john's not put that into the question. We'll have to wait to see what he says, and I'll flip (2) if there's a moddy thing. kelalaka's asked for clarification. $\endgroup$ – Paul Uszak Dec 9 '18 at 23:57

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.