Question 2: Alternative pseudo-randomness implies pseudo-randomness

The ubiquitous wrong answer

Suppose $D$ is a distinguisher and $c$ is a constant such that for infinitely many $n$ \begin{equation} \label{eq:D_pr} |p_D(n) - r_D(n)| > 1/n^c \end{equation} The following relationship between $q_D$,$p_D$ and $r_D$ is easily established: \begin{equation} \label{eq:relating_q_p_r} q_D(n) = \frac{1}{2} + \frac{1}{2}(p_D - r_D) \end{equation} Substituting in the lowerbound on $p_D - r_D$ from \eqref{eq:D_pr}, we get that \begin{equation} \label{eq:D_apr} q_D(n) = \frac{1}{2} + \frac{1}{2n^c} \end{equation} which, for $c' = c+1$ shows that $D$ is not alternatively pseudo-random for the same family of $n$.

The glaring error

If $|a - b| > c$ it does not follow that $a - b > c$.

The issue and two correct solutions

What is at issue? Whether $D$ outputs $1$ more often on a pseudorandomly generated string than a randomly generated string may depend on the input length.

Solution 1 (non-uniform setting)

If we fix $n$ we may assume without loss of generality that $p_D(n) > r_D(n)$ (were this not the case, we could replace $D_n$ with the $D_n'(x) = 1 - D_n(x)$).

Many students asserted we could assume that $p_D(n) > r_D(n)$ without fixing $n$. Without reference to $n$, this is an assertion that $\forall n p_D(n) > r_D(n)$. This is incorrect: it is a logical possibility that whether $p_D(n) > r_D(n)$ may vary with on $n$.

It is only legal to fix the input length (thereby defining our distinguisher in a manner that depends upon it) if we are working in the non-uniform setting. Describing your distinguisher as a single algorithm and in manner uniform in the input length (i.e. without reference to it) you are working in the uniform setting.

Solution 2 (uniform setting)

This proposition in question still holds if we restrict ourselves to uniform distinguishers. It is not true the $D$ that breaks the pseudorandomness of $G$ also breaks $G$'s alternative pseudorandomness, however we can define a slightly more complicated $D'$ that does the job. $D'$ on input $\alpha$ where $|\alpha|$ will first guess whether $p_D(n) > r_D(n)$ and then either output $D(\alpha)$ or $1 - D(\alpha)$.

How do we guess if $p_D(n) > r_D(n)$? One can estimate $p_D(n)$ by running $D$ on samples from $G(U_n)$ (likewise for $r_D(n)$). If the estimates $\widehat{p_D(n)}$ and $\widehat{r_D(n)}$ are sufficiently precise enough of the time, then whether $\widehat{p_D(n)} > \widehat{r_D(n)}$ can be used as a proxy for $p_D(n) > r_D(n)$. The chernoff bound can be used to determine the number of trials needed to obtain sufficient precision and confidence of the aforementioned estimators.