科普文章 - 对 Goldreich-Levin 定理的证明和讨论

对 Goldreich-Levin 定理的证明和讨论

我们今天要介绍的 Goldreich-Levin 定理是布尔函数分析中的一个重要结论。它在密码学中有直接的应用，同时它又与 Learning Theory 有深刻的联系。

从 One-Way Function 到 Pseudorandom Generator

这里简单回顾一下 OWF 和 PRG 的定义。

• 定义 1（One-Way Function, OWF）：函数 $f:\{0,1\}^n\to\{0,1\}^m$ 被称为一个单向函数，如果：

  • 存在确定性多项式算法 $A$ 计算 $f$；
  • 对任意 p.p.t. $B$，存在 negligible 函数 $\varepsilon(\cdot)$ 使得
  $$\Pr_{x\leftarrow \{0,1\}^n}[x'\leftarrow B(1^n,f(x)):f(x')=f(x)]\leq\varepsilon(n).$$

• 定义 2（Pseudorandom Generator, PRG）：函数 $G:\{0,1\}^n\to\{0,1\}^m$ 被称为一个伪随机数生成器，如果：

  • $m>n$；
  • 存在确定性多项式算法 $A$ 计算 $G$；
  • $G(\mathcal U(\{0,1\}^n))\approx_c\mathcal U(\{0,1\}^m)$，其中 $\mathcal U$ 表示均匀分布，$\approx_c$ 表示 computational indistinguishability，即不存在 p.p.t. 以 non-negligible 概率区分 $G$ 的输出和均匀的随机数。

注意，由于 p.p.t. 和 negligible 函数都只有渐进意义，上述定义只讨论有限的 $n$ 时是无意义的。事实上无论 OWF 还是 PRG 都应该是一族函数 $\{F_n\}_{n\in\mathbb Z}$ 和 $\{G_n\}_{n\in\mathbb Z}$，但我们这里可以只关注某个特定的 $n$，所以滥用了符号。

• 定义 3（One-Way Permutation, OWP）：函数 $f:\{0,1\}^n\to\{0,1\}^n$ 被称为一个单向置换，如果 $f$ 是单向函数，且是双射。

这篇文章的目标之一就是证明如下命题：

• 定理 4：若 OWP 存在，则 PRG 存在。

事实上，定理 4 的更强版本——即 OWF 存在推出 PRG 存在——也是成立的，但其证明涉及更多技术细节，不在本文中提及。

简单起见，我们接下来只使用 $\{0,1\}^n\to\{0,1\}^n$ 的 OWP 构造 $\{0,1\}^{2n}\to\{0,1\}^{2n+1}$ 的 PRG，容易使用这种形式的 PRG 构造更一般的 PRG。接下来我们直接给出构造：

• 构造 5：令 $f:\{0,1\}^n\to\{0,1\}^n$ 是一个 OWP，定义 $G:\{0,1\}^{2n}\to\{0,1\}^{2n+1}$ 如下：

  $$G(x\circ r)=f(x)\circ r\circ \langle x,r\rangle,$$

  其中 $x,r\in\{0,1\}^n$，$\circ$ 表示拼接，$\langle x,r\rangle=\left(\sum_{i=0}^{n-1}x_ir_i\right)\bmod 2$ 为 $x,r$ 在 $\mathbb F_2^n$ 中的内积。

容易发现 $G(x\circ r)$ 的前 $2n$ 位是均匀随机的，因此证明上述构造的关键步骤就在于证明 $G(x\circ r)$ 的最后一位（即 $\langle x,r\rangle$）是不能被前 $2n$ 位预测的。

Goldreich-Levin 定理：描述一 [1] [2]

我们现在希望证明，若 $f$ 是 One-Way 的，则不存在一个多项式算法能够以 non-negligible 概率给定 $f(x),r$ 预测 $\langle x,r\rangle$。用逆否命题来描述，我们就是要证明下列定理：

• 定理 6（Goldreich-Levin）：设 Oracle $A(f(x),r)$ 满足

  $$\Pr_{x,r\in\{0,1\}^n}[A(f(x),r)=\langle x,r\rangle]\ge \frac{1}{2}+\frac{1}{q(n)},$$

  其中 $q(\cdot)$ 是多项式，则存在使用该 Oracle 的 p.p.t. $B^A(y)$ 使得

  $$\Pr_{x\in\{0,1\}^n}[y\leftarrow f(x),x'\leftarrow B^A(y):f(x')=y]\ge \frac{1}{q'(n)},$$

  其中 $q’(n)$ 是一个多项式。

Remark：我们将会看到，$B$ 对 $f(x)$ 唯一的使用方式是作为 Oracle $A$ 的输入，所以这里 $f$ 的结构是不重要的，本质上这是一个基于 $A(r)$ 求解 $x$ 的学习问题。

接下来我们着手证明定理 6。省流可以直接跳过中间冗长（且可能不一定 readable）的 Sketch 看证明。

想法 1（Sketch）

既然 $A$ 的输出是一个 bit，有一个简单的想法是能否还原 $x$ 的每一位。

考虑直接令 $r=e_i$（只有第 $i$ 位为 $1$ 的二进制数），这时调用 $A(f(x),r)$ 就有概率能得到 $x$ 的第 $i$ 位。

然而，这个朴素的想法有着严重的问题：对于特定的 $x,r$，$\Pr[A(f(x),r)=\langle x,r\rangle]$ 的概率可能不是 $\frac{1}{2}+\frac{1}{q(n)}$——我们甚至不知道这个概率是否大于 $\frac{1}{2}$，所以是完全无法准确预测的。

想法 2（Sketch）

先解决 $x$ 的随机性，称 $x$ 是好的当且仅当

$$\Pr_{r\in\{0,1\}^n}[A(f(x),r)=\langle x,r\rangle]\ge\frac{1}{2}+\frac{1}{2q(n)},$$

由 Markov 不等式可以证明至少有 $\frac{1}{2q(n)}$ 比例的 $x$ 是好的。我们只需要对这些 $x$ 有 non-negligible 的概率成功即可。

再解决 $r$ 的随机性，我们可以通过引入混淆来利用 $A$ 的平均成功率：假设我们现在需要还原 $x$ 的第 $i$ 位，随机取 $r\in\{0,1\}^n$ 然后计算 $S=A(f(x),r)+A(f(x),r+e_i)$ 来近似 $\langle x,e_i\rangle$，这个估计的来源是内积的线性性 $\langle x,e_i\rangle=\langle x,r\rangle+\langle x,r+e_i\rangle$。

现在分析算对 $\langle x,e_i\rangle$ 的概率：$A(f(x),r)$ 和 $A(f(x),r+e_i)$ 各有 $\frac{1}{2}-\frac{1}{2q(n)}$ 的概率失败，因此用 union bound 得到总失败率至多为 $1-\frac{1}{q(n)}$，这个值只要大于 $\frac{1}{2}$ 就是没有用的。

所以根据我们现有的技术，想法 2 只能解决 $A$ 的平均成功率为 $\frac{3}{4}+\frac{1}{q(n)}$ 的情况——因为这时根据 union bound 得到的总失败率是 $\frac{1}{2}-\frac{1}{q(n)}$。

想法 3（Sketch）

想法 2 的主要问题在于给定 $e_i$ 后 $r$ 和 $r+e_i$ 并非独立，所以我们只能用 union bound 控制算法的成功率，而 union bound 是很不精细的。但是，假设我们能以某种方式猜出 $\langle x,r\rangle$ 的准确值，这样就只需要向 Oracle 询问 $A(f(x),r+e_i)$ 了，成功率就是 $\frac{1}{2}+\frac{1}{2q(n)}$ 了。

问题在于我们需要得出每一个 $\langle x,e_i\rangle$，所以对于某个 $e_i$ 至少要超过 $1-\frac{1}{n}$ 的正确率（这样在利用 union bound 分析算法正确率时才能得到一个大于 $0$ 的数）。所以我们要考虑如何把单个 $e_i$ 的成功率从 $\frac{1}{2}+\frac{1}{2q(n)}$ boost 成 $1-\frac{1}{q^(n)}$，其中 $q^(n)$ 是任意给定的多项式。

一个想法是取 $M$ 个独立的随机数 $r_1,\ldots,r_M$，并假设我们知道 $b_i=\langle x,r_i\rangle$。这样，我们向 Oracle 询问所有 $b_i’\leftarrow A(f(x),r_i+e_i)$，然后取 $\{b_i-b_i’\}_{i=1}^M$ 的众数就可以利用概率论工具将成功率提高到 $1-\frac{1}{q^*(n)}$。

但是问题来了，为了达到希望的成功率，需要有 $M=\text{poly}(n)$，但是这样一来我们无法接受用 $O(2^M)$ 的复杂度猜测 $b_1,\ldots,b_M$。解决这个问题的关键在于我们事实上不需要 $r_1,\ldots,r_M$ 之间完全独立，只需要它们两两独立即可（稍后证明中会看到这一点），这是一个更弱的条件，允许我们构造更结构化的 $r_1,\ldots,r_M$，具体地：令 $m=\log_2 M$，随机取 $r_1,\ldots,r_m$，并猜测 $b_i=\langle x,r_i\rangle$。对于每个 $I\subseteq[m]$，令 $r_I=\sum_{i\in I}r_i, b_I=\sum_{i\in I}b_i$，这样的一组 $\{r_I\}_{I\subseteq [m]}$ 就满足两两独立的性质，且我们可以 $O(2^m)=O(M)$ 地猜出所有 $\{b_I\}_{I\subseteq [m]}$，大功告成。下面我们来书写完整证明。

定理 6 证明

构造算法 $B^A(y)$ 如下，其中 $m=O(\log n)$ 是待定的参数，$M=2^m$：

• 独立随机采样 $r_1,\ldots,r_m\leftarrow \{0,1\}^n$。

• 枚举 $b_1,\ldots,b_m\in\{0,1\}$，对于每一组 $\{b_1,\ldots,b_m\}$：

  • 枚举 $k\leftarrow \{1,\ldots,n\}$：

    • 令 $S_k=0$。

    • 枚举 $\varnothing\subsetneq I\subseteq [m]$，计算 $s_{k,I}=A(f(x),\sum_{i\in I}r_i+e_k)+\sum_{i\in I}b_i$；若 $s_{k,I}=1$ 则 $S_k\leftarrow S_k+1$；若 $s_{k,I}=0$ 则 $S_k\leftarrow S_k-1$。

    • 若 $S_k>0$ 则令 $x_k=1$；否则令 $x_k=0$。

  • 令 $x=x_1\ldots x_n$，若 $f(x)=y$ 则输出 $x$ 并停机。

• 输出 $\perp$。

接下来我们要证明，通过选取合适的 $m$，可以使得 $B^A$ 的运行时间为 $\text{poly}(n)$，且

$$\Pr_{x\in\{0,1\}^n}[B^A(f(x))=x]\ge \frac{1}{q'(n)},$$

其中 $q’(n)$ 是一个多项式。

• 引理7：令 $P(x)=\Pr_{r\in\{0,1\}^n}[A(f(x),r)=\langle x,r\rangle], T=\left\{x\mid P(x)\ge\frac{1}{2}+\frac{1}{2q(n)}\right\}$，则 $|T|\ge \frac{1}{2q(n)}\cdot 2^n$。

  证明：我们有 $P(x)\leq 1$，同时

  $$\frac{1}{2}+\frac{1}{q(n)}\leq \mathbb E_{x\in\{0,1\}^n}P(x)\leq \left(1-\frac{|T|}{2^n}\right)\left(\frac{1}{2}+\frac{1}{2q(n)}\right)+\frac{|T|}{2^n}\cdot 1,$$

  因此 $|T|\ge \frac{1}{2q(n)}\cdot 2^n$。

称 $T$ 中的 $x$ 为好的。这告诉我们有 non-negligible fraction 的 $x$ 是好的。

由于 $b_1,\ldots,b_m$ 取遍了所有可能，所以存在一次循环中 $b_i=\langle x,r_i\rangle$，我们只考虑这次循环，因此下面始终假设 $b_i=\langle x,r_i\rangle$ 成立。记 $r_I=\sum_{i\in I}r_i\in\{0,1\}^n, b_I=\sum_{i\in I}b_i\in \{0,1\}$。对任意 $I\subseteq [n]$，根据内积的线性性，我们有 $b_I=\langle x,r_I\rangle$。

• 引理 8：对于任意 $\varnothing\subsetneq I\subseteq [n]$，$r_I$ 服从 $\{0,1\}^n$ 的均匀分布；对于任意 $\varnothing\subsetneq I,J\subseteq [n]$，若 $I\ne J$，则 $r_I$ 和 $r_J$ 独立。

  证明：对于任意 $\varnothing\subsetneq I\subseteq [n]$，任取 $i\in I$，固定所有 $r_j (j\neq i)$ 后 $r_i$ 和 $r_I$ 形成双射，由于 $r_i$ 服从 $\{0,1\}^n$ 的均匀分布，$r_I$ 也服从 $\{0,1\}^n$ 的均匀分布。

  对于任意 $\varnothing\subsetneq I,J\subseteq [n], I\ne J$，不妨设 $I\not\subseteq J$。任取下标 $i$ 使得 $i\in I, i\notin J$，固定所有 $r_j (j\neq i)$ 后 $r_J$ 为定值，而 conditioned on 这个条件，由于 $r_i$ 和 $r_I$ 形成双射，$r_I$ 依然服从 $\{0,1\}^n$ 的均匀分布。因此 $r_I,r_J$ 独立。

由于 $r_I$ 均匀分布，所以对于好的 $x$ 有 $\Pr[A(f(x),r_I+e_k)=\langle x,r_I+e_k\rangle]\ge\frac{1}{2}+\frac{1}{2q(n)}$，因此

$$\Pr[s_{k,I}=\langle x,e_k\rangle]\ge\frac{1}{2}+\frac{1}{2q(n)}.$$

为了让叙述更加方便，定义 $s’_{k,I}=\begin{cases}-1 & (s_{k,I}\ne \langle x,e_k\rangle)\ 1 & (s_{k,I}=\langle x,e_k\rangle)\end{cases}$，则

$$\mathbb E[s'_{k,I}]\ge\frac{1}{q(n)}.$$

注意到 $S_k=(-1)^{\langle x,e_k\rangle +1}\sum_{\varnothing\subsetneq I\subseteq [n]}s’_{k,I}$，所以只要 $\sum_{\varnothing\subsetneq I\subseteq [n]}s’_{k,I}>0$，上述算法就会成功。由于 $r_I \{I\subseteq [n]\}$ 两两独立，所以 $s_{k,I} \{I\subseteq [n]\}$ 也两两独立。我们可以计算 $S_k$ 的方差，然后用 Chebyshev 不等式估计算法的成功率。

• 引理 9：$\mathbb E\left[\sum_{\varnothing\subsetneq I\subseteq [M]}s’_{k,I}\right]\ge\frac{M}{2q(n)}$，$\text{Var}\left[\sum_{\varnothing\subsetneq I\subseteq [M]}s’_{k,I}\right]\leq M$。

  证明：先看期望，我们知道 $\mathbb E[s’_{k,I}]\ge\frac{1}{q(n)}$，因此

  $$\mathbb E\left[\sum_{\varnothing\subsetneq I\subseteq [M]}s'_{k,I}\right]=\sum_{\varnothing\subsetneq I\subseteq [M]}\mathbb E[s'_{k,I}]=\frac{M-1}{q(n)}\ge\frac{M}{2q(n)}.$$

  再看方差。$\text{Var}[s’_{k,I}]=\mathbb E[{s’_{k,I}}^2]-(\mathbb E[s’_{k,I}])^2\leq 1$，由于 $s’_{k,I}$ 两两独立，我们有

  $$\text{Var}\left[\sum_{\varnothing\subsetneq I\subseteq [M]}s'_{k,I}\right]=\sum_{\varnothing\subsetneq I\subseteq [M]}\text{Var}[s'_{k,I}]\leq M-1<M.$$

• 引理 10：$\Pr\left[\sum_{\varnothing\subsetneq I\subseteq [M]}s’_{k,I}< 0\right]\leq \frac{2q(n)}{M}$。

  证明：据 Chebyshev 不等式，有

  $$\begin{aligned} \Pr\left[\sum_{\varnothing\subsetneq I\subseteq [M]}s'_{k,I}< 0\right]&\leq\Pr\left[\left|\sum_{\varnothing\subsetneq I\subseteq [M]}s'_{k,I}-\mathbb E\left[\sum_{\varnothing\subsetneq I\subseteq [M]}s'_{k,I}\right]\right|\ge\frac{M}{2q(n)}\right]\\ &\leq \frac{\text{Var}\left[\sum_{\varnothing\subsetneq I\subseteq [M]}s'_{k,I}\right]}{(M/2q(n))^2}\\ &\leq \frac{2q(n)}{M}. \end{aligned}$$

因此，还原任意一个 $s_k$ 失败的概率至多是 $\frac{2q(n)}{M}$。利用 union bound 可知，存在一个 $s_k$ 失败的概率至多为 $\frac{2nq(n)}{M}$。

这意味着对于任意好的 $x$，$B^A(f(x))=x$ 的概率至少为 $1-\frac{2nq(n)}{M}$，令 $M=4nq(n)$ 即 $m=\log_2(4nq(n))$，则这个概率至少为 $\frac{1}{2}$，因此我们得到了

$$\Pr_{x\in\{0,1\}^n}[B^A(f(x))=x]\ge \frac{|T|}{2^n}\cdot\frac{1}{2}\ge\frac{1}{4q(n)}.$$

Goldreich-Levin 定理：描述二 [3]

上面的证明显得非常 adhoc，下面我们要介绍一些关于布尔函数的内容，以及对定理 6 的另一个曲线救国的证明。

• 定义 11（Fourier Basis）：对于 $S\subseteq [n]$，定义 $\chi_S:\{-1,1\}^n\to \{-1,1\}$ 为 $\chi_S(x)=\prod_{i\in S}x_i$，即 $\chi_S(x)$ 表示 $x$ 在 $S$ 这个下标集合内有奇数还是偶数个 $-1$。

• 定义 12：对于 $f,g:\{-1,1\}^n\to\mathbb R$，定义 $\langle f,g\rangle=\mathbb E_{x\in\{0,1\}^n}[f(x)g(x)]$。定义 $\Vert f\Vert_2=\sqrt{\langle f,f\rangle}$。

容易验证上面的定义符合内积的各条性质。现在，布尔函数 $\{f:\{-1,1\}^n\to\mathbb R\}$ 形成了一个 $\mathbb R$ 上的内积空间。

• 引理 13：$\langle\chi_S,\chi_T\rangle=[S=T]$，即 $\{\chi_S(x)\}_{S\subseteq [n]}$ 是一组归一化正交基。

  证明：对于 $S=T$，$\forall x, \chi_S(x)\chi_S(x)=1$，所以 $\langle \chi_S,\chi_S\rangle=1$。

  对于 $S\neq T$，不妨设 $S\not\subseteq T$。任取下标 $i$ 使得 $i\in S, i\notin T$，固定所有 $x_j (j\neq i)$ 后 $\chi_T(x)$ 为定值，而 $\mathbb E_{x_i\in\{0,1\}}\chi_S(x)=0$，所以 $\langle\chi_S,\chi_T\rangle=0$。

  由于布尔函数空间的维数为 $2^n$，$\{\chi_S(x)\}_{S\subseteq [n]}$ 恰好组成了一组归一化正交基，称为傅里叶基。

• 定义 14（Fourier Coefficient）：任意布尔函数 $f:\{-1,1\}^n\to \mathbb R$ 可以写为傅里叶基的线性组合：

  $$f(x)=\sum_{S\subseteq[n]}\hat f(S)\chi_S(x),$$

  系数 $\hat f(S)=\langle f,\chi_S\rangle$ 称为 $f$ 的傅里叶系数。

• 推论 15（Parseval’s Identity）：$\Vert f(x)\Vert_2^2=\sum_{S\subseteq[n]}\hat f(S)^2$。

直观地说，$\hat f(S)$ 衡量了 $f$ 与 $\chi_S$ 的接近程度。让我们回顾定理 6，我们有一个 Oracle $A(f(x),r)$ 以 non-negligible 的概率正确输出 $\langle x,r\rangle$，因此 $A(f(x),\cdot)$ 应该是和 $\chi_x$ 很接近的（当然我们要先把 $A$ 转换成一个布尔函数，这将在之后的证明中说明），具体地，$\hat A(f(x),x)$ 是 non-negligible 的。所以定理 6 可以大致归结成：给定一个布尔函数的 Oracle，可以多项式时间求出它 non-negligible 的傅里叶系数。下面我们将介绍解决这一问题的工具。

• 定理 16（Goldreich-Levin）：给定 Oracle $f:\{-1,1\}^n\to [-1,1]$ 和参数 $\gamma,\delta$，存在时间为 $\text{poly}\left(n,1/\gamma,1/\delta\right)$ 的算法 $B^f$ 使得：

  • $B^f$ 输出一个集合 $L=\{S_1,\ldots,S_m\}$，其中 $S_i\subseteq[n]$。

  • 下列条件以至少 $1-\delta$ 概率满足：

    对于任意 $S$ 使得 $\hat f(S)\ge\gamma$，$S\in L$。

    对于任意 $S$ 使得 $\hat f(S)<\frac{\gamma}{2}$，$S\notin L$。

简而言之，$B^f$ 输出 $f$ 所有较大的傅里叶系数。

定理 16 证明

• 定义 17（”Hypercube”）：一个超立方体 $H(m,S) (0\leq m\leq n, S\subseteq[m])$ 是一个 $[n]$ 的子集族：

  $$H(m,S)=\{S\cup T\mid T\subseteq \{m+1,\ldots,n\}\}$$

  即对于 $1,\ldots,m$ 中的每个下标 $i$，我们都指定了它必须在（$i\in S$）或必须不在（$i\notin S$）某个子集中，这样的子集构成的集合。

定义子过程 $C^f(m,S)$ 满足：

• $C^f$ 的运行时间为 $\text{poly}(n,1/\gamma’,1/\delta’)$，其中 $\gamma’,\delta’$ 是待定的数。

• 以至少 $1-\delta’$ 的概率，$\left|C^f(m,S)-\sum_{R\in H(m,S)}\hat f(R)^2\right|<\gamma’$。

$C^f$ 用于估计一个超立方体内的傅里叶系数平方和。我们先介绍如何通过 $C^f$ 构造 $B^f$，再说明如何实现 $C^f$。

构造算法 $B^f$ 如下：

• 令 $HS$ 是一个超立方体的集合，初始时 $HS=\{H(0,\varnothing)\}$，即只有一个包含所有子集的超立方体。

• 不断循环下列步骤直到 $HS$ 中所有超立方体的大小为 $1$：

  • 任意取出一个大小不为 $1$ 的超立方体 $H(m,S)\leftarrow HS$，令 $HS\leftarrow HS\backslash\{H(m,S)\}$。

  • 若 $C^f(m+1,S)\ge\frac{\gamma^2}{2}$， 则令 $HS\leftarrow HS\cup\{H(m+1,S)\}$。

  • 若 $C^f(m+1,S\cup\{m+1\})\ge\frac{\gamma^2}{2}$， 则令 $HS\leftarrow HS\cup\{H(m+1,S\cup\{m+1\})\}$。

• 输出 $L=\bigcup_{H(m,S)\in HS} H(m,S)$，注意每个 $H(m,S)$ 其实都只包含一个元素。

下面我们来证明，只要所有对 $C^f$ 调用的误差都不超过 $\gamma’=\frac{\gamma^2}{4}$，则 $B^f$ 的输出是正确的，且时间复杂度是多项式的。

• 引理 18：若 $B^f$ 每次调用 $C^f$ 时都有 $\left|C^f(m,S)-\sum_{R\in H(m,S)}\hat f(R)^2\right|<\frac{\gamma^2}{4}$，则 $|HS|\leq\frac{4}{\gamma^2}$ 始终成立，$B^f$ 的循环次数不超过 $\frac{4n}{\gamma^2}$，调用 $C^f$ 的次数不超过 $\frac{8n}{\gamma^2}$，从而 $B^f$ 是多项式时间的。

  证明：第一次循环之后，$HS$ 中的每个超立方体 $H(m,S)$ 都满足

  $$\sum_{R\in H(m,S)}\hat f(R)^2\ge C^f(m,S)-\frac{\gamma^2}{4}\ge\frac{\gamma^2}{2}-\frac{\gamma^2}{4}=\frac{\gamma^2}{4},$$

  且不同超立方体是不交的。根据 Parseval’s identity 有

  $$1\ge \Vert f\Vert_2^2\ge\sum_{H(m,S)\in HS}\sum_{R\in H(m,S)}\hat f(R)^2\ge |HS|\frac{\gamma^2}{4},$$

  故 $|HS|\leq \frac{4}{\gamma^2}$。可以用完全相同的办法证明：对于每个 $m$，曾经出现在 $HS$ 中的形如 $H(m,S)$ 的超立方体数量也不超过 $\frac{4}{\gamma^2}$（因为它们也两两不交）。对不同的 $0\leq m<n$ 求和，我们就知道循环次数不超过 $\frac{4n}{\gamma^2}$。因为每次循环调用两次 $C^f$，所以调用 $C^f$ 的次数不超过 $\frac{8n}{\gamma^2}$。

• 引理 19：若 $B^f$ 每次调用 $C^f$ 时都有 $\left|C^f(m,S)-\sum_{R\in H(m,S)}\hat f(R)^2\right|<\frac{\gamma^2}{4}$，则 $B^f$ 的输出 $L$ 满足：

  对于任意 $S$ 使得 $\hat f(S)\ge\gamma$，$S\in L$。

  对于任意 $S$ 使得 $\hat f(S)<\frac{\gamma}{2}$，$S\notin L$。

  证明：引理 18 的证明中已经说明了 $HS$ 中的每个超立方体满足

  $$\sum_{R\in H(m,S)}\hat f(R)^2\ge\frac{\gamma^2}{4},$$

  因此若 $\hat f(S)<\frac{\gamma}{2}$ 即 $\hat f(S)^2<\frac{\gamma^2}{4}$，则 $S$ 不会出现在最终输出 $L$ 中。

  若 $\hat f(S)\ge\gamma$ 即 $\hat f(S)^2\ge \gamma^2>\frac{\gamma^2}{2}+\frac{\gamma^2}{4}$，所以包含 $S$ 的超立方体一定不会被从 $HS$ 中丢掉，即 $S$ 能保留到最终输出 $L$ 中。

由于我们会调用 $C^f$ 至多 $\frac{8n}{\gamma^2}$ 次，根据 union bound，它们都成功的概率至少是 $1-\frac{8n}{\gamma^2}\delta’$。令 $\delta’=\frac{\gamma^2\delta}{8n}$，就可以使得这个概率为 $1-\delta$，即 $B^f$ 的成功率为 $1-\delta$。我们剩下的工作只有把 $C^f$ 实现出来。

• 引理 20：

  $$\sum_{R\in H(m,S)}\hat f(R)^2=\mathbb E_{x,y\subseteq\{1,\ldots,m\},\ z\subseteq\{m+1,\ldots,n\}}[f(x\cup z)f(y\cup z)\chi_S(x)\chi_S(y)],$$

  注意这里混用了“长度为 $n$ 的 01 串”和“$[n]$ 的子集”（对应 $01$ 串中 $1$ 对应的下标集合）。

  证明：

  首先注意到

  $$\sum_{T\subseteq\{m+1,\ldots,n\}}\chi_T(x)\chi_T(y)=2^{n-m}[\forall i\in\{m+1,\ldots,n\},x_i=y_i].$$

  其证明和 $\{\chi_S\}_{S\subseteq[n]}$ 构成正交基的证明相同，不再赘述。

  利用这个关系，我们有

  $$\begin{aligned} \sum_{R\in H(m,S)}\hat f(R)^2&=\sum_{T\in\{m+1,\ldots,n\}}\hat f(S\cup T)^2\\ &=\sum_{T\in\{m+1,\ldots,n\}}\left(\mathbb E_{x\in\{0,1\}^n}[f(x)\chi_S(x)\chi_T(x)]\right)^2\\ &=\sum_{T\in\{m+1,\ldots,n\}}\mathbb E_{x,y\in\{0,1\}^n}[f(x)f(y)\chi_S(x)\chi_S(y)\chi_T(x)\chi_T(y)]\\ &=\mathbb E_{x,y\in\{0,1\}^n}\left[f(x)f(y)\chi_S(x)\chi_S(y)\sum_{T\in\{m+1,\ldots,n\}}\chi_T(x)\chi_T(y)\right]\\ &=\mathbb E_{x,y\subseteq \{1,\ldots,m\},\ z\subseteq\{m+1,\ldots,n\}}[f(x\cup z)f(y\cup z)\chi_S(x)\chi_S(y)]. \end{aligned}$$

因此 $C^f$ 直接采样 $x,y,z$ 估算上述期望即可，由于目标函数值域为 $[-1,1]$，用 Hoeffding 不等式知道：可以通过 $\text{poly}\left(\frac{1}{\gamma’}\log\frac{1}{\delta’}\right)$ 次采样实现 $C^f$ 的正确率要求。

定理 16 扩展

在继续之前，我们先对定理 16 进行一个小扩展。

在定理 16 的描述中，算法 $B^f$ 拥有 $f$ 的 Oracle。现在我们考虑一个更困难的情况：$B^{f’}$ 只拥有 $f$ 的一个 noisy Oracle $f’$，其中 $f’$ 接受两个输入 $x$ 和 $r$，$x$ 是 $f$ 的输入，$r$ 是其随机性，满足：

$$f'(x,r)\in[-1,1],\qquad \mathbb E_{r\in \{0,1\}^m}[f'(x,r)]=f(x),$$

$m$ 是 $n$ 的多项式。

在这个前提下，定理 16 的结论仍然成立——因为 $B$ 唯一用到 Oracle 的地方是调用 $C$，而 $C$ 调用 Oracle 是为了计算 $f(x\cup z)f(y\cup z)\chi_S(x)\chi_S(y)$ 关于 $x,y,z$ 的期望。现在我们只需对 $r$ 也取期望，即在采样时也采 $r$（注意，两次对 Oracle 的访问 $f(x\cup z)$ 和 $f(y\cup z)$ 需要采两个独立的 $r_1,r_2$），就可以保持期望正确，且目标函数值域为 $[-1,1]$ 的要求，用 Hoeffding 不等式可知采样复杂度不会增加。

下面我们利用定理 16 给出定理 6 的一个简单证明。

定理 6 证明

与上一个证明一样，我们仍然令 $P(x)=\Pr_{r\in\{0,1\}^n}[A(f(x),r)=\langle x,r\rangle]$，令 $T=\left\{x\mid P(x)\ge\frac{1}{2}+\frac{1}{2q(n)}\right\}$ 为好的 $x$ 的集合。我们知道 $|T|\ge \frac{1}{2q(n)}\cdot 2^n$，接下来我们只处理这些好的 $x$。

$A$ 可能是一个随机算法，我们用 $r’$ 表示 $A$ 的随机性。令 $g(f(x),r)=\mathbb E_{r’}[A(f(x),r,r’)]$，则对于好的 $x$，我们有

$$\begin{aligned} \hat g(f(x),x)&=\mathbb E_{r\in\{0,1\}^n}\Big[\mathbb E_{r'}[A(f(x),r,r')]\langle x,r\rangle\Big]\\ &=\mathbb E_{r\in\{0,1\}^n}\mathbb E_{r'}\Big[A(f(x),r,r')\langle x,r\rangle\Big]\\ &\ge(\frac{1}{2}+\frac{1}{2q(n)})\cdot 1+(\frac{1}{2}-\frac{1}{2q(n)})\cdot(-1)\\ &=\frac{1}{q(n)}. \end{aligned}$$

因此，我们令 $\gamma=\frac{1}{q(n)}$，利用定理 16 中的算法求出候选集合 $L$，尝试 $L$ 中的每个元素 $x’$ 检查是否满足 $f(x’)=f(x)$ 即可。根据定理 16，成功率为 $1-\delta$。

注意，这里我们用到了之前提到的扩展，因为我们没有 $g$ 的 Oracle，只有它的一个 noisy Oracle $A$（带有随机性 $r’$）。

总结

我们给出了 Goldreich-Levin 定理（定理 6）的两种证明，第一种是直接来自密码学和编码理论的证明，主要利用了用 Chebyshev 不等式控制和的期望时只需要变量两两独立的良好性质；第二种是来自布尔函数调和分析的证明，我们利用了内积的性质，将问题转化为从 Oracle $A$ 中学习其频谱上值较大的位置（定理 16）。

布尔函数分析是一个强大的工具，它在分析决策树等结构时也是很有力的。

[1] Goldreich, Oded, and Leonid A. Levin. “A hard-core predicate for all one-way functions.” Proceedings of the twenty-first annual ACM symposium on Theory of computing. 1989.

[2] Mihir Bellare. The Goldreich-Levin Theorem, 1999.

[3] O’Donnell, Ryan. Analysis of boolean functions. Cambridge University Press, 2014.

本文参考了 密码学基础 Lecture 8（IIIS, Tsinghua, Spring 2025）内容和 Analysis of Boolean Functions Lecrture 7（CMU 18-859S, Spring 2007）Scribe Note