【通用单向函数】

利用通用机（Universal Machine）的概念，以及弱单向函数可以转化为强单向函数的命题，可以证明存在一种通用单向函数（Universal One-Way Function）。

通用不是指它无条件单向，而是指存在一个固定的、多项式时间可计算的函数 $f_{\mathrm{uni}}$，只要世界上存在单向函数，那么这个固定函数 $f_{\mathrm{uni}}$ 就是单向函数。

由此，具有如下命题：

Proposition：存在一个多项式时间可计算函数，它是强单向函数，当且仅当单向函数存在。

【证明】

固定时间上界

针对上述命题，首先考虑时间上界不统一的问题。虽然任意单向函数都可以在多项式时间内计算，但不同函数对应的多项式时间上界可能不同。如果直接处理所有多项式时间可计算的单向函数，后续就很难用一个统一的固定构造来覆盖它们。因此，需要先把这些单向函数规范到某个固定的计算时间范围内。

为此，将多项式时间考虑为二次时间（Quadratic Time），那么证明的第一步就是要说明：单向函数存在，当且仅当存在可以在二次时间内计算的单向函数。

需要注意的是，这里具体选择的二次时间并不重要，重要的是存在某个固定的时间上界。

设 $f$ 是任意一个单向函数，计算 $f$ 的算法时间复杂度由某个多项式 $\mathrm{poly}(\cdot)$ 上界。定义函数：

$g(x'x'')=f(x')x''$

其中，输入被分解为 $x’$ 和 $x’’$，并满足 $|x’x’’|=\mathrm{poly}(|x’|)$。$x’’$ 的作用相当于填充输入长度，使得总输入长度等于计算 $f(x’)$ 所需的多项式时间上界。

在计算函数 $g$ 时，算法先把输入解析为 $x’$ 和 $x’’$，使得 $|x’x’’|=\mathrm{poly}(|x’|)$，然后计算 $f(x’)$，最后输出 $f(x’)x’’$。在这个过程中，解析和其他额外操作可以在关于总输入长度 $|x’x’’|$ 的二次时间内完成，而计算 $f(x’)$ 的时间为 $\mathrm{poly}(|x’|)=|x’x’’|$，即相对于新输入长度是线性的。

因此，函数 $g$ 可以在二次时间内计算。

同时，$g$ 仍然是单向函数。直观上，如果存在有效算法能够反演 $g(x’x’’)=f(x’)x’’$，那么就可以从它的输出中得到 $x’$，从而反演 $f(x’)$，这会违反 $f$ 的单向性。所以，单向函数存在时，也存在二次时间可计算的单向函数。

通用单向函数的构造

在上述过程中，已经说明可以只考虑二次时间可计算的单向函数，因此下面只需要构造一个能够统一模拟二次时间机器的固定函数即可。

定义通用函数：

$f_{\mathrm{uni}}(\operatorname{desc}(M),x)=(\operatorname{desc}(M),M(x))$

其中，$\operatorname{desc}(M)$ 是图灵机 $M$ 的描述。$M(x)$ 的定义如下：

如果 $M$ 在输入 $x$ 上的运行时间不超过二次时间，那么 $M(x)$ 就是 $M$ 在输入 $x$ 上的输出
如果 $M$ 在输入 $x$ 上没有在二次时间内停止，那么规定 $M(x)=x$

由此，可以不失一般性地认为，每一个字符串都可以看作某台图灵机的描述。

由于通用机只需要模拟 $M$ 在输入 $x$ 上的二次时间运行过程，并使用计步器检查其是否超过二次时间上界。如果超过该上界，就直接输出 $x$。因此，函数 $f_{\mathrm{uni}}$ 可以由通用机在多项式时间内计算，即 $f_{\mathrm{uni}}$ 是一个固定的、多项式时间可计算函数。

通用单向函数的弱单向性

下面，只需要证明：只要单向函数存在，$f_{\mathrm{uni}}$ 至少是弱单向函数

将通用单向函数 $f_{\mathrm{uni}}$ 的第一个输入固定为某个二次时间单向函数 $g$ 的机器描述 $\operatorname{desc}(M_g)$，即 $M_g$ 是计算 $g$ 的二次时间图灵机。由于 $M_g$ 在二次时间内计算 $g$，所以对于任意输入 $x$，有：

$f_{\mathrm{uni}}(\operatorname{desc}(M_g),x) = (\operatorname{desc}(M_g),g(x))$

也就是说，当 $f_{\mathrm{uni}}$ 的第一个输入固定为 $\operatorname{desc}(M_g)$ 时，$f_{\mathrm{uni}}$ 的行为本质上就是在计算 $g$，只不过在输出中额外保留了机器描述 $\operatorname{desc}(M_g)$。因此，如果存在一个有效算法能够反演 $f_{\mathrm{uni}}$ 在这类输入上的输出，那么就可以直接把它改造成一个反演 $g$ 的有效算法。

具体地说，设某个算法在长度为 $|\operatorname{desc}(M_g)|+n$ 的输入上，能够以至少 $1-\varepsilon(n)$ 的概率反演 $f_{\mathrm{uni}}$，由于固定前缀 $\operatorname{desc}(M_g)$ 的长度是 $|\operatorname{desc}(M_g)|$，这一前缀在所有同长度前缀中只占 $2^{-|\operatorname{desc}(M_g)|}$ 的比例。因此，即使把全部失败概率都集中到这个固定前缀对应的输入集合上，该集合的条件失败概率也至多为：

$2^{-|\operatorname{desc}(M_g)|}\cdot \varepsilon(n)$

于是，可以得到一个算法在长度为 $n$ 的输入上，以至少：

$1-2^{|\operatorname{desc}(M_g)|}\cdot \varepsilon(n)$

的概率能够反演 $g$。

需要注意的是，由于 $M_g$ 只依赖于固定的函数 $g$，而不随安全参数 $n$ 增长。因此，$|\operatorname{desc}(M_g)|$ 是一个常数，故而乘上常数因子 $2^{|\operatorname{desc}(M_g)|}$ 不会改变失败概率是否可察觉。

所以，如果 $f_{\mathrm{uni}}$ 不是弱单向函数，也就是说存在有效算法能够以过高概率反演 $f_{\mathrm{uni}}$，那么上述构造就会得到一个有效算法，使其也能够以过高概率反演 $g$，这与 $g$ 是单向函数矛盾。

因此，只要单向函数存在，$f_{\mathrm{uni}}$ 至少是弱单向函数。

矛盾推出

通过上述证明，可以得到如下证明转换过程：

任意单向函数可规范化为二次时间可计算的单向函数
构造一个能够模拟二次时间机器的多项式时间可计算的通用函数 $f_{\mathrm{uni}}$
$f_{\mathrm{uni}}$ 至少是弱单向函数

根据弱单向函数的存在性定理，任何弱单向函数都可以转化为强单向函数。

因此，命题得证。

【构造的意义与限制】

上述构造的关键在于，只需要考虑某个固定时间上界内可计算的单向函数。

但是，对于每一个固定多项式 $\mathrm{poly}(\cdot)$，可以构造一个多项式时间机器，通用地模拟所有运行时间由 $\mathrm{poly}(\cdot)$ 上界的机器。

不过，函数 $f_{\mathrm{uni}}$ 的构造并不实用，它可能只有在非常大的输入长度上才难以反演，因为输入中需要包含非平凡算法的编码，而这些编码本身可能已经很长。

此外，为了从 $f_{\mathrm{uni}}$ 得到强单向函数，还需要对它应用前一节的弱到强转换。具体来说，需要在超过 $2^L$ 个输入上使用 $f_{\mathrm{uni}}$，其中每个输入长度为 $L+n$，$L$ 是潜在单向函数编码长度的下界，$n$ 是实际安全参数。

因此，这种转换在效率上非常不实际。