伪随机生成器与单向函数的存在性

【单向函数存在性命题】

在讨论伪随机性时，一直假设伪随机生成器的存在，并研究其具有的性质。但是，一个自然的问题是：伪随机生成器是否真的存在？

在密码学中，伪随机生成器的存在性与单向函数密切相关，具体来说，伪随机生成器存在的充分必要条件是单向函数存在，二者在计算复杂性意义下是等价的。

在标准伪随机生成器中，伪随机生成器的定义是依托于单向函数的，充分条件无需证明。因此，只需要证明必要条件是：如果伪随机生成器存在，那么单向函数也必须存在。

由此，有如下命题：

Proposition：设 $G$ 是一个扩展因子为 $l(n)=2n$ 的伪随机生成器，定义函数 $f:\{0,1\}^{*}\rightarrow\{0,1\}^{*}$，满足：

$$f(x,y)\triangleq G(x)$$

则 $f$ 是一个强单向函数。其中，$x$ 是真正参与生成伪随机输出的种子，$y$ 是一个长度相同但完全没有作用的随机字符串，要求 $|x|=|y|$

【命题证明】

证明思路

需要证明的目标是：$f$ 满足单向函数性质，即：$f$ 可以高效计算，且任何概率多项式时间算法都不能有效反演

首先，考虑高效计算。由于 $f(x,y)=G(x)$，而 $G$ 是伪随机生成器，其本身就要求可以在多项式时间内计算。因此 $f$ 也是多项式时间可计算的。

其次，考虑反演困难。采用反证法，假设存在一个概率多项式时间算法 $A$，能够有效对 $f$ 进行反演，即对于无穷多个 $n$，算法 $A$ 给定 $f(U_{2n})$ 能够以非忽略概率找到一个对应的输入：

$$P[ f(A(f(U_{2n})))=f(U_{2n}) ] > \frac{1}{\mathrm{poly}(n)}$$

其中，$U_{2n}$ 表示长度为 $2n$ 的均匀随机输入。

如果存在这样的求逆算法 $A$，那么可以利用 $A$ 构造一个区分器 $D$，使其能够区分真正随机序列 $U_{2n}$ 和伪随机序列 $G(U_n)$。

但是这与伪随机生成器的安全性矛盾，因此不存在有效求逆算法，所以 $f$ 是单向函数。

区分器的构造

区分器 $D$ 的目标是，输入 $\alpha\in\{0,1\}^{*}$，判断 $\alpha$ 是来自真随机分布 $U_{2n}$ 还是伪随机分布 $G(U_n)$。其具体执行步骤如下：

1. 将输入 $\alpha$ 交给求逆算法 $A$，得到输出 $\beta$
2. 检查 $f(\beta)=\alpha$ 是否成立
3. 如果成立，输出 $1$；如果不成立，输出 $0$，即：

$$D(\alpha)=1 \iff f(A(\alpha))=\alpha$$

区分优势

情况一

首先，考虑输入来自伪随机分布。假设：$\alpha=G(U_n)$，由于 $f(x,y)=G(x)$，因此有：

$$f(U_{2n})=G(U_n)$$

进而根据反证假设，可得：

$$P[D(G(U_n))=1]=P[f(A(G(U_n)))=G(U_n)] > \frac{1}{\mathrm{poly}(n)}$$

也就是说，如果输入是真正的伪随机输出，算法 $A$ 有明显概率成功找到原像。

情况二

进一步，考虑输入来自均匀随机分布，假设：$\alpha=U_{2n}$。显然，只有当 $\alpha$ 存在某个原像，即 $\alpha$ 必须属于 $G(U_n)$ 的输出集合时，区分器 $D$ 才会输出 $1$。

由于 $G: \{0,1\}^{n} \rightarrow \{0,1\}^{2n}$，输入空间大小为 $2^n$，因此最多只能产生 $2^n$ 个不同输出。

但是所有 $2n$ 位字符串数量为 $2^{2n}$，所以随机选择一个 $2n$ 位字符串落入 $G(U_n)$ 输出集合的概率最多为：

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

因此，有：

$$P[D(U_{2n})=1] \leq 2^{-n}$$

矛盾推出

综合考虑无穷多个 $n$ 两种情况下的区分优势，有：

$$P[D(G(U_n))=1] - P[D(U_{2n})=1] > \frac{1}{\mathrm{poly}(n)} - \frac{1}{2^n} > \frac{1}{2\mathrm{poly}(n)}$$

这说明区分器 $D$ 可以以不可忽略优势区分 $G(U_n)$ 和 $U_{2n}$，但是这与 $G$ 是伪随机生成器的定义矛盾。

因此，假设不存在，即不存在能够有效求逆 $f$ 的算法。

所以 $f(x,y)=G(x)$ 是强单向函数。