1
$\begingroup$

I can't seem to find an answer to this. For instance, I have this question:

Show that, if $P=NP$, there aren't any pseudo-random generators (even with amplification factor $n+1$).

My gut tells me this is because, in a world where $P=NP$, pretty much any process can be efficiently inverted so there aren't one-way functions (which pseudo-random generators rely on).

$\endgroup$
3
$\begingroup$

Amplification is equivalent to "stretch", the number of (seemingly) random bits that your algorithm generates given the truly random seed.

Let $G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a PRG that maps strings of length $n$ to strings of length $l(n)$, then $l(n)$ is said to be the stretch function of $G$. If $l(n)>n$ and $l$ is injective, then you have $\forall n :|Im(G)\cap\{0,1\}^n|\le 2^{n-1}$. You can use this to construct a language $L\in NP$, such that $L\in P$ allows you to break $G$ (construct a distinguisher with success probability $\ge\frac{1}{2})$. Note that you can relax the injectivity requirement by ignoring some of the output (i.e. given a PRG with stretch $l(n)>n$, you can construct a PRG with stretch $l'(n)=n+1$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm having trouble understanding this expression: $\forall n :|Im(G)\cap\{0,1\}^n|\le 2^{n-1}$. What is $Im$ in this context? $\endgroup$ – Pedro Costa Jun 17 at 9:49
  • 1
    $\begingroup$ The image of $G$ $\endgroup$ – Ariel Jun 17 at 10:01
  • $\begingroup$ Then isn't $Im(G)\cap\{0,1\}^n = \emptyset$ since $Im(G)$ has outputs with size $n+1$ (considering the example I gave) and $\{0,1\}^n$ has outputs with size $n$. So, let's say, isn't $000$ considered different from $00$? $\endgroup$ – Pedro Costa Jun 17 at 11:13
  • $\begingroup$ $Im(G)$ is the image of $G$ as a function from $\{0,1\}^*$ to $\{0,1\}^*$, you were talking about $Im\left(G|_{\{0,1\}^n}\right)$ $\endgroup$ – Ariel Jun 17 at 11:14
  • $\begingroup$ But you said $G$ maps strings of length $n$ to strings of length $l(n)$. So in that case, won't $Im(G)$ have outputs with size $l(n)$? $\endgroup$ – Pedro Costa Jun 17 at 11:17

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.