3
$\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?

Improve this question
$\endgroup$
4
  • $\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
    Commented Nov 27, 2017 at 14:29
  • $\begingroup$ @tylo I updated the question, could you look again? $\endgroup$
    – Napoleon
    Commented Nov 27, 2017 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
    Commented Nov 28, 2017 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
    Commented Nov 28, 2017 at 7:48

1 Answer 1

Reset to default
2
$\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$.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Nov 29, 2017 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
    Commented Nov 29, 2017 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
    Commented Nov 29, 2017 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
    Commented Nov 29, 2017 at 15:09

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