【基本思想】

基于单向置换的伪随机生成器构造与基于置换集合的伪随机生成器构造中的伪随机生成器的构造均基于硬核谓词，硬核谓词的输出长度为 $1$ 比特，因此每进行一次单向置换 $f_i$，只能产生一个伪随机比特。

将该思想推广到硬核函数上，即不再要求 $H(x)\in\{0,1\}$，而允许 $H(x)\in\{0,1\}^{m},m>1$。此时，每执行一次单向置换，可以输出多个伪随机比特。

【硬核函数的输出长度】

记 $\ell_H((H(i,\cdot))$ 表示硬核函数 $H(i,\cdot)$ 输出空间大小的二进制对数，即：

$\ell_H((H(i,\cdot))= \log_2 |\mathrm{Range}(H(i,\cdot))|$

也就是说，$\ell_H((H(i,\cdot))$ 表示每次调用硬核函数 $H(i,\cdot)$ 可以输出多少比特。

由于任何单向函数都可以修改为具有硬核函数的形式，因此每次调用硬核函数输出 $O(\log n)$ 个伪随机比特，即：

$\ell_H(n)=O(\log n)$

进一步，如果 $H(i,\cdot)\in\{0,1\}$，那么 $|\mathrm{Range}(H(i,\cdot))|=2$，故有：

$\ell_H(n)=\log_2 2=1$

所以，任何硬核谓词都可以看作输出长度为 $\ell_H(n)=1$ 的硬核函数。

此外，对于 RSA 集合，如果假设 RSA 是单向的，那么最低有效的 $O(\log n)$ 位硬核函数，即一次 RSA 迭代可以产生 $O(\log n)$ 个安全比特。同理，Rabin 集合也具有类似性质。

【构造】

基于硬核函数的伪随机生成器构造，是基于置换集合的伪随机生成器构造的直接推广。

Construction：设 $(I,D,F)$ 是一个单向置换集合，即对于索引 $i$ 存在 $f_i$，设 $H$ 是对应的硬核函数，$\mathrm{poly}(\cdot)$ 为任意多项式，对于 $n\in\mathbb{N}$ 与随机种子 $r,s\in\{0,1\}^{\mathrm{poly}’(n)}$，首先利用 $r$ 选择置换 $i=I(1^n,r)$ 得到置换函数 $f_i$，然后利用 $s$ 选择初始点 $s_0=D(i,s)$，之后对于 $1\leq j\leq \mathrm{poly}(n)$ 进行迭代，计算 $\alpha_j=H(i,s_{j-1})$ 和 $s_j=f_i(s_{j-1})$ ，最终输出：
$G(r,s) = \alpha_1\alpha_2\cdots\alpha_{\mathrm{poly}(n)}$

需要注意的是，在基于硬核函数的伪随机生成器构造中，硬核谓词 $B(i,s_{j-1})$ 输出一个比特，因此 $\sigma_j=B(i,s_{j-1})$，而现在的硬核函数 $H(i,s_{j-1})$ 输出 $\ell_H(n)$ 个比特，因此 $\alpha_j=H(i,s_{j-1})$。

所以，现在每一步输出长度从 $1$ 比特增加到 $\ell_H(n)$，最终输出长度 $\mathrm{poly}(n)\cdot \ell_H(n)$

【硬核函数的伪随机生成器定理】

Theorem：设 $(I,D,F)$，$H$，$\mathrm{poly}(n)$，$\mathrm{poly}’(n)$，$G$ 满足上述构造，且有：
$\mathrm{poly}(n)\cdot \ell_H(n) > 2\mathrm{poly}'(n)$
若对于所有 $n$，$I$ 输出范围中的任意 $i$，随机变量 $D(i)$ 在 $D_i$ 上均匀分布，则 $G$ 是伪随机生成器。

需要注意的是，在基于硬核函数的伪随机生成器构造中，种子长度为 $2\mathrm{poly}’(n)$，输出长度 $\mathrm{poly}(n)$，因此需要：$\mathrm{poly}(n)>2\mathrm{poly}’(n)$。而在现在的构造中，每一步输出 $\ell_H(n)$ 比特，总输出 $\mathrm{poly}(n)\cdot\ell_H(n)$ 比特，因此将条件扩展为 $\mathrm{poly}(n)\cdot\ell_H(n)>2\mathrm{poly}’(n)$

【定理证明】

基本思路

该命题的证明与基于置换集合的伪随机生成器构造中的命题类似。

首先反转输出顺序，令 $t=\mathrm{poly}(n)$，定义 $\bar G_i^t(x)$ 为 $G_i^t(x)$ 的逆序，即：

$\bar G_i^t(x) = H(i,f_i^{t-1}(x)) \cdot H(i,f_i^{t-2}(x)) \cdots H(i,x)$

由于只是改变比特顺序，所以当且仅当 $\bar G_i^t(x)$ 是伪随机时，$G_i^t(x)$ 是伪随机的。因此只需要证明反向序列 $\bar G$ 与均匀随机串不可区分，即可证明 $G$ 是伪随机生成器。

反证假设

对无限多个 $n$，令 $h(n)=\ell_H(n)$，假设存在一个概率多项式时间区分器 $D$，能够以不可忽略优势区分真实输出和随机输出，即对于某个多项式 $\mathrm{poly}(n)$，有：

$\left| P[D(\bar G_{I_n}^{t}(X_n))=1] - P[D(U_{t\cdot h(n)})=1] \right| > \frac{1}{\mathrm{poly}(n)}$

其中，$I_n$ 表示 $I(1^n)$ 的随机输出，$X_n=D(I_n)$ 在 $D_{I_n}$ 上均匀分布。

由于每次的输出是一个 $h(n)$ 长的字符串，为此定义混合分布 $H_0, H_1,\cdots, H_t$，其中 $H_j$ 表示前 $j$ 个 $h(n)$ 长的字符串真实的硬核函数输出，剩下的 $t-j$ 个 $h(n)$ 长的字符串使用均匀随机字符串，即：

$H_j= H(i,f_i^{t-1}(x)) \cdots H(i,f_i^{t-j}(x)) \cdot U_{(t-j)h(n)}$

此时，对于首尾两项，有：

$H_0=U_{t\cdot h(n)}, \quad H_t=\bar G_i^t(x)$

如果 $D$ 能够以不可忽略优势区分 $H_0$ 和 $H_t$，那么必然存在某个 $j\in\{0,\ldots,t-1\}$，使得 $D$ 能够以不可忽略优势区分相邻的两个分布 $H_j$ 和 $H_{j+1}$。

这两个分布之间唯一的区别，就是其中一个 $h(n)$ 长的字符串，在 $H_j$ 中是均匀随机的 $U_{h(n)}$，在 $H_{j+1}$ 中是真实的 $H(i,x)$。

因此，如果能区分整个生成器输出，就能区分 $H(i,x)$ 和真正的随机 $h(n)$ 长的字符串。

区分器构造

现在构造一个算法 $A$，在得到输入 $(i,y,z)$ 时，判断 $z$ 属于哪一种情况。其中，$y=f_i(x)$，而 $z$ 有两种可能：

$z=H(i,x)$
$z= U_{h(n)}$

算法 $A$ 的步骤如下：

随机选择 $j\in\{0,\ldots,t-1\}$
基于 $y=f_i(x)$，计算 $f_i(y),f_i^2(y),\cdots$
计算对应的硬核函数输出 $H(i,y),\ H(i,f_i(y)),\cdots,H(i,f_i^{j-1}(y))$
构造字符串 $W= H(i,f_i^{j-1}(y)) \cdots H(i,y) \cdot z \cdot U_{(t-j-1)h(n)}$
将 $W$ 交给区分器 $D$

此时，针对 $z$ 的两种情况，分别进行分析。如果 $z=H(i,x)$，那么因为 $y=f_i(x)$，有：$f_i^{k}(y)=f_i^{k+1}(x)$，因此 $W$ 的真实部分为：

$H(i,f_i^j(x)) \cdots H(i,f_i(x)) H(i,x)$

这恰好对应 $H_{j+1}$。如果 $z$ 是均匀随机的 $U_{h(n)}$，那么该位置仍然是随机的 $h(n)$ 长的比特串，所以 $W$ 对应 $H_j$。

因此，若 $D$ 能够区分 $H_j$ 和 $H_{j+1}$，那么 $A$ 就能够区分 $H(i,x)$ 和 $U_{h(n)}$

矛盾推出

由于 $H$ 是该单向置换集合的硬核函数，那么根据定义，在给定 $(i,f_i(x))$ 时，$H(i,x)$ 应当和均匀随机字符串 $U_{h(n)}$ 在多项式时间内不可区分，即：

$(i,f_i(x),H(i,x)) \approx_c (i,f_i(x),U_{h(n)})$

但是利用 $D$ 构造出的一个多项式时间算法 $A$，能够以不可忽略优势区分这两个分布，产生矛盾。

因此，不存在这样的 $D$，所以 $G(U_{2\mathrm{poly}’(n)})$ 与 $U_{\mathrm{poly}(n)\cdot h(n)}$ 是不可区分的，即：

$G(U_{2\mathrm{poly}'(n)}) \approx_c U_{\mathrm{poly}(n)\cdot h(n)}$

种子 $(r,s)$ 的长度为 $2\mathrm{poly}’(n)$，输出长度为 $\mathrm{poly}(n)\cdot h(n)=\mathrm{poly}(n)\ell_{H}(n)$，而定理假设 $\mathrm{poly}(n)\cdot \ell_h(n)>2\mathrm{poly}(n)$，因此输出长度严格大于种子长度。

同时，$I,D,F,H$ 都是多项式时间可计算的，且 $\mathrm{poly}(n)$ 是多项式，所以 $G$ 也是多项式时间算法。

综上，$G$ 是一个伪随机生成器。

【构造的效率分析】

基于硬核函数的伪随机生成器每应用一次单向置换 $f_i$，都会输出一次对应的硬核函数值 $H(i,x)$。

设硬核函数的输出长度为 $\ell_H(n)$，则每进行一次单向置换运算，就可以产生 $\ell_H(n)$ 个伪随机比特。也就是说，相比于硬核谓词每次只能输出 $1$ 比特，使用硬核函数可以显著提高伪随机生成器的生成效率。

例如，对于 Rabin 单向置换，其核心迭代操作是模平方：

$x= x^2 \pmod N$

其中，$N$ 是一个 $n$ 比特模数。

目前已知 Rabin 集合可以得到长度为 $O(\log n)$ 的硬核函数，因此每进行一次模平方，可以安全输出 $O(\log n)$ 个伪随机比特。

因此，如果能够证明 Rabin 集合存在一个更长的硬核函数，使得：

$\ell_H(n)=\Omega(n)$

那么就可以得到一个非常高效的伪随机生成器：每进行一次模平方运算，就可以输出 $\Omega(n)$ 个伪随机比特。