均匀分布系综与伪随机系综

【引入】

在密码学中，伪随机性（Pseudorandomness）通常指的是相对于多项式时间算法的伪随机性。也就是说，所谓伪随机，并不是指统计意义上接近真正随机，而是指与均匀分布计算不可区分。

在计算不可区分性中，一个特殊但非常重要的情形是：两个概率系综中，有一个是均匀分布系综。

如果一个概率系综与某个均匀分布系综计算不可区分，那么这个概率系综就称为伪随机系综（Pseudorandom Ensemble）。直观来说，伪随机系综并不要求自己真的服从均匀分布，而是要求任何概率多项式时间算法都无法将它与均匀分布区分开。

因此，伪随机系综可能与均匀分布在统计上相距很远，但只要这种差异无法被概率多项式时间算法发现，它仍然可以被称为伪随机。

【均匀分布系综】

基本形式

记 $U_m$ 表示在所有长度为 $m$ 的比特字符串上均匀分布的随机变量，即：

$$U_m \sim \{0,1\}^m$$

那么，对于任意字符串 $\alpha\in\{0,1\}^m$，都有：

$$P[U_m=\alpha]=\frac{1}{2^m}$$

标准均匀系综

最标准的均匀分布系综是：

$$\{U_n\}_{n\in\mathbb N}$$

称为标准均匀系综（Standard Uniform Ensemble），第 $n$ 个随机变量 $U_n$ 均匀分布在所有 $n$ 比特字符串上。

一般形式

除了标准均匀系综 $\{U_n\}_{n\in\mathbb N}$ 之外，也常把如下形式的系综称为均匀系综：

$$\{U_{\ell(n)}\}_{n\in\mathbb N}$$

其中，$\ell:\mathbb N\rightarrow\mathbb N$，$\ell(n)$ 表示输出字符串的长度。

也就是说，在安全参数为 $n$ 时，随机变量不是均匀输出 $n$ 比特字符串，而是均匀输出 $\ell(n)$ 比特字符串。例如，如果 $\ell(n)=2n$，那么有：

$$U_{\ell(n)}=U_{2n}$$

表示均匀分布在所有 $2n$ 比特字符串上。

这样定义更灵活，因为在密码学中，很多构造的输出长度不一定等于安全参数 $n$。

【伪随机系综】

定义

设 $X=\{X_n\}_{n\in\mathbb N}$ 是一个概率系综，如果存在一个均匀系综：

$$U=\{U_{\ell(n)}\}_{n\in\mathbb N}$$

使得：

$$X\approx_c U$$

即 $X$ 和 $U$ 在多项式时间内不可区分，那么称 $X$ 是伪随机系综（Pseudorandom Ensemble）。

直观理解

伪随机系综的核心含义是：$X_n$ 的输出看起来像长度为 $\ell(n)$ 的均匀随机字符串。

也就是说，虽然 $X_n$ 的产生方式可能并不是真正均匀随机的，但对于任何概率多项式时间区分器 $D$，都有：

$$\left| P[D(X_n)=1] - P[D(U_{\ell(n)})=1] \right|$$

是可忽略的。

因此，高效算法无法判断自己拿到的是 $X_n$ 还是 $U_{\ell(n)}$，这就是伪随机的含义：不一定真正随机，但在高效观察者看来与真正随机没有区别。

长度问题

在伪随机系综中 $X_n$ 的输出长度不一定等于 $n$，也就是说 $|X_n|$ 不一定是 $n$，而均匀随机变量 $U_m$ 的输出长度一定是 $m$，即：

$$|U_m|=m$$

因此，如果 $X$ 与 $\{U_{\ell(n)}\}_{n\in\mathbb N}$ 计算不可区分，那么通常要求 $X_n$ 的输出长度与 $\ell(n)$ 一致。

如果 $\ell:\mathbb N\rightarrow\mathbb N$ 是多项式时间可计算的，并且：

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

满足伪随机系综的定义，那么以非常高的概率有：

$$|X_n|=\ell(n)$$

否则，如果 $X_n$ 的长度经常不等于 $\ell(n)$，那么区分器只需要检查输入长度，就能轻易区分 $X_n$ 和 $U_{\ell(n)}$。

例如，若 $U_{\ell(n)}$ 总是输出 $\ell(n)$ 比特字符串，而 $X_n$ 经常输出其他长度的字符串，那么区分器可以执行：

$$D(\alpha)= \begin{cases} 1, & |\alpha|=\ell(n)\\ 0, & |\alpha|\neq \ell(n) \end{cases}$$

这样就能明显区分二者。

因此，伪随机性通常隐含着：$X_n$ 的输出长度应当几乎总是等于对应均匀分布的输出长度。