# What is a non-OWF?

We know that A function $$f:\Bbb Z_2^n \longrightarrow\Bbb Z_2^m$$ is a (strong) one-way function (OWF), if:

• $$f$$ can be computed by a PT algorithm. Equivalently, there exists a PPT algorithm that on input $$x$$ outputs $$f(x)$$, for all $$x\in \Bbb Z_2^n$$.
• For all PPT adversaries $$A$$, there exists a negligible function $$\operatorname{negl}_A(n)$$ such that, for all large enough $$n$$, we have $$\operatorname{Pr}\left[f(x)=f(z): x \stackrel{\\\}{\leftarrow}\Bbb Z_2^n,\ z \leftarrow A(f(x))\right] \leq \operatorname{negl}_A(n) .$$ In other words, in terms of Games, for all PPT adversaries $$A$$ who play the Game $$\operatorname{OWF}$$ (getting $$f(x)\in \Bbb Z_2^m$$ and returning some pre-image $$z\in \Bbb Z_2^n$$), where

Game $$\operatorname{OWF}_f$$

• Procedure Initialize

• $$x \stackrel{\\\}{\leftarrow}\Bbb Z_2^n$$

• Return $$f(x)$$

• Procedure Finilize($$z$$)

• Return ($$f(x)=f(z)$$)

there exists a negligible function $$\operatorname{negl}_A(n)$$ such that, for all large enough $$n$$, we have $$\Pr[\operatorname{OWF}_f^A\implies \text{True}]\leq \operatorname{negl}_A(n).$$

My Question here is how can we interpret formally the negation of this definition? So, what is a non-OWF $$f$$?

My answer is that there exist an adversary $$A$$ such that the probability that $$A$$ wins the above Game is non-negligible (some people use the term noticeable).

Does this mean that the probability that, for any $$x\in \Bbb Z_2^n$$ (even if this $$x$$ is predefined by us), $$A$$ returns a correct pre-image $$z$$ of $$f(x)$$ is non-negligible?

In addition, does it mean that in this case we can feed $$A$$ with any $$y\in \Bbb Z_2^m$$, it can return us some $$z\in \Bbb Z_2^n$$ such that $$y=f(z)$$ with some noticeable probability? I think that this happens only if $$f$$ is surjective.

Thank you.

Update. So, to be even more precise, assume that we need to implement the following reduction; We want to show that if a function $$f$$ is not an OWF, then we can factor any $$N\in \Bbb Z^+$$. Check Prop 3 of 2.4.2 of these notes. Then, we write a pseudocode to define an adversary $$B$$ against $$N$$, which invokes $$A$$. And it says that $$A$$ takes $$N$$ and returns some value.

I can understand that $$A$$ is an algorithm, so we can put in it any value. But, in $$A(N)$$, how do we precisely employ the fact that $$f$$ is not an OWF?

I would say that if $$f$$ is surjective, then $$N=f(x)$$ for some specific $$x$$. So, if $$A$$ succeeds means that it can find a valid pre-image $$z$$ of $$f(x)$$.

Is the event of picking a specific $$x_0$$ from $$\Bbb Z_2^n$$ and feed $$A$$ with $$f(x_0)$$ a subset of the event that we pick uniformly at random an $$x$$ from $$\Bbb Z_2^n$$ and feed $$A$$ with $$f(x)$$?

• Nicely formatted question, but extreme nitpick: British English: "initialise" and "finalise", American English: "initialize" and "finalize" choose 1. "Finilize" seems a typo. Oct 10, 2023 at 1:10
• Yes, this is rare and requires encouragement. +1 for the nice format... Oct 10, 2023 at 10:13
• Thanks for the nice words, I try to be as clear as possible so that people are able to precisely understand my question and use the introduced notation as well. Oct 10, 2023 at 10:56
• Note that, once answered, do not change the question too much, this can make the answer invalid.. Oct 10, 2023 at 11:35
• Sure, but I think all comes down to the non-onewayness of $f$... Oct 10, 2023 at 11:48

The definition of a OWF involves a distribution over $$x$$. So the negation also involves a distribution.

"$$f$$ is not a OWF" means: [either $$f$$ is not polynomial-time, or] there is a PPT adversary such that $$\Pr[ \text{OWF}^{A}_f \Rightarrow \text{true} ]$$ is nonnegligible function of the security parameter.

My answer is that there exist an adversary $$A$$ such that the probability that $$A$$ wins the above Game is non-negligible (some people use the term noticeable).

I agree with this, but be careful: "non-negligible" and "noticeable" mean slightly different things. See this answer.

Does this mean that the probability that, for any $$x\in \Bbb Z_2^n$$ (even if this $$x$$ is predefined by us), $$A$$ returns a correct pre-image $$z$$ of $$f(x)$$ is non-negligible?

In addition, does it mean that in this case we can feed $$A$$ with any $$y\in \Bbb Z_2^m$$, it can return us some $$z\in \Bbb Z_2^n$$ such that $$y=f(z)$$ with some noticeable probability? I think that this happens only if $$f$$ is surjective.

The only thing we know about $$A$$ is that when you feed it inputs exactly as distributed in the OWF game, it has a certain property. This is a guarantee about $$A$$'s probabilistic behavior when receiving a particular distribution of inputs. We can't infer much about $$A$$'s behavior on any particular input. So I would not write "for any $$x \in \{0,1\}^n$$'' or "any $$y \in \{0,1\}^m$$,'' as you have done.

• Thanks a lot for your answer. Regarding noticeable term, indeed sometimes may mean different things, but in these notes cs.cmu.edu/~goyal/15356/lecture_notes.pdf I followed, he interprets it as a "significant" quantity. Oct 10, 2023 at 10:59
• Now, suppose that we want to implement a reduction, like in Prop 2 of 2.4.2 on the above notes; We assume that $f$ is not an OWF, and we want to prove that for any $N\in \Bbb Z^+$, we can break the Factoring Assumption. So, we try to build an adversary $B$ against $N$, and we used inside its pseudocode $A$. But we have to feed $A$ with $N$. So, how can we imagine happening this? Oct 10, 2023 at 11:04
• I think you misunderstand what it means to break the factoring assumption. See 2.4.1 of those notes. It doesn't mean "there is an algorithm that can successfully factor any $N$", it means "there is an algorithm that succeeds at factoring with non-negligible probability, when its input is drawn from a particular distribution." So the reduction algorithm receives its input $N$ according to some distribution, which conveniently happens to be the same distribution that the adversary sees in $\text{OWF}_f$. Oct 10, 2023 at 14:57
• Indeed, $B(N)$ plays the Game say $\operatorname{Factor}$, which picks to primes $p,q$ uniformly at random and returns their product $N:=pq$ to $B$ and his goal is to find these $p,q$. So, in our case, the Game $\operatorname{Factor}$ picks this $N=pq$ as we said and subsequently invokes $A$. Is the distribution of these $N$s the same as picking $x$ uniformly at random, consider it as a collection of $n^2$ $n$-bit integers, pick the first two, and return $f(x)=pq=N$? Oct 10, 2023 at 16:04
• Thanks for your answer. I may open another topic :) Oct 12, 2023 at 10:57