高效构造性系综的计算不可区分性

【基本问题】

根据计算不可区分性的定义，两个概率系综 $X=\{X_n\}_{n\in\mathbb N}$ 和 $Y=\{Y_n\}_{n\in\mathbb N}$ 被认为是计算不可区分的，是指任何高效算法都无法根据单个样本区分它们。

也就是说，区分器只能拿到一个样本 $X_n$ 或 $Y_n$，然后判断这个样本来自哪个分布。但是在很多密码学应用中，敌手往往不止看到一个样本，而是可能看到多个独立样本。

因此，一个自然的问题是：如果两个概率系综基于单个样本不可区分，那么它们基于多个样本是否仍然不可区分？

【基本定义】

重复采样下的不可区分性

设两个概率系综分别为 $X=\{X_n\}_{n\in\mathbb N}$ 和 $Y=\{Y_n\}_{n\in\mathbb N}$，如果对于任意概率多项式时间算法 $D$、任意两个正多项式 $\mathrm{poly}(\cdot)$ 和 $\mathrm{poly}’(\cdot)$，以及所有充分大的 $n$，都有：

$$\left| \Pr[D(X_n^{(1)},\ldots,X_n^{(\mathrm{poly}(n))})=1] - \Pr[D(Y_n^{(1)},\ldots,Y_n^{(\mathrm{poly}(n))})=1] \right| < \frac{1}{\mathrm{poly}'(n)}$$

则称 $X$ 和 $Y$ 是多项式时间采样下不可区分的（Indistinguishable by Polynomial-Time Sampling）。

其中：

• $X_n^{(1)},\ldots,X_n^{(\mathrm{poly}(n))}$ 和 $Y_n^{(1)},\ldots,Y_n^{(\mathrm{poly}(n))}$ 分别是 $\mathrm{poly}(n)$ 个相互独立的随机变量
• 每个 $X_n^{(i)}$ 都与 $X_n$ 同分布，每个 $Y_n^{(i)}$ 都与 $Y_n$ 同分布
• $\mathrm{poly}(n)$ 表示区分器拿到的样本个数，且样本个数只能是关于安全参数 $n$ 的多项式

直观来说，这个定义要求：即使区分器可以看到多项式多个独立样本，也无法有效区分这些样本全部来自 $X_n$，还是全部来自 $Y_n$

可高效构造的概率系综

如果存在一个概率多项式时间算法 $S$，使得对于每个 $n$，随机变量 $S(1^n)$ 和 $X_n$ 具有完全相同的分布，则概率系综：

$$X\overset{\mathrm{def}}{=}\{X_n\}_{n\in\mathbb N}$$

称为多项式时间可构造的（Polynomial-Time Constructible）。

也就是说，存在一个高效采样算法 $S$，输入安全参数 $1^n$，就能生成一个服从分布 $X_n$ 的样本，可记为：

$$S(1^n)\equiv X_n$$

其中，$\equiv$ 表示两个随机变量同分布。

可高效构造强调的是：不仅知道分布 $X_n$ 存在，而且能够在多项式时间内从这个分布中采样。

【计算不可区分性定理】

定理

Theorem：设 $X=\{X_n\}_{n\in\mathbb N}$ 和 $Y=\{Y_n\}_{n\in\mathbb N}$ 是两个多项式时间可构造的概率系综。如果 $X$ 和 $Y$ 在多项式时间内不可区分，即：

$$X\approx_c Y$$

那么 $X$ 和 $Y$ 在重复采样下仍然不可区分。

等价表述

对于任意概率系综 $Z=\{Z_n\}_{n\in\mathbb N}$ 和任意多项式 $\mathrm{poly}(\cdot)$，定义 $Z$ 的 $\mathrm{poly}(\cdot)$-重乘积系综为：

$$\{(Z_n^{(1)},\ldots,Z_n^{(\mathrm{poly}(n))})\}_{n\in\mathbb N}$$

其中，每个 $Z_n^{(i)}$ 都是 $Z_n$ 的独立拷贝。

则上述定理可等价表述为：

如果 $X\approx_c Y$，并且 $X,Y$ 都是多项式时间可构造的，那么对于任意多项式 $\mathrm{poly}(\cdot)$，$X$ 的 $\mathrm{poly}(\cdot)$-重乘积系综与 $Y$ 的 $\mathrm{poly}(\cdot)$-重乘积系综仍然计算不可区分。

对于上述定理，形式上有：

$$X\approx_c Y \Longrightarrow (X_n^{(1)},\ldots,X_n^{(\mathrm{poly}(n))}) \approx_c (Y_n^{(1)},\ldots,Y_n^{(\mathrm{poly}(n))})$$

也就是说，对于任意多项式个独立样本，区分器仍然无法有效判断这些样本来自 $X_n$ 还是来自 $Y_n$。

定理证明

证明思路

在信息论意义下，上述定理类似结论是比较直接的：如果两个概率系综是统计接近的，那么它们的多项式重乘积系综仍然是统计接近的。

这是因为统计距离本身可以直接控制多个独立样本下的整体差异。但是，在计算不可区分性的情形中，证明不能直接依赖统计距离，因为两个分布可能在统计上相距很远。

该定理的证明采用反证法和归约思想。

要证明的是如果单个样本下 $X$ 和 $Y$ 不可区分，那么多个样本下 $X$ 和 $Y$ 也不可区分。

那么，假设多个样本下可以区分，即存在概率多项式时间算法 $D$，以及正多项式 $\mathrm{poly}(\cdot)$、$\mathrm{poly}’(\cdot)$，使得对于无穷多个 $n$，都有：

$$\Delta(n) \overset{\mathrm{def}}{=} \left| P[D(X_n^{(1)},\ldots,X_n^{(\mathrm{poly}(n))})=1] - P[D(Y_n^{(1)},\ldots,Y_n^{(\mathrm{poly}(n))})=1] \right| > \frac{1}{\mathrm{poly}'(n)}$$

其中，$\Delta(n)$ 表示区分器 $D$ 在多样本实验中的区分优势，因为 $\Delta(n)$ 大于某个多项式倒数，所以它是不可忽略的。

因此，只需要利用这个多样本区分器 $D$，来构造另一个概率多项式时间区分器 $D’$，使得 $D’$ 只拿到一个样本，也能够区分 $X_n$ 和 $Y_n$。

如果这样的 $D’$ 存在，就与假设 $X\approx_c Y$ 矛盾。所以，多样本区分器 $D$ 不可能存在。

因此，整体归约逻辑是：如果能够区分多个样本，就能区分单个样本。而定理假设不能区分单个样本，因此可以推出不能区分多个样本。

混合分布

对于每个 $k=0,1,\ldots,\mathrm{poly}(n)$，定义混合随机变量 $H_n^k$ 为一个长度为 $\mathrm{poly}(n)$ 的样本序列：

$$H_n^k \overset{\mathrm{def}}{=} (X_n^{(1)},\ldots,X_n^{(k)},Y_n^{(k+1)},\ldots,Y_n^{(\mathrm{poly}(n))})$$

其中，前 $k$ 个样本是 $X_n$ 的独立拷贝，后 $\mathrm{poly}(n)-k$ 个样本是 $Y_n$ 的独立拷贝，所有样本之间相互独立。

特别地，当 $k=0$ 时，全部样本都来自 $Y_n$，即：

$$H_n^0 = (Y_n^{(1)},\ldots,Y_n^{(\mathrm{poly}(n))})$$

当 $k=\mathrm{poly}(n)$ 时，全部样本都来自 $X_n$，即：

$$H_n^{\mathrm{poly}(n)} = (X_n^{(1)},\ldots,X_n^{(\mathrm{poly}(n))})$$

混合分布构造了一条从全 $Y$ 到全 $X$ 的路径：

$$H_n^0,H_n^1,\ldots,H_n^{\mathrm{poly}(n)}$$

其中，每相邻两个混合分布只相差一个位置：

$$H_n^k = (X_n^{(1)},\ldots,X_n^{(k)},Y_n^{(k+1)},\ldots,Y_n^{(\mathrm{poly}(n))})$$

也就是说，$H_n^k$ 与 $H_n^{k+1}$ 的区别只在第 $k+1$ 个位置：

• $H_n^k$ 的第 $k+1$ 个位置是 $Y_n$
• $H_n^{k+1}$ 的第 $k+1$ 个位置是 $X_n$

因此，如果一个算法能够明显区分两个极端分布 $H_n^0$ 和 $H_n^{\mathrm{poly}(n)}$，那么在这条混合链上，必然存在某一对相邻混合分布也能被明显区分。

单样本区分器

构造

考虑构造一个新的区分器 $D’$，其输入是一个单个样本 $\alpha$，这个样本可能来自 $X_n$，也可能来自 $Y_n$。

算法 $D’$ 的目标是判断 $\alpha$ 来自 $X_n$ 还是来自 $Y_n$。

具体过程如下：

（1）随机均匀选择一个位置： $k\in\{0,1,\ldots,\mathrm{poly}(n)-1\}$

（2）使用 $X$ 的高效采样算法，生成 $k$ 个独立样本 $x_1,\ldots,x_k$

（3）使用 $Y$ 的高效采样算法，生成 $\mathrm{poly}(n)-k-1$ 个独立样本 $y_{k+2},\ldots,y_{\mathrm{poly}(n)}$

（4）将输入样本 $\alpha$ 放在第 $k+1$ 个位置，组成长度为 $\mathrm{poly}(n)$ 的序列

$$(x_1,\ldots,x_k,\alpha,y_{k+2},\ldots,y_{\mathrm{poly}(n)})$$

（5）调用原来的多样本区分器 $D$，并输出：

$$D'( \alpha )=D(x_1,\ldots,x_k,\alpha,y_{k+2},\ldots,y_{\mathrm{poly}(n)})$$

区分器 $D’$ 的运行过程包括：

• 随机选择 $k$
• 生成多项式个 $X_n$ 样本
• 生成多项式个 $Y_n$ 样本
• 运行一次概率多项式时间算法 $D$

由于 $\mathrm{poly}(n)$ 是多项式，$X$ 和 $Y$ 都是多项式时间可构造的，$D$ 是概率多项式时间算法，所以 $D’$ 也是概率多项式时间算法。

区分优势

断言一

Claim：单样本区分器 $D’$ 的输入来自 $X_n$ 时的接受概率为：

$$P[D'(X_n)=1] = \frac{1}{\mathrm{poly}(n)} \sum_{k=0}^{\mathrm{poly}(n)-1} P[D(H_n^{k+1})=1]$$

证明：如果输入 $\alpha$ 来自 $X_n$，那么 $D’$ 构造出的序列为：

$$(x_1,\ldots,x_k,\alpha,y_{k+2},\ldots,y_{\mathrm{poly}(n)})$$

其中，前 $k$ 个样本来自 $X_n$，第 $k+1$ 个样本 $\alpha$ 也来自 $X_n$，后 $\mathrm{poly}(n)-k-1$ 个样本来自 $Y_n$。

因此，整个序列服从混合分布 $H_n^{k+1}$，而 $k$ 是从 $\{0,\ldots,\mathrm{poly}(n)-1\}$ 中均匀选取的，那么根据混合分布的定义，断言得证。

断言二

Claim：单样本区分器 $D’$ 的输入来自 $Y_n$ 时的接受概率为：

$$P[D'(Y_n)=1] = \frac{1}{\mathrm{poly}(n)} \sum_{k=0}^{\mathrm{poly}(n)-1} P[D(H_n^k)=1]$$

证明：如果输入 $\alpha$ 来自 $Y_n$，那么 $D’$ 构造出的序列为：

$$(x_1,\ldots,x_k,\alpha,y_{k+2},\ldots,y_{\mathrm{poly}(n)})$$

其中，前 $k$ 个样本来自 $X_n$，第 $k+1$ 个样本 $\alpha$ 来自 $Y_n$，后 $\mathrm{poly}(n)-k-1$ 个样本来自 $Y_n$。

因此，这整个序列服从混合分布 $H_n^k$，而 $k$ 是从 $\{0,\ldots,\mathrm{poly}(n)-1\}$ 中均匀选取的，那么根据混合分布的定义，断言得证。

断言三

Claim：单样本区分器 $D’$ 的区分优势为：

$$\left| P[D'(X_n)=1] - P[D'(Y_n)=1] \right| = \frac{\Delta(n)}{\mathrm{poly}(n)}$$

证明：

单样本区分器 $D’$ 的区分优势为：

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

将断言一与断言二的接受概率带入，有：

$$\begin{align*} &\left| P[D'(X_n)=1] - P[D'(Y_n)=1]\right| \\ =& \left| \frac{1}{\mathrm{poly}(n)} \sum_{k=0}^{\mathrm{poly}(n)-1} P[D(H_n^{k+1})=1] - \frac{1}{\mathrm{poly}(n)} \sum_{k=0}^{\mathrm{poly}(n)-1} P[D(H_n^k)=1] \right| \\ =& \frac{1}{\mathrm{poly}(n)}\left| \sum_{k=0}^{\mathrm{poly}(n)-1} P[D(H_n^{k+1})=1] - \sum_{k=0}^{\mathrm{poly}(n)-1} P[D(H_n^k)=1] \right| \\ =& \frac{1}{\mathrm{poly}(n)}\left| \sum_{k=0}^{\mathrm{poly}(n)-1} \left( P[D(H_n^{k+1})=1] - P[D(H_n^k)=1] \right)\right| \\ \end{align*}$$

显然，内部求和项为中间项可相互抵消的望远镜级数，故有：

$$\left| P[D'(X_n)=1] - P[D'(Y_n)=1]\right| =\frac{1}{\mathrm{poly}(n)}\left| P[D(H_n^{\mathrm{poly}(n)})=1) - P[D(H_n^{0})=1)] \right|$$

又因为 $H_n^{\mathrm{poly}(n)}=(X_n^{(1)},\ldots,X_n^{(\mathrm{poly}(n))})$，$H_n^0=(Y_n^{(1)},\ldots,Y_n^{(\mathrm{poly}(n))})$，因此有：

$$\left| P[D(H_n^{\mathrm{poly}(n)})=1] - P[D(H_n^0)=1] \right| = \Delta(n)$$

即：

$$\left| P[D'(X_n)=1] - P[D'(Y_n)=1]\right| = \frac{\Delta(n)}{\mathrm{poly}(n)}$$

断言得证。

矛盾推出

根据反设，存在一个多样本区分器 $D$，以及两个正多项式 $\mathrm{poly}(\cdot)$ 和 $\mathrm{poly}’(\cdot)$，使得对于无穷多个 $n$，都有：

$$\Delta(n)> \frac{1}{\mathrm{poly}'(n)}$$

对不等式两边同时除以 $\mathrm{poly}(n)$，有：

$$\frac{\Delta(n)}{\mathrm{poly}(n)} = \frac{1}{\mathrm{poly}(n)\mathrm{poly}'(n)}$$

由断言三可知，单样本区分器 $D’$ 的区分优势为 $\frac{\Delta(n)}{\mathrm{poly}(n)}$，即对于无穷多个 $n$，有：

$$\left| P[D'(X_n)=1] - P[D'(Y_n)=1] \right| = \frac{\Delta(n)}{\mathrm{poly}(n)} > \frac{1}{\mathrm{poly}(n)\mathrm{poly}'(n)}$$

由于 $\mathrm{poly}(n)$ 和 $\mathrm{poly}’(n)$ 都是正多项式，所以 $\mathrm{poly}(n)\mathrm{poly}’(n)$ 仍然是正多项式，因此 $\frac{1}{\mathrm{poly}(n)\mathrm{poly}’(n)}$ 是某个正多项式的倒数，这意味着 $D’$ 的区分优势是不可忽略的。

这说明 $D’$ 能够以不可忽略的优势区分单个样本 $X_n$ 和 $Y_n$，但 $D’$ 是概率多项式时间算法，这与定理假设 $X\approx_c Y$ 矛盾。

所以，原来的多样本区分器 $D$ 不可能存在。因此，$X$ 和 $Y$ 在重复采样下仍然计算不可区分，定理得证。

【混合技术】

混合技术（Hybrid Technique）是一种特殊的归约论证方法，它通常用于证明：由简单概率系综构造出的复杂概率系综仍然计算不可区分。

使用混合技术需要满足三个关键条件：

1. 两端混合分布等于目标复杂分布：混合链的两个端点必须正好是要证明不可区分的两个复杂分布
2. 相邻混合分布能还原到基本分布：每一对相邻混合分布只在一个位置上不同
3. 混合分布数量必须是多项式个：如果混合分布数量是指数级，那么这个区分优势可能被摊薄成可忽略量

在上述定理证明中，就用到了混合技术这种方法。具体来说，基本概率系综是 $X$ 和 $Y$，复杂概率系综是 $\mathrm{poly}(n)$ 个独立样本组成的乘积系综，要证明的是如果单个 $X_n$ 和 $Y_n$ 不可区分，那么多个独立样本也不可区分。

混合技术的做法是在两个复杂分布之间插入一系列中间分布：

$$H_n^0,H_n^1,\ldots,H_n^{\mathrm{poly}(n)}$$

其中，$H_n^0$ 是全 $Y$ 分布，$H_n^{\mathrm{poly}(n)}$ 是全 $X$ 分布，相邻两个混合分布只相差一个位置。

如果存在算法能区分首尾两个分布，那么必然可以从某种意义上找到一对相邻分布存在可利用的差异。