# Inefficient pseudorandom distribution using a few random bits

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

• Use the probabilistic method. A random function is a PRG with high probability. – Or Meir Jun 17 '15 at 16:21
• Why $O(\log \log |\mathcal{C}|)$ random bits needed in this case? – user34478 Jun 17 '15 at 16:39
• Try to do the calculation. – Or Meir Jun 17 '15 at 19:48
• You have log|C| random elements in your distribution. How many bits do you need to choose one of them at random? – Kaveh Jun 17 '15 at 19:51
• @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}$. – user34478 Jun 17 '15 at 20:10