1
$\begingroup$

Suppose the following PRG $G : \{0,1\}^n \rightarrow \{0,1\}^{n +l}$, I want to prove that $G$ is one way function (and not building one), for:

  1. $l = \omega (\log n)$
  2. $l = 1$

For $l = \log n$, suppose that $G$ isn't OWF, so there's an inverter $A$ which succeeds w.p. $\geq 1/p(n)$, trying to build a distinguisher $B$ from inverter $A$ to $G$, I can do as follows:

$B(y)$ assigns 1 to each input successfully inverted. So $\Pr[B(y) = 1 : y = f(x) = G(x)] \geq 1/p(n)$, and for random input $\Pr[B(U_{n + \log n})] \geq 2^{n}/2^{\log n + n}$. All in all, the distinguisher succeeds w.p.

$$|\Pr[B(y) = 1 : y = f(x) = G(x)] - \Pr[B(U_{n + \log n})]| \geq 1/n - 1/p(n) \geq 1/2n$$

But for $l=1$, I get a bound of $1/4$ ($1/2 -1/p(n) \geq 1/4$)... It doesn't feel correct, but does (?) follow the definition of distinguisher for PRGs.

What am I missing?

$\endgroup$
  • $\begingroup$ From the question, it's completely unclear what you are actually doing, and then where the problem is. But maybe this question and answer is helpful to you. However, the properties of PRFs, PRGs and OWFs are to some degree related but not the same. For a correct proof the details matter. $\endgroup$ – tylo Nov 27 '17 at 14:29
  • $\begingroup$ @tylo I updated the question, could you look again? $\endgroup$ – Napoleon Nov 27 '17 at 15:17
  • $\begingroup$ What exactly is your question? Why 1/4 is sufficient advantage for a PRF distinguisher? Your proof itself - though missing a lot of details - would appear to be on the right track. $\endgroup$ – Maeher Nov 28 '17 at 1:12
  • $\begingroup$ I want to prove that $G$ is OWF. 1/4 is enough, because its PRG should be computional indistinguishble for any negligible function, and 1/4 is greater for any negligeble function $\endgroup$ – Napoleon Nov 28 '17 at 7:48
1
$\begingroup$

$$l = \log n: \Pr[B(Un+\log n)]≥2^n/2^{n+\log n} \cdot 1/p(n)$$ Since even if the input of $B$ is from the image of $G$, the probability to invert it is $1/p(n)$. So you need to correct this case and it will help you with $l = 1$.

$\endgroup$
  • $\begingroup$ Firat of all, shouldn't your bound be $\leq$ (cause otherwise you can't bound $|\Pr[B(G(U_n)) = 1] - \Pr[B(U_{n + \log n})]|$)? Second, if I follow your way, for $l = \log n$ we get bound of $1/2p(n)\log n$, and for $l = 1$ we've get a bound of $\geq 2^n/2^{n+1}/p(n) = 1/2p(n)$. Am I correct? And finally, I stiil don't understand what's wrong with my previous way. $\endgroup$ – Napoleon Nov 29 '17 at 14:36
  • $\begingroup$ in the random case, it's not enough to be from the image. first of all, it should be from the image and then A should invert it right the second is done with probability 1/p(n). $\endgroup$ – sosolo Nov 29 '17 at 14:56
  • $\begingroup$ Indeed, but now how you can bound from below, the substraction of two prob. which theoretically can both be big? $\endgroup$ – Napoleon Nov 29 '17 at 15:02
  • $\begingroup$ $1/p(n) - 2^{n}/(2^{n+1}*p(n)) = 1/p(n)$ so G isn't a PRG $\endgroup$ – sosolo Nov 29 '17 at 15:09

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.