Score:3

Distribution distinguishability as a decision problem

cl flag

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.

Score:1
ag flag

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

user50394 avatar
cl flag
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.
ckamath avatar
ag flag
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.)
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.