伪随机性与不可预测性

【引入】

伪随机序列在密码学应用中有一个非常重要的性质：不可预测性（Unpredictability）。

直观来说，一个序列是不可预测的，即代表任何高效算法即使已经看到了这个序列的前面若干位，也无法以明显高于随机猜测的概率预测下一位。

因为对于一个真正均匀随机的二进制序列来说，即使知道前面所有位，也无法帮助预测下一位。下一位仍然只能以概率 $\frac{1}{2}$ 猜中。因此，如果一个序列看起来像随机序列，那么它也应该具有这种下一位不可预测的性质。

【不可预测性】

定义

若对于系综 $\{X_n\}_{n\in\mathbb{N}}$，任意概率多项式时间算法 $A$，任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：

$$P[A(1^{|X_n|},X_n)=\mathrm{next}_A(X_n)] < \frac{1}{2}+\frac{1}{\mathrm{poly}(n)}$$

则称该系综 $\{X_n\}_{n\in\mathbb{N}}$ 在多项式时间内不可预测。其中，$\mathrm{next}_A(x)$ 表示算法 $A$ 尚未读取的下一位。

假设算法 $A$ 在输入 $(1^{|x|},x)$ 时，只读取了 $x$ 的前 $k<|x|$ 位，那么有：

$$\mathrm{next}_A(x)=x_{k+1}$$

如果算法 $A$ 把整个字符串 $x$ 都读完了，那么此时已经不存在下一位可以预测，因此 $\mathrm{next}_A(x)$ 被定义为一个均匀随机比特。

同时，算法 $A$ 的输入是 $(1^{|x|},x)$，其中的 $1^{|x|}$ 是一个长度为 $|x|$ 的一元字符串，其作用是让算法在真正读取 $x$ 之前，就知道输入字符串的长度。这是因为，如果算法 $A$ 读取了整个 $x$，那么它必须去猜一个完全随机的比特，因此成功概率不可能超过 $\frac{1}{2}$。真正有意义的情况是，算法 $A$ 只读取 $x$ 的前 $k$ 位，然后尝试根据这 $k$ 位预测第 $k+1$ 位。

含义

一个系综 $\{X_n\}_{n\in\mathbb{N}}$ 在多项式时间内不可预测的意思是：不存在任何概率多项式时间算法，能够在看到序列前缀之后，以不可忽略地高于 $\frac{1}{2}$ 的概率预测下一位。

其中，不可忽略地高于 $\frac{1}{2}$ 的概率是指存在某个多项式 $\mathrm{poly}(n)$，使预测成功概率至少达到：

$$\frac{1}{2}+\frac{1}{\mathrm{poly}(n)}$$

如果某个算法能够达到这种优势，那么这个序列就是可预测的

【伪随机性的等价定理】

Theorem：一个系综 $\{X_n\}_{n\in\mathbb{N}}$ 是伪随机的，当且仅当它在多项式时间内不可预测。

该定理说明，在计算复杂度意义下，一个序列的伪随机性和下一位不可预测性是等价的。

换句话说：

1. 如果一个序列是伪随机的，那么任何高效算法都无法根据前缀预测下一位
2. 如果任何高效算法都无法根据前缀预测下一位，那么这个序列不能被高效地区分于真正随机序列，满足伪随机性

【定理证明】

伪随机性推出不可预测性

证明思路

如果 $\{X_n\}$ 是伪随机的，那么它与某个均匀分布系综在多项式时间内不可区分，而真正的均匀随机序列显然是不可预测的，因为无论算法多么强大，只要它没有看到下一位，就不可能以超过 $\frac{1}{2}$ 的概率预测下一位。

因此，如果 $\{X_n\}$ 是伪随机的，它也必须是不可预测的。

否则，如果存在一个算法能够预测 $\{X_n\}$ 的下一位，那么就可以利用这个预测算法区分 $\{X_n\}$ 和真正的均匀随机序列，从而与伪随机性的假设矛盾。

证明

不失一般性地假设 $X_n$ 是长度为 $n$ 的随机变量，即 $|X_n|=n$。此时，$\{X_n\}$ 与标准均匀随机集合 $\{U_n\}$ 在多项式时间内不可区分。

反设 $\{X_n\}$ 在多项式时间内是可预测的，也就是说存在一个概率多项式时间算法 $A$、某个多项式 $\mathrm{poly}$，以及无穷多个 $n$，使得：

$$P[A(1^n,X_n)=\mathrm{next}_A(X_n)] \geq \frac{1}{2}+\frac{1}{\mathrm{poly}(n)}$$

接下来利用预测算法 $A$ 构造区分器 $D$，区分器 $D$ 在输入 $y$ 时，执行如下操作：

1. 运行算法 $A(1^{|y|},y)$
2. 记录算法 $A$ 实际读取了多少位
3. 记录算法 $A$ 对下一位的预测
4. 如果预测正确，则输出 $1$；如果预测错误，则输出 $0$

显然，对于 $X_n$，由于 $A$ 能够成功预测其下一位，所以有：

$$P[D(X_n)=1] = P[A(1^n,X_n)=\mathrm{next}_A(X_n)] \geq \frac{1}{2}+\frac{1}{\mathrm{poly}(n)}$$

而对于真正均匀随机的 $U_n$，下一位与前缀完全独立，因此无论 $A$ 如何预测，都不可能以超过 $\frac{1}{2}$ 的概率成功，即：

$$P[D(U_n)=1] = P[A(1^n,U_n)=\mathrm{next}_A(U_n)] \leq \frac{1}{2}$$

那么有：

$$P[D(X_n)=1]-P[D(U_n)=1] \geq \frac{1}{\mathrm{poly}(n)}$$

这说明 $D$ 能够以不可忽略优势区分 $X_n$ 和 $U_n$，与 $X_n$ 是伪随机的假设矛盾。

因此，伪随机性推出不可预测性。

不可预测性推出伪随机性

证明思路

需要证明：如果一个序列在多项式时间内不可预测，那么它一定是伪随机的。

从信息论的角度考虑。在不考虑计算复杂度的情况下，一个 $0/1$ 随机变量序列不可预测，当且仅当这些随机变量相互独立且均匀分布于 $\{0,1\}$。也就是说，只有真正随机序列才完全不可预测。

而在计算意义下，类似结论仍然成立：如果一个序列不能被任何多项式时间算法预测下一位，那么它在多项式时间内就无法与真正随机序列区分，因此它是伪随机的。

因此，采用反证法：假设 $\{X_n\}$ 不是伪随机的，那么存在一个多项式时间区分器 $D$，能够区分 $X_n$ 和均匀随机序列 $U_n$。那么，可以利用这个区分器 $D$ 构造一个预测算法 $A$，使 $A$ 能够预测 $X_n$ 的下一位，从而与不可预测性的假设矛盾。

混合分布的构造

仍然假设 $|X_n|=n$，并反设 $\{X_n\}$ 不是伪随机的。那么，存在一个概率多项式时间算法 $D$，某个多项式 $\mathrm{poly}$，以及无穷多个 $n$，使得：

$$|P[D(X_n)=1]-P[D(U_n)=1]| \geq \frac{1}{\mathrm{poly}(n)}$$

设 $S$ 是使上式成立的无穷集合，那么在这些 $n$ 中，要么有无穷多个 $n$ 使差值为正，要么有无穷多个 $n$ 使差值为负。如果差值为正，就直接使用 $D$。如果差值为负，就把 $D$ 的输出取反，用 $1-D$ 替代 $D$。

因此，不失一般性地可以假设，对于无穷多个 $n$，下式成立：

$$P[D(X_n)=1]-P[D(U_n)=1] \geq \frac{1}{\mathrm{poly}(n)}$$

对于每一个满足上式的 $n$，定义 $n+1$ 个混合分布 $H_n^0,H_n^1,\dots,H_n^n$，对于每个 $0\leq k \leq n$，定义：

$$H_n^k \overset{\text{def}}{=} \operatorname{pref}_{k}(X_n) \cdot \operatorname{suff}_{n-k}(U_n)$$

其中：

• $\operatorname{pref}_j(\alpha)$ 是字符串 $\alpha$ 位长为 $j$ 的前缀，即 $\alpha$ 的前 $j$ 个比特
• $\operatorname{suff}_j(\alpha)$ 是字符串 $\alpha$ 位长为 $j$ 的后缀，即 $\alpha$ 的后 $j$ 个比特
• $x\cdot y$ 表示字符串 $x$ 和 $y$ 的连接

此时，对于 $H_n^0$ 与 $H_n^n$ 有：

• $H_n^0$：前 $0$ 位来自 $X_n$，后 $n$ 位来自 $U_n$，即 $H_n^0 \equiv U_n$
• $H_n^n$：前 $n$ 位来自 $X_n$，后 $0$ 位来自 $U_n$，即 $H_n^n \equiv X_n$

中间的 $H_n^k$ 则表示：前 $k$ 位已经替换为 $X_n$ 的真实前缀，后面仍然保持均匀随机。

相邻混合分布的区分优势

由于 $D$ 可以区分 $H_n^0=U_n$ 和 $H_n^n=X_n$，并且区分优势至少为 $\frac{1}{\mathrm{poly(n)}}$，那么从 $H_n^0$ 一步一步变化到 $H_n^n$ 的过程中，必然存在某一对相邻混合分布 $H_n^k$ 和 $H_n^{k+1}$，使得 $D$ 对它们的接受概率存在区分优势。

考虑相邻混合分布之间的区分优势，有：

$$\sum_{k=0}^{n-1} \left( P[D(H_n^{k+1})=1] - P[D(H_n^k)=1] \right) =P[D(H_n^n)=1]-P[D(H_n^0)=1]$$

根据混合分布的端点项，$H_n^n \equiv X_n$，$H_n^0 \equiv U_n$，所以有：

$$P[D(H_n^n)=1]-P[D(H_n^0)=1] = P[D(X_n)=1]-P[D(U_n)=1] \geq \frac{1}{\mathrm{poly}(n)}$$

这说明，如果整体上 $X_n$ 和 $U_n$ 可以被区分，那么平均来看，某一步把随机位换成 $X_n$ 的真实位时，也会产生可检测的区分优势。

因此，从平均意义上看，有如下断言：

Claim：对于每一个满足 $P[D(X_n)=1]-P[D(U_n)=1] \geq \frac{1}{\mathrm{poly}(n)}$ 的 $n$，有：

$$\frac{1}{n} \sum_{k=0}^{n-1} \left( P[D(H_n^{k+1})=1] - P[D(H_n^k)=1] \right) \geq \frac{1}{\mathrm{poly}(n)\cdot n}$$

由区分器构造预测器

预测算法 $A$

根据上述断言，利用利用区分器 $D$ 构造一个预测 $\{X_n\}$ 的下一个比特的算法 $A$，该算法的目标是：在只读取 $X_n$ 的前 $k$ 位之后，预测第 $k+1$ 位。

算法 $A$ 在输入 $1^n$ 和字符串 $x=x_1x_2\cdots x_n$ 时，执行如下步骤：

1. 从集合 $\{0,1,\dots,n-1\}$ 中均匀随机选择一个 $k$
2. 读取 $x$ 的前 $k$ 位 $x_1,\dots,x_k$
3. 独立均匀随机生成 $r_{k+1},\dots,r_n\in\{0,1\}$
4. 构造字符串 $x_1\cdots x_k r_{k+1}\cdots r_n$
5. 把该字符串输入区分器 $D$
6. 如果 $D$ 输出 $1$，则 $A$ 预测 $x_{k+1}=r_{k+1}$；如果 $D$ 输出 $0$，则 $A$ 预测 $x_{k+1}=1-r_{k+1}$

这个算法 $A$ 的核心思想是：它不知道真正的第 $k+1$ 位 $x_{k+1}$，于是先随机猜一个候选值 $r_{k+1}$，然后把 $x_1,\dots,x_k,r_{k+1},\dots,r_n$ 交给区分器 $D$。

如果 $r_{k+1}$ 恰好等于真实的 $x_{k+1}$，那么这个输入更像 $H_n^{k+1}$，因为它的前 $k+1$ 位都来自 $X_n$；如果 $r_{k+1}$ 不等于真实的 $x_{k+1}$，那么这个输入在第 $k+1$ 位上与 $X_n$ 的真实前缀相反，因此它不再像 $H_n^{k+1}$。

于是，如果 $D$ 判断这个字符串更像 $X_n$，也就是输出 $1$，算法 $A$ 就相信 $r_{k+1}$ 是正确的；如果 $D$ 输出 $0$，算法 $A$ 就认为 $r_{k+1}$ 可能是错误的，于是输出它的相反值 $1-r_{k+1}$。

断言

对于预测算法 $A$，有如下断言。

Claim：对于每个满足 $P[D(X_n)=1]-P[D(U_n)=1] \geq \frac{1}{\mathrm{poly}(n)}$ 的 $n$，预测算法 $A$ 满足：

$$P[A(1^n,X_n)=\mathrm{next}_A(X_n)] \geq \frac{1}{2}+\frac{1}{\mathrm{poly}(n)\cdot n}$$

该断言说明，预测算法 $A$ 能够以不可忽略优势预测 $X_n$ 的下一位。

断言证明

记 $X^j$ 为 $X_n$ 的第 $j$ 位，对于固定的 $k$，算法 $A$ 随机生成 $R^{k+1},R^{k+2},\dots,R^n$，其中每个 $R^j$ 都是独立均匀随机比特。

算法 $A$ 猜中第 $k+1$ 位有两种情况：

1. $D$ 输出 $1$，并且随机比特 $R^{k+1}$ 正好等于真实位 $X^{k+1}$
2. $D$ 输出 $0$，并且随机比特 $R^{k+1}$ 正好不等于真实位 $X^{k+1}$

因此预测成功概率为：

$$\begin{align*} s_A(n) =& P[A(1^n,X_n)=\mathrm{next}_A(X_n)] \\ =& \frac{1}{n} \sum_{k=0}^{n-1} \Big( P \big[ (D(X^1\cdots X^kR^{k+1}\cdots R^n)=1) \wedge (R^{k+1}=X^{k+1})\big] \\ &+ P\big[(D(X^1\cdots X^k R^{k+1}\cdots R^n)=0) \wedge (R^{k+1}\neq X^{k+1}) \big] \Big) \\ =& \frac{1}{2n} \sum_{k=0}^{n-1} \Big( P\big[ D(X^1\cdots X^k X^{k+1} R^{k+2}\cdots R^n)=1 \big] \\ &+\big(1-P\big[ D(X^1\cdots X^k \overline{X}^{k+1} R^{k+2}\cdots R^n)=1 \big] \big) \Big) \\ \end{align*}$$

其中，$R^{k+1}$ 是均匀随机比特，故有 $P[R^{k+1}=X^{k+1}]=\frac{1}{2}$；$\overline{X}^{k+1}\overset{\text{def}}{=}1-X^{k+1}$ 表示第 $k+1$ 位取真实位的相反值。

定义分布 $Z$，其前 $k$ 位来自 $X_n$，第 $k+1$ 位取真实位的相反值，后面全部随机，即：

$$Z = X^1\cdots X^k \overline{X^{k+1}} R^{k+2}\cdots R^n$$

此时，$s_A(n)$ 可化为：

$$s_A(n)= \frac{1}{2} + \frac{1}{2n} \sum_{k=0}^{n-1} \Big( P\big[ D(H^{k+1}_{n})=1 \big] -P\big[ D(Z)=1 \big] \Big) \\$$

而对于第 $k+1$ 个混合分布 $H_{n}^{k+1}$，有：

$$H_n^{k+1} = X^1\cdots X^k X^{k+1} R^{k+2}\cdots R^n$$

注意到，$H_n^{k}$ 的第 $k+1$ 位本就是随机的，因此其可以看作以下两个分布的平均：

1. 第 $k+1$ 位等于真实值，此时分布为 $H_n^{k+1}$
2. 第 $k+1$ 位等于真实值的相反值，此时分布为 $Z$

因此，有：

$$P[D(H_n^k)=1] = \frac{ P[D(H_n^{k+1})=1] + P[D(Z)=1] }{2}$$

即有：

$$P[D(Z)=1] = 2P[D(H_n^k)=1] - P[D(H_n^{k+1})=1]$$

将其代入 $s_A(n)$，有：

$$\begin{align*} s_A(n) &= \frac{1}{2} + \frac{1}{2n} \sum_{k=0}^{n-1} \Big( P\big[ D(H^{k+1}_{n})=1 \big] - 2P[D(H_n^k)=1] + P[D(H_n^{k+1})=1] \Big) \\ &= \frac{1}{2} + \frac{1}{n} \sum_{k=0}^{n-1} \Big( P\big[ D(H^{k+1}_{n})=1 \big] - P[D(H_n^k)=1] \Big) \\ \end{align*}$$

根据相邻混合分布的区分优势断言可知，相邻混合分布的区分优势大于等于 $\frac{1}{\mathrm{poly}(n)\cdot n}$，故有：

$$\begin{align*} s_A(n) &= \frac{1}{2} + \frac{1}{n} \sum_{k=0}^{n-1} \Big( P\big[ D(H^{k+1}_{n})=1 \big] - P[D(H_n^k)=1] \Big) \\ &\geq \frac{1}{2}+ \frac{1}{\mathrm{poly}(n)\cdot n} \end{align*}$$

证明完毕。

完成反证

算法 $A$ 是概率多项式时间算法，因为它只是随机选择一个位置 $k$，生成随机比特，并调用一次概率多项式时间区分器 $D$。

预测算法 $A$ 的断言表明，对于无穷多个 $n$，算法 $A$ 可以 $\frac{1}{2}+ \frac{1}{\mathrm{poly}(n)\cdot n}$ 的概率预测 $X_n$ 的下一位。

而 $\mathrm{poly}(n)\cdot n$ 仍然是多项式，因此这个优势是不可忽略的，这与 $\{X_n\}$ 在多项式时间内不可预测的假设矛盾。

因此，反设不成立。所以，可由不可预测性推出伪随机性。