In these slides, it is mentioned that for a class of functions $\mathcal{C}$, a pseudorandom generator is a distribution $D$ such that

  1. $D$ fools $\mathcal{C}$.
  2. $D$ is efficiently samplable.
  3. $D$ is sampled using a few random bits.

Then if you want to achieve $(1)$ and $(2)$, let $D = U$, where $U$ is the uniform distribution. This is clear to me. It's mentioned further that for $(1)$ and $(3)$: $\forall \mathcal{C}$ $\exists$ inefficiently samplable $D$ using $O(\log \log |\mathcal{C}|)$ random bits. Could someone explain how to construct such an inefficient $D$?

  • 2
    $\begingroup$ Use the probabilistic method. A random function is a PRG with high probability. $\endgroup$ – Or Meir Jun 17 '15 at 16:21
  • $\begingroup$ Why $O(\log \log |\mathcal{C}|)$ random bits needed in this case? $\endgroup$ – user34478 Jun 17 '15 at 16:39
  • 2
    $\begingroup$ Try to do the calculation. $\endgroup$ – Or Meir Jun 17 '15 at 19:48
  • $\begingroup$ You have log|C| random elements in your distribution. How many bits do you need to choose one of them at random? $\endgroup$ – Kaveh Jun 17 '15 at 19:51
  • $\begingroup$ @Kaveh But $\mathcal{C}$ is the class of functions to be fooled. How can this be related to the number of random functions to choose from, which should fool all $f \in \mathcal{C}$? That is, first we fix a distribution $D$, then the promise is it should fool $\mathcal{C}$, meaning this should be oblivious to the size of $\mathcal{C}$. $\endgroup$ – user34478 Jun 17 '15 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.