The Complexity of Advice in Computational Indistinguishability

Question

One of the cornerstones of the modern cryptography is the definition of computational indistinguishability: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc.

Below, we will first define this concept, and then investigate some of its properties:

Let $U=\{U_n\}$ and $V=\{V_n\}$ be two distribution ensembles, indexed by natural numbers. That is, for every $n \in \mathbb{N}$, $U_n$ and $V_n$ are probability distributions. We call $U$ and $V$ computationally indistinguishable if, for all probabilistic Turing machine $D$ which is polynomial-time in the length of its first input, all positive polynomial $p(\cdot)$, every sufficiently large $n \in \mathbb{N}$, and all advice strings $z \in \{0,1\}^*$:

$\left|\Pr_{u \leftarrow U_n}[D(1^n,u,z)=1]-\Pr_{v \leftarrow V_n}[D(1^n,v,z)=1]\right|<\frac{1}{p(n)}.$

The probability is taken over the choice of $u$ and $v$, as well as the internal coin tosses of $D$.

An equivalent definition is obtained by replacing the $\forall z \in \{0,1\}^*$ part by a quantifier over all functions $f$, and letting $z=f(1^n)$. Note that $f$ can be an uncomputable function.

The question is:

Are there distribution ensembles $U$ and $V$ which are computationally distinguishable, but if we restrict $f$ to computable functions, then $U$ and $V$ are computationally indistinguishable?

Goldreich argued that in cryptographic settings, where all parties are modeled by probabilistic polynomial-time Turing machines, $f$ must be computable by a polynomial-time machine.

Now consider other settings, such as the case of single- or multi-prover interactive proofs. It is proven (Shamir, Babai et al.) that the parties in such systems need not be more powerful than PSPACE and NEXP machines, respectively.

Is it rational to consider uncomputable functions $f$ in such cases? In particular, do we need to consider $f$ to be computable by machines whose power is beyond PSPACE or NEXP, respectively?

Answer 1

Case 1. The distributions $U_n$ and $V_n$ are computable in the sense that we can eventually tell if your displayed inequality is violated, for fixed $n$ and $z$.

It seems the answer to the first question (following "The question is") is No in this case. Suppose there is a $D$ and a $p$ such that for infinitely many $n$, there is a $z$ violating the inequality. I claim we can find a computable function $f$ such that $f(1^n)$ is infinitely often such a $z$. What $f$ does is run all searches for $z$ for various values of $n$ in parallel. When one is found for some $n$, we define $f(1^n)=z$ and the searches for undefined values $m<n$ are called off and $f(1^m)$ is defined arbitrarily. Then another parallel search is instituted for a larger value of $n$.

Case 2, we do not make any assumption about $U$ and $V$. Then Yes. Both $U_n$ and $V_n$ will be deterministic in the following construction.

Let $D(1^n,w,z)$ simply compute whether $w=z$ and output 1 if this is the case. But $U_n$ and $V_n$ will output the $n$th element $s_n$, $t_n$, of sets $S$ and $T$, respectively. Then such a function $f$ would have the property that infinitely often $f(1^n)=s_n\ne t_n$ or vice versa. Now suppose that $n\mapsto s_n$ and $n\mapsto t_n$ both dominate all computable functions, and $\{n: s_n\ne t_n\}$ is infinite (such sets $S$ and $T$ clearly exist). Then a function $f$ exists with the required property, but cannot be computable.