# Distribution distinguishability as a decision problem

In the definition of a pseudorandom function, we consider two distributions $$D_0$$ and $$D_1$$ over functions, where $$D_0$$ is the distribution of a random function and $$D_1$$ is the distribution of a pseudorandom function (defined as the distribution of $$F_k$$ under uniform $$k$$ for some public function $$F$$). The function $$F\sim D_1$$ is pseudorandom if no probabilistic polynomial time (PPT) machine can distinguish it from $$F\sim D_0$$. More formally, two oracle distributions $$D_0$$ and $$D_1$$ are computationally indistinguishable if for every PPT distinguisher $$M$$, $$\left|\Pr_{O\sim D_0}[M^O(1^n)=1]-\Pr_{O\sim D_1}[M^O(1^n)=1]\right|=n^{-\omega(1)}.$$

I think that this definition can be phrased as an oracular language not in $$\mathsf{BPP}$$, but I am not sure how to do it. Hence my question is: Can we define a language $$L^A$$ which is not in $$\mathsf{BPP}^A$$ for some oracle $$A$$ iff $$D_0$$ and $$D_1$$ are computationally indistinguishable for any PPT machine?

As mentioned in this paper by Bennett and Gill, relative to a random oracle $$A$$, we can define a language $$L^A=\{1^n:\text{the first 2^n bits of A have n consecutive zeros}\}$$ and clearly $$L^A\notin\mathsf{P}^A$$. I am not sure how to solve my question because it refers to two distributions over functions.

Here's a candidate. Let's define $$A=\{A_n:\{0,1\}^n\to\{0,1,\}^n\}_{n\in\mathbb{N}}$$ to be a "hybrid" oracle, i.e., the $$n$$-th oracle $$A_n$$ is sampled either from $$D_{0,n}$$ or $$D_{1,n}$$ with probability $$1/2$$. The language $$L^A$$ is now defined as $$L^A:=\{1^n:A_n \text{ is pseudorandom}\}.$$ We claim that $$L^A\notin\mathbf{BPP}^A$$. Suppose for contradiction that it is, and let $$\mathsf{D}^A$$ be the PPT machine that decides $$L^A$$ in an infinitely-often manner. By definition of $$A$$, $$\mathsf{D}^A$$ can distinguish between $$D_0$$ and $$D_1$$ infinitely-often and hence break the pseudorandomness of $$F$$.
• Thanks. In the example due to Bennett and Gill, the definition of $L^A$ itself does not refer to any distribution, and then if $A$ is random, $L^A\notin\mathsf{P}^A$ with probability 1. Your definition of $L_A$ depends on both distributions, and I wonder if the dependence is necessary or makes it circular. Jan 6, 2023 at 17:31