硬核函数

【硬核函数的定义】

基本思想

在强单向函数的内积硬核谓词定理中，证明了每一个单向函数都可以经过简单修改，从而具有一个硬核谓词。硬核谓词本质上是关于原像 $x$ 的一比特信息，即使已经知道函数值 $f(x)$，也无法高效预测这一比特。

但是，很多情况下，不仅希望隐藏原像中的某一个比特信息，而是希望从原像中提取出的多个比特整体上也保持计算隐藏性。

对于多比特情形，通常不直接定义为难以猜中真实值，而是采用另一种更自然的定义：多个比特的真实值应当与同长度的随机串在计算上不可区分。也就是说，给定 $f(x)$ 之后，$h(x)$ 看起来应当像一个真正随机的字符串。

因此，如果 $h$ 是一个多项式时间可计算函数，并且任何高效算法都无法区分

$$(f(x),h(x)),\quad (f(x),r)$$

其中，$r$ 是与 $h(x)$ 等长的均匀随机串，那么就称 $h$ 是 $f$ 的硬核函数。

定义

设 $h:\{0,1\}^{*}\rightarrow \{0,1\}^{*}$ 是一个多项式时间可计算函数，并且是长度规则的，即对于任意满足 $|x|=|y|$ 的字符串 $x,y$，都有 $|h(x)|=|h(y)|$。令 $\ell(n)\overset{\mathrm{def}}{=}|h(1^n)|$，若对于任意概率多项式时间算法 $D’$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有：

$$\left| P[D'(f(X_n),h(X_n))=1] - P[D'(f(X_n),R_{\ell(n)})=1] \right| < \frac{1}{\mathrm{poly}(n)}$$

则称 $h$ 是函数 $f$ 的硬核函数（Hard-Core Function）。其中，$X_n$ 是在 $\{0,1\}^n$ 上均匀分布的随机变量，$R_{\ell(n)}$ 是在 $\{0,1\}^{\ell(n)}$ 上均匀分布的随机变量，并且二者相互独立。

直观地说，这一定义表达的是：即使给定 $f(x)$，$h(x)$ 仍然在计算意义下像随机串一样。敌手不仅无法准确恢复 $h(x)$，甚至无法把真实的 $h(x)$ 和一个同长度随机串区分开来。

当 $\ell(n)\equiv 1$ 时，硬核函数退化为只输出一比特的函数，因此该定义与强单向函数的内积硬核谓词定理中的硬核谓词定义等价。

实例

对于 RSA、Rabin 和 DLP 对应的单向函数族，如果这些函数族确实是单向的，那么可以构造输出长度为 $O(\log n)$ 的简单硬核函数。

例如，在 RSA 函数族中，设

$$\mathrm{RSA}_{N,e}(x)=x^e \bmod N$$

如果 RSA 函数族是单向的，那么给定

$$x^e \bmod N$$

想要区分 $x$ 的 $O(\log |N|)$ 个最低有效位和一个均匀随机的 $O(\log |N|)$-bit 字符串，在计算上是不可行的。也就是说，RSA 原像 $x$ 的若干个最低有效位可以作为 RSA 函数的硬核函数输出。

类似结论也适用于 Rabin 函数族和 DLP 函数族。

【强单向函数硬核函数定理】

定理

Theorem：设 $f$ 是任意一个强单向函数，定义：

$$g_2(x,s)\overset{\mathrm{def}}{=}(f(x),s)$$

其中，$|s|=2|x|$。设 $|x|=n$，并令 $s=(s_1,s_2,\dots,s_{2n})$

对于每个 $i$，定义 $b_i(x,s)$ 为二进制向量 $x$ 与 $s$ 中长度为 $n$ 的滑动窗口 $(s_{i+1},s_{i+2},\dots,s_{i+n})$ 之间的模二内积，即：

$$b_i(x,s) = \langle x,(s_{i+1},\dots,s_{i+n})\rangle \bmod 2$$

进一步，定义函数：

$$h(x,s) \overset{\mathrm{def}}{=} b_1(x,s)b_2(x,s)\cdots b_{\ell(|x|)}(x,s)$$

其中，对于任意常数 $c>0$，有：

$$\ell(n)\overset{\mathrm{def}}{=} \min\{n,\lceil c\log_2 n\rceil\}$$

则函数 $h$ 是函数 $g_2$ 的硬核函数。

虽然 $g_2(x,s)$ 已经公开了 $f(x)$ 和随机串 $s$，但是由 $x$ 和 $s$ 的多个滑动窗口内积得到的这些比特：

$$b_1(x,s),\dots,b_{\ell(n)}(x,s)$$

在计算上仍然像随机串一样，无法被高效区分。

直观理解

这个构造可以看成强单向函数的内积硬核谓词定理的多比特版本。

在单比特情形中，通常考虑：

$$b(x,r)=\langle x,r\rangle \bmod 2$$

也就是说，随机选择一个向量 $r$，然后输出 $x$ 与 $r$ 的模二内积，即使知道 $f(x)$ 和 $r$，也无法高效预测这个比特。

不过，这里不只选一个 $r$，而是用一个较长的随机串 $s$ 构造出多个相关的窗口：

$$(s_2,\dots,s_{n+1}),\quad (s_3,\dots,s_{n+2}),\quad \dots$$

然后分别计算它们与 $x$ 的模二内积，从而得到多个比特。

只要输出比特的数量是对数级别的，这些比特整体上仍然可以作为硬核函数。

证明

证明思路

该定理的证明并不是直接证明 $h(x,s)$ 与随机串不可区分，而是先把问题转化为对 $h(x,s)$ 中若干比特异或值的预测问题。

具体来说，$h(x,s)$ 由多个比特组成：

$$h(x,s)=b_1(x,s)b_2(x,s)\cdots b_{\ell(n)}(x,s)$$

如果某个高效算法能够从 $g_2(x,s)=(f(x),s)$ 中提取出关于 $h(x,s)$ 的有效信息，那么直观上，它应当能够对这些比特的某些组合产生预测优势。

这里重点考察的是任意非空比特子集的异或，即：

$$\bigoplus_{i\in I} b_i(x,s), \quad I\subseteq \{1,2,\dots,\ell(n)\},\ I\neq \varnothing$$

证明的核心是说明：这些异或本质上仍然可以写成某种内积硬核谓词的形式。由于强单向函数的内积硬核谓词无法从公开信息中被高效预测，因此 $h(x,s)$ 中任意非空比特子集的异或也无法被高效预测。

另一方面，对于输出长度为对数级别的函数来说，若其任意非空比特子集的异或都无法被高效预测，那么整个输出字符串就无法与同长度随机串高效区分。

而在本定理中，由于 $\ell(n)=O(\log n)$，因此这个条件正好满足。于是，由任意非空异或的不可预测性，可以推出 $h(x,s)$ 与同长度均匀随机串在计算上不可区分，最终得到 $h$ 是 $g_2$ 的硬核函数。

非空异或不可预测性

命题

Proposition：设 $I_n\subseteq \{1,2,\dots,\ell(n)\}$ 是任意一个非空集合序列，定义：

$$b_{I_{|x|}}(x,s) \overset{\mathrm{def}}{=} \bigoplus_{i\in I_{|x|}} b_i(x,s).$$

也就是说，$b_{I_{|x|}}(x,s)$ 表示从

$$h(x,s)=b_1(x,s)b_2(x,s)\cdots b_{\ell(n)}(x,s)$$

中取出由集合 $I_{|x|}$ 指定的那些比特，并对它们做异或。

对于任意概率多项式时间算法 $A’$、任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n$，都有

$$P[A'(I_n,g_2(U_{3n}))=b_{I_n}(U_{3n})] < \frac{1}{2}+\frac{1}{\mathrm{poly}(n)}$$

其中，$U_{3n}$ 是在 $\{0,1\}^{3n}$ 上均匀分布的随机变量。因为 $g_2$ 的输入是 $(x,s)$，其中 $|x|=n$，$|s|=2n$，所以总长度是 $3n$

这一命题的含义是：即使给定 $g_2(x,s)=(f(x),s)$，并且知道要预测的是哪些位置上的异或，任何高效算法也不能以显著大于 $\frac{1}{2}$ 的概率预测：

$$\bigoplus_{i\in I} b_i(x,s)$$

也就是说，$h(x,s)$ 中任意非空比特子集的异或都是难以预测的。

证明

证明思路

在强单向函数的内积硬核谓词定理中，对于函数 $g(x,r)=(f(x),r)$ 以及 $b(x,r)=\langle x,r\rangle \bmod 2$，$b(x,r)$ 是 $g(x,r)$ 的硬核谓词。也就是说，给定 $(f(x),r)$，任何高效算法都不能以显著大于 $\frac{1}{2}$ 的概率预测 $b(x,r)$

因此，如果能够证明预测 $b(x,r)$ 可以归约到预测 $h(x,s)$ 中某个非空异或，那么后者也必然是困难的。

证明目标是说明：如果存在高效算法能够从 $g_2(x,s)=(f(x),s)$ 中预测

$$b_I(x,s)=\bigoplus_{i\in I}b_i(x,s)$$

那么就可以构造另一个高效算法，从 $g(x,r)=(f(x),r)$ 中预测内积硬核谓词

$$b(x,r)=\langle x,r\rangle \bmod 2$$

但是根据前面的强单向函数内积硬核谓词定理，$b(x,r)$ 无法从 $(f(x),r)$ 中被高效预测。因此，预测 $b_I(x,s)$ 也应当是不可能的。

具体来说，令 $X_n\in\{0,1\}^{n}$ 为表示原像 $x$ 的随机变量，$R_n\in\{0,1\}^{n}$ 为表示内积硬核谓词中的随机向量 $r$，$S_n\{0,1\}^{2n}$ 为多比特构造中的随机串。

要证明是的：在给定 $(f(X_n),R_n)$ 时预测 $b(X_n,R_n)$，可以归约到给定 $(f(X_n),S_{2n})$ 时预测 $(X_n,S_{2n})$

关键等式

定义：

$$\operatorname{sub}_i(s_1,\dots,s_{2n}) \overset{\mathrm{def}}{=} (s_{i+1},s_{i+2},\dots,s_{i+n})$$

其中，$\operatorname{sub}_i(s)$ 是随机串 $s$ 中从第 $i+1$ 位开始、长度为 $n$ 的滑动窗口。

对于任意满足 $|s|=2|x|$ 的 $x,s$，以及任意集合 $I\subseteq \{1,\dots,\ell(n)\}$，有：

$$\begin{aligned} b_I(x,s) &= \bigoplus_{i\in I}b_i(x,s) \\ &= \bigoplus_{i\in I} \langle x,\operatorname{sub}_i(s)\rangle \bmod 2 \\ &= \left\langle x, \bigoplus_{i\in I}\operatorname{sub}_i(s) \right\rangle \bmod 2 \end{aligned}$$

该式说明：$h(x,s)$ 中任意非空比特子集的异或，本质上仍然是 $x$ 与某个 $n$ 比特向量之间的模二内积，只不过这里的随机向量 $r$ 被写成了 $r=\bigoplus_{i\in I}\operatorname{sub}_i(s)$

随机性事实

接下来，需要两个随机性事实。

（1）对于任意非空集合 $I$，如果 $S_{2n}$ 在 $\{0,1\}^{2n}$ 上均匀分布，那么 $\bigoplus_{i\in I}\mathrm{sub}_i(S_{2n})$ 在 $\{0,1\}^n$ 上也是均匀分布的。

直观上，虽然这些滑动窗口之间可能有重叠，但只要 $I$ 非空，它们的异或结果仍然保留了足够的随机性，因此得到的是一个均匀随机的 $n$ 比特向量。

（2）给定任意 $r\in\{0,1\}^{n}$ 和非空集合 $I$​，可以可以高效地从如下集合中均匀选取一个字符串 $s$

$$\left\{ s: \bigoplus_{i\in I}\operatorname{sub}_i(s)=r \right\}$$

这说明，在构造归约算法时，可以人为地选择一个满足条件的 $s$，使得

$$\bigoplus_{i\in I}\operatorname{sub}_i(s)=r$$

由于这种构造保证了

$$b(x,r)=b_I(x,s)$$

所以如果 $A’$ 能够预测 $b_I(x,s)$，那么新算法就能预测硬核谓词 $b(x,r)$。这与已知的硬核谓词不可预测性矛盾，因此 $A’$ 不存在。

反证假设

现在反设命题不成立。

存在一个高效算法 $A’$、一个正多项式 $\mathrm{poly}(\cdot)$，以及无穷多个 $n$ 和对应的非空集合 $I_n$，使得：

$$P[A'(I_n,g_2(U_{3n}))=b_{I_n}(U_{3n})] \geq \frac{1}{2}+\frac{1}{p(\mathrm{poly})}$$

即 $A’$ 能够以非忽略优势预测某个非空异或。

由于 $\ell(n)=O(\log n)$，所以所有非空集合 $I\subseteq \{1,\dots,\ell(n)\}$ 的数量为：

$$2^{\ell(n)}-1=\operatorname{poly}(n)$$

因此，可以枚举所有可能的 $I$，并通过随机实验估计每个 $I$ 对应的成功概率：

$$p_I \overset{\mathrm{def}}{=} P[A'(I,g_2(U_{3n}))=b_I(U_{3n})]$$

从中选出一个成功概率足够高的集合 $I$，使得：

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

这里把优势从 $\frac{1}{\mathrm{poly}(n)}$ 放宽到 $\frac{1}{2p(n)}$ 是为了允许估计过程中存在小的误差。

矛盾推出

接下来构造一个新算法，用来预测内积硬核谓词 $b(x,r)$。

新算法的输入是 $y=f(x), r$，其步骤为：

1. 根据输入长度 $n=|r|$，找到前面选出的集合 $I$
2. 均匀随机选取一个字符串 $s$，使其满足 $\bigoplus_{i\in I}\operatorname{sub}_i(s)=r$
3. 输出 $A’(I,(y,s))$

由于 $s$ 满足 $\bigoplus_{i\in I}\operatorname{sub}_i(s)=r$，所以根据关键等式，有：

$$b_I(x,s) = b\left(x,\bigoplus_{i\in I}\operatorname{sub}_i(s)\right) = b(x,r)$$

因此，算法 $A’$ 对 $b_I(x,s)$ 的预测结果，正好就是对 $b(x,r)$ 的预测结果。

当 $r$ 在 $\{0,1\}^n$ 上均匀随机选取时，上述构造得到的 $s$ 在 $\{0,1\}^{2n}$ 上也是均匀分布的。所以新算法预测 $b(x,r)$ 的成功概率与 $A’$ 预测 $b_I(x,s)$ 的成功概率一致，至少为 $\frac{1}{2}+\frac{1}{2\mathrm{poly}(n)}$。这说明构造出了一个高效算法，能够从 $(f(x),r)$ 中以非忽略优势预测

$$b(x,r)=\langle x,r\rangle \bmod 2$$

但这与前面已经证明的结论矛盾：$b(x,r)$ 是 $g(x,r)=(f(x),r)$ 的硬核谓词，不能被任何高效算法以非忽略优势预测。因此，反设不成立。

所以，对于任意非空集合序列 $I_n\subseteq \{1,\dots,\ell(n)\}$，不存在高效算法能够从 $g_2(x,s)=(f(x),s)$ 中以非忽略优势预测：

$$b_{I_n}(x,s) = \bigoplus_{i\in I_n}b_i(x,s)$$

也就是说，$h(x,s)$ 中任意非空比特子集的异或都是不可高效预测的。

命题得证。

计算异或引理

引理

Lemma：设设 $f$ 和 $h$ 是任意长度规则函数，令 $\ell(n)\overset{\mathrm{def}}{=}|h(1^n)|$，对于任意算法 $D$，定义：

$$p \overset{\mathrm{def}}{=} P[D(f(X_n),h(X_n))=1],\quad q \overset{\mathrm{def}}{=} P[D(f(X_n),R_{\ell(n)})=1]$$

其中，$X_n$ 在 $\{0,1\}^n$ 上均匀分布，$R_{\ell(n)}$ 在 $\{0,1\}^{\ell(n)}$ 上均匀分布，并且二者相互独立。

利用 $D$ 构造一个新算法 $G=G_D$。算法 $G$ 的输入是 $y, S\subseteq \{1,\dots,\ell(n)\}, \ell(n)$，算法随机选择：

$$r=r_1r_2\cdots r_{\ell(n)}\in \{0,1\}^{\ell(n)}$$

然后输出：

$$G(y,S,\ell(n)) = D(y,r)\oplus 1\oplus \left(\bigoplus_{i\in S}r_i\right)$$

若 $I_\ell$ 是从 $\{1,\dots,\ell(n)\}$ 的所有非空子集中均匀随机选出的集合，则有

$$P \left[ G(f(X_n),I_\ell,\ell(n)) = \bigoplus_{i\in I_\ell}h_i(X_n) \right] = \frac{1}{2} + \frac{p-q}{2^{\ell(n)}-1}$$

其中，$h_i(x)$ 表示 $h(x)$ 的第 $i$ 个比特，$p-q$ 用于衡量算法 $D$ 区分真实输出 $h(X_n)$ 和随机串 $R_{\ell(n)}$ 的能力，如果 $p-q$ 是非忽略量，那么 $D$ 就是一个有效区分器。

该引理说明：如果存在一个算法 $D$，能够区分 $(f(X_n),h(X_n))$ 和 $(f(X_n),R_{\ell(n)})$，那么就可以利用 $D$ 构造另一个算法 $G$，使其能够预测 $h(X_n)$ 中某个随机非空比特子集的异或。预测优势为：

$$\frac{p-q}{2^{\ell(n)}-1}$$

其中，分母 $2^{\ell(n)}-1$ 是所有非空子集的数量。

因此，如果 $\ell(n)=O(\log n)$，那么有：

$$2^{\ell(n)}-1=\operatorname{poly}(n)$$

这意味着：只要 $D$ 的区分优势 $p-q$ 是非忽略的，那么算法 $G$ 的预测优势仍然是非忽略的。

这就是为什么定理中只能保证输出长度为对数级别。因为只有在 $\ell(n)=O(\log n)$ 时，所有非空异或的数量仍然是多项式规模，区分优势不会被指数级地稀释掉。

证明

计算异或引理的证明本质上是在计算算法 $G$ 的成功概率。

固定某个 $x\in \{0,1\}^n$，并令 $z=h(x),\ell=\ell(n)$，记 $\mathcal{C}$​ 为集合 $\{1,\dots,\ell\}$ 的所有非空子集，因此有：

$$|\mathcal C|=2^\ell-1$$

对于任意 $S\in\mathcal C$​，定义关系 $r\equiv_S h(x)$，其代表：

$$\bigoplus_{i\in S}r_i = \bigoplus_{i\in S}h_i(x)$$

也就是说，$r$ 与 $z$ 在位置集合 $S$ 上的异或相同。

令 $\Delta(r)$ 表示随机变量 $D(f(x),r)$，算法 $G$ 的输出为：

$$G(f(x),S,\ell) = D(f(x),r)\oplus 1\oplus \left(\bigoplus_{i\in S}r_i\right)$$

它希望预测的是 $\bigoplus_{i\in S}h_i(x)$，因此 $G$ 成功当且仅当以下两种情况之一发生：

1. $\Delta(r)=1$，并且 $r\equiv_S h(x)$
2. $\Delta(r)=0$，并且 $r\not\equiv_S h(x)$

于是，定义：

$$s(x) \overset{\mathrm{def}}{=} P\left[ G(f(x),I_\ell,\ell) = \bigoplus_{i\in I_\ell}h_i(x) \right]$$

其中，$I_\ell$ 是从 $\mathcal C$ 中均匀随机选取的非空集合。

则有：

$$\begin{aligned} s(x) &= \frac{1}{|\mathcal C|} \sum_{S\in\mathcal C} \Pr\left[ G(f(x),S,\ell) = \bigoplus_{i\in S}h_i(x) \right] \\ &= \frac{1}{|\mathcal C|} \sum_{S\in\mathcal C} \left( P[\text{event 1}] + P[\text{event 2}] \right) \\ &= \frac{1}{2|\mathcal C|} \sum_{S\in\mathcal C} \left( P[\Delta(R_\ell)=1\mid R_\ell\equiv_S h(x)] + P[\Delta(R_\ell)=0\mid R_\ell\not\equiv_S h(x)] \right) \end{aligned}$$

这里第二个条件 $R_\ell\not\equiv_S h(x)$ 不是等价关系。因为当 $\Delta(R_\ell)=0$ 时，算法 $G$ 会额外翻转一次结果，所以只有当 $R_\ell$ 与 $h(x)$ 在 $S$ 上的异或不同时，$G$ 才会预测正确。

由于

$$P[\Delta(R_\ell)=0\mid R_\ell\not\equiv_S h(x)] = 1- P[\Delta(R_\ell)=1\mid R_\ell\not\equiv_S h(x)]$$

所以：

$$\begin{aligned} s(x) &= \frac12 + \frac{1}{2|\mathcal C|} \sum_{S\in\mathcal C} \Big( \Pr[\Delta(R_\ell)=1\mid R_\ell\equiv_S h(x)] - P[\Delta(R_\ell)=1\mid R_\ell\not\equiv_S h(x)] \Big) \end{aligned}$$

对于固定的 $S$，满足 $R_\ell\equiv_S h(x)$ 的字符串 $R_\ell$ 有 $2^{\ell-1}$ 个，满足 $R_\ell\not\equiv_S h(x)$ 的字符串也有 $2^{\ell-1}$ 个。因此，有：

$$\begin{aligned} s(x) &= \frac12 + \frac{1}{2|\mathcal C|}\cdot \frac{1}{2^{\ell-1}} \left( \sum_{S\in\mathcal C} \sum_{r\equiv_S h(x)} P[\Delta(r)=1]\right. \left. - \sum_{S\in\mathcal C} \sum_{r\not\equiv_S h(x)} P[\Delta(r)=1] \right)\\ &= \frac12 + \frac{1}{2^\ell|\mathcal C|} \left( \sum_r \sum_{S\in EQ(r,h(x))} P[\Delta(r)=1] - \sum_r \sum_{S\in NE(r,h(x))} P[\Delta(r)=1] \right) \end{aligned}$$

其中：

$$\begin{align*} EQ(r,z)\overset{\mathrm{def}}{=} \{S\in\mathcal C:r\equiv_S z\} \\ NE(r,z)\overset{\mathrm{def}}{=} \{S\in\mathcal C:r\not\equiv_S z\} \end{align*}$$

接下来利用计数事实：

当 $r\neq z$ 时：

$$|EQ(r,z)|=2^{\ell-1}-1, \qquad |NE(r,z)|=2^{\ell-1}$$

当 $r=z$ 时：

$$EQ(z,z)=\mathcal C, \qquad NE(z,z)=\varnothing$$

因此：

$$\begin{aligned} s(x) &= \frac12 + \frac{1}{2^\ell|\mathcal C|} \sum_{r\neq h(x)} \left( (2^{\ell-1}-1)P[\Delta(r)=1] - 2^{\ell-1}P[\Delta(r)=1] \right) \\ &\quad + \frac{1}{2^\ell|\mathcal C|} |\mathcal C|P[\Delta(h(x))=1] \\ &= \frac12 - \frac{1}{2^\ell|\mathcal C|} \sum_{r\neq h(x)} P[\Delta(r)=1] + \left( \frac{1}{|\mathcal C|} - \frac{1}{2^\ell|\mathcal C|} \right) P[\Delta(h(x))=1] \end{aligned}$$

将 $\Delta(r)=D(f(x),r)$ 代回，有：

$$\begin{aligned} s(x) &= \frac12 + \frac{1}{|\mathcal C|} \left( P[D(f(x),h(x))=1] - P[D(f(x),R_\ell)=1] \right) \end{aligned}$$

最后，对 $x$ 取期望：

$$\begin{aligned} \mathbb E[s(X_n)] &= \frac12 + \frac{1}{|\mathcal C|} \left( P[D(f(X_n),h(X_n))=1] - P[D(f(X_n),R_\ell)=1] \right)\\ &= \frac12 + \frac{1}{2^\ell-1}(p-q) \end{aligned}$$

即：

$$P \left[ G(f(X_n),I_\ell,\ell(n)) = \bigoplus_{i\in I_\ell}h_i(X_n) \right] = \frac12 + \frac{p-q}{2^{\ell(n)}-1}$$

引理得证。

定理推出

在非空异或不可预测性命题中，已经证明 $h(x,s)$ 的任意非空比特子集的异或都无法从 $g_2(x,s)=(f(x),s)$ 中被高效预测。

而计算异或引理说明：当输出长度满足 $\ell(n)=O(\log n)$ 时，任意非空异或不可预测，就可以推出整个字符串与随机串不可区分。

因此，可以得到：$h(x,s)$ 与 $R_{\ell(n)}$ 在给定 $g_2(x,s)$ 后不可高效区分，即：函数 $h$ 是函数 $g_2$ 的硬核函数。