【归约论证的基本结构】
回顾弱单向函数的存在性定理中的证明结构：给定一个弱单向函数 $f$，首先构造一个多项式时间可计算函数 $g$，然后证明 $g$ 是强单向函数。
证明使用了归约论证（Reducibility Argument），其基本思想是：如果存在一个有效算法能够以不可忽略概率反演函数 $g$，从而否定 $g$ 的强单向性，那么就可以利用这个算法构造出一个有效算法来反演函数 $f$，从而否定 $f$ 的弱单向性。因此，只要 $f$ 的弱单向性成立，$g$ 就必须是强单向的。
需要注意的是，这里的算法变换本质上是一个随机化 Cook 归约（Randomized Cook Reduction），它并不对反演函数 $g$ 的算法结构作任何隐含或显式假设。
这里的归约论证，是为了强调它不同于标准的最坏情形复杂度归约（Worst-Case Complexity Reduction）。二者的共同点在于，它们都把求解一个问题的任务，转化为求解另一个问题的任务，即借助一个能够解决第二个问题的过程，构造出一个能够解决第一个问题的过程。
但二者的关键区别在于：
- 标准归约（Standard Reduction）：通常假设第二个问题存在一个完美求解过程，能够在所有实例上正确工作，也就是在最坏情形下也能解决问题。因此，归约可以把这个求解过程调用在非常非典型的实例上。
- 归约论证（Reducibility Argument）：不能假设第二个问题的求解过程在所有实例上都正确。这里通常只知道某个算法在某个特定分布下，以一定概率成功解决第二个任务。因此，在归约中不能随意把它调用在任意实例上。
因此，在密码学归约论证中，必须分析归约论证过程会在第二个任务上诱导出怎样的输入分布。
很多情况下，这个诱导出的分布恰好等于假设中算法能够成功的分布，在少数情况下，也可能只需要两个分布在特定意义下足够接近。
但无论是哪种情况，都必须对归约所诱导的分布进行仔细分析。
【信息论场景】
弱单向函数的存在性定理中，有一个自然的信息论类比：如果一个实验具有可察觉的失败概率，那么将这个实验重复足够多次之后，至少出现一次失败的概率会变得非常高。
但是，存在性定理的证明明显比这个信息论类比复杂得多。原因在于，在信息论场景中，重复实验之间通常按定义就是相互独立的，而在计算复杂性场景中，无法保证这种独立性。
弱单向函数的存在性定理中的朴素论证，实际上正是试图把计算场景当成独立实验来处理，但这种独立性不能被保证。
同时，二者还有一个重要区别：
- 信息论场景：如果每次实验都有一定失败概率，那么所有实验都不失败的概率会随着重复次数呈指数下降。
- 计算复杂性场景：只能得到关于多项式时间算法反演概率的某种可忽略上界，而且这个上界可能没有明确的指数形式。
具体来说，在存在性定理的证明中构造出的函数 $g$，可能仍然存在某种有效反演算法，其成功概率只是次指数地下降，例如 $2^{-(\log_2 n)^3}$。而对应的信息论界通常会是指数下降的，例如 $e^{-n}$。
因此，信息论类比只能帮助理解直觉，但不能替代计算复杂性场景中的正式证明。
