【概述】
某些函数虽然在某个不可忽略比例的输入上难以反演，但在大部分输入上可能仍然容易反演，因此它只能满足弱单向性，而不能满足强单向性
但是，从存在性角度看，弱单向函数和强单向函数是等价的，即：
【弱单向函数蕴含强单向函数】
弱单向函数的构造
设函数 $f$ 是一个长度保持的单向函数，即输入和输出长度相同。现在基于 $f$ 构造一个新函数 $g$。对输入 $(x,r)$，定义：
其中，$|x|=|r|$，$r$ 是一个二进制控制字符串，用来决定函数 $g$ 是否调用函数 $f$
这个构造的核心思想是：函数只在少量输入上调用单向函数 $f$，而在绝大多数输入上直接表现为恒等函数。因此，函数 $g$ 的反演难度只来自于那一小部分真正调用函数 $f$ 的输入
具体来说，考虑长度为 $2n$ 的输入 $(x,r)$，其中 $|x|=|r|=n$。函数 $g$ 只在 $r$ 的前 $\log_2 n$ 位全为 $0$ 时，才会计算 $f(x)$。随机选择 $r\in \{0,1\}^n$ 时，这一事件发生的概率为：
因此，在所有长度为 $2n$ 的输入中，只有大约 $\frac{1}{n}$ 的输入才会触发函数 $f$，在剩下的 $1-\frac{1}{n}$ 的输入上，函数是恒等映射，即 $g(x,r)=(x,r)$
由此可以看出，函数 $g$ 不可能是强单向函数。因为对绝大多数输入来说，对函数 $g$ 反演非常容易：当函数 $g$ 等于恒等映射时，反演算法只需要直接输出收到的值，就可以得到一个合法原像。也就是存在一个简单反演策略，能够在至少 $1-\frac{1}{n}$ 比例的输入上成功对函数 $g$ 反演。这与强单向函数要求任意高效算法只能以可忽略概率成功反演的条件相矛盾
但是，函数 $g$ 可以是弱单向函数。原因在于：虽然函数 $g$ 在大部分输入上容易反演，但它在 $\frac{1}{n}$ 比例的输入上继承了函数 $f$ 的反演困难性。由于 $\frac{1}{n}$ 不是可忽略量，所以这部分困难输入足以使 $g$ 满足弱单向性的要求
更具体地说，在触发函数 $f$ 的输入上，有：
此时若要对 $g$ 反演，就必须从 $f(x)$ 中恢复出某个 $x’\in f^{-1}(f(x))$，这本质上就是在对 $f$ 反演。因此，任何能够在这部分输入上有效反演 $g$ 的算法，都可以被用来构造一个反演 $f$ 的算法
所以，证明函数 $g$ 是弱单向函数，可以采用归约论证（Reducibility Argument）：
假设函数 $g$ 不是弱单向函数，那么存在概率多项式时间能够以非常高的概率对 $g$ 反演
由于 $g$ 在 $1-\frac{1}{n}$ 比例的输入上本来就容易反演，若该算法的成功概率明显高于这一基准，则它必须在一部分触发函数 $f$ 的输入上也成功
因此，可以利用它构造一个算法对函数 $f$ 反演，从而推出函数 $f$ 也不是弱单向函数
这与假设 $f$ 是弱单向函数矛盾
因此，函数 $g$ 具有一种弱但不强的性质：它不是强单向函数，因为它在绝大多数输入上容易反演；但它仍然是弱单向函数，因为它在不可忽略比例的输入上保留了函数 $f$ 的反演困难性
弱单向性的证明
命题
由上述构造方式，可以得到一个命题：
Proposition：若函数 $f$ 是一个单向函数，即使只是弱意义下的单向函数，那么由上述方式构造出的函数 $g$ 也是弱单向函数
这个命题的证明思路是：假设存在一个概率多项式时间算法 $B’$ 可以很好地反演函数 $g$，那么可以利用 $B’$ 构造另一个概率多项式时间算法 $A’$ 来反演函数 $f$
证明
归约算法的构造
给定一个用于反演 $g$ 的概率多项式时间算法 $B’$，构造一个用于反演 $f$ 的概率多项式时间算法 $A’$
算法 $A’$ 在输入 $y$ 时，执行如下步骤：
- 令 $n=|y|$，并令 $l=\log_2 n$
- 从 $\{0,1\}^{n-l}$ 中均匀随机选择一个字符串 $r’$
- 构造字符串 $0^l r’$，即前 $l$ 位为 $0$，后面接随机串 $r’$
- 计算 $z=B’(0^l r’,y)$
- 输出 $z$ 的后 $n$ 位
这个构造的含义是：算法 $A’$ 想要反演 $f(y)$，于是构造一个会触发函数 $g$ 中困难部分的输入形式，即让 $r$ 的前 $\log_2 n$ 位全为 $0$。此时，对于任意 $x\in\{0,1\}^n$，有：
因此，如果 $y=f(x)$，那么 $(0^l r’,y)$ 就是 $g$ 的某个输出。若 $B’$ 能够成功反演这个输出，那么它输出结果的后 $n$ 位就是某个 $x’\in f^{-1}(f(x))$，即：$A’$ 可以通过调用 $B’$ 来反演 $f$
关键概率关系
令 $S_{2n}$ 表示所有长度为 $2n$ 且以前 $\log_2 n$ 个 $0$ 开头的字符串集合，即：
随机选择 $U_{2n}$ 时，有：
集合 $S_{2n}$ 对应的正是函数 $g$ 会调用函数 $f$ 的那部分输入。那么，根据 $A’$ 和 $g$ 的构造，可以得到：
该不等式表示，$A’$ 反演 $f$ 的成功概率，至少等于 $B’$ 在触发 $f$ 的输入区域上反演 $g$ 的成功概率，即右边的概率为：在输入落入集合 $S_{2n}$ 的条件下，算法 $B’$ 成功反演 $g$ 的概率，故可写为：
记事件：
即 $E$ 表示 $B’$ 成功反演 $g$。由条件概率公式以及不等式：
可以将条件转为整体概率：
进一步，由于：
因此有：
将事件 $E$ 的定义带回，整理上述各不等式，有：
也就是说，如果 $B’$ 反演 $g$ 的成功概率只是接近 $1-\frac{1}{n}$，那么它可能只是利用了函数 $g$ 在大多数输入上等于恒等函数这一特性；但如果它的成功概率明显超过 $1-\frac{1}{n}$，那么超过的那部分成功率就必须来自调用函数 $f$ 的困难区域，于是这部分成功率可以被放大 $n$ 倍，从而转化为反演函数 $f$ 的成功概率
矛盾推出
由上述不等式可知，如果 $B’$ 在长度 $2n$ 上反演 $g$ 的成功概率大于：
那么 $A’$ 在长度 $n$ 上反演 $f$ 的成功概率就大于：
也就是说，$B’$ 对 $g$ 的高成功反演能力，会转化为 $A’$ 对 $f$ 的高成功反演能力
因此，如果 $g$ 不是弱单向函数，那么对于任意多项式 $\mathrm{poly}(\cdot)$，都存在无穷多个长度，使得 $g$ 可以以至少
的概率被反演。特别地，在长度 $m=2n$ 的情形下，根据上述归约可推出：存在一个概率多项式时间算法 $A’$，能够至少以
的概率反演函数 $f$。令
则上式可写为：
这意味着函数 $f$ 也可以被概率多项式时间算法以过高概率反演，从而说明函数 $f$ 不是弱单向函数
这与假设 $f$ 是弱单向函数矛盾，因此，$g$ 必须是弱单向函数
用 $\alpha(n)$ 表示反演优势
上述证明也可使用反演优势来理解
由于函数 $g$ 在 $1-\frac{1}{n}$ 比例的输入上等于恒等函数，所以任何算法即使完全不理解函数 $f$，也可能达到大约 $1-\frac{1}{n}$ 的反演成功率
因此，真正有意义的是超过这一基准的部分。若某个算法 $B’$ 在长度 $2n$ 上反演 $g$ 的成功概率为：
那么 $\alpha(n)$ 就表示它在困难区域上获得的额外反演优势。
根据上述的不等式归约证明，可以得到一个反演 $f$ 的概率多项式时间算法，其成功概率为：
所以，如果 $\alpha(n)$ 太大，就会导致 $f$ 被高概率反演，从而违背 $f$ 的弱单向性。换言之，任何高效算法反演 $g$ 时，都不能在基准成功率 $1-\frac{1}{n}$ 之上获得过大的额外优势
进一步，由于 $f$ 是弱单向函数，算法不可能以过高概率反演 $f$，因此对某个多项式 $\mathrm{poly}’(\cdot)$，必须有：
即：
因此，在任意概率多项式时间算法反演 $g$ 时，都存在一个多项式倒数级别的失败概率，即反演 $g$ 的失败概率至少为：
因此，$g$ 满足弱单向函数的定义
【存在性关系】
存在性定理
上述构造与证明说明，只要单向函数存在，就可以构造出一个弱单向但不是强单向的函数。因此，不能认为所有单向函数都是强单向函数
但是，也不能认为所有单向函数都只能是弱单向函数。事实上，弱单向函数的存在可以推出强单向函数的存在
Theorem：弱单向函数存在当且仅当强单向函数存在。
其中一个方向是直接的：如果强单向函数存在，那么弱单向函数当然存在，因为强单向性本身就是更强的反演困难性要求
但更重要的是另一个方向：如果弱单向函数存在，那么也可以通过某种困难性放大方法构造出强单向函数
