计算不可区分性与统计接近性

【统计距离】

对于每个可能的字符串 $\alpha$，分别比较 $P[X_n=\alpha]$ 和 $P[Y_n=\alpha]$，两者的差值表示两个分布在字符串 $\alpha$ 上分配的概率相差多少，将所有可能字符串上的概率差取绝对值后相加，再乘以 $\frac12$，就得到两个分布之间的整体差异。

设两个概率系综分别为 $X=\{X_n\}_{n\in\mathbb N}$，$Y=\{Y_n\}_{n\in\mathbb N}$，对于每个安全参数 $n$，随机变量 $X_n$ 和 $Y_n$ 之间的统计距离（Statistical Distance）定义为：

$$\Delta(X_n,Y_n) \overset{\mathrm{def}}{=} \frac{1}{2} \sum_{\alpha} \left| P[X_n=\alpha] - P[Y_n=\alpha] \right|$$

统计距离满足：

$$0\leq \Delta(X_n,Y_n)\leq 1$$

其中：

• $\Delta(X_n,Y_n)=0$：两个分布完全相同
• $\Delta(X_n,Y_n)$ 接近 $0$：两个分布在统计上非常相似
• $\Delta(X_n,Y_n)$ 接近 $1$：两个分布在统计上差异很大

相应地，两个概率系综之间的统计距离可以表示为关于安全参数 $n$ 的函数：

$$\Delta(n) \overset{\mathrm{def}}{=} \Delta(X_n,Y_n)$$

如果 $\Delta(n)$ 是关于安全参数 $n$ 的可忽略函数，则称概率系综 $X$ 和 $Y$ 是统计接近的（Statistically Close），否则称统计相远的（Statistically Distant）

【统计接近与计算不可区分性】

计算不可区分性可视为概率论中统计接近概念的弱化。统计接近要求两个概率系综在分布本身上非常相似，计算不可区分性只要求任何高效算法都无法发现它们之间的差异。

对于任意区分器 $D$，都有：

$$\left| P[D(X_n)=1] - P[D(Y_n)=1] \right| \leq \Delta(n)$$

这限制了所有区分算法能够获得的最大区分优势，这里的区分算法甚至可以具有无限的计算能力，而不要求一定是多项式时间算法。

因此，如果 $\Delta(n)$ 是可忽略的，那么任意概率多项式时间区分器的区分优势也必然是可忽略的。也就是说，如果两个概率系综 $X$ 和 $Y$ 是统计接近的，那么它们一定也是计算不可区分的。

但两个概率系综计算不可区分，并不意味着它们在统计上接近。可能存在两个概率分布，它们在数学结构上具有非常明显的差异，但发现这种差异需要执行计算上不可行的操作。此时，任何高效算法都无法区分它们，因此它们仍然是计算不可区分的。

所以，统计接近是一个比计算不可区分更强的要求。

【统计相远但计算不可区分】

命题

Proposition：存在概率系综 $X=\{X_n\}_{n\in\mathbb N}$，使得 $X$ 与均匀分布系综 $U\overset{\mathrm{def}}{=}\{U_n\}_{n\in\mathbb N}$ 统计相远，但在多项式时间内不可区分，即：

$$X \approx_c U$$

其中，符号 $\approx_c$ 表示计算不可区分

此外，$X_n$ 的全部概率只分配在至多 $2^{\frac{n}{2}}$ 个 $n$ 比特字符串上。

命题含义

统计相远

均匀分布 $U_n$ 的概率分布在全部 $2^n$ 个 $n$ 比特字符串上，而 $X_n$ 只会输出至多 $2^{\frac{n}{2}}$ 个字符串。因此，$X_n$ 的支撑集只占全部 $n$ 比特字符串中的：

$$\frac{2^{\frac{n}{2}}}{2^n} = 2^{-\frac{n}{2}}$$

设 $S_n$ 是 $X_n$ 的支撑集，即：

$$S_n=\{\alpha:P[X_n=\alpha]>0\}$$

则：

$$P[X_n\in S_n]=1$$

在均匀分布下，有：

$$P[U_n\in S_n] \leq 2^{-\frac{n}{2}}$$

因此：

$$\Delta(n) \geq 1-2^{-\frac{n}{2}}$$

随着 $n$ 增大，该统计距离趋近于 $1$，所以 $X$ 和 $U$ 不仅不是统计接近的，而且在统计意义上相距非常远。

计算不可区分

虽然 $X_n$ 的所有输出都集中在一个很小的集合 $S_n$ 中，但这个集合本身可能无法被任何多项式时间算法识别。

定义函数 $f:\{0,1\}^{*}\rightarrow\{0,1\}$，使得当且仅当 $x$ 属于相应的支撑集时有 $f(x)=1$，即：

$$f(x)= \begin{cases} 1, & P[X_{|x|}=x]>0\\ 0, & P[X_{|x|}=x]=0 \end{cases}$$

那么对于 $X_n$，有：

$$P[f(X_n)=1]=1$$

而对于均匀分布 $U_n$，有：

$$P[f(U_n)=1] \leq 2^{-\frac{n}{2}}$$

因此，函数 $f$ 可以非常明显地区分 $X_n$ 和 $U_n$。

但是，由于 $X$ 和 $U$ 是计算不可区分的，所以这个函数 $f$ 必然无法在多项式时间内计算。否则，$f$ 本身就可以作为一个高效区分器，产生接近于 $1$ 的区分优势，与计算不可区分性矛盾。

这说明，计算不可区分的两个概率系综可以在某些性质上存在巨大差异，只要这些性质无法被高效计算。

证明

证明思路

需要证明：存在一个概率系综 $X=\{X_n\}_{n\in\mathbb N}$ 使得它和均匀分布系综 $U=\{U_n\}_{n\in\mathbb N}$ 满足两个性质：

1. $X$ 和 $U$ 在统计上相距很远
2. $X$ 和 $U$ 在多项式时间内不可区分

证明的核心不是直接构造一个可以高效采样的 $X_n$，而是使用概率方法证明这样的 $X_n$ 存在，即随机选择的对象以正概率满足目标性质，因此至少存在一个确定对象满足该性质。

考虑一个更强的结论：对于所有充分大的 $n$，存在一个随机变量 $X_n$，它只分布在至多 $2^{\frac{n}{2}}$ 个 $n$ 比特字符串上，并且对于任意规模至多为 $2^{\frac{n}{8}}$ 的布尔电路 $C_n$，都有：

$$\left| P[C_n(U_n)=1] - P[C_n(X_n)=1] \right| < 2^{-\frac{n}{8}}$$

这个结论比多项式时间不可区分更强，因为任意多项式时间算法都可以转化为多项式规模电路，而当 $n$ 足够大时，任意多项式规模都小于 $2^{\frac{n}{8}}$。

因此，如果所有规模不超过 $2^{\frac{n}{8}}$ 的电路都无法区分 $X_n$ 和 $U_n$，那么所有概率多项式时间区分器当然也无法区分它们。

证明思路如下：

1. 随机选取一个很小的支撑集
2. 令 $X_n$ 均匀分布在这个支撑集上
3. 证明对于任意固定的小规模电路，这样随机选出来的 $X_n$ 几乎一定能欺骗它
4. 利用布尔不等式说明，存在某个 $X_n$ 能够同时欺骗所有小规模电路
5. 因为所有多项式时间区分器都可以转化为多项式规模电路，所以 $X$ 和 $U$ 是多项式时间不可区分的

支撑集构造

从所有 $n$ 比特字符串组成的集合 $\{0,1\}^n$ 中独立且均匀地选择 $2^{\frac{n}{2}}$ 个字符串：

$$s_1,s_2,\ldots,s_{2^{\frac{n}{2}}}$$

由于这些字符串可以存在重复，因此它们构成一个多重集合。

定义随机变量 $X_n$，先均匀随机选择一个下标 $i\in\{1,2,\ldots,2^{\frac{n}{2}}\}$，然后输出对应的字符串 $s_i$。由于这个多重集合一共只有 $2^{\frac{n}{2}}$ 个元素，所以 $X_n$ 的全部概率质量集中在至多 $2^{\frac{n}{2}}$ 个 $n$ 比特字符串上，即：

$$P[X_n=s_i]=\frac{1}{2^{\frac{n}{2}}}$$

这种构造保证 $X_n$ 的支撑集大小不超过：

$$2^{\frac{n}{2}}$$

固定电路

固定一个具有 $n$ 个输入的布尔电路 $C_n$，设电路 $C_n$ 接收均匀随机字符串时输出 $1$ 的概率为 $p_n$，即：

$$p_n \overset{\mathrm{def}}{=} P[C_n(U_n)=1]$$

对于每个随机选择的字符串 $s_i$，定义随机变量：

$$\zeta_i=C_n(s_i)$$

因为 $C_n$ 是布尔电路，其输出为 $0$ 或 $1$，所以：

$$\zeta_i\in\{0,1\}$$

又因为每个 $s_i$ 都是从 $\{0,1\}^n$ 中独立且均匀选出的，故有：

$$\mathbb E[\zeta_i] = P[C_n(U_n)=1] = p_n$$

而电路 $C_n$ 接收 $X_n$ 的样本时输出 $1$ 的概率实际为：

$$P[C_n(X_n)=1] = \frac{1}{2^{\frac{n}{2}}} \sum_{i=1}^{2^{\frac{n}{2}}} C_n(s_i) = \frac{1}{2^{\frac{n}{2}}} \sum_{i=1}^{2^{\frac{n}{2}}} \xi_i$$

因此，对于固定电路 $C_n$，要证明它无法区分 $X_n$ 和 $U_n$，只需要证明上式样本均值与期望 $p_n$ 非常接近。

Chernoff 界

由于 $\zeta_1,\zeta_2,\ldots,\zeta_{2^{\frac{n}{2}}}$ 是相互独立的 0/1 随机变量，并且每个随机变量的期望都是 $p_n$，所以可以使用 Chernoff 界控制样本平均值与期望之间的偏差。

根据 Chernoff 界，大量独立随机变量的平均值偏离其期望较多的概率非常小。令：

$$m=2^{\frac{n}{2}}, \quad \varepsilon=2^{-\frac{n}{8}}$$

Chernoff 界给出：

$$P\left[ \left| p_n - \frac{1}{m} \sum_{i=1}^{m}\zeta_i \right| \geq \varepsilon \right] \leq 2e^{-2m\varepsilon^2}$$

将 $m,\varepsilon$​ 代入，有：

$$m\varepsilon^2 = 2^{\frac{n}{2}}\cdot(2^{-\frac{n}{8}})^2 = 2^{\frac{n}{2}}\cdot 2^{-\frac{n}{4}} = 2^{\frac{n}{4}}$$

因此：

$$P\left[ \left| p_n - \frac{1}{2^{\frac{n}{2}}} \sum_{i=1}^{2^{\frac{n}{2}}}\zeta_i \right| \geq 2^{-\frac{n}{8}} \right] \leq 2e^{-2\cdot 2^{\frac{n}{4}}} < 2^{-2^{\frac{n}{4}}}$$

这个概率非常小，其说明对于一个固定电路 $C_n$，随机选择出来的多重集合几乎一定满足：

$$\left| P[C_n(U_n)=1] - P[C_n(X_n)=1] \right| < 2^{-\frac{n}{8}}$$

也就是说，随机选择出来的 $X_n$ 几乎一定能够欺骗这个固定电路，即电路接收 $X_n$ 的样本和接收 $U_n$ 的样本时，输出 $1$ 的概率几乎相同。

欺骗小规模电路

仅仅证明 $X_n$ 能够欺骗一个固定电路还不够，还需要证明存在一个 $X_n$，能够同时欺骗所有规模不超过 $2^{\frac{n}{8}}$ 的电路。

规模不超过 $2^{\frac{n}{8}}$ 的电路虽然数量很多，但仍然是有限的。使用布尔不等式，将所有某个小规模电路不能被 $X_n$ 欺骗这一事件的概率加起来，由于单个电路欺骗失败的概率已经被 Chernoff 界控制得非常小，而规模不超过 $2^{\frac{n}{8}}$ 的电路总数虽然很大，但仍然不足以抵消这个极小概率。因此，当 $n$ 足够大时，这一事件的概率仍小于 $1$。

所以，至少存在一组具体的字符串：

$$s_1,s_2,\ldots,s_{2^{\frac{n}{2}}}$$

使得由它们定义的 $X_n$ 能够同时欺骗所有规模不超过 $2^{\frac{n}{8}}$ 的电路。

也就是说，对于所有规模不超过 $2^{\frac{n}{8}}$ 的电路 $C_n$，都有：

$$\left| P[C_n(U_n)=1] - P[C_n(X_n)=1] \right| < 2^{-\frac{n}{8}}$$

那么，只需要固定这样一组字符串，并令 $X_n$ 均匀分布在这组字符串构成的多重集合上，就得到了满足要求的随机变量 $X_n$。

计算不可区分性推出

已经证明，对于每个充分大的 $n$，存在一个随机变量 $X_n$，使得任意规模不超过 $2^{\frac{n}{8}}$ 的电路 $C_n$ 都无法以超过 $2^{-\frac{n}{8}}$ 的优势区分 $X_n$ 和 $U_n$。

对于任意概率多项式时间区分器 $D$，在固定输入长度 $n$ 后，都可以表示为一个多项式规模的电路族。虽然 $D$ 可能是概率算法，但它的内部随机性也可以通过额外随机输入或固定内部随机性的方式转化到电路模型中，因此不会获得比前面小规模电路更强的区分能力。

由于任意多项式规模最终都会小于指数规模 $2^{\frac{n}{8}}$，所以当 $n$ 足够大时，任意概率多项式时间区分器 $D$ 对应的电路也属于前面考虑的小规模电路范围。

因此，对于任意概率多项式时间区分器 $D$，都有：

$$\left| P[D(X_n)=1] - P[D(U_n)=1] \right| < 2^{-\frac{n}{8}}$$

而 $2^{-\frac{n}{8}}$ 是关于 $n$ 的可忽略函数，所以任意概率多项式时间区分器的区分优势都是可忽略的，故有：

$$X\approx_c U$$

同时，由于 $X_n$ 的支撑集大小至多为 $2^{\frac{n}{2}}$，而 $U_n$ 均匀分布在全部 $2^n$ 个字符串上，所以二者在统计上相距很远，即：

$$X\not\approx_s U$$

其中，$\not\approx_s$ 表示不是统计接近，$\approx_c$ 表示计算不可区分。

这个命题说明：统计接近一定推出计算不可区分，但计算不可区分不一定推出统计接近，两个分布即使在统计意义上差异巨大，也可能无法被任何高效算法区分。