5
$\begingroup$

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)$?

$\endgroup$
5
  • 2
    $\begingroup$ Nicely formatted question, but extreme nitpick: British English: "initialise" and "finalise", American English: "initialize" and "finalize" choose 1. "Finilize" seems a typo. $\endgroup$
    – Maarten Bodewes
    Oct 10, 2023 at 1:10
  • 1
    $\begingroup$ Yes, this is rare and requires encouragement. +1 for the nice format... $\endgroup$
    – kelalaka
    Oct 10, 2023 at 10:13
  • $\begingroup$ 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. $\endgroup$
    – Chris
    Oct 10, 2023 at 10:56
  • $\begingroup$ Note that, once answered, do not change the question too much, this can make the answer invalid.. $\endgroup$
    – kelalaka
    Oct 10, 2023 at 11:35
  • $\begingroup$ Sure, but I think all comes down to the non-onewayness of $f$... $\endgroup$
    – Chris
    Oct 10, 2023 at 11:48

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Chris
    Oct 10, 2023 at 10:59
  • $\begingroup$ 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? $\endgroup$
    – Chris
    Oct 10, 2023 at 11:04
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Mikero
    Oct 10, 2023 at 14:57
  • $\begingroup$ 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$? $\endgroup$
    – Chris
    Oct 10, 2023 at 16:04
  • $\begingroup$ Thanks for your answer. I may open another topic :) $\endgroup$
    – Chris
    Oct 12, 2023 at 10:57

Your Answer

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

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