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.


1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$
    – user50394
    Commented Jan 6, 2023 at 17:31
  • $\begingroup$ Interesting question. I think it should be possible to derandomise the construction and fix an oracle. (Don't think there is anything circular going on here though.) $\endgroup$
    – ckamath
    Commented Jan 6, 2023 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.