【强单向函数的内积硬核谓词定理】
定理
设 $f$ 是任意强单向函数，定义函数：
其中，$|x|=|r|$。再定义谓词 $b(x,r)$ 为二进制向量 $x$ 和 $r$ 的模二内积，即：
基于上述定义，对于函数 $g$ 与谓词 $b$，有：谓词 $b$ 是函数 $g$ 的硬核谓词。
其中，谓词 $b$ 通常称为内积硬核谓词（Inner-Product Hard-Core Predicate）。
直观含义
如果 $f$ 是强单向函数，那么给定 $g(x,r)=(f(x),r)$，任何高效算法都无法以显著高于 $\frac{1}{2}$ 的概率预测：
对于二进制向量的模二内积：
$r_i$ 只有两种可能：
- 若 $r_i=1$，则 $x_i r_i=x_i$
- 若 $r_i=0$，则 $x_ir_i=0$
因此，求和过程中真正留下来的只有满足 $r_i=1$ 的位置，即：
在二进制运算中，若干个比特的和模二等价于它们的异或，故有：
直观地说，$r$ 的作用就是一个选择掩码：$r_i=1$ 表示选中 $x_i$，$r_i=0$ 表示不选中 $x_i$。最后再把所有被选中的 $x_i$ 进行异或。
因此，定理可以直观理解为：如果 $f$ 是强单向函数，那么在给定 $f(x)$ 和随机选择向量 $r$ 的情况下，想要预测 $x$ 中由 $r$ 选出的随机子集比特的异或值，在计算上是困难的。
换句话说，即使 $r$ 是公开的，攻击者也无法显著优于随机猜测地判断 $\bigoplus_{i:r_i=1}x_i$ 的取值。
函数 $g$ 的构造
原函数 $f(x)$ 未必有一个显然可用的硬核谓词。定理的做法是把 $f$ 扩展成 $g(x,r)=(f(x),r)$，这里 $r$ 被直接公开，并不要求隐藏，真正需要隐藏的是：
也就是说，虽然 $r$ 是已知的，但由于 $x$ 被隐藏在 $f(x)$ 后面，攻击者无法预测 $x$ 与 $r$ 的模二内积。
这个构造的意义在于：它把任意强单向函数 $f$ 转换成一个具有明确硬核谓词的函数 $g$。同时，$g$ 仍然保持 $f$ 的重要性质：
- 如果 $f$ 是强单向函数，那么 $g$ 也是强单向函数
- 如果 $f$ 是长度保持的，那么 $g$ 也保持相应的长度结构
- 如果 $f$ 是单射，那么 $g$ 也是单映射
强单向函数的约束
定理要求 $f$ 是强单向函数，而不能只是弱单向函数。这是因为，强单向函数要求任何概率多项式时间算法反演成功的概率都是可忽略的，而弱单向函数只要求任何高效算法在反演时有一个非可忽略的失败概率。
定理的结论是硬核谓词，即预测成功概率不能显著超过 $\frac{1}{2}$。这种结论非常强，需要底层函数的反演困难性也足够强。如果 $f$ 只是弱单向函数，那么上述内积硬核谓词不一定是硬核谓词。
因此，这一定理的逻辑是：
而不能简单替换为：
【证明思路】
基本思路
为证明谓词 $b(x,r)=\langle x,r\rangle \bmod 2$ 是函数 $g(x,r)=(f(x),r)$ 的硬核谓词，采用反证法。
证明的核心思路是：假设存在一个高效算法 $G$，能够在给定 $(f(x),r)$ 的情况下，显著优于随机猜测地预测内积比特
那么可以利用这个预测能力构造一个反演算法，使其从 $f(x)$ 中恢复出 $x$。
为了完成这一归约，首先将算法 $G$ 的平均预测优势转化为一批固定输入上的预测优势，随后在这些固定输入上，利用 $G$ 的预测能力逐步恢复原像。由于这些固定输入所占比例仍然是非可忽略的，因此得到的反演算法在整体上也具有非可忽略的成功概率。
这就与 $f$ 是强单向函数的假设矛盾。因此，不存在这样的高效预测算法 $G$，从而说明 $b(x,r)$ 是 $g(x,r)$ 的硬核谓词。
平均预测优势
假设存在一个概率多项式时间算法 $G$，在输入 $f(x)$ 和 $r$ 后，试图猜测 $x$ 与 $r$ 的模二内积：
也就是说，$G$ 的任务是根据 $(f(x),r)$ 预测 $b(x,r)$。
令 $\varepsilon(n)$ 表示算法 $G$ 在长度为 $n$ 的输入上的整体预测优势，设 $X_n$ 和 $R_n$ 是两个相互独立的随机变量，并且都在 $\{0,1\}^n$ 上均匀分布，则：
其中，$\frac{1}{2}$ 是随机猜测一个比特的成功概率。
因此，$\varepsilon(n)$ 表示算法 $G$ 相比随机猜测多出的成功概率。
反证假设
假设 $b$ 不是 $g$ 的硬核谓词。
根据硬核谓词的否定形式，存在一个高效预测算法 $G$、一个正多项式 $\mathrm{poly}(\cdot)$，以及一个无限的输入长度集合 $\mathcal{N}$，使得对每个 $n\in\mathcal{N}$，都有：
也就是说，算法 $G$ 可以在无穷多个输入长度上，以非可忽略优势预测：
接下来固定这个算法 $G$，并且只考虑满足上述条件的输入长度 $n\in\mathcal{N}$。
固定输入优势
固定输入成功率
算法 $G$ 的优势 $\varepsilon(n)$ 是在随机选择 $x$ 和随机选择 $r$ 的整体平均意义下定义的，为了后续构造反演算法，需要把这种整体平均优势转化为关于固定输入 $x$ 的预测优势。
对每个固定的 $x\in\{0,1\}^n$，定义：
这里的概率只取在随机选择的 $R_n$ 以及算法 $G$ 的内部随机性上，$x$ 是固定的。因此，$s(x)$ 表示：当原像固定为 $x$ 时，算法 $G$ 对随机 $r$ 的预测成功概率。
由于整体预测优势的定义可知：
左边也可以看作先随机选取 $X_n$，再对固定的 $X_n$ 考察 $s(X_n)$，因此有：
这说明，从所有 $x\in\{0,1\}^n$ 的平均意义上看，算法 $G$ 的预测成功概率比随机猜测高出 $\varepsilon(n)$。
断言
既然 $G$ 在整体平均上具有非可忽略优势，那么必然存在一批好的输入 $x$，使得在这些固定的 $x$ 上，算法 $G$ 仍然具有明显预测优势，即存在如下断言：
Claim：存在一个集合 $S_n\subseteq\{0,1\}^n$，其大小至少为：
并且对每个 $x\in S_n$，都有：
即至少有 $\frac{\varepsilon(n)}{2}$ 比例的长度为 $n$ 的输入 $x$ 满足：当 $x$ 固定时，算法 $G$ 在随机 $R_n$ 上预测 $b(x,R_n)$ 的成功概率仍然至少为 $\frac{1}{2}+\frac{\varepsilon(n)}{2}$。
断言证明
下面证明上述断言：$S_n$ 的大小至少为 $\frac{\varepsilon(n)}{2}\cdot 2^n$
定义所有固定输入优势至少为 $\frac{\varepsilon(n)}{2}$ 的输入集合：
反设：$|S_n|<\frac{\varepsilon(n)}{2}\cdot 2^n$，即随机选取 $X_n$ 时，有：
对于 $x\in S_n$，由于 $s(x)$ 是成功概率，所以有平凡上界：
而对于 $x\notin S_n$，根据 $S_n$ 的定义，有：
因此，联立求期望可得：
由于 $\varepsilon(n)>0$，有：
所以：
这与 $\mathbb{E}_{X_n}[s(X_n)] = \frac{1}{2}+\varepsilon(n)$ 矛盾。所以反设不成立，即必有：
断言得证。
【反演算法的改进方向】
逐位恢复的基本想法
上一节已经得到，对每个好输入 $x\in S_n$，算法 $G$ 在给定 $f(x)$ 和随机 $R_n$ 时，可以以略高于随机猜测的概率预测：
即：
接下来的目标是利用这种预测能力反演 $f$，即从 $f(x)$ 中恢复出 $x$。
由于 $x\in\{0,1\}^n$ 是一个长度为 $n$ 的比特串，因此只要能够恢复每一位 $x_i$，就可以恢复整个 $x$。那么，一个自然想法是：能否利用 $G$ 对内积比特的预测，逐位恢复 $x_i$？
理想化的强假设
为了说明如何利用算法 $G$ 的预测能力恢复原像 $x$，先考虑一个理想化情形。
对固定的 $x\in S_n$，我们知道算法 $G$ 在随机 $r$ 上预测 $b(x,r)$ 的成功概率为 $s(x)$，前面已经证明，对于 $x\in S_n$，有：
这说明 $G$ 的预测结果比随机猜测好一些。但这个优势可能很小，并不足以直接用于恢复 $x$ 的每一位。
为清楚说明恢复思路，假设 $G$ 的预测能力更强，即对于固定的 $x\in S_n$，有：
这个假设的含义是：对于固定的 $x$，算法 $G$ 在随机选择的 $r$ 上预测 $b(x,r)$ 时，不只是略好于随机猜测，而是具有相当高的可靠性。
这里的 $\frac{3}{4}$ 只是为了分析一个更容易理解的理想情形。在这个情形下，算法 $G$ 的错误率足够低，因此可以先忽略一般情形中的误差放大问题，专注于说明为什么预测内积比特有可能帮助恢复 $x$ 的每一位。
朴素恢复方法
设 $x_i$ 表示 $x$ 的第 $i$ 个比特，为了恢复 $x_i$，随机选择 $r\in\{0,1\}^n$，然后分别计算 $G(f(x),r)$ 和 $G(f(x),r\oplus e^i)$，其中，$e^i$ 是第 $i$ 个位置为 $1$、其他位置为 $0$ 的 $n$ 维二进制向量：
如果算法 $G$ 在这两个点上都预测正确，即：
那么将这两个预测结果异或，有：
也就是说，如果 $G$ 在 $r$ 和 $r\oplus e^i$ 这两个输入上都预测正确，那么就可以恢复出 $x_i$。
强假设下朴素方法的有效性
在理想化假设下：
所以算法 $G$ 在固定 $x$ 上的平均错误概率小于：
对于随机选取的 $r$，希望下面两个事件同时发生：
根据并集界，两个事件中至少有一个出错的概率至多是两倍的平均错误概率，因此两个都正确的概率至少为：
所以，在强假设下，每次随机选取 $r$，通过 $G(f(x),r)\oplus G(f(x),r\oplus e^i)$ 得到正确 $x_i$ 的概率都显著高于 $\frac{1}{2}$。
于是，可以重复上述过程多项式次，并采用多数投票，从而以很高概率恢复 $x_i$，对每一位 $i$ 都这样做，就可以恢复整个 $x$，进而反演 $f(x)$。
朴素方法的局限
上述朴素方法给出了一个重要思路：如果能够可靠地预测内积比特，就可以利用内积的线性性恢复 $x$ 的每一位。
但是，这个朴素方法依赖了一个过强的假设：
而实际上，我们只知道：
也就是说，算法 $G$ 只比随机猜测好一点，远远达不到超过 $\frac{3}{4}$ 的成功概率。
问题的根源在于：为了恢复一个比特 $x_i$，朴素方法需要同时调用两次 $G$，分别预测 $b(x,r)$ 和 $b(x,r\oplus e^i)$，只有当这两次预测都正确时，才能得到正确的 $x_i$，这会导致错误概率被放大。
因此，朴素方法只是一个启发，它展示了如何用内积预测恢复原像，但还不能完成一般情形下的证明，需要改进使用 $G$ 的方式，使恢复每一位时只依赖一次 $G$ 的预测，从而避免错误概率翻倍。
朴素方法的改进方向
重复调用
对于算法 $G$ 使用方式的改进，一个自然想法是：既然 $G$ 有错误，那能不能对同一个输入多次运行 $G$，然后多数投票降低错误率？
由于 $G$ 的错误不一定是独立随机噪声，它可能在某些输入上总是回答正确，而在另一些输入上总是回答错误。例如，$G$ 可能在所有输入 $(f(x),r)$ 的 $\frac{3}{4}$ 上总是回答正确，而在剩下的 $\frac{1}{4}$ 上总是回答错误。此时，如果某个输入恰好属于它总是出错的那一部分，那么无论重复运行多少次，得到的仍然是错误答案。
因此，算法 $G$ 的平均错误概率不能通过对同一输入重复调用来降低。
这说明，需要一种新的使用 $G$ 的方式，不是简单重复调用 $G$，而是重新组织需要查询的随机向量，使得每次恢复比特时尽量只依赖一次 $G$ 的预测。
单次预测
为了避免错误概率被放大，一个关键想法是：在恢复 $x_i$ 时，不再同时依赖 $G$ 对 $b(x,r)$ 和 $b(x,r\oplus e^i)$ 的同时预测。
具体来说，朴素方法需要同时预测 $b(x,r)$ 和 $b(x,r\oplus e^i)$，我们希望只用 $G$ 预测其中一个值，而另一个值通过其他方式获得。这样一来，每个 $r$ 和每个 $i$ 只需要调用一次 $G$，错误概率就不会被翻倍。但是，这又带来一个新问题：如何知道另一个值？
我们假设只用 $G$ 来预测 $b(x,r\oplus e^i)$，$b(x,r)$ 通过猜测的方式获得。如果只需要猜一个 $b(x,r)$，那么成功概率是 $\frac{1}{2}$，如果只需要猜对对数个这样的值，成功概率仍然是多项式倒数，也就是非可忽略的。
但是，在恢复 $x$ 的过程中，需要处理多项式多个不同的 $r$，如果对每个 $r$ 都独立猜测 $b(x,r)$，那么全部猜对的概率会是指数级小的。这就无法得到一个非可忽略成功概率的反演算法。
因此，需要一种特殊方式生成这些 $r$：
- 这些 $r$ 要足够随机，使得 $G$ 在它们上仍然具有预测优势
- 所有对应的 $b(x,r)$ 又不能太难猜，最好只需要猜少量基础值就能推出全部值
这两个要求看起来是矛盾的，但可以通过两两独立（Pairwise Independent）的构造同时满足。
两两独立的构造
假设需要生成 $m=\mathrm{poly}(n)$ 个向量 $r$，取：
然后独立均匀地选择 $\ell$ 个字符串 $s_1,\dots,s_\ell\in\{0,1\}^n$，接着，不再直接猜所有 $m$ 个 $b(x,r)$，只猜 $b(x,s_1),\dots,b(x,s_\ell)$，并记这些猜测值为 $\sigma_1,\dots,\sigma_\ell$，其中每个 $\sigma_j$ 都是独立均匀随机选取的比特。
此时，全部猜对的概率为 $2^{-\ell}$，故有：
这是非可忽略的概率。
接下来，只需要利用这 $\ell$ 个基础向量 $s_1,\dots,s_\ell$ 生成多项式个查询向量。具体来说，对集合 $\{1,2,\dots,\ell\}$ 的每个非空子集 $J$，定义：
也就是说，每个 $r_J$ 是若干个 $s_j$ 的异或。
因为非空子集 $J$ 的数量是 $2^\ell-1=m$，所以这种方式正好生成 $m$ 个向量 $r_J$，这些 $r_J$ 具有两个重要性质：
- 每个 $r_J$ 都在 $\{0,1\}^n$ 上均匀分布
- 不同的 $r_J$ 两两独立
因此，虽然这些 $r_J$ 是由少量基础向量 $s_1,\dots,s_\ell$ 组合出来的，但从算法 $G$ 的角度看，它们仍然具有足够的随机性，这就保证了算法 $G$ 在这些查询向量上仍然可以发挥原来的预测优势。
此时，只需要证明：为什么只猜测基础内积值 $b(x,s_1),\dots,b(x,s_\ell)$，就能够得到所有 $b(x,r_J)$ 的猜测值。
关键在于，内积硬核谓词对第二个变量是线性的，也就是说：
因此，对于 $r_J=\bigoplus_{j\in J}s_j$，有：
所以，如果猜对了所有基础值 $b(x,s_1),\dots,b(x,s_\ell)$，那么就可以推出所有 $b(x,r_J)$ 对应的猜测为：
也就是说，只需要猜 $\ell$ 个基础内积值，就能推出多项式多个 $r_J$ 对应的内积值。
这正好解决了前面的困难：既得到了多项式多个足够随机的查询向量 $r_J$，又避免了对多项式多个 $b(x,r_J)$ 逐个独立猜测。由于只需要猜对 $\ell$ 个基础值，全部猜对的概率仍然是多项式倒数，从而是非可忽略的。
【定理证明】
基本设定
下面回到正式证明。
证明目标是：利用假设存在的预测算法 $G$，构造一个反演算法 $A$，使得 $A$ 能够以非可忽略概率从 $f(x)$ 中恢复出 $x$，从而与 $f$ 的强单向性矛盾。
回顾前面的反证假设：存在一个概率多项式时间算法 $G$、一个正多项式 $\mathrm{poly}(\cdot)$，以及无限多个输入长度组成的集合 $\mathcal{N}$，使得对每个 $n\in\mathcal{N}$，都有：
其中 $\varepsilon(n)$ 是算法 $G$ 预测内积比特的平均优势。
此外，为简化讨论，假设 $f$ 是长度保持函数
反演算法
随机猜测算法
设输入为 $y$，其中 $y$ 被认为是某个 $x$ 的像，即有：
算法 $A$ 的目标是从 $y$ 中恢复出 $x$。令 $n\stackrel{\mathrm{def}}{=}|y|$，并取：
记 $m=2^\ell-1$，则有：
在此基础上，算法 $A$ 的步骤如下：
（1）选择基础向量和基础猜测
算法 $A$ 独立均匀地选择 $s_1,\dots,s_\ell\in\{0,1\}^n$，同时独立均匀地选择，$\sigma_1,\dots,\sigma_\ell\in\{0,1\}$，其中 $s_1,\dots,s_\ell$ 是基础向量，而 $\sigma_1,\dots,\sigma_\ell$ 是算法对基础内积值的猜测。
直观来说，$\sigma_j$ 是对 $b(x,s_j)$ 的猜测。
（2）生成查询向量与内积猜测
对于每个非空子集 $J\subseteq\{1,2,\dots,\ell\}$，算法计算：
其中，$r_J$ 是由基础向量异或得到的查询向量，$\rho_J$ 是对应内积值 $b(x,r_J)$ 的猜测。
如果所有基础猜测都是正确的，即：
那么利用内积硬核谓词的线性性质，有：
因此，只要少量基础猜测全部正确，就可以推出所有 $b(x,r_J)$ 的值。
（3）逐位生成候选值
对于每一位 $i\in\{1,\dots,n\}$，以及每个非空子集 $J\subseteq\{1,2,\dots,\ell\}$，计算：
其中，$e^i$ 是第 $i$ 个标准基向量，即第 $i$ 位为 $1$、其他位为 $0$。
这个式子的含义是：用 $\rho_J$ 作为对 $b(x,r_J)$ 的猜测，用 $G(y,r_J\oplus e^i)$ 作为对 $b(x,r_J\oplus e^i)$ 的预测，然后二者异或，尝试得到 $x_i$。
因为如果 $\rho_J=b(x,r_J)$，且 $G(y,r_J\oplus e^i)=b(x,r_J\oplus e^i)$，那么：
所以每个 $z_i^J$ 都可以看作对第 $i$ 位 $x_i$ 的一次候选恢复。
（4）多数投票恢复每一位
对于每个 $i\in\{1,\dots,n\}$，令 $z_i$ 为所有 $z_i^J$ 中出现次数更多的那个比特，即多数投票结果。
最后输出：
即反演算法 $A$ 对原像 $x$ 的恢复结果。
朴素枚举算法
在反演算法 $A$ 中，$\sigma_1,\dots,\sigma_\ell$ 是随机猜测的，因此只有在这些猜测全部正确时，算法才有机会成功。其还有一种替代实现。
具体来说，不随机猜测，而是枚举所有可能的 $\sigma_1,\dots,\sigma_\ell\in\{0,1\}$，此时有 $2^\ell$ 种可能。
对每一种可能的基础猜测，都按照上述方法计算一个候选字符串 $z$。然后在所有候选 $z$ 中，优先输出满足：
的那个。
这种替代算法记为 $A’$。它的思想是用枚举代替随机猜测，因此在成功概率上会更好，但需要进一步讨论其效率和实现。
成功概率分析
下面分析算法 $A$ 在输入 $y=f(x)$，且 $x\in S_n$ 时的成功概率。
基础猜测正确时的化简
仍然考虑内积硬核谓词对第二个变量的线性性性质。对于任意 $x,\alpha,\beta\in\{0,1\}^n$，都有：
因此：
所以，如果所有基础猜测都正确，即：
那么对所有非空子集 $J$，都有：
在这个条件下：
因此，要证明多数投票能够恢复 $x_i$，只需要证明：对于每个固定的 $i$，多数个 $z_i^J$ 等于 $x_i$。
多数投票的正确性断言
由此，可以得到如下断言：
Claim：对于每个 $x\in S_n$ 和每个 $1\le i\le n$，有：
其中，$r_J=\bigoplus_{j\in J}s_j$，概率取在独立均匀选择的 $s_1,\dots,s_\ell$ 上。
这个断言的含义是：对固定的 $x\in S_n$ 和固定的第 $i$ 位来说，绝大多数 $J$ 都会给出正确的候选值 $x_i$，因此多数投票可以正确恢复 $x_i$，并且失败概率小于 $\frac{1}{2n}$。
断言证明
随机变量的定义
对每个非空子集 $J$，定义一个 $0/1$ 随机变量 $\zeta_J$：
也就是说，$\zeta_J=1$ 表示由子集 $J$ 得到的候选值正确恢复了第 $i$ 位 $x_i$。
由于内积谓词对第二个变量具有线性性质，有：
因此，如果算法 $G$ 在输入 $(f(x),r_J\oplus e^i)$ 上预测正确，即：
那么：
所以此时 $\zeta_J=1$。
反过来，如果 $\zeta_J=1$，即：
又因为：
两式同时异或 $b(x,r_J)$，即可得到：
因此：
也就是说，$\zeta_J=1$ 的条件正是算法 $G$ 在输入 $(f(x),r_J\oplus e^i)$ 上预测正确。
单个候选正确概率
由于每个 $r_J$ 都在 $\{0,1\}^n$ 上均匀分布，所以 $r_J\oplus e^i$ 也在 $\{0,1\}^n$ 上均匀分布。
因此，算法 $G$ 在输入 $(f(x),r_J\oplus e^i)$ 上预测正确的概率就是 $s(x)$，而 $x\in S_n$，由前面的固定输入优势可知：
又由于对当前考虑的 $n\in\mathcal{N}$，有：
所以：
因此，每个 $\zeta_J=1$ 的概率至少为：
两两独立性
接下来证明随机变量 $\zeta_J$ 两两独立，证明思路是：先证明这些向量 $r_J$ 两两独立，再由 $\zeta_J$ 依赖于 $r_J\oplus e^i$ 推出 $\zeta_J$ 两两独立。
任取两个不同的非空子集 $J\ne K$，不妨设 $K\setminus J\ne\varnothing$，于是可以取：
这意味着 $s_k$ 出现在 $r_K$ 的表达式中，但不出现在 $r_J$ 的表达式中。因此，在给定 $r_J$ 的条件下，$s_k$ 仍然保持均匀随机，并且独立于 $r_J$。
对任意 $\alpha,\beta\in\{0,1\}^n$，考虑条件概率：
由于 $r_K=\bigoplus_{j\in K}s_j$，且 $k\in K$，可以将 $r_K$ 写成：
在给定除 $s_k$ 之外的其他向量后，要使 $r_K=\beta$，$s_k$ 只能取唯一值：
而 $s_k$ 在 $\{0,1\}^n$ 上均匀分布，并且不参与 $r_J$ 的构造，所以即使给定 $r_J=\alpha$，$s_k$ 仍然均匀。因此：
另一方面，$r_K$ 本身也是 $\{0,1\}^n$ 上的均匀随机向量，所以：
于是：
这说明 $r_J$ 和 $r_K$ 相互独立。由于 $J,K$ 是任意两个不同的非空子集，所以所有 $r_J$ 是两两独立的。
进一步地，由于 $r_J\oplus e^i$ 只是 $r_J$ 加上一个固定向量 $e^i$，不会破坏均匀性和两两独立性，因此这些 $r_J\oplus e^i$ 也两两独立。
而 $\zeta_J$ 的定义为：
所以 $\zeta_J$ 是由 $r_J\oplus e^i$ 决定的 $0/1$ 随机变量，因此，$\zeta_J$ 之间也是两两独立的。
多数投票的正确性
令 $m=2^\ell-1$，于是共有 $m$ 个非空子集 $J$，也就是有 $m$ 个随机变量 $\zeta_J$。考虑随机变量之和：
它表示有多少个候选值正确恢复了 $x_i$。
由前面 $\zeta_J=1$ 的最小概率 $P[\zeta_J=1]\ge \frac{1}{2}+\frac{1}{2\mathrm{poly}(n)}$ 可得：
我们希望证明多数候选值正确，即：
其失败事件为：
若该事件发生，则 $Z$ 至少偏离其期望：
因此：
由于 $\zeta_J$ 是 $0/1$ 随机变量，其方差满足：
又因为这些 $\zeta_J$ 两两独立，所以：
由 Chebyshev 不等式可得：
又因为：
所以：
因此：
等价地：
也就是说，多数个 $\zeta_J$ 等于 $1$ 的概率至少为 $1-\frac{1}{2n}$，将 $\zeta_J$ 的定义代回去，有：
断言得证。
整体恢复
如果所有基础猜测都正确，即：
那么对所有非空子集 $J$，都有：
在这个条件下，上述断言说明：对于每一位 $i$，多数投票恢复出正确 $x_i$ 的概率至少为 $1-\frac{1}{2n}$。那么，对所有 $i=1,\dots,n$ 使用并集界，至少有概率 $1-\frac{n}{2n}=\frac{1}{2}$ 所有位都恢复正确。
因此，在基础猜测全部正确的条件下，算法 $A$ 输出 $z=x$ 的概率至少为 $\frac{1}{2}$
固定输入成功率
算法 $A$ 中，$\sigma_1,\dots,\sigma_\ell$ 是独立均匀猜测的比特，对于固定的 $x$ 和固定的 $s_1,\dots,s_\ell$，每个 $\sigma_j$ 猜中 $b(x,s_j)$ 的概率是 $\frac{1}{2}$。因此，所有基础猜测全部正确的概率为 $2^{-\ell}$
由于：
所以 $2^{-\ell}$ 是一个多项式倒数，可以写为：
因此，当 $x\in S_n$ 时，算法 $A$ 在输入 $f(x)$ 上恢复出 $x$ 的概率至少为：
整体反演成功概率
上述只分析了 $x\in S_n$ 的情况，现在考虑随机输入 $X_n\leftarrow U_n$。由固定输入优势的断言可知：
又因为：
所以：
因此，对随机输入 $U_n$，算法 $A$ 反演 $f(U_n)$ 的成功概率至少为：
即：
这仍然是一个多项式倒数，因此是非可忽略的。
矛盾推出
由于 $m=2^\ell-1$，而：
算法 $A$ 需要调用 $G$ 的次数大约是：
并且其他计算也都是多项式时间内完成的。
因此，$A$ 是一个概率多项式时间反演算法，并且它以非可忽略概率反演 $f$。
这与 $f$ 是强单向函数的假设矛盾，所以反证假设不成立，即不存在高效算法 $G$ 能够以非可忽略优势预测：
因此，$b$ 是 $g(x,r)=(f(x),r)$ 的硬核谓词。
【归约效率的改进】
前面的证明已经说明，如果存在算法 $G$ 能以非可忽略优势预测内积谓词
那么就可以构造反演算法，从 $f(x)$ 中恢复 $x$，从而与 $f$ 的强单向性矛盾。
那么，上述的这个反演归约能不能做得更高效？也就是说，在给定预测算法 $G$ 的运行时间和预测优势时，能否构造出运行时间更短、成功概率更好的反演算法？
定理证明的量化结论
基本反演归约的效率界
设 $G$ 是一个概率算法，用来预测硬核谓词：
其运行时间为 $t_G(n)$，预测优势为 $\varepsilon(n)$，也就是说，算法 $G$ 的预测成功概率为：
前面的证明实际上给出了如下结论。
Proposition：如果存在上述的预测算法 $G$，则存在一个反演算法 $A$，其运行时间为：
并且满足：
这说明，只要预测算法 $G$ 有非可忽略优势 $\varepsilon(n)$，就可以构造一个概率多项式时间反演算法 $A$，以非可忽略概率反演 $f$。
成功概率分析
这里的成功概率可以理解为两个因素的乘积：
- 固定输入优势断言说明，至少有 $\frac{\varepsilon(n)}{2}$ 比例的输入 $x$ 属于集合 $S_n$，对于这些输入，算法 $G$ 在固定 $x$ 后仍然具有足够的预测优势
- 对于每个 $x\in S_n$，算法 $A$ 需要随机猜测基础内积值 $\sigma_1,\cdots,\sigma_l$，这些基础猜测全部正确的概率大约为 $\frac{\varepsilon(n)^2}{4n}$
在基础猜测正确后，前面的多数投票分析可以恢复 $x$。因此整体反演成功概率至少为：
运行时间分析
在反演算法 $A$ 中，需要构造大约 $m=O\left(\frac{n}{\varepsilon(n)^2}\right)$ 个查询向量 $r_J$，对于每一位 $i=1,\dots,n$，都要在这些查询向量上调用预测算法 $G$。因此，调用 $G$ 的总次数大约为：
而每次调用 $G$ 的时间是 $t_G(n)$，所以反演算法 $A$ 的运行时间为：
朴素枚举算法
前面还提到过随机猜测算法 $A$ 的另一种替代实现朴素枚举算法 $A’$。
$A$ 是随机猜测 $\sigma_1,\dots,\sigma_\ell$，因此它需要承担基础猜测全部正确的概率损失，而 $A’$ 不随机猜测这些基础值，而是枚举所有可能的 $\sigma_1,\dots,\sigma_\ell\in\{0,1\}$，然后对每一种可能的基础猜测都运行恢复过程，得到一个候选字符串 $z$。最后，算法 $A’$ 输出满足 $f(z)=y$ 的候选字符串。
这样做的好处是：正确的基础猜测一定会被枚举到，因此不再需要乘上随机猜测全部正确的概率 $2^{-\ell}$。
由于 $A’$ 枚举了所有可能的基础猜测，所以只要输入 $x\in S_n$，正确的基础猜测一定在枚举范围内。此时，前面的多数投票分析仍然说明，算法至少以 $\frac{1}{2}$ 的概率恢复出整个 $x$。
此外，随机输入 $U_n$ 落入集合 $S_n$ 的概率至少为：
因此，有：
但是，代价是运行时间变大。因为需要枚举大约 $2^\ell$ 组基础猜测，而每一组都要重新执行恢复过程。因此 $A’$ 的运行时间为：
也就是说，$A’$ 的成功概率更好，但运行时间更差。
高效归约
高效反演归约的效率界
对于两个反演算法 $A$ 和 $A’$，算法 $A$ 随机猜测基础值 $\sigma_1,\dots,\sigma_\ell$，运行较快，但成功概率较低；算法 $A’$ 枚举所有可能的基础值，成功概率较高，但运行时间较大。
接下来给出一个更高效的实现 $A’’$，它的目标是同时改善运行时间和成功概率之间的平衡。
Proposition：设 $G$ 的运行时间为 $t_G(n)$，预测优势为 $\varepsilon(n)$，定义
则存在算法 $A’’$，其期望运行时间为：
并且满足：
因此，算法 $A’’$ 的运行时间与成功概率的比值大约为：
这比前面的算法更高效，并且在某种意义上已经接近最优，只差一个多项式因子。
证明思路
上述命题的证明分为三步：
- 更精细的固定输入分析：前面的固定输入优势断言只是粗略地说明，存在一批输入 $x$，其固定输入优势至少为 $\frac{\varepsilon(n)}{2}$，这里需要更精细的分层分析
- 给出朴素枚举算法 $A’$ 更高效的实现方式：原来的朴素枚举算法 $A’$ 要枚举所有基础猜测并重复恢复，运行时间较高，通过构造矩阵枚举算法 $A’$，利用矩阵运算同时处理所有枚举情况
- 构造最终的随机分层算法 $A’’$：由于不知道输入属于哪一层优势集合，$A’’$ 随机选择一个层级参数，再调用矩阵枚举算法 $A’$
更精细的固定输入分析
固定优势
记 $L\stackrel{\mathrm{def}}{=}\log_2\frac{1}{\varepsilon(n)}$，对于固定输入成功率 $s(x)=P[G(f(x),R_n)=b(x,R_n)]$，由于 $\mathbb{E}_{X_n}[s(X_n)] = \frac{1}{2}+\varepsilon(n)$，等价地，有：
其中，$s(x)-\frac{1}{2}$ 就是固定输入 $x$ 上的预测优势。
分层断言
由此，可以得到如下断言：
Claim：存在某个 $i\in\{1,\dots,L\}$，以及集合 $S_n\subseteq\{0,1\}^n$，使得：
并且对每个 $x\in S_n$，都有：
这个断言说明，虽然不知道固定输入优势集中在哪些输入上，但总可以找到某一层 $i$，使得这一层同时满足两个条件：
- 这一层的输入数量至少占 $2^{i-1}\varepsilon(n)$ 的比例
- 这一层中每个输入的固定预测优势至少为 $\frac{2^{-i-1}}{L}$
这里比前面的固定输入优势断言更精细，因为它不是只找一个统一阈值，而是把不同优势水平的输入分层处理。
证明
定义 $A_i$ 是固定输入优势至少达到第 $i$ 层阈值的输入集合：
为了估计每一层对平均优势的贡献，对任意非空集合 $S\subseteq\{0,1\}^n$，定义：
其中，$a(S)$ 是集合 $S$ 中固定输入优势的最大值，$a(\varnothing)=0$
反设断言不成立，即对所有 $i=1,\dots,L$，都有：
写为概率形式，有：
把整个输入空间分成若干层：
于是平均固定优势可以按层估计为：
分别估计这些层对平均优势 $\mathbb{E}\left[s(X_n)-\frac12\right]$ 的贡献：
在 $A_1$ 上，由于 $s(x)\leq 1$，因此有 $a(A_1)\leq \frac{1}{2}$，即固定输入优势最多为 $\frac12$；又由反设 $P[X_n\in A_1]<\varepsilon(n)$，因此第一部分的贡献小于 $\frac{1}{2}\cdot \varepsilon(n)=\frac{\varepsilon(n)}{2}$
如果 $x\in A_i\setminus A_{i-1}$，那么 $x\notin A_{i-1}$，所以 $s(x) < \frac12+\frac{2^{-i}}{L}$，因此 $a(A_i\setminus A_{i-1}) \le \frac{2^{-i}}{L}$；又由于 $P[X_n\in A_i\setminus A_{i-1}] \le P[X_n\in A_i] < 2^{i-1}\varepsilon(n)$，所以第 $i$ 层贡献小于 $2^{i-1}\varepsilon(n)\cdot \frac{2^{-i}}{L} = \frac{\varepsilon(n)}{2L}$
在补集 $\{0,1\}^n\setminus A_L$ 上，由于 $x\notin A_L$，所以 $s(x) < \frac{1}{2}+\frac{2^{-L-1}}{L}$，因此 $a(\{0,1\}^n\setminus A_L) \le \frac{2^{-L-1}}{L}$；又因为 $L=\log_2\frac{1}{\varepsilon(n)}$，所以 $2^{-L}=\varepsilon(n)$，故补集部分贡献至多为 $\frac{2^{-L-1}}{L} = \frac{\varepsilon(n)}{2L}$
因此总期望优势满足：
这与 $\mathbb{E}\left[s(X_n)-\frac12\right] = \varepsilon(n)$ 矛盾，因此反设不成立，必然存在某个 $i\in\{1,\dots,L\}$，使得：
令 $S_n=A_i$，则对每个 $x\in S_n$，都有：
同时：
断言得证。
矩阵枚举算法 $A’$
固定优势层
由前面的分层断言可知，存在某个 $i\in\{1,\dots,L\}$，以及集合 $S_n\subseteq\{0,1\}^n$，使得：
并且对每个 $x\in S_n$，都有：
固定这样一个 $i$，并记 $\eta\stackrel{\mathrm{def}}{=}\frac{2^{-i-1}}{L}$，于是对应的集合可以写为：
也就是说，对于每个 $x\in S_n$，算法 $G$ 在固定输入 $x$ 上预测内积比特的优势至少为 $\eta$。
根据前面的朴素枚举算法 $A’$，适当设置参数后，对于每个 $x\in S_n$，算法 $A’$ 可以以至少 $\frac12$ 的概率从 $f(x)$ 中恢复出 $x$，但其运行时间为：
接下来的目标是给出一个更高效的实现，使运行时间降低为：
符号化表示
为了便于后续计算，将布尔值 $0,1$ 改写成 $\pm1$ 形式。定义：
也就是说：
- 若 $b(x,r)=0$，则 $b’(x,r)=1$
- 若 $b(x,r)=1$，则 $b’(x,r)=-1$
这样一来，原来两个比特是否相等的问题，可以转化为两个 $\pm1$ 数相乘是否为 $1$。
如果 $G$ 预测正确，则有：
如果 $G$ 预测错误，则有：
因此乘积 $b’(x,r)\cdot G’(y,r)$ 的期望反映了算法 $G$ 的预测优势。
进一步，定义：
其中 $s(x)-\frac12$ 是固定输入 $x$ 上的预测优势。因此，如果 $x\in S_n$，则：
从而：
三个事实
事实 1
对于每个 $x$，有：
其中，$U_n$ 是 $\{0,1\}^n$ 上的均匀随机向量。
上式的含义是：虽然 $G$ 预测的是 $b(x,U_n\oplus e_i)$，但乘上 $b’(x,U_n)$ 后，期望方向会偏向 $(-1)^{x_i}$。
因此，只要对很多随机向量求和，就可以通过总和的符号判断 $x_i$。
事实 2
令 $R$ 是一个随机选择的 $q\times n$ 布尔矩阵。对于任意不同的非零向量：
都有 $uR$ 和 $vR$ 在 $\{0,1\}^n$ 上均匀分布且两两独立。
这其实是前面两两独立性的随机向量构造的矩阵形式，前面用 $r_J=\bigoplus_{j\in J}s_j$ 生成两两独立向量，这里则是将基础向量 $s_j$ 放成矩阵 $R$ 的各行，而 $vR$ 就对应某个子集异或。
事实 3
对于任意 $x\in\{0,1\}^n, v\in\{0,1\}^q$，都有：
这是因为：
这其实只是把内积关系写成矩阵形式。
符号恢复断言
断言
取：
令 $R$ 是随机选择的 $q\times n$ 布尔矩阵，则有：
Claim：对任意 $x\in S_n$，对于随机选择的矩阵 $R$，以至少 $\frac12$ 的概率，存在某个 $\sigma\in\{0,1\}^q$，使得对每个 $1\le i\le n$，都有：
其中，$\mathrm{sign}(\cdot)$ 是符号函数。
由于：
所以如果求和结果为正，就判断 $x_i=0$，如果求和结果为负，就判断 $x_i=1$。
也就是说，存在某个 $\sigma$，使得对所有位置 $i$，都可以通过这个求和式的符号恢复 $x_i$。
证明
为了证明存在这样的 (\sigma)，取：
这里的 (\sigma) 是证明中使用的存在性对象，实际算法并不知道 (x)，因此不知道这个 (\sigma)，但后续算法会枚举所有 (\sigma\in\{0,1\}^q)，所以这个正确的 (\sigma) 一定包含在枚举范围内。
由事实 3 可知：
因此，对固定的 $i$，求和式变为：
根据事实 1，对于每个非零 $v$，都有：
由于 $x\in S_n$，有：
所以每一项的期望都朝着 $(-1)^{x_i}$ 的方向偏移。
根据事实 2，不同非零 $v$ 对应的 $vR$ 两两独立，因此这些求和项具有足够的独立性，可以使用 Chebyshev 不等式控制偏差。
当 $q=\left\lceil \log_2\left(\frac{2n}{\eta^2}+1\right) \right\rceil$ 时，非零 $v$ 的数量 $2^q-1$ 足够大，可以保证对每个固定的 $i$，求和式符号错误的概率至多为 $\frac{1}{2n}$，再对所有 $i=1,\dots,n$ 使用并集界，就得到所有位置同时正确的概率至少为：
因此断言成立。
矩阵记号
为了高效同时处理所有 $\sigma$，引入矩阵形式。
定义一个 $2^q\times 2^q$ 的矩阵 $B$，其中行由 $\sigma\in\{0,1\}^q$ 标记，列由 $v\in\{0,1\}^q$ 标记，则矩阵元素为：
对每个 $i$，定义一个 $2^q$ 维向量 $\bar g_i$，其第 $v$ 个分量为：
于是矩阵乘法 $B\bar g_i$ 的第 $\sigma$ 个分量正好是：
这正是上述断言中用于判断第 $i$ 位的求和式。
这里的矩阵 $B$ 本质上就是 Hadamard 矩阵，其乘法可以用快速 Walsh-Hadamard 变换实现，即矩阵乘法 $B\bar g_i$ 可以一次性计算出所有 $\sigma$ 对第 $i$ 位的恢复判断。
算法流程
给定输入 $y=f(x)$ 以及参数 $\eta$，设置 $q=\left\lceil\log_2\left(\frac{2n}{\eta^2}+1\right)\right\rceil$，然后执行如下步骤：
Step1：计算预测向量：对每个 $i=1,\dots,n$，计算向量：
Step2：矩阵变换：对每个 $i=1,\dots,n$，计算：
将所有 $\bar z_i$ 作为列组成一个矩阵 $Z$，矩阵 $Z$ 的维度为 $2^q\times n$。
Step3：由符号得到候选原像：令 $Z’$ 是一个 $2^q\times n$ 的布尔矩阵，表示 $Z$ 中每个元素的符号。具体来说，对行 $\sigma$、列 $i$，若：
则令 $Z_{\sigma,i}’=1$，否则令 $Z_{\sigma,i}’=0$
此时，$Z’$ 的每一行对应某个 $\sigma$ 得到的候选字符串 $z$。
Step4：验证候选原像：扫描 $Z’$ 的所有行，每一行都是一个候选字符串 $z\in\{0,1\}^n$，算法输出第一个满足：
的候选字符串 $z$。
由前面的断言可知，对于 $x\in S_n$，该算法以至少 $\frac12$ 的概率成功恢复 $x$。
运行时间分析
计算所有 $\bar g_i$ 需要调用 $G$ 共 $n\cdot 2^q$ 次，由于 $2^q=O\left(\frac{n}{\eta^2}\right)$，所以这部分的时间复杂度为：
矩阵变换部分可以用 Walsh-Hadamard 变换实现，其时间复杂度为：
因此总运行时间为：
这比朴素枚举算法 $A’$ 的 $O\left(\frac{n^3}{\eta^4}\right)\cdot t_G(n)$ 要高效得多。
随机分层算法 $A’’$
算法流程
前面的矩阵枚举算法 $A’$ 需要输入一个参数 $\eta$。如果知道分层断言中对应的正确层 $i$，就可以令：
并在集合 $S_n$ 上以至少 $\frac12$ 的概率反演成功。
但是，实际算法并不知道哪一个 $i$ 满足分层断言。因此，需要构造一个新的算法 $A’’$，通过随机选择层级来避免提前知道 $i$。
令 $L=\log_2\frac{1}{\varepsilon(n)}$，算法 $A’’$ 在输入 $y=f(x)$ 时，执行如下操作：
- 从集合 $\{1,\dots,L\}$ 中随机选择一个 $j$，其中选择 $j$ 的概率为 $2^{-2j+1}$。这些概率之和小于 $1$，因此剩余概率对应算法直接停止并不输出。
- 如果选中了某个 $j$，则令：$\eta_j \stackrel{\mathrm{def}}{=}\frac{2^{-j-1}}{L}$
- 调用前面构造的矩阵枚举算法 $A’$，输入为 $y$，参数为 $\eta_j$
- 算法 $A’’$ 输出 $A’$ 的输出结果
期望运行时间证明
当 $A’’$ 选择层级 $j$ 时，调用矩阵枚举算法 $A’$，其运行时间为：
由于 $\eta_j=\frac{2^{-j-1}}{L}$，所以：
因此，当选择 $j$ 时，对应运行时间为：
而选择 $j$ 的概率是 $2^{-2j+1}$，所以期望运行时间为：
其中，$2^{-2j+1}$ 和 $2^{2j}$ 相乘后只剩常数因子，因此上式为：
因为一共有 $L$ 项，并且在通常假设 $t_G(n)\ge \log n$ 下，对数项可以被 $t_G(n)$ 吸收，所以有：
这就是高效反演归约的效率界命题中的运行时间。
成功概率证明
设 $i\le L$ 是满足分层断言的那个下标，并令 $S_n$ 是对应的输入集合。由分层断言可知：
对于 $x\in S_n$，固定输入优势至少为 $\eta_i=\frac{2^{-i-1}}{L}$，如果算法 $A’’$ 随机选择的 $j\ge i$，则：
也就是说，$A’$ 使用的参数 $\eta_j$ 不超过真实优势下界，因此矩阵枚举算法 $A’$ 的正确性分析仍然适用。由前面的符号恢复断言可知，在这种情况下，对于每个 $x\in S_n$，算法 $A’$ 至少以概率 $\frac12$ 成功从 $f(x)$ 中恢复 $x$，因此：
由 $A’’$ 的选择规则：
该和式至少包含第一项，所以：
于是：
又因为：
所以：
因此：
即：
由此，高效反演归约的效率界命题得证。
