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?


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

  • $\begingroup$ Thanks. In case 2, we indeed make an assumption about $U$ and $V$: The assumption is that they are generated by probabilistic PSPACE (or NEXP) Turing machines, since all parties in the protocol are thus limited. Although there's one subtlety: The BPP party of the protocol receives $z$. $z$ is assumed to be the extra knowledge to this party, but this knowledge (such as the history of his previous interactions) cannot be generated by machines whose power is beyond PSPACE (NEXP) right? $\endgroup$ Dec 26, 2010 at 11:37
  • $\begingroup$ If $U$ and $V$ are generated like that then we should be in Case 1 and the question is if my $f$ there is computed using only polynomial space? Seems unclear since we would need a bound on how separated the various $n$'s are... $\endgroup$ Dec 26, 2010 at 17:32

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.