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

<p>It seems the answer to the first question (following "The question is") is <strong>No</strong> 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&lt;n$ are called off and $f(1^m)$ is defined arbitrarily. Then another parallel search is instituted for a larger value of $n$. </p>

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

<p>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.  </p>

CC BY-SA 2.5
2010-12-26T11:37:34.570Z
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?
Sadeq Dousti
CC BY-SA 2.5
2010-12-26T17:32:59.543Z
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...
Bjørn Kjos-Hanssen
CC BY-SA 2.5
2010-12-26T07:24:57.203Z
2010-12-26T07:24:57.203Z
Bjørn Kjos-Hanssen
<p>One of the cornerstones of the modern cryptography is the definition of <strong>computational indistinguishability</strong>: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc.</p>
<p>Below, we will first define this concept, and then investigate some of its properties:</p>
<p>Let <span class="math-container">$U=\{U_n\}$</span> and <span class="math-container">$V=\{V_n\}$</span> be two distribution ensembles, indexed by natural numbers. That is, for every <span class="math-container">$n \in \mathbb{N}$</span>, <span class="math-container">$U_n$</span> and <span class="math-container">$V_n$</span> are probability distributions. We call <span class="math-container">$U$</span> and <span class="math-container">$V$</span> <strong>computationally indistinguishable</strong> if, for all probabilistic Turing machine <span class="math-container">$D$</span> which is polynomial-time in the length of its first input, all positive polynomial <span class="math-container">$p(\cdot)$</span>, every sufficiently large <span class="math-container">$n \in \mathbb{N}$</span>, and all advice strings <span class="math-container">$z \in \{0,1\}^*$</span>:</p>
<p><span class="math-container">$\left|\Pr_{u \leftarrow U_n}[D(1^n,u,z)=1]-\Pr_{v \leftarrow V_n}[D(1^n,v,z)=1]\right|&lt;\frac{1}{p(n)}.$</span></p>
<p>The probability is taken over the choice of <span class="math-container">$u$</span> and <span class="math-container">$v$</span>, as well as the internal coin tosses of <span class="math-container">$D$</span>.</p>
<p>An equivalent definition is obtained by replacing the <span class="math-container">$\forall z \in \{0,1\}^*$</span> part by a quantifier over all functions <span class="math-container">$f$</span>, and letting <span class="math-container">$z=f(1^n)$</span>. Note that <span class="math-container">$f$</span> can be an uncomputable function.</p>
<p>The question is:</p>
<blockquote>
<p>Are there distribution ensembles <span class="math-container">$U$</span> and <span class="math-container">$V$</span> which are computationally <strong>distinguishable</strong>, but if we restrict <span class="math-container">$f$</span> to computable functions, then <span class="math-container">$U$</span> and <span class="math-container">$V$</span> are computationally <strong>indistinguishable</strong>?</p>
</blockquote>
<p><a href="http://www.wisdom.weizmann.ac.il/%7Eoded/PS/uniform.ps" rel="nofollow noreferrer">Goldreich</a> argued that in cryptographic settings, where all parties are modeled by probabilistic polynomial-time Turing machines, <span class="math-container">$f$</span> must be computable by a polynomial-time machine.</p>
<p>Now consider other settings, such as the case of single- or multi-prover interactive proofs. It is proven (<a href="https://dl.acm.org/doi/10.1145/146585.146609" rel="nofollow noreferrer">Shamir</a>, <a href="https://doi.org/10.1007/BF01200056" rel="nofollow noreferrer">Babai <em>et al.</em></a>) that the parties in such systems need not be more powerful than PSPACE and NEXP machines, respectively.</p>
<blockquote>
<p>Is it rational to consider uncomputable functions <span class="math-container">$f$</span> in such cases? In particular, do we need to consider <span class="math-container">$f$</span> to be computable by machines whose power is beyond PSPACE or NEXP, respectively?</p>
</blockquote>

<cc.complexity-theory><computability><cr.crypto-security><advice-and-nonuniformity>
The Complexity of Advice in Computational Indistinguishability
Sadeq Dousti
# The Complexity of Advice in Computational Indistinguishability

(Asked by: username_0 on 2010-12-25)

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](http://www.wisdom.weizmann.ac.il/%7Eoded/PS/uniform.ps) 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](https://dl.acm.org/doi/10.1145/146585.146609), [Babai *et al.*](https://doi.org/10.1007/BF01200056)) 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?

**Tags:** cc.complexity-theory, computability, cr.crypto-security, advice-and-nonuniformity


---

## 1 answers

### Answer by username_1 on 2010-12-26. Score: 2 | Accepted answer

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

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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...  

---

