【在部分长度上定义的单向函数】
基本思想
单向函数默认定义在整个字符串集合上，即：
但在很多情况下，考虑定义域是所有二进制集合的一个子集的单向函数，会更加方便。也就是说，单向函数不一定要定义在所有长度的字符串上，可以只定义在某些特定长度的字符串上，以便于在定义域中引入某些结构
一种特别重要的情形是，函数的定义域为：
其中，$l(\cdot)$ 是某个多项式。此时，单向函数只在长度属于某个多项式形式的字符串集合上定义
长度集合与后继函数
设 $I\subseteq \mathbb{N}$ 是一个自然数集合，用 $s_I(n)$ 表示 $n$ 关于集合 $l$ 的后继（Successor），即：
也就是说，$s_I(n)$ 是集合 $I$ 中大于 $n$ 的最小整数
如果存在一个算法，使得该算法在输入 $n$ 后，能够在 $\mathrm{poly}(n)$ 的时间内停机，并输出：
那么则称集合 $I$ 是多项式时间可枚举的（Polynomial-time-enumerable）
这里要求输出的是一元形式 $1^{s_I(n)}$，因为算法必须在多项式时间内输出这么长的字符串，所以输出长度本身不能超过多项式规模。因此，这一要求隐含地保证了：
也就是说，集合 $I$ 中下一个可用长度不会距离当前长度太远
指定长度集合上的单向函数
设 $I$ 是一个多项式时间可枚举的集合，函数 $f$ 的定义域为 $\bigcup\limits_{n\in I}\{0,1\}^{n}$，即 $f$ 只在长度属于集合 $I$ 上的二进制串上定义。如果 $f$ 是多项式时间可计算的，且在所有属于 $I$ 的长度 $n$ 上都难以求逆函数，那么 $f$ 就是在长度集合 $I$ 上的强单向函数或弱单向函数
以强单向函数为例，其困难性条件可表述为：对于任意概率多项式时间算法 $A’$，任意正多项式 $\mathrm{poly}(\cdot)$，以及所有充分大的 $n\in I$，都有
其中，$U_n$ 是在 $\{0,1\}^n$ 上均匀选取的随机变量。该式表明，即使给定 $f(U_n)$ 和长度信息 $1^n$，任何高效算法成功找到一个原像的概率也只能是可忽略的
普通单向函数可以看作上述定义的特殊情形，即强单向函数与弱单向函数中定义的普通单向函数等价于在长度集合 $I=\mathbb{N}$ 上的单向函数
部分长度单向函数构造普通单向函数
定义在某些特定长度集合 $I$ 上的单向函数，可以转化为定义在所有二进制串集合 $\{0,1\}^{*}$ 上的普通单向函数
设函数 $f$ 的定义域为 $\bigcup\limits_{n\in I}\{0,1\}^n$，则可以构造一个函数 $g:\{0,1\}^{*}\to \{0,1\}^{*}$，定义为：
其中，$x’$ 是 $x$ 的最长前缀，且 $|x’|\in I$
也就是说，对于任意输入 $x$，即使它的长度不属于 $I$，也可以从它前面截取一个长度属于 $I$ 的最长前缀 $x’$，然后将 $f$ 作用在这个前缀上，这样就把原来只在部分长度上定义的函数 $f$，扩展成了一个定义在所有字符串上的函数 $g$
进一步，如果原函数 $f$ 是长度保持的，那么还可以构造一个长度保持的函数 $g’$，即：
其中，$x’$ 是 $x$ 中长度属于 $I$ 的最长前缀，$x’’$ 是剩余部分，即 $x=x’x’’$
由于 $f$ 是长度保持的，所以 $|f(x’)|=|x’|$，因此：
所以 $g’$ 也是长度保持的
由此，具有如下命题：
Proposition：设 $I$ 是一个多项式时间可枚举集合，并且函数 $f$ 在长度集合 $I$ 上是强单向的或弱单向的。那么，前面定义的两个函数：
以及
在普通意义下也是强单向函数或弱单向函数。其中，$x’$ 是 $x$ 中长度属于 $I$ 的最长前缀，且在第二个定义中有 $x=x’x’’$
也就是说，如果函数 $f$ 只在某些特定长度上难以求逆函数，那么通过上述方式扩展得到的 $g$ 和 $g’$，在所有二进制串 $\{0,1\}^{*}$ 上仍然难以求逆函数
【可归约性论证】
证明思想
假设函数 $g$ 可以被某个高效算法以不允许的成功概率求逆函数，那么就可以利用这个算法构造出另一个高效算法，用来以不允许的成功概率对函数 $f$ 求逆，这就与 $f$ 在长度集合 $I$ 上是单向函数的假设矛盾
换句话说，证明要说明：对函数 $f$ 求逆可以被高效地归约为对函数 $g$ 求逆
这里的归约比通常意义下的归约更强，因为它不仅要保证算法可以被高效模拟，还要保证求逆函数成功概率能够被适当地保留下来
也就是说，如果存在高效算法能够以不可忽略概率对函数 $g$ 求逆，那么由它构造出的算法也能够以不可忽略概率对函数 $f$ 求逆。由于这与 $f$ 的单向性假设矛盾，因此 $g$ 也必须保持求逆困难性
多项式时间可计算性
证明函数 $g$ 和 $g’$ 都可以在多项式时间内计算
采用直接证明：
由于 $I$ 是多项式时间可枚举的，那么给定 $n$，可以在多项式时间内计算 $s_I(n)$。进一步地，可以在多项式时间内判断一个整数 $m$ 是否属于 $I$，即：
也就是说，如果 $m-1$ 在集合 $I$ 中的后继正好是 $m$，那么 $m$ 就属于 $I$
因此，对于任意输入 $x$，可以在多项式时间内找到满足如下条件的最大整数 $m$：
找到 $m$ 后，取 $x$ 的前 $m$ 位作为 $x’$，然后计算 $f(x’)$，即可得到 $g(x)=f(x)$。同理，对于 $g’$，只需要保留剩余后缀 $x’’$，并输出 $g’(x)=f(x’)x’’$
因此，只要 $f(x)$ 是多项式时间可计算的，$g(x)$ 和 $g’(x)$ 也是多项式时间可计算的
求逆困难性
接下来证明函数 $g$ 保留了函数 $f$ 的求逆困难性，函数 $g’$ 的证明类似。同时，只讨论 $f$ 是强单向函数的情形，弱单向函数的情形可以用类似方式证明
证明思路
采用反证法
原命题是函数 $g$ 保留了函数 $f$ 的求逆困难性，假设命题不成立，即存在一个概率多项式时间算法 $B’$，它可以以不可忽略的成功概率对函数 $g$ 求逆，也就是说，给定 $y=g(x)$ 和长度信息 $1^m$，算法 $B’$ 能够以不可忽略的概率输出某个 $z\in g^{-1}(y)$
进一步，利用 $B’$ 构造一个概率多项式时间算法 $A’$，使得 $A’$ 可以以不可忽略的成功概率对函数 $f$ 求逆，即在输入 $y=f(x’)$ 和长度信息 $1^n$ 时，输出某个 $x’\in f^{-1}(y)$
那这就与函数 $f$ 在长度集合 $I$ 上是强单向函数的假设矛盾，原命题成立
这个归约的关键是：当输入长度属于 $I$ 时，函数 $g$ 与 $f$ 的行为是一致的
更一般地，如果 $n\in I$，并且输入字符串可以写成 $x=x’x’’$，且 $|x’|=n$，$|x’’|$ 不超过下一个属于 $I$ 的长度之前的间隔，那么 $x’$ 仍然是 $x$ 中长度属于 $I$ 的最长前缀，因此：
这意味着，如果能够对函数 $g$ 求逆，即给定 $y$ 找到某个满足 $g(z)=y$ 的原像 $z$，那么就有可能从 $z$ 中取出长度为 $n$ 的前缀，从而得到 $f$ 的一个原像。也就是说，对函数 $f$ 求逆可以归约为对函数 $g$ 求逆
证明
对函数 $f$ 求逆到对函数 $g$ 求逆的归约
算法 $A’$ 的输入为 $(y,1^n)$，其中 $y$ 来自 $f(U_n)$，且 $n\in I$。对于任意：
长度为 $m$ 的随机串 $U_m$ 的前 $n$ 位服从 $\{0,1\}^{n}$ 上的均匀分布，并且由于在区间 $n,\dots,s_I(n)-1$ 内不存在新的属于 $I$ 的长度，所以 $U_m$ 中长度属于 $I$ 的最长前缀正好是前 $n$ 位。因此，$g(U_m)$ 与 $f(U_n)$ 具有相同分布
换句话说，函数 $g$ 作用在长度为 $m$ 的随机串上时，本质上就是对其前 $n$ 位应用函数 $f$
于是，$A’$ 可以调用函数 $g$ 的求逆算法 $B’$，尝试在不同长度 $m$ 上求逆 $y$。如果 $B’$ 返回一个长度为 $m$ 的字符串 $z$，并且满足 $g(z)=y$，那么 $A’$ 取 $z$ 的长度为 $n$ 的前缀作为函数 $f$ 的原像
此时的问题在于：$m$ 应该如何选取？
由于 $I$ 是多项式时间可枚举的，所以：
因此，从 $n$ 到 $s_I(n)-1$ 的所有长度数量仍然是多项式级别，可以全部进行枚举以选取合适的 $m$
求逆算法 $A’$ 的构造
在此基础上，给定一个对函数 $g$ 求逆的算法 $B’$，构造一个对函数 $f$ 求逆的算法 $A’$
在输入 $y$ 和 $1^n$ 时，$y$ 被认为来自 $f(U_n)$，并且 $n\in I$，算法 $A’$ 执行如下步骤：
（1）计算 $s_I(n)$，并令：
此时，对于所有 $i=1,\dots,k$，都有 $n+i\notin I$
（2）对于每个 $i=0,1,\dots,k$，算法 $A’$ 调用 $B’$：
如果 $g(z_i)=y$，则 $A’$ 输出 $z_i$ 的长度为 $n$ 的前缀
$A’$ 的正确性分析
下面说明上述算法 $A’$ 的输出确实是函数 $f$ 的合法原像，并且 $A’$ 仍然是概率多项式时间算法
在长度区间 $n,n+1,\dots,s_I(n)-1$ 之内，唯一属于 $I$ 的相关前缀长度就是 $n$，那么 $x’x’’$ 中长度属于 $I$ 的最长前缀是 $x’$。因此，对于任意 $x’\in \{0,1\}^n$，以及任意满足 $|x’’|\leq k$ 的字符串 $x’’$，都有：
所以，如果算法 $B’$ 返回的某个 $z_i$ 满足 $g(z_i)=y$，那么由于 $z_i$ 的长度为 $n+i$，且 $0\leq i\leq k$，所以 $z_i$ 中长度属于 $I$ 的最长前缀就是其前 $n$ 位。取 $z_i$ 的前 $n$ 位，记为 $x’$，则由 $g$ 的定义可得：
因此，$A’$ 输出的是 $f$ 的合法原像
又因为 $s_I(n)=\mathrm{poly}(n)$，并且 $s_I(n)$ 可以在多项式时间内计算，所以 $k=s_I(n)-n-1$ 也是多项式规模。算法 $A’$ 只需要对 $i=0,1,\dots,k$ 进行多项式次数的枚举，并在每次枚举中调用一次 $B’$。因此，如果 $B’$ 是概率多项式时间算法，那么 $A’$ 也仍然是概率多项式时间算法
矛盾推出
上一节已经说明，算法 $A’$ 的输出是函数 $f$ 的合法原像，且当 $B’$ 是概率多项式时间算法时，$A’$ 也是概率多项式时间算法。那么，只需要说明：如果 $B’$ 能够以不可忽略概率对函数 $g$ 求逆，那么 $A’$ 也能够以不可忽略概率对函数 $f$ 求逆，原命题即可得证
设 $B’$ 在输入 $(g(U_m),1^m)$ 时成功对函数 $g$ 求逆的概率为 $\varepsilon(m)$，由于整数可以按照如下形式被划分为若干区间：
其中，每个区间对应某个 $n\in I$，所以任意长度 $m\in\mathbb{N}$ 都会落入某个这样的区间。也就是说，对于某个 $n\in I$，有：
在这种情况下，算法 $A’$ 在输入 $(f(U_n),1^n)$ 时，会枚举到长度 $m$，并调用
而在该长度区间内，$g(U_m)$ 与 $f(U_n)$ 具有相同分布。换言之，这次调用等价于让 $B’$ 在输入 $(g(U_m),1^m)$ 上进行求逆。因此，$A’$ 至少能够继承 $B’$ 在长度 $m$ 上的成功概率
也就是说，若 $B’$ 在无限多个长度 $m$ 上以不可忽略概率成功对函数 $g$ 求逆，那么 $A’$ 也会在无限多个长度 $n\in I$ 上以不可忽略概率成功对函数 $f$ 求逆，这与 $f$ 在长度集合 $I$ 上是强单向函数的假设矛盾
因此，不存在这样的高效算法 $B’$，所以 $g$ 也是强单向函数
成功概率分析的严格化
下面，对矛盾推出进行更严格的成功概率分析
反设与长度集合
反设命题不成立，即：函数 $g$ 不是强单向函数
那么，存在一个概率多项式时间算法 $B’$，以及一个多项式 $\mathrm{poly}(\cdot)$，使得对于无限多个长度 $m$，算法 $B’$ 在输入 $(g(U_m),1^m)$ 时能够以至少 $\frac{1}{\mathrm{poly}(m)}$ 的概率成功对函数 $g$ 求逆
记这些长度构成的集合为 $M$，则对所有 $m\in M$，都有：
但是，$f$ 的单向性只定义在长度集合 $I$ 上，而攻击长度 $m$ 是普通长度，未必属于 $I$。因此，不能直接说 $B’$ 在长度 $m$ 上攻击 $g$ 成功，就立刻推出存在一个算法在同一长度 $m$ 上攻击 $f$ 成功
为了解决长度对应问题，需要把每个普通长度 $m$ 映射回一个属于 $I$ 的合法长度，定义函数：
这里为了避免和集合 $I$ 混淆，将 $I(m)$ 记为 $\ell(m)$，它表示不超过 $m$ 的、属于集合 $I$ 的最大长度
显然，对任意 $m$，都有 $\ell(m)\leq m$ 且 $m\leq s_I(\ell(m))-1$，因此任意长度 $m$ 都落在某个由 $\ell(m)\in I$ 决定的区间中：
进一步，考虑这个长度对应关系为什么能够把 $B’$ 对 $g$ 的攻击转化为 $A’$ 对 $f$ 的攻击。令 $n=\ell(m)$，则有：
根据算法 $A’$ 的构造，当 $A’$ 在输入 $(f(U_n),1^n)$ 时，它会枚举所有长度 $n,n+1,\dots,s_I(n)-1$，并在每个长度 $t$ 上调用 $B’(f(U_n),1^t)$。由于 $m$ 正好落在这个区间中，所以 $A’$ 一定会枚举到长度 $m$，并调用 $B’(f(U_n),1^m)$
另一方面，在这个长度区间内，长度为 $m$ 的随机串 $U_m$ 的前 $n$ 位服从 $\{0,1\}^n$ 上的均匀分布，并且其长度属于 $I$ 的最长前缀正好是前 $n$ 位。因此，$g(U_m)$ 与 $f(U_n)$ 具有相同分布
所以，$A’$ 调用 $B’(f(U_n),1^m)$，本质上等价于让 $B’$ 在输入 $(g(U_m),1^m)$ 上对函数 $g$ 求逆
这就说明，如果 $B’$ 在长度 $m$ 上能够成功对函数 $g$ 求逆，那么 $A’$ 在对应的合法长度 $n=\ell(m)$ 上就能够继承这次成功
断言一
Claim：$A’$ 至少继承 $B’$ 的成功概率
令 $m$ 是任意整数，并令 $n=\ell(m)$，根据 $\ell(m)$ 的定义，$n$ 是不超过 $m$ 的最大合法长度，因此有：
这说明长度 $m$ 落在算法 $A’$ 需要枚举的长度区间中
根据算法 $A’$ 的构造，当输入为 $(f(x’),1^n)$ 时，算法 $A’$ 会依次调用 $B’(f(x’),1^t)$，其中 $t\in\{n,\dots,s_I(n)-1\}$。由于 $m$ 正好属于这个区间，所以 $A’$ 一定会调用到 $B’(f(x’),1^m)$
另一方面，对任意 $x’’\in\{0,1\}^{m-n}$，字符串 $x’x’’$ 的长度属于 $I$ 的最长前缀就是 $x’$，因此：
这说明，$B’$ 在输入 $(g(U_m),1^m)$ 上对函数 $g$ 求逆的过程，可以被看作是在输入 $(f(U_n),1^m)$ 上寻找某个原像。若 $B’$ 成功输出 $g(U_m)$ 的一个原像，那么 $A’$ 在输入 $(f(U_n),1^n)$ 时，也能够通过取该原像的前 $n$ 位，得到 $f(U_n)$ 的一个合法原像
因此，$B’$ 在长度 $m$ 上的每一次成功，都可以转化为 $A’$ 在长度 $n=\ell(m)$ 上的一次成功。所以，算法 $A’$ 在长度 $n=\ell(m)$ 上对函数 $f$ 求逆的成功概率，至少不低于算法 $B’$ 在长度 $m$ 上对函数 $g$ 求逆的成功概率，即：
所以，$A’$ 的成功概率至少不低于 $B’$ 在对应长度上的成功概率
断言二
Claim：长度 $m$ 受 $\ell(m)$ 多项式控制
断言一已经说明，算法 $B’$ 在长度 $m$ 上的成功可以转化为算法 $A’$ 在长度 $n=\ell(m)$ 上的成功。接下来还需要保证长度 $m$ 不会比对应的合法长度 $\ell(m)$ 大得过分
这是因为强单向性的成功概率需要按照输入长度来衡量，如果 $m$ 相对于 $\ell(m)$ 过大，那么即使 $B’$ 在长度 $m$ 上具有不可忽略的成功概率，也不一定能够推出 $A’$ 在长度 $\ell(m)$ 上具有不可忽略的成功概率。因此，需要证明 $m$ 可以被 $\ell(m)$ 的某个多项式上界控制
由于 $I$ 是多项式时间可枚举的，所以存在某个多项式 $\mathrm{poly}’(\cdot)$，使得对所有 $n\in I$，都有：
又因为 $\ell(m)$ 是不超过 $m$ 的最大合法长度，所以 $m$ 一定小于 $\ell(m)$ 的下一个合法长度，即：
于是有：
因此，存在某个多项式 $\mathrm{poly}’(\cdot)$，使得对所有 $m$ 都有：
这说明，普通长度 $m$ 与其对应的合法长度 $\ell(m)$ 之间只相差多项式规模，即长度从 $m$ 转换到 $\ell(m)$ 时，不可忽略成功概率不会因为输入长度的改变而消失
无限多个成功长度的传递
由上述的形式化部分可以知道，$B’$ 在集合 $M$ 中的无限多个长度 $m$ 上，可以以不可忽略概率成功对函数 $g$ 求逆。但是，为了推出函数 $f$ 不是强单向函数，需要说明这些长度 $m$ 对应到长度集合 $I$ 后，仍然能够得到无限多个合法长度
为此，定义集合 $S$ 表示那些由 $M$ 中的长度 $m$ 映射得到的、属于 $I$ 的合法长度：
根据断言二，$S$ 必须是无限集合。否则，如果 $S$ 是有限集合，那么存在一个上界 $\mu$，使得对所有 $\ell(m)\in S$，都有：
于是，对所有 $m\in M$，都有：
这意味着 $M$ 中所有元素都被常数 $\mathrm{poly}’(\mu)$ 这一上界控制，因此 $M$ 只能是有限集合，与 $M$ 是无限集合矛盾。
所以，$S$ 必须是无限集合
成功概率不可忽略性的传递
上一节已经说明，集合 $S$ 是无限集合。也就是说，$B’$ 在无限多个普通长度 $m\in M$ 上的成功，可以对应到无限多个合法长度 $n\in I$ 上。那么，只需要说明在这些合法长度 $n$ 上，算法 $A’$ 对函数 $f$ 求逆的成功概率仍然是不可忽略的，即可证明函数 $g$ 必须是强单向函数
任取一个长度 $n\in S$，根据 $S$ 的定义，存在某个 $m\in M$，使得：
由于 $m\in M$，根据反设中对 $M$ 的定义，算法 $B’$ 在长度 $m$ 上成功对函数 $g$ 求逆的概率至少为 $\frac{1}{\mathrm{poly}(m)}$，再根据断言一，算法 $A’$ 在长度 $n=\ell(m)$ 上成功对函数 $f$ 求逆的概率至少不低于算法 $B’$ 在长度 $m$ 上成功对函数 $g$ 求逆的概率。因此：
进一步，根据断言二，有：
由于 $\mathrm{poly}(\cdot)$ 是正多项式，可以不失一般性地假设其单调递增，因此：
因此，算法 $A’$ 在每个 $n\in S$ 上都能以至少 $\frac{1}{\mathrm{poly}(n)}$ 级别的概率成功对函数 $f$ 求逆，又因为 $S$ 是无限集合，所以 $A’$ 在无限多个合法长度 $n\in I$ 上都能以不可忽略概率成功对函数 $f$ 求逆，这与函数 $f$ 在长度集合 $I$ 上是强单向函数的假设矛盾
因此，反设不成立，函数 $g$ 必须是强单向函数
长度保持情形下的证明
对于长度保持版本的单向函数 $g’(x)=f(x’)x’’$，其证明方法与函数 $g$ 的证明类似
如果能够高效对函数 $g’$ 求逆，那么也可以利用该算法构造出对函数 $f$ 求逆的算法。因为在 $g’$ 的输出中，$f(x’)$ 仍然是由 $f$ 作用在最长合法前缀 $x’$ 上得到的，而后缀 $x’’$ 只是为了保持整体长度不变。因此，函数 $g’$ 的求逆同样会暴露出可以用来恢复 $f$ 原像前缀的信息
所以，$g’$ 也保持了 $f$ 的强单向性或弱单向性
