## Introduction

The problem concerns two pseudorandom generators

**RandFunc1**and**RandFunc2** Say a distinguisher D gets to make q queries to either RandFunc1 or RandFunc2, but D does not know whether it is making queries to RandFunc1 or RandFunc2. However, D’s job is to try to tell whether its queries are being answered by RandFunc1 or RandFunc2. (We assume that D is not allowed to reset the table T to being uninitialized—what I mean is that D is always talking to the “same” copy of RandFunc1 or RandFunc2, whichever it is.) We define D’s advantage $\Delta_D$ as the quantity \begin{equation} \Delta_D = \Pr[D^{RandFunc1} = 1]-\Pr[D^{RandFunc2} = 1] \end{equation} Here $D^{RandFunc1}$ means “D with oracle access to RandFunc1” and likewise $D^{RandFunc2}$ means “D with oracle access to RandFunc2”. The notation $D^{RandFunc1} = 1$ means that D outputs the bit ‘1’ after making its q queries (we assume that D outputs 0 or 1). So if, after seeing the query answers, D thinks it is speaking to RandFunc1, then it should output 1; and if it thinks that it is speaking to RandFunc2, then it should output 0.

## The Frequentist's Approach

A frequentist, knowing n

othing about Bayesianism, would naturally following the Maximum Likelihood approach. The disting uisher would be assumed to make decisions and output the hypothesis with larger likelihood. Let $m = 2^n$. Given $q$ observations, the likelihood of

**RandRunc1**is \begin{equation} p_1 = \binom{q}{k}{(\frac{1}{m})^k(1-\frac{1}{m})^{q-k}} \end{equation} and the likelihood of \textbf{RandFunc2} is \begin{equation} p_2 = \binom{q}{k}{(\frac{1}{m^2})^{k}(1-\frac{1}{m^2})^{q-k}} \end{equation} where there are $k$ 0s in the observations. The distinguisher outputs 1 if and only if $p_1 > p_2$. Let the support involved in such event be $S$. \begin{equation} \Delta_D = \Pr[D = 1 | RandFunc1] - \Pr[D=1 | RandFunc2] = \sum\limits_{s \in S}{p_1(s)}-\sum\limits_{s \in S}{p_2(s)} \end{equation} This is exactly the statistical distance between the two distributions. Therefore, \begin{equation} \Delta_D = \sum\limits_{s \in S}\binom{q}{k}{(\frac{1}{m})^k(1-\frac{1}{m})^{q-k}}-\binom{k}{q}{(\frac{1}{m^2})^{k}(1-\frac{1}{m^2})^{q-k}} \end{equation} which is equal to \begin{equation} \Delta_D = \sum\limits_{s \in S}\binom{q}{k}{(\frac{1}{m})^{k} (1-\frac{1}{m})^{q-k}(1-(\frac{1}{m})^k (1+\frac{1}{m})^{q-k})} \end{equation} Clearly $(\frac{1}{m})^k (1+\frac{1}{m})^{q-k}$ is a monodically decreasing function with respect to $k$. So \begin{equation} \Delta_D = \sum\limits_{k=1}^{q}\binom{q}{k}{(\frac{1}{m})^{k} (1-\frac{1}{m})^{q-k}|1-(\frac{1}{m})^k (1+\frac{1}{m})^{q-k}|} \end{equation} \begin{equation} \Delta_D \leq \sum\limits_{k=1}^{q}\binom{q}{k}{(\frac{1}{m})^{k} (1-\frac{1}{m})^{q-k}} = 1-(1-\frac{1}{m})^{q} \end{equation} This is bounded by $\Delta_D \leq \frac{q}{m}$ according to Bernoulli's Inequality. Therefore at least $q = \Omega(m)$ queries are needed to have advantage $\Omega(1)$. We now show that such number of queries are \textbf{sufficient} to have advantage $\Omega(1)$. We can in principle compute the support $S$ explicitly. Consider the inequality \begin{equation} 1-\binom{q}{k}(\frac{1}{m})^{k}(1+\frac{1}{m})^{q-k} \geq 0 \end{equation} We have \begin{equation} k \geq k_0 = \frac{q \ln(1+\frac{1}{m})}{\ln(1+\frac{1}{m})+\ln(m)} \approx \frac{q}{m \ln(m)} \end{equation} This implies that \begin{equation} \Delta_D \geq (1-\frac{1}{m^2})^{q}-(1-\frac{1}{m})^{q} \approx \frac{q}{m}-\frac{q}{m^2} \end{equation} This implies that queries unto $\Theta(\frac{m^2}{m-1}) = \Theta(m)$ is sufficient for advantage $\Theta(1)$.## The Bayesianist's Approach

A Bayesianist, however, would like to compute the

**"posterior distribution"**of each hypothesis based on the observations $Q$. More specifically, the distinguisher's belief of which RandFunc physically exists can be computed by the Bayes theorem: \begin{equation} \Pr[randfunc = RandFunc1 | Q] = \frac{P_1\Pr[Q | RandFunc1]}{P_1\Pr[Q | RandFunc1]+P_2\Pr[Q | RandFunc2]} \end{equation} where $P_1, P_2$ is the prior belief of each function to be present. Suppose we formalize the observations by $Q = (r_1,r_2,...,r_k)$ where $r_i \in \{0,1\}$. The response of some query $r_i = 0$ if and only if the string generated is $00...0$. Therefore, for RandFunc1, $\Pr[r_i = 0] = \frac{1}{m}$ and for RandFunc2 $\Pr[r_i = 0] = \frac{1}{m^2}$. Therefore the Bayes rule reduces to \begin{equation} \Pr[randfunc = RandFunc1 | Q] = \frac{P_1 \frac{1}{m}^u (1-\frac{1}{m})^{k-u}}{P_1 \frac{1}{m}^u (1-\frac{1}{m})^{k-u}+P_2\frac{1}{m^2}^u (1-\frac{1}{m^2})^{k-u}} \end{equation} if there are u $00...0$ in the responses. Therefore, the probability that the distinguisher outputs $1$ is marginalised over all possible function responses for $k$ queries. \begin{equation} \Delta_D = \sum\limits_{u = 0}^{k}{\binom{k}{u} (\frac{1}{m}^u (1-\frac{1}{m})^{k-u}-\frac{1}{m^2}^u (1-\frac{1}{m^2})^{k-u})\frac{P_1 \frac{1}{m}^u (1-\frac{1}{m})^{k-u}}{P_1 \frac{1}{m}^u (1-\frac{1}{m})^{k-u}+P_2\frac{1}{m^2}^u (1-\frac{1}{m^2})^{k-u}}} \end{equation}