单向函数的高效放大

【基本思想】

弱单向函数的存在定理中，已经讨论过如何把弱单向函数放大强单向函数，但是，这种构造方法实际效率很差，只有理论意义。

原来的放大方式是：如果一个函数 $f$ 在长度为 $n$ 的输入上，有至少 $\frac{1}{\mathrm{poly}(n)}$ 比例的输入难以反演，那么可以构造一个新函数 $g$，使得 $g$ 在几乎所有输入上都难以反演。

但是问题在于，构造出来的 $g$ 的输入长度会从 $n$ 增长到大约 $n^2\mathrm{poly}(n)$。也就是说，它把长度为 $n$ 上的弱困难性，转化成了长度为 $\operatorname{poly}(n)$ 上的强困难性，但这个长度膨胀太大，因此实际意义有限。

例如，如果 $f$ 在长度为 $1000$ 的输入中有 $1\%$ 的输入难以反演，那么原来的放大方法只能说明构造出的 $g$ 在长度约为 $100000000$ 的输入上几乎处处难以反演。这种结论对实际安全参数选择帮助不大。

因此，更理想的放大方式应当是：如果 $f$ 在长度为 $n$ 的输入上具有弱单向性，那么构造出的强单向函数 $g$ 应当只需要长度为 $O(n)$ 的输入，而不是 $\operatorname{poly}(n)$ 长度的输入。

这就是单向函数的高效放大（Efficient Amplification of One-Way Functions）想要解决的问题。

【定量单向性】

定义

为了更精确地讨论单向函数的放大，引入定量单向性（Quantitative One-Wayness）。

设 $T:\mathbb N\rightarrow \mathbb N$ 和 $\varepsilon:\mathbb N\rightarrow \mathbb R$ 是多项式时间可计算函数，对于一个多项式时间可计算函数 $f:\{0,1\}^{*}\rightarrow \{0,1\}^{*}$，若对于任意运行时间不超过 $T(\cdot)$ 的算法 $A’$，以及所有充分大的 $n$，算法 $A’$ 对 $f(U_n)$ 反演的失败概率都至少为 $\varepsilon(n)$，那么称 $f$ 在时间 $T(\cdot)$ 下具有 $\varepsilon(n)$ 单向性，即：

$$P[A'(f(U_n))\notin f^{-1}(f(U_n))] < \varepsilon(n)$$

其中，$U_n$ 是在 $\{0,1\}^n$ 上均匀分布的随机变量。

直观地说，$\varepsilon(n)$ 表示算法反演失败的比例下界。如果 $f$ 是 $\varepsilon(n)$ 单向的，那么任意时间 $T(n)$ 内的算法，在长度为 $n$ 的随机输入上，至少有约 $\varepsilon(n)$ 的概率反演失败。

定量单向性下的重新表述

弱单向性与强单向性

借助定量单向性，可以重新描述弱单向函数和强单向函数。

若函数 $f$ 是弱单向函数，如果存在某个多项式 $\mathrm{poly}(\cdot)$，使得 $f$ 在多项式时间下具有 $\frac{1}{\mathrm{poly}(\cdot)}$ 单向性，即任意多项式时间算法在反演 $f(U_n)$ 时，其失败概率至少为：

$$\frac{1}{\mathrm{poly}(\cdot)}$$

若函数 $f$ 是强单向函数，如果对于任意多项式 $\mathrm{poly}’(\cdot)$，$f$ 在多项式时间下都具有 $1-\frac{1}{\mathrm{poly}’(\cdot)}$ 单向性，即任意多项式时间算法对 $f(U_n)$ 的反演成功概率至多为：

$$\frac{1}{\mathrm{poly}'(\cdot)}$$

换句话说，弱单向函数只要求在一个可察觉比例的输入上难以反演，强单向函数要求在几乎所有输入上都难以反演，只有一个可忽略比例的输入可能被成功反演。

存在性定理

弱单向函数的存在性定理也可以用定量单向性的语言重新表述。

如果存在一个多项式 $\mathrm{poly}(\cdot)$，以及一个多项式时间可计算函数 $f$，使得 $f$ 在时间 $T(\cdot)$ 下具有 $\frac{1}{\mathrm{poly}(\cdot)}$ 单向性，那么可以构造一个强单向函数 $g$。

但是这个构造有一个明显缺点：它会导致输入长度显著膨胀。

具体来说，若 $f$ 的输入长度是 $n$，则构造出的 $g$ 的输入长度大约是

$$n^2\mathrm{poly}(n)$$

因此，该结论对应的时间关系是：

$$T'(n^2\mathrm{poly}(n))=T(n)$$

换句话说，想要说明 $g$ 在长度 $n^2\mathrm{poly}(n)$ 上难以反演，只能回到 $f$ 在长度 $n$ 上的难以反演性。

这不是一个高效放大结果，因为它把输入长度从 $n$ 放大到了 $\operatorname{poly}(n)$。

【高效放大的目标】

理想的高效放大应该满足：

$$T'(O(n))=T(n)$$

也就是说，构造出的强单向函数 $g$ 的输入长度只比原函数 $f$ 的输入长度大一个常数倍，而不是多项式倍。

等价地，可以写成：

$$T'(n)=T(\varepsilon n)$$

其中，$\varepsilon>0$ 是某个常数。

这种结果才说明：长度为 $n$ 上的弱困难性，可以有效转化为长度为 $O(n)$ 上的强困难性。

【单向置换的高效放大】

正则单向函数

上述的高效放大并不一定对所有单向函数都能直接得到，一种可处理的重要情形是正则单向函数。

如果存在一个多项式时间可计算函数 $m:\mathbb N\rightarrow \mathbb N$，以及一个多项式 $\mathrm{poly}(\cdot)$，使得对于 $f$ 值域中的任意 $y$，长度为 $n$ 的原像数量都介于 $\frac{m(n)}{\mathrm{poly}(n)}$ 和 $m(n)\cdot \mathrm{poly}(n)$ 之间，那么函数 $f$ 称为正则单向函数（Regular One-Way Functions）。

也就是说，正则函数要求每个输出点 $y$ 的原像数量大致处于同一个规模，最多只允许相差一个多项式因子。

我们只考虑一种更特殊的情形：单向置换，其是长度保持且单射的函数，因此每个输出恰好只有一个原像，是最典型的正则函数。

单向置换高效放大定理

Theorem：设 $\mathrm{poly}(\cdot)$ 是一个多项式，$T:\mathbb N\rightarrow\mathbb N$ 是一个时间函数。假设 $f$ 是一个多项式时间可计算的置换，并且 $f$ 在时间 $T(\cdot)$ 下具有 $\frac{1}{\mathrm{poly}}$ 单向性，即 $f$ 是一个弱单向置换。

那么，存在一个常数 $\gamma>1$，一个多项式 $\mathrm{poly}’$，一个多项式时间可计算的置换 $F$，使得对于任意多项式时间可计算函数 $\delta:\mathbb N\rightarrow [0,1]$，函数 $F$ 在时间 $T’(\cdot)$ 下具有 $1-\varepsilon(\cdot)$ 单向性，其中时间函数满足：

$$T'(\gamma n) = \frac{\varepsilon(n)^2}{\mathrm{poly}'(n)}\cdot T(n)$$

该定理说明：如果 $f$ 是弱单向置换，那么可以构造一个新的置换 $F$，使得 $F$ 成为强单向置换，并且输入长度只从 $n$ 增加到 $\gamma n$，也就是只增加一个常数倍。

具体来说，若原函数 $f$ 的输入长度为 $n$，则新函数 $F$ 的输入长度为 $\gamma n$，这与前面低效放大中的长度 $n^2\mathrm{poly}(n)$ 形成对比。低效放大会把输入长度放大到多项式规模，而这里的高效放大只产生线性长度膨胀。

因此，该定理实现了真正意义上的高效放大，即将弱单向置换转换为强单向置换，并且长度损耗只是 $O(n)$

基本思想

单向置换 $f$ 的高效放大，其核心思想是：将 $f$ 作用在许多不同的输入上，使得想要反演构造出的新函数，就必须在某些困难实例上成功反演 $f$。

在单向函数的存在性定理证明中，$f$ 被作用在彼此无关的输入上，即这些输入是原始输入中互不相交的不同部分。这样做的好处是证明比较简单，但缺点是构造效率很低，因为输入长度会显著膨胀。

考虑一种更高效的方式：不再让 $f$ 作用在完全无关的输入上，而是让 $f$ 作用在一系列相关的输入上。最自然的想法是反复迭代 $f$，即从某个初始点 $x$ 出发，依次计算

$$x,\quad f(x),\quad f(f(x)),\quad \cdots$$

但是，单纯迭代 $f$ 并不能保证困难性得到放大。原因是：如果某些容易被反演算法处理的实例，在经过 $f$ 映射之后仍然落在这个容易被反演算法处理的实例集合中，那么反复迭代 $f$ 仍然可能一直停留在容易区域中。因此，不能仅仅希望这种坏情况不会发生。

为避免这一问题，需要在连续两次应用 $f$ 之间加入一定的随机化步骤，但随机化不能太多，因为这些随机信息最终也要被编码进构造函数的输入中，如果每一步都使用大量随机性，那么构造出的函数仍然会变得低效。

为此，采用在扩展图（Expander Graph）上随机游走的方式进行随机化方式。具体来说，在每次应用 $f$ 之后，在一个扩展图上随机走一步，这样每一步只需要少量随机比特，却能获得接近独立随机采样的效果。

扩展图

定义

设 $G=(V,E)$ 是一个图。如果它满足以下三个条件，则称它为一个 $(n,d,c)$-扩展图：

1. $G$ 有 $n$ 个顶点，即 $|V|=n$
2. 每个顶点的度数都是 $d$，即 $G$ 是 $d$-正则图
3. $G$ 满足扩展性质：对于任意子集 $S\subset V$，如果 $|S|\leq \frac{n}{2}$，则有

$$|N(S)|\geq (1+c)|S|$$

其中，$c>0$ 称为扩展因子（Expansion Factor），$N(S)$ 表示集合 $S$ 中所有顶点的邻居集合，即：

$$N(S)=\{u\in V:\exists v\in S\text{ such that }(u,v)\in E\}$$

直观来说，扩展图的特点是：任何不太大的顶点集合 $S$，其邻居集合都会明显大于 $S$ 本身。也就是说，从一个集合出发，只要沿边走一步，就会迅速扩散到更多顶点。

显式构造的扩展图族

在单向置换的高效放大中，使用显式构造的扩展图族（Explicitly Constructed Expander Family）。它指的是一族图 $\{G_n\}_{n\in\mathbb{N}}$，其中 $G_n$ 的顶点可以用长度为 $n$ 的二进制串表示，即顶点集合为 $\{0,1\}^n$。因此，$G_n$ 实际上有 $2^n$ 个顶点。

所谓显式构造，是指存在一个多项式时间算法，使得给定图中某个顶点的表示，可以高效输出该顶点的所有邻居。

同时，图的度数 $d$、扩展因子 $c$ 以及寻找邻居的算法，对于整个图族都是固定的常数或固定算法。

扩展图上的随机游走

图上的随机游走（Random Walk），是指从一个均匀随机选择的初始顶点出发，每一步都从当前顶点的邻居中均匀随机选择一个顶点并移动过去，由此得到一个顶点序列。

扩展图的扩展性质能够推出一个非常重要的随机性结论：虽然随机游走中相邻顶点之间并不是独立的，但在扩展图上，随机游走仍然表现出很强的类随机性。

具体来说，对于顶点集合中的任意一个常数密度子集，以及任意参数 $l$，长度为 $O(l)$ 的随机游走完全没有碰到该子集的概率至多为 $2^{-l}$

这个概率与独立随机选择 $O(l)$ 个顶点时的情况相当，也就是说，在扩展图上走 $O(l)$ 步，虽然只用了很少的随机性，但效果接近于独立随机采样了 $O(l)$ 个顶点。

这正是扩展图在单向性放大中有用的原因：它用很少的随机比特，就能让构造过程有较好的扩散性，从而更可能碰到困难实例。

构造方式

我们希望反复应用 $f$，但又不希望过程一直停留在容易被反演算法处理的实例集合中。因此，在每次应用 $f$ 之后，先在扩展图上走一步，再继续应用 $f$。

具体来说，将 $f$ 的定义域 $\{0,1\}^n$ 看作扩展图 $G_n$ 的顶点集合，构造过程从某个顶点 $x$ 出发，交替执行两类操作：

1. 对当前顶点应用单向置换 $f$
2. 在扩展图上按照某个指定方向走一步

整个过程可以理解为：

$$x \longrightarrow f(x) \longrightarrow g_{\sigma_1}(f(x)) \longrightarrow f(g_{\sigma_1}(f(x))) \longrightarrow g_{\sigma_2}(f(g_{\sigma_1}(f(x)))) \longrightarrow \cdots$$

其中，$g_{\sigma_i}$ 表示在扩展图上按照标签 $\sigma_i$ 指定的边走一步。

形式化地，设 $\{G_n\}_{n\in\mathbb{N}}$ 是一族 $d$-正则图，其中 $G_n$ 的顶点集合为 $\{0,1\}^n$，并且假设每个顶点都有自环。对每个顶点关联的边进行标号，标号集合为 $\{1,2,\ldots,d\}$，对于每个标签 $l\in\{1,2,\ldots,d\}$，用 $g_l(x)$ 表示从顶点 $x$ 出发，沿着标签为 $l$ 的边走一步所到达的顶点。

设 $f:\{0,1\}^{*}\to \{0,1\}^{*}$ 是一个单射且长度保持的函数，$\lambda$ 为空序列。对于任意 $k\geq 0$、$x\in\{0,1\}^n$ 以及 $\sigma_1,\sigma_2,\ldots,\sigma_k\in\{1,2,\ldots,d\}$，定义函数 $F$ 如下：

• 当随机步序列为空时：

$$F(x,\lambda)=x$$

• 当随机步序列为 $\sigma_1\sigma_2\cdots\sigma_k$ 时，递归定义为：

$$F(x,\sigma_1\sigma_2\cdots\sigma_k) = \left( \sigma_1, F(g_{\sigma_1}(f(x)),\sigma_2\cdots\sigma_k) \right)$$

即先对 $x$ 应用 $f$，然后根据 $\sigma_1$ 在扩展图上走一步，得到新的顶点 $g_{\sigma_1}(f(x))$，接着以这个新顶点为起点，继续处理剩余的标签序列 $\sigma_2,\ldots,\sigma_k$。

更直观地，可以令 $y_0=x$，并对 $i=1,2,\ldots,k$ 定义：

$$y_i=g_{\sigma_i}(f(y_{i-1}))$$

于是最终有：

$$F(x,\sigma_1\sigma_2\cdots\sigma_k) = (\sigma_1,\sigma_2,\ldots,\sigma_k,y_k)$$

因此，$F$ 的输出由两部分组成：

1. 随机游走所使用的标签序列 $\sigma_1,\sigma_2,\ldots,\sigma_k$
2. 经过交替应用 $f$ 和扩展图步之后得到的最终顶点 $y_k$

展开来看，最终顶点为：

$$y_k = g_{\sigma_k} \left( f\left( g_{\sigma_{k-1}} \left( f\left( \cdots g_{\sigma_1}(f(x)) \cdots \right) \right) \right) \right)$$

进一步，如果给定一个函数 $k:\mathbb{N}\to\mathbb{N}$，则将输入 $\alpha$ 解析为 $\alpha=(x,\sigma_1,\ldots,\sigma_t)$，其中 $t=k(|x|)$，且每个 $\sigma_i\in\{1,2,\ldots,d\}$，有：

$$F_k(\alpha)=F(x,\sigma_1,\ldots,\sigma_t)$$

由此可见，$F_k$ 的输入是初始顶点和一段扩展图行走方向，输出则是同一段行走方向和最终到达的顶点。这个构造的本质是：用扩展图随机游走代替完全独立的随机采样，从而在只引入少量随机性的情况下，使迭代过程具有足够的扩散性，并最终实现单向置换的高效放大。

以 $k=4$ 为例，从 $x$ 得到 $y$ 的过程如下图所示。图中标记为 $f$ 的圆圈表示对当前顶点应用单向置换 $f$，标记为 $g$ 的方框表示在扩展图上走一步，其方向由辅助输入 $\sigma_i$ 指定。

直观理解

上述构造可以理解为：从初始点 $x$ 出发，每一轮先应用一次单向置换 $f$，再根据少量随机比特在扩展图上走一步。重复多轮之后，把所有方向 $\sigma_1,\ldots,\sigma_k$ 和最终到达的顶点 $y_k$ 一起作为输出。

之所以要保留 $\sigma_i$，是因为这些标签代表了构造过程中使用的随机性，它们必须作为输出的一部分保留下来，才能使整个函数保持单射性和长度保持性。

这个构造的关键优势在于：

1. 如果每次都重新选择一个完全随机的新输入，则随机性开销很大
2. 如果只反复迭代 $f$，又可能一直停留在容易被反演算法处理的实例中
3. 使用扩展图随机游走，可以用很少的随机性获得接近独立采样的扩散效果

换句话说，扩展图在这里的作用是：用少量随机比特，把迭代过程从可能的容易区域中搅动出去，使其更可能经过困难实例，从而使反演整个构造函数变得更难。

【困难性放大】

上文中给出了单向置换的高效放大的构造方式，其基本形式是：从初始点 $x$ 出发，交替执行应用 $f$ 和在扩展图上走一步，最后输出所有辅助标签以及最终顶点。

下面给出一个命题，说明这个构造 $F_k$ 确实具有困难性放大（Hardness Amplification）的作用，即如果原来的置换 $f$ 在某一比例的输入上难以反演，那么构造出的 $F_k$ 会在更大比例的输入上难以反演。

命题

Proposition：设 $d\in\mathbb N$、$c>0$ 和 $\ell$ 为常数，$\alpha:\mathbb N\to\mathbb R$ 与 $T:\mathbb N\to\mathbb N$ 为函数，并满足以下条件：

（1）图族 $\{G_n\}_{n\in\mathbb N}$ 是一个显式构造的 $(d,c)$-扩展图族

（2）置换 $f$ 是多项式时间可计算的，并且在时间 $T(\cdot)$ 下具有 $\alpha’(\cdot)$ 单向性，其中

$$\alpha'(n)=\alpha(n)+2^{-n}$$

（3）函数 $\alpha:\mathbb N\to\mathbb R$ 是多项式时间可计算的

（4）参数 $\ell$ 足够大，满足：

$$\ell \geq \frac{4+c^2}{c^2}\cdot d$$

那么，$F_k$ 是多项式时间可计算的，并且对于任意多项式时间可计算函数 $\varepsilon:\mathbb N\to\mathbb R$，置换 $F_k$ 在时间 $T’(\cdot)$ 下具有 $((1-\varepsilon(\cdot))\beta(\cdot))$ 单向性，其中：

$$\beta(n+k(n)\log_2 d) = 1-\left(1-\frac{\alpha(n)}{2}\right)^{k(n)/\ell}$$

并且：

$$T'(n+k(n)\log_2 d) = \frac{(\varepsilon(n)\alpha(n))^2}{O(n+k(n))^3}\cdot T(n)$$

需要注意的是，输入由两部分组成：一个长度为 $n$ 的初始点 $x$，以及 $k(n)$ 个边标签，每个标签需要 $\log_2 d$ 比特表示。因此，$F_k$ 的输入长度为：

$$m=n+k(n)\log_2 d$$

命题的含义

这个命题可以理解为：如果原函数 $f$ 在至少 $\alpha(n)$ 比例的输入上难以反演，那么通过构造 $F_k$，可以把困难实例的比例放大到：

$$\beta(m) = 1-\left(1-\frac{\alpha(n)}{2}\right)^{k(n)/\ell}$$

其中，$\beta(m)$ 可以理解为：一条长度为 $k(n)$ 的随机路径命中困难集合的概率。

如果 $\alpha(n)$ 较小，则可以近似使用：

$$1-(1-a)^r\approx ar$$

因此，当 $\alpha(n)$ 很小时，有：

$$\beta(m) \approx \frac{k(n)}{2\ell}\alpha(n)$$

这说明，随着随机游走步数 $k(n)$ 增加，困难比例会被逐步放大。

特别地，当取 $k(n)=3n, \alpha(n)=\frac{1}{\mathrm{poly}(n)}$ 时，可以得到：

$$\beta(O(n)) = 1-\left(1-\frac{\alpha(n)}{2}\right)^{3n/\ell},\quad T'(O(n)) = \mathrm{poly}\left(\frac{\varepsilon(n)}{n}\right)\cdot T(n)$$

也就是说，输入长度只增加到 $O(n)$，但困难性可以得到显著放大。

此时可以得到以下几种典型情形：

• 如果 $\alpha(n)=o\left(\frac{1}{n}\right)$，那么：

$$\beta(O(n))\approx 1.5n\cdot \alpha(n)$$

也就是说，当原本困难实例比例非常小时，经过 $O(n)$ 次扩展图随机步之后，困难比例大约被放大了 $n$ 倍。

• 如果 $\alpha(n)\leq \frac{1}{2n}$，那么：

$$\beta(O(n))>1.02n\cdot \alpha(n)$$

这说明，即使原始困难比例只有 $\frac{1}{n}$ 量级，构造仍能带来线性倍数的放大。

• 如果 $\alpha(n)$ 是常数，则有：

$$\beta(O(n))>1-2^{-\Omega(n)}$$

这意味着，如果原函数 $f$ 已经在常数比例的输入上难以反演，那么构造后的 $F_k$ 会在几乎所有输入上难以反演，从而接近强单向性。

因此，困难性放大命题说明：单向置换的高效放大构造可以在只增加常数倍输入长度的情况下，把弱单向性逐步放大为强单向性。

证明思路

具体来说，命题的证明由两类论证组成：

1. 组合论证（Combinatorics）：说明扩展图上的随机游走会以足够高的概率命中任意给定密度的集合
2. 归约论证（Reducibility Argument）：说明如果能高概率反演 $F_k$，那么就可以构造一个算法高概率反演原函数 $f$，从而与 $f$ 的单向性假设矛盾

这两部分分别对应随机游走引理和归约引理。随机游走引理是组合性质，负责证明随机路径会碰到困难集合；归约引理是密码学论证，负责证明如果能反演整条路径，就能反演路径中的困难点。

随机游走引理

前置假设

扩展图

在分析单向置换的高效放大构造时，真正关心的不是原扩展图 $G_n$ 上的普通随机游走，而是图 $G_{f,n}$ 上的随机游走。

定义：

$$G_{f,n}=(\{0,1\}^n,E_{f,n})$$

其中，

$$E_{f,n}=\{(u,v):(f(u),v)\in E_n\}$$

这个定义的含义是：在 $G_{f,n}$ 中，从 $u$ 到 $v$ 有一条边，当且仅当在原图 $G_n$ 中，从 $f(u)$ 到 $v$ 有一条边。这正好对应构造中的一轮操作：

$$u \longrightarrow f(u) \longrightarrow g_\sigma(f(u))$$

由于 $f$ 是置换，它只是重新排列顶点，不会改变图的扩展性质。因此，$G_{f,n}$ 仍然保持扩展图的良好性质。

谱性质

对于正则图，其扩展性质可以推出邻接矩阵的特征值性质。

具体来说，如果图是 $(d,c)$​-扩展图，设邻接矩阵的前两个特征值绝对值之比为 $\rho$，则有：

$$\rho \leq 1-\frac{c^2}{(4+c^2)d} < 1$$

这表示随机游走每走一步，都会在一定程度上把分布推向均匀分布，$\rho$ 越小，随机游走混合得越快。

路径图

为了使随机游走具有更强的混合性质，进一步考虑 $\ell$ 步路径图，即将原图中长度为 $\ell$ 的路径看作新图中的一条边。

如果原图的特征值比为 $\rho$，那么 $\ell$ 步路径图的特征值比至多为 $\rho^\ell$。由于命题中假设：

$$\ell \geq \frac{4+c^2}{c^2}\cdot d$$

可以推出：

$$\rho^\ell<\frac{1}{2}$$

引理

Lemma：设 $G$ 是一个正则图，其邻接矩阵的前两个特征值绝对值之比小于 $\frac{1}{2}$。设 $S$ 是图中顶点集合的一个子集，其测度为 $\mu$，即 $S$ 占所有顶点的比例为 $\mu$。

那么，在图 $G$ 上进行长度为 $t$ 的随机游走时，随机游走路径命中 $S$ 的概率至少为

$$1-\left(1-\frac{\mu}{2}\right)^t$$

即随机游走完全避开 $S$ 的概率至多为：

$$\left(1-\frac{\mu}{2}\right)^t$$

随机游走引理说明，如果每一步都是从整个顶点集合中独立均匀随机选点，那么每一步命中 $S$ 的概率就是 $\mu$，长度为 $t$ 的独立采样完全避开 $S$ 的概率为：

$$(1-\mu)^t$$

扩展图上的随机游走不是独立采样，因为当前顶点和下一个顶点有关。但是，由于扩展图混合性很好，它的行为接近独立采样。

引理给出的界是 $\left(1-\frac{\mu}{2}\right)^t$，比理想独立采样的 $(1-\mu)^t$ 稍弱一些，但仍然足够强。

也就是说，在扩展图上走 $t$ 步，命中密度为 $\mu$ 的集合的概率至少接近于独立随机采样 $t$ 次的效果。

证明思路

随机游走引理的证明基于扩展图的谱性质。

设 $G$ 是一个正则图，将 $G$ 的邻接矩阵除以图的度数，可以得到一个随机矩阵 $M$，该矩阵描述了在图 $G$ 上随机走一步的过程。由于 $G$ 是正则图，均匀分布在随机游走下保持不变。因此，若用 $\boldsymbol{\boldsymbol{\pi}}$ 表示顶点集合上的均匀分布，则有：

$$M\boldsymbol{\pi}=\boldsymbol{\pi}$$

也就是说，均匀分布 $\boldsymbol{\pi}$ 是随机矩阵 $M$ 的最大特征值 $1$ 所对应的特征向量。同时，随机矩阵 $M$ 的特征值比例与原邻接矩阵的特征值比例相同。

由于扩展图具有良好的谱性质，第二大特征值的绝对值被严格控制在 $1$ 以下，这意味着任何偏离均匀分布的部分，都会在随机游走过程中逐步衰减。

因此，可以将顶点集合上的概率分布分解为两部分：

1. 均匀分布方向的分量：该部分对应最大特征值 $1$，在随机游走过程中保持不变
2. 偏离均匀分布的分量：该部分对应其他特征值，会被随机游走矩阵逐步压缩

由于第二大特征值较小，偏离均匀分布的分量在每一步随机游走后都会变小。因此，随机游走会不断把当前分布推向均匀分布。

随机游走引理关心的是：长度为 $t$ 的随机游走是否会经过某个集合 $S$。设 $S$ 在顶点集合中的密度为：

$$\mu=\frac{|S|}{|V|}$$

证明的目标是上界随机游走完全不经过 $S$ 的概率，或者等价地，下界随机游走至少一次命中 $S$ 的概率。

这个过程可以理解为：从均匀分布出发，每走一步，就检查路径是否进入了 $S$。如果路径进入了 $S$，这条路径就被筛掉；如果没有进入 $S$，它就继续保留下来。因此，集合 $S$ 的作用类似于一个筛子（Sieve），每一步都会过滤掉已经进入 $S$ 的路径。

如果当前分布接近均匀分布，那么进入 $S$ 的概率大约就是 $S$ 的密度 $\mu$。因此，在这一轮筛选中，大约有 $\mu$ 比例的路径会进入 $S$ 并被删除，剩余的概率质量大约只剩下 $1-\mu$。

但是，筛选操作本身会破坏分布的均匀性。因为进入 $S$ 的概率质量被删除后，剩下的残余分布不一定仍然接近均匀分布。如果没有扩展性，残余分布可能逐渐集中在某些能够避开 $S$ 的区域中，之后就很难再碰到 $S$，筛选也就会逐渐失效。

扩展图的作用正是在这里体现出来的：每进行一次随机游走，残余分布中偏离均匀分布的分量都会被压缩。特别地，除了均匀分布方向以外，其余非均匀分量的 $L_2$ 范数会按照第二大特征值的比例下降。当特征值比小于 $\frac12$ 时，可以理解为这些非均匀分量在每一步都会被至少压低一个常数因子。

因此，随机游走过程中实际上不断重复两类操作：

1. 筛选：如果路径进入集合 $S$，就将其删除
2. 混合：在扩展图上继续随机走一步，将剩余分布重新拉向均匀分布

筛选操作负责删除进入 $S$ 的概率质量，混合操作负责恢复残余分布的均匀性。正因为扩展图能够不断压缩非均匀分量，残余分布不会长期集中在避开 $S$ 的区域中，而是会反复被推回接近均匀的状态。

于是，只要残余分布接近均匀，集合 $S$ 每一步都能筛掉大约 $\mu$ 比例的概率质量；而扩展图的谱性质保证了这种接近均匀的状态能够持续恢复。因此，随机游走完全避开 $S$ 的概率会随着步数增加而指数下降。

这就是随机游走引理的核心思想：虽然扩展图上的随机游走不是独立采样，但由于谱间隙的存在，它在命中任意固定密度集合时，表现得接近独立随机采样。

上界证明

下面给出一个更形式化的证明框架，以说明前面证明思想如何转化为矩阵分析。但这个简单分析只能得到一个较弱的界，不能直接推出随机游走引理所声称的结论。

随机游走引理希望证明：随机游走不经过 $S$ 的概率最多为 $\left(1-\frac{\mu}{2}\right)^t$，但这个弱界证明框架只能证明随机游走不经过 $S$ 的概率最多为 $\left((1-\mu)+\rho^2\right)^{\frac{t}{2}}$

设 $M$ 表示正则图 $G=(V,E)$ 上随机走一步的随机矩阵，$\rho$ 是 $M$ 的第二大特征值绝对值的上界，其中最大特征值为 $1$。由于 $G$ 是正则图，顶点集合上的均匀分布 $\boldsymbol{\pi}$ 在随机游走下保持不变，即

$$M\boldsymbol{\pi}=\boldsymbol{\pi}$$

设 $S\subseteq V$ 是需要命中的顶点集合，其密度为

$$\mu=\frac{|S|}{|V|}$$

证明的目标是估计随机游走完全不经过 $S$ 的概率。

筛选矩阵

为了描述没有进入 $S$ 这一事件，引入 $0$-$1$ 筛选矩阵 $P$。矩阵 $P$ 的作用是保留 $V\setminus S$ 上的概率质量，并删除 $S$ 上的概率质量，即：

$$(P\mathbf{v})_i= \begin{cases} v_i, & i\notin S\\ 0, & i\in S \end{cases}$$

因此，对于一个概率分布向量 $\mathbf{v}$，$P\mathbf{v}$ 表示删去所有已经进入 $S$ 的概率质量之后剩下的残余分布。

此时，一次随机走一步并删除进入 $S$ 的路径的过程可以表示为：

$$PM$$

其中，$M$ 表示先随机走一步，$P$ 表示随后筛掉进入 $S$ 的概率质量。

未命中概率

从均匀分布 $\boldsymbol{\pi}$ 出发，连续进行 $t$ 步随机游走，并在每一步后删除进入 $S$ 的路径，则剩下的残余分布为：

$$(PM)^t\boldsymbol{\boldsymbol{\pi}}$$

这个向量的所有坐标都是非负的，并且它的坐标和正好等于随机游走在 $t$ 步内始终没有经过 $S$ 的概率，因此 $t$ 步随机游走不经过 $S$ 的概率为 $|(PM)^t\boldsymbol{\pi}|_1$。为使用谱分析，使用 $L_1$ 范数上界进行放缩，即对于任意向量 $\mathbf{v}\in\mathbb R^{|V|}$，有：

$$\|\mathbf{v}\|_1\leq \sqrt{|V|}\cdot \|\mathbf{v}\|_2.$$

因此，$t$ 步随机游走不经过 $S$ 的概率为

$$\sqrt{|V|}\cdot \|(PM)^t\boldsymbol{\pi}\|_2$$

此时，问题转化为控制残余分布的 $L_2$ 范数。

压缩估计

我们的目标是证明，对于任意向量 $\mathbf{z}$，都有：

$$\|PM\mathbf{z}\| \leq \sqrt{(1-\mu)+\rho^2}\cdot \|\mathbf{z}\|$$

即执行一次随机游走与筛选后，向量范数会被压缩一个固定因子。

将 $\mathbf{z}$ 分解为两部分：

$$\mathbf{z}=\mathbf{z}_1+\mathbf{z}_2$$

其中，$\mathbf{z}_1$ 是 $\mathbf{z}$ 在均匀分布方向上的分量，$\mathbf{z}_2$ 是与均匀分布方向正交的分量。

对于 $\mathbf{z}_1$，由于均匀分布方向对应最大特征值 $1$，随机游走矩阵 $M$ 不改变这一方向，即

$$M\mathbf{z}_1=\mathbf{z}_1$$

筛选矩阵 $P$ 会删除集合 $S$ 上的坐标。由于 $S$ 的密度为 $\mu$，均匀分布方向上的分量经过筛选后，其 $L_2$ 范数变为原来的 $\sqrt{1-\mu}$ 倍，即：

$$\|PM\mathbf{z}_1\| = \|P\mathbf{z}_1\| = \sqrt{1-\mu}\cdot \|\mathbf{z}_1\|$$

对于 $\mathbf{z}_2$，由于它与均匀分布方向正交，随机游走矩阵 $M$ 会按照第二大特征值的上界对其进行压缩，即：

$$\|M\mathbf{z}_2\| \leq \rho\|\mathbf{z}_2\|$$

而 $P$ 只是将部分坐标置零，不会增大 $L_2$ 范数，因此：

$$\|PM\mathbf{z}_2\| \leq \|M\mathbf{z}_2\| \leq \rho\|\mathbf{z}_2\|$$

将 $\mathbf{z}_1$ 与 $\mathbf{z}_2$ 联立，有：

$$\begin{aligned} \|PMz\| &= \|PM(\mathbf{z}_1+\mathbf{z}_2)\| \\ &\leq \|PM\mathbf{z}_1\|+\|PM\mathbf{z}_2\| \\ &\leq \sqrt{1-\mu}\cdot \|\mathbf{z}_1\| + \rho\cdot \|\mathbf{z}_2\| \end{aligned}$$

根据 Cauchy-Schwarz 不等式，有：

$$\sqrt{1-\mu}\cdot \|\mathbf{z}_1\| + \rho\cdot \|\mathbf{z}_2\| \leq \sqrt{(1-\mu)+\rho^2} \cdot \sqrt{\|\mathbf{z}_1\|^2+\|\mathbf{z}_2\|^2}$$

由于 $\mathbf{z}_1$ 与 $\mathbf{z}_2$ 正交，故有：

$$\sqrt{\|\mathbf{z}_1\|^2+\|\mathbf{z}_2\|^2} = \|\mathbf{z}_1+\mathbf{z}_2\| = \|\mathbf{z}\|$$

综上，可得：

$$\|PM\mathbf{z}\| \leq \sqrt{(1-\mu)+\rho^2}\cdot \|\mathbf{z}\|$$

未命中概率上界

将上述的压缩估计连续应用 $t$ 次，有：

$$\|(PM)^t\boldsymbol{\pi}\| \leq \left((1-\mu)+\rho^2\right)^{\frac{t}{2}}\|\boldsymbol{\pi}\|$$

由于 $\boldsymbol{\pi}$ 是均匀分布向量，每个坐标都是 $\frac{1}{|V|}$，所以：

$$\|\boldsymbol{\pi}\| = \sqrt{|V|\cdot \frac{1}{|V|^2}} = \frac{1}{\sqrt{|V|}}$$

而 $t$ 步随机游走不经过 $S$ 的概率至多为 $\sqrt{|V|}\cdot |(PM)^t\boldsymbol{\pi}|$，将上式带入，有：

$$\begin{align*} \sqrt{|V|}\cdot \|(PM)^t\boldsymbol{\pi}\| &\leq \sqrt{|V|}\cdot\left((1-\mu)+\rho^2\right)^{\frac{t}{2}}\|\boldsymbol{\pi}\|\\ &= \sqrt{|V|}\cdot\left((1-\mu)+\rho^2\right)^{\frac{t}{2}}\frac{1}{\sqrt{|V|}}\\ &=\left((1-\mu)+\rho^2\right)^{\frac{t}{2}} \end{align*}$$

即： $t$ 步随机游走不经过 $S$ 的概率至多为：

$$\left((1-\mu)+\rho^2\right)^{\frac{t}{2}}$$

这说明，随机游走完全避开 $S$ 的概率会随着步数 $t$ 指数下降。

上界适用范围

如果进一步满足 $\mu\geq 2\rho^2$，则有：

$$(1-\mu)+\rho^2 \leq 1-\frac{\mu}{2}$$

于是可以得到，$t$ 步随机游走不经过 $S$ 的概率至多为：

$$\left(1-\frac{\mu}{2}\right)^{\frac{t}{2}}$$

这个界已经体现出扩展图随机游走的核心作用：筛选操作会删除进入 $S$ 的概率质量，而随机游走的谱性质会不断压缩非均匀分量，使残余分布重新趋向均匀，从而保证筛选持续有效。

但是，该上界仍然有一定限制。它只有在 $\mu$ 足够大时才有用，当 $\mu$ 很小时，条件 $\mu\geq 2\rho^2$ 可能不成立。此外，它得到的指数是 $\frac{t}{2}$，而更强的随机游走结论希望得到指数为 $t$ 的界。

因此，这个上界证明的意义在于说明谱分析如何控制避开 $S$ 的概率：均匀分布方向由筛选矩阵削减，非均匀方向由随机游走矩阵压缩，两者共同导致残余概率质量不断下降。

归约引理

归约思想

随机游走引理说明一件事：如果顶点集合 $S$ 在图中具有一定密度，那么扩展图上的随机路径会以较高概率经过 $S$。

但是，仅有这个性质还不够，还需要把它转化成密码学意义上的单向性放大结论。也就是说，需要说明：如果原函数 $f$ 在某些点上难以反演，而随机路径经常经过这些点，那么构造出的函数 $F_k$ 就应该更难反演。

这一部分的证明思想与简单困难性放大类似，但两者有两个关键区别：

（1）在简单困难性放大中，通常考虑从 $\{0,1\}^n$ 中独立选取 $k$ 个输入，若困难集合 $S$ 的密度为 $2^{-n}|S|$，那么一个均匀随机选取的 $k$ 元序列完全不包含 $S$ 中元素的概率为 $(1-2^{-n}|S|)^k$。因此，至少有一个元素落入 $S$ 的概率为：

$$1-(1-2^{-n}|S|)^k$$

这是一种非常直接的组合事实，因为序列中的每个元素都是独立均匀选取的。而在当前构造中，不能使用这种独立采样的分析。

这里的 $k$ 个中间点不是彼此独立的随机输入，而是由固定正则图上的 $k$ 步随机游走产生的。因此，需要使用更一般的随机路径性质：如果集合 $S$ 的密度为 $\alpha(n)$，那么由 $k$ 步随机游走产生的路径，会有至少

$$\beta(n+k(n)\log_2 d)$$

比例经过集合 $S$。

（2）简单困难性放大关注的是在一组相互独立的输入上分别反演原函数 $f$。也就是说，构造通常类似于：

$$(x_1,\ldots,x_k) \longmapsto (f(x_1),\ldots,f(x_k))$$

如果能反演整个构造，就意味着能够反演其中某些独立实例。

但在当前构造中，$F_k$ 是从一个初始点出发，连续多次应用 $f$，并在相邻两次应用之间穿插扩展图上的移动 $g_\sigma$。因此，分析对象不是多个独立输入，而是同一个初始输入在迭代过程中产生的一串中间点：

$$x \longrightarrow g_{\sigma_1}(f(x)) \longrightarrow g_{\sigma_2}(f(g_{\sigma_1}(f(x)))) \longrightarrow \cdots$$

换句话说，当前证明要处理的是单个实例上的连续演化过程，而不是多个独立实例的并列组合。

因此，这里的归约证明比简单放大的证明更复杂，它需要同时处理两个问题：

1. 随机路径是否会经过原函数 $f$ 的困难输入集合
2. 如果能够反演整条路径对应的 $F_k$ 输出，是否能够反推出路径中某一步对应的 $f$ 的原像

前一个问题由随机游走性质提供保证，后一个问题则由归约引理完成。

具体地，后续将使用如下形式的路径命中概率：

$$\beta(n+k(n)\log_2 d) = 1-\left(1-\frac{\alpha(n)}{2}\right)^{k(n)/\ell}$$

其中，$\alpha(n)$ 表示困难集合的密度，$\beta$ 表示长度为 $k(n)$ 的随机路径经过该困难集合的概率下界，$\ell$ 是由扩展图谱分析引入的常数参数。

这一表达式的含义是：虽然当前构造中的中间点不是独立采样得到的，但扩展图随机游走仍然保证它们能够以接近独立采样的方式命中困难集合。

归约引理正是基于这个路径命中性质，它的基本逻辑是：如果原函数 $f$ 在 $\alpha’(n)$ 比例的输入上难以反演，并且扩展图随机路径能以至少 $\beta$ 的概率命中任意 $\alpha(n)$ 密度的集合，那么构造出的 $F_k$ 至少在大约 $\beta$ 比例的输入上难以反演。

反过来说，如果能在超过允许范围的概率下反演 $F_k$，那么就可以利用这个反演算法来反演 $f$，从而与 $f$ 的单向性矛盾。

引理

Lemma：设 $f$ 在时间 $T(\cdot)$ 下是 $\alpha’(\cdot)$ 单向的，并且 $\alpha’(\cdot)$ 满足：

$$\alpha'(n)\geq \alpha(n)+2^{-n}$$

如果 $G_{f,n}$ 满足随机路径性质，并且

$$\beta(n+k(n)\log_2 d)>\alpha(n)$$

那么对于任意多项式时间可计算函数 $\varepsilon:\mathbb N\to\mathbb R$，函数 $F_k$ 在时间 $T’(\cdot)$ 下具有 $((1-\varepsilon(\cdot))\beta(\cdot))$ 单向性，其中

$$T'(n+k(n)\log_2 d) = \frac{\varepsilon(n)^2\alpha(n)^2}{O(n+k(n))^3}\cdot T(n)$$

需要注意的是，如果

$$\beta(n+k(n)\log_2 d)\leq \alpha(n)$$

则这个引理没有意义，因为此时构造后的困难比例并没有超过原来的困难比例，谈不上放大。

证明

反证假设

证明采用反证法。

目标是证明 $F_k$ 不能被过高概率地反演，为此假设存在一个算法可以较高概率地反演 $F_k$，然后利用它构造关于原函数 $f$ 的反演算法。

由于 $F_k$ 的输入由一个长度为 $n$ 的初始点 $x$ 和 $k(n)$ 个边标签组成，而每个标签需要 $\log_2 d$ 比特表示。因此，$F_k$ 的输入长度可表示为：

$$m=n+k(n)\log_2 d.$$

那么，反证假设可写为：存在一个算法可以在时间 $T’(m)$ 内，以至少

$$1-(1-\varepsilon(m))\beta(m) = 1-\beta(m)+\varepsilon(m)\beta(m)$$

的概率反演 $F_k$。

这表示该算法的反演成功概率超过了 $1-\beta(m)$，并且多出来的部分为 $\varepsilon(m)\beta(m)$。

若令 $\varepsilon’(m)=\frac{\varepsilon(m)\beta(m)}{2}$，则反演成功概率至少为：

$$1-\beta(m)+2\varepsilon'(m)$$

反演算法转化

下面，将这个平均意义上成功的反演算法，转化为一个更方便使用的算法 $A$。

由于该算法在所有输入上的平均成功概率至少为 $1-\beta(m)+2\varepsilon’(m)$，所以至少有 $1-\beta(m)+\varepsilon’(m)$ 比例的输入，其单点成功概率不低于 $\varepsilon’(m)$。否则，如果成功概率至少为 $\varepsilon’(m)$ 的输入比例小于 $1-\beta(m)+\varepsilon’(m)$，那么整体平均成功概率就无法达到 $1-\beta(m)+2\varepsilon’(m)$

对于这些单点成功概率至少为 $\varepsilon’(m)$ 的输入，可以通过独立重复运行来放大成功概率。具体来说，对同一个输入重复运行大约 $\frac{m}{\varepsilon’(m)}$ 次，就可以把失败概率降到指数小（例如降低到 $1-2^{-m}$ 量级），从而得到压倒性成功概率。

于是，可以得到一个新的算法 $A$，它满足：

1. 在至少 $1-\beta(m)+\varepsilon’(m)$ 比例的输入上，能够以压倒性概率成功反演 $F_k$
2. 运行时间为 $\frac{m}{\varepsilon’(m)}\cdot T’(m)$

由于 $\varepsilon’(m)=\frac{\varepsilon(m)\beta(m)}{2}$，所以 $A$ 的运行时间可以写成：

$$\frac{2m\cdot T'(m)}{\varepsilon(m)\beta(m)}$$

反演路径

$F_k$ 的输入可以写成 $(x,\sigma_1,\ldots,\sigma_k)$，其中 $x\in\{0,1\}^n, \sigma_i\in\{1,2,\ldots,d\}$，这组输入不仅是一个字符串，也可看成图上的一条长度为 $k$ 的路径。

具体地，令 $y_0=x$，并对 $i=1,2,\ldots,k$ 定义：

$$y_i=g_{\sigma_i}(f(y_{i-1}))$$

于是，$y_0,y_1,\ldots,y_k$ 就是由初始点 $x$ 和标签序列 $\sigma_1,\ldots,\sigma_k$ 确定的一条路径。

因此，算法 $A$ 反演 $F_k$ 的输入，也可以理解为算法 $A$ 在反演一条路径对应的输出。

记 $k=k(n), m=n+k\log_2 d$， $I_n$ 为所有可以被 $A$ 以压倒性概率成功反演的路径集合。由于 $A$ 在至少 $1-\beta+\varepsilon’$ 比例的输入上可以稳定反演 $F_k$，所以：

$$|I|\geq (1-\beta+\varepsilon')\cdot 2^m$$

也就是说，可被 $A$ 稳定反演的路径至少占所有路径的 $1-\beta+\varepsilon’$ 比例。

好顶点与坏顶点

接下来需要把可反演路径很多转化成多数顶点附近有足够多可反演路径。

对任意顶点 $v$，记 $\mathcal P_v$ 为所有经过 $v$ 的长度为 $k$ 的路径集合，并令 $I_v$ 表示所有经过 $v$，并且可以被 $A$ 稳定反演的路径，即：

$$I_v=I\cap \mathcal P_v$$

如果

$$\frac{|I_v|}{|\mathcal P_v|} \geq \frac{\varepsilon'}{k}$$

则称顶点 $v$ 是好顶点（Good Vertex），否则，称 $v$ 是坏顶点（Bad Vertex）。

这个定义的直观含义是：如果 $v$ 是好顶点，那么随机选择一条经过 $v$ 的路径时，有至少 $\frac{\varepsilon’}{k}$ 的概率选到一条可被 $A$ 成功反演的路径。

路径保留断言

断言

Claim：设 $I’$ 是 $I$ 中不经过坏顶点的路径集合，即：

$$I' = I\setminus \bigcup_{v\in\text{bad}} I_v$$

则：$I’$ 在所有路径中的密度大于 $1-\beta$

证明

用 $\mu(\cdot)$ 表示路径集合在所有路径中的密度。由于 $I$ 的密度至少为 $1-\beta+\varepsilon’$，即有：

$$\mu(I)\geq 1-\beta+\varepsilon'$$

从 $I$ 中删除所有经过坏顶点的路径后，得到 $I’$。因此，有：

$$\mu(I') \geq \mu(I)-\sum_{v\in\text{bad}}\mu(I_v)$$

对于坏顶点 $v$，根据定义 $\frac{|I_v|}{|\mathcal P_v|}<\frac{\varepsilon’}{k}$，有：

$$\mu(I_v) < \frac{\varepsilon'}{k}\mu(\mathcal P_v)$$

故有：

$$\begin{aligned} \mu(I') &\geq \mu(I)-\sum_{v\in\text{bad}}\mu(I_v) \\ &> 1-\beta+\varepsilon' - \sum_v\frac{\varepsilon'}{k}\mu(\mathcal P_v) \end{aligned}$$

由于每条长度为 $k$ 的路径最多经过 $k$ 个相关顶点，所以：

$$\sum_v\mu(\mathcal P_v)\leq k$$

代入化简可得：

$$\mu(I') > 1-\beta+\varepsilon' - \frac{\varepsilon'}{k}\cdot k = 1-\beta$$

这说明，即使删除所有经过坏顶点的可反演路径，剩下的只经过好顶点的可反演路径仍然超过 $1-\beta$ 比例。

好顶点密度断言

断言

Claim：好顶点的密度大于 $1-\alpha$

证明

采用反证法。

假设坏顶点集合 $S$ 的密度至少为 $\alpha$，即：

$$|S|\geq \alpha\cdot 2^n$$

根据随机路径性质，任意密度至少为 $\alpha$ 的顶点集合，都会被至少 $\beta$ 比例的长度为 $k$ 的路径经过。因此，至少有 $\beta$ 比例的路径会经过坏顶点集合 $S$。

但是，$I’$ 中的路径只经过好顶点，不经过任何坏顶点。故而，$I’$ 只能包含那些不经过 $S$ 的路径，其密度最多为 $1-\beta$

这与 $\mu(I’)>1-\beta$ 矛盾，所以，坏顶点集合的密度不可能达到 $\alpha$。

反演算法构造

现在利用算法 $A$ 构造一个反演原函数 $f$ 的算法，给定 $y=f(x)$ 恢复出 $x$。

构造的基本思想是：虽然算法不知道 $x$，但它知道 $y=f(x)$。因此，可以把 $y$ 放在一条随机路径的中间位置，然后从 $y$ 继续沿路径后缀向后走，构造出一个完整的 $F_k$ 输出。之后调用 $A$ 反演这个输出。如果 $A$ 成功反演整条路径，就可以恢复路径起点，再沿路径前缀重新计算，从而得到满足 $f(x)=y$ 的原像 $x$。

算法具体步骤如下：输入 $y$，重复以下步骤 $\frac{2nk}{\varepsilon\beta}$ 次

（1）随机选择一个位置 $i\in\{1,2,\ldots,k\}$ 并随机选择标签序列 $\sigma_1,\sigma_2,\ldots,\sigma_k\in\{1,2,\ldots,d\}$

（2）将 $y$ 看作某一步应用 $f$ 后得到的值，根据标签 $\sigma_i$ 在扩展图上走一步，再继续执行后缀标签序列，计算：

$$y'=F(g_{\sigma_i}(y),\sigma_{i+1}\cdots\sigma_k)$$

直观地说，如果 $y=f(x)$，那么：

$$g_{\sigma_i}(y)=g_{\sigma_i}(f(x))$$

正好是从顶点 $x$ 执行第 $i$ 轮操作后到达的下一个顶点，继续执行后缀 $\sigma_{i+1},\ldots,\sigma_k$，就可以得到这条路径的最终输出点。

（3）调用 $A$ 反演对应的 $F_k$ 输出：

$$x'\leftarrow A(\sigma_1,\ldots,\sigma_k,y')$$

如果 $A$ 成功，则 $x’$ 是这条路径的起点。

（4）从 $x’$ 出发，按照前缀标签 $\sigma_1,\ldots,\sigma_{i-1}$ 正向运行构造，得到某个顶点 $x$：

$$x=F(x',\sigma_1\cdots\sigma_{i-1})$$

这里的 $x$ 应该是路径中第 $i-1$ 步后的顶点，也就是满足下一步应用 $f$ 后得到 $y$ 的那个点。

（5）检查 $f(x)=y$，如果成立，则输出 $x$，否则继续重复

好顶点的有效性

设输入为 $y=f(x)$，弱 $x$ 是好顶点，那么根据好顶点的定义，在所有经过 $x$ 的长度为 $k$ 的路径中，至少有 $\frac{\varepsilon’}{k}$ 比例属于可反演路径集合 $I$。

又因为 $\varepsilon’=\frac{\varepsilon\beta}{2}$，所以随机选到一条经过 $x$ 且可被 $A$ 成功反演的路径的概率至少为：

$$\frac{\varepsilon'}{k} = \frac{\varepsilon\beta}{2k}$$

因此，算法重复 $\frac{2nk}{\varepsilon\beta}$ 次后，以压倒性概率至少会选中一条可反演路径。

一旦选中了这样的路径，算法 $A$ 就能以压倒性概率恢复这条路径的起点 $x’$。随后，从 $x’$ 沿着前缀标签 $\sigma_1,\ldots,\sigma_{i-1}$ 重新计算，就可以得到目标点 $x$，并通过检查 $f(x)=y$ 确认反演结果正确。

因此，对于好顶点 $x$，上述算法能够以至少 $1-2^{-n}$ 的概率成功反演 $f(x)$。

随机输入成功概率

由前面的好顶点密度断言可知，好顶点的密度大于 $1-\alpha(n)$。也就是说，当 $x$ 在 $U_n$ 中均匀随机选取时，$x$ 是好顶点的概率至少为 $1-\alpha(n)$。

对于这些好顶点，反演算法成功的概率至少为 $1-2^{-n}$。因此，该算法在输入 $f(U_n)$ 上的总体成功概率至少为：

$$(1-\alpha(n))(1-2^{-n})$$

进一步，有：

$$\begin{align*} (1-\alpha(n))(1-2^{-n}) &=1-2^{-n}-\alpha(n)+2^{-n}\alpha(n) \\ &> 1-\alpha(n)-2^{-n} \end{align*}$$

又因为引理假设 $\alpha’(n)\geq \alpha(n)+2^{-n}$，所以：

$$1-\alpha(n)-2^{-n} \geq 1-\alpha'(n).$$

因此，构造出的算法可以以至少 $1-\alpha’(n)$ 的概率反演 $f$。

运行时间分析

反演 $f$ 的算法一共重复 $\frac{2nk}{\varepsilon\beta}$ 次，每次重复中，需要调用一次算法 $A$，而算法 $A$ 的运行时间为 $\frac{2m\cdot T’(m)}{\varepsilon\beta}$。因此，整个反演算法的运行时间为：

$$\frac{2nk}{\varepsilon\beta} \cdot \frac{2m\cdot T'(m)}{\varepsilon\beta} = \frac{4nmk}{\varepsilon^2\beta^2}\cdot T'(m)$$

由于 $\beta(m)\geq \alpha(n)$，并且 $T’(m)$ 被定义为：

$$T'(m) = \frac{\varepsilon(m)^2\alpha(n)^2}{O(n+k(n))^3}\cdot T(n)$$

所以可以将总运行时间控制在 $T(n)$ 以内，也就是说，假设中的 $F_k$ 反演算法会导出一个时间不超过 $T(n)$ 的 $f$ 反演算法。

矛盾推出

综上所述，如果存在算法能够在时间 $T’(m)$ 内，以至少 $1-(1-\varepsilon(m))\beta(m)$ 的概率反演 $F_k$，那么就可以构造出一个算法，在时间 $T(n)$ 内，以至少 $1-\alpha’(n)$ 的概率反演 $f$。

但是，这与 $f$ 在时间 $T(\cdot)$ 下具有 $\alpha’(\cdot)$ 单向性的假设矛盾。因此，最初的反证假设不成立。

也就是说，$F_k$ 不能被如此高概率地反演，即：$F_k$ 在时间 $T’(\cdot)$ 下具有 $(1-\varepsilon(\cdot))\beta(\cdot)$ 单向性。

命题证明

根据得到两个引理：

1. 随机游走引理：如果图具有足够好的谱扩展性，那么随机游走会以较高概率命中任意给定密度的顶点集合
2. 归约引理：如果随机路径会以至少 $\beta$ 的概率命中任意密度为 $\alpha(n)$ 的集合，那么可以把这个路径命中性质转化为 $F_k$ 的单向性放大结论

只需要将它们应用到图 $G_{f,n}$ 上即可。

设 $S\subseteq V$ 是 $G_{f,n}$ 中任意一个测度为 $\alpha(n)$ 的顶点集合。由随机游走引理可知，在满足谱条件的图上，长度为 $t$ 的随机游走命中 $S$ 的概率至少为：

$$1-\left(1-\frac{\alpha(n)}{2}\right)^t$$

这里的含义是：如果 $S$ 是原函数 $f$ 的困难输入集合，那么扩展图随机游走会以较高概率经过这个困难集合。

但是，在命题的证明中，为了保证随机游走引理的谱条件成立，前面并不是直接在 $G_{f,n}$ 上应用一步随机游走，而是先构造了一个 $\ell$ 步路径图，这个 $\ell$ 步路径图中的一条边，对应原图 $G_{f,n}$ 中一条长度为 $\ell$ 的路径。

因此，如果在原图 $G_{f,n}$ 上进行长度为 $k(n)$ 的随机游走，那么它大致对应于在 $\ell$ 步路径图上进行长度为 $\frac{k(n)}{\ell}$ 的随机游走。

于是，原图 $G_{f,n}$ 上长度为 $k(n)$ 的随机游走命中 $S$ 的概率至少为：

$$1-\left(1-\frac{\alpha(n)}{2}\right)^{k(n)/\ell}$$

因此，可以定义：

$$\beta(n+k(n)\log_2 d) = 1-\left(1-\frac{\alpha(n)}{2}\right)^{k(n)/\ell}$$

这里的 $\beta$ 正是归约引理中需要的路径命中概率下界。

归约引理要求图 $G_{f,n}$ 满足路径命中性质：对任意测度为 $\alpha(n)$ 的顶点集合 $S$，至少有 $\beta$ 比例的长度为 $k(n)$ 的路径会经过 $S$。

由上面的随机游走分析，已经得到这个性质，并且得到了 $\beta(n+k(n)\log_2 d)$。同时，在命题中取：

$$\alpha'(n)=\alpha(n)+2^{-n}$$

于是可以直接应用归约引理，即：如果 $f$ 在时间 $T(\cdot)$ 下具有 $\alpha’(n)$ 单向性，那么构造出的 $F_k$ 在时间 $T’(\cdot)$ 下具有 $((1-\varepsilon(\cdot))\beta(\cdot))$ 单向性。

此时，时间函数满足：

$$T'(n+k(n)\log_2 d) = \frac{(\varepsilon(n)\alpha(n))^2}{O(n+k(n))^3}\cdot T(n).$$

这正是困难性放大命题要证明的结论。

替代分析

谱条件替换

前面对单向置换高效放大的分析，是通过扩展图的特征值比例（Eigenvalue Ratio）完成的，而不是直接使用扩展图的组合定义。也就是说，虽然扩展图最初是通过扩展性质定义的，但真正用于随机游走分析的是图的谱性质。

问题在于，从组合扩展性质转换到特征值比例时，参数转换并不是紧的。因此，如果最终仍然把结果表述为扩展性质，就会损失一些常数因子。为了得到更紧的分析，可以直接从谱性质出发。

具体来说，可以将困难性放大命题中的条件 1 替换为：存在某个常数 $\rho<1$，使得显式构造图族 ${G_n}$ 中每个图的特征值比例都至多为 $\rho$。

这里的特征值比例可以理解为：随机游走矩阵中第二大特征值绝对值与最大特征值的比值。由于最大特征值为 $1$，所以它实际上就是第二大特征值绝对值的上界，$\rho$ 越小，说明图上的随机游走混合得越快。

原来的证明中，为了让随机游走引理适用，需要把原图中的 $\ell$ 步路径看作新图中的一条边，这样做的目的是让新图的特征值比例变成 $\rho^\ell$。只要选择 $\ell$ 使得 $\rho^\ell<\frac{1}{2}$,就可以使用随机游走引理。

因此，条件 4 可以替换为：

$$\ell\geq \max\left\{1,\left\lceil \log_{\rho}\frac12 \right\rceil\right\}$$

由于 $0<\rho<1$，当 $\ell$ 增大时，$\rho^\ell$ 会下降，所以这个条件的含义是：选择足够大的 $\ell$，使 $\ell$ 步路径图的特征值比例小于 $\frac12$。

紧致性分析

原来的证明路径是：

$$\text{组合扩展性质} \Longrightarrow \text{特征值比例界} \Longrightarrow \text{随机游走命中性质}$$

其中，第一步转换会造成参数损失。采用替代分析则直接假设图族具有良好的特征值比例，因此证明路径变成：

$$\text{特征值比例界} \Longrightarrow \text{随机游走命中性质}$$

这样就避免了从组合扩展性质到谱性质的松弛转换，因此可以得到更好的常数。

同时，对于由 $G_n$ 和 $f$ 复合得到的图 $G_{f,n}$，其特征值比例不大于原图 $G_n$ 的特征值比例。直观地说，$f$ 是顶点集合上的置换，只是重新排列顶点，不会破坏随机游走的谱混合性质。因此，如果 $G_n$ 的特征值比例至多为 $\rho$，那么 $G_{f,n}$ 也满足相同或更好的特征值比例界。

参数选择

替代分析允许使用一族显式构造的扩展图 ${G_n}$，其度数为 $18$，并且特征值比例小于 $\frac{1}{2}$。既然特征值比例本身已经小于 $\frac12$，就不需要再取多步路径图，因此可以直接令 $\ell=1$。

此时若取 $k(n)=3n$，则路径命中概率变为：

$$\beta(15n) \approx 1-\left(1-\frac{\alpha(n)}{2}\right)^{3n}$$

相应地，时间函数满足：

$$T'(15n) \approx \frac{(\varepsilon(n)\alpha(n))^2}{O(n)^3}\cdot T(n)$$

需要注意的是，这里的 $15n$ 的不是精确常数，而是强调输入长度仍然只是 $O(n)$。因为 $F_k$ 的输入由初始点 $x$ 和 $k(n)$ 个边标签组成，当图的度数是常数时，每个标签只需要常数比特表示，所以总输入长度仍然是线性的。

放大效果

在这种更紧的分析下，当 $\alpha(n)\leq \frac{1}{2n}$ 时，有：

$$\beta(15n)>1.02n\cdot \alpha(n)$$

也就是说，如果原函数 $f$ 的困难输入比例只有大约 $\alpha(n)$，那么构造后的函数 $F_k$ 的困难比例可以被放大到至少线性倍数规模。

而如果 $\alpha$ 是一个正常数，则有：

$$\beta(15n)>1-2^{-\Omega(n)}$$

这表示：如果原函数 $f$ 已经在常数比例的输入上难以反演，那么经过构造后，$F_k$ 将在几乎所有输入上难以反演。

实例

取 $n=1000$，并令 $k\approx 960$，若原函数 $f$ 在长度为 $1000$ 的字符串中，有 $1%$ 的输入在实际中难以反演，那么构造出的 $F_k$ 可以做到：在长度约为 $5000$ 的输入中，有 $99%$ 的输入在实际中难以反演。

这个例子说明，高效放大的作用非常直观，使原来的 $1\%$ 难以反演放大到 $99\%$ 难以反演，并且输入长度只是从 $1000$ 增加到约 $5000$，仍然是常数倍增长，而不是平方级或更高阶的多项式增长。

【单向置换高效放大定理推出】

单向置换高效放大定理可以通过反复应用单向置换构造的困难性放大命题证明。

设原函数 $f$ 是 $\frac{1}{\mathrm{poly}(n)}$ 单向的，其中多项式 $\mathrm{poly}$ 的次数为 $\delta$，对困难性放大命题应用 $\delta+1$ 次，并且每次都取：

$$k(n)=3n$$

在前 $\delta$ 次应用中，取：

$$\varepsilon(n)=0.01$$

经过第 $i$ 次放大后，得到的函数大致具有 $\frac{1}{2n^{\delta-i}}$ 单向性。

因此，经过 $\delta$ 次放大之后，得到的函数具有大约 $\frac{1}{2}$ 单向性。也就是说，它已经在常数比例的输入上难以反演。

需要注意的是，$\frac{1}{2}$ 单向性值得单独关注，因为它表示函数在多数输入上已经表现出单向性，可以称为多数单向（Mostly One-Way）。

在最后一次，即第 $\delta+1$ 次应用困难性放大命题时，取 $\varepsilon(n)$ 为目标误差函数。由于此时原函数已经在常数比例的输入上困难，再经过一次放大，困难比例就会变成 $1-\varepsilon(n)$，从而得到强单向置换。