强单向函数与弱单向函数

【强单向函数】

定义

若函数 $f:\{0,1\}^{*} \to \{0,1\}^{*}$ 满足：

（1）容易计算：存在一个确定性多项式时间算法 $A$，使得对于任意输入 $x$，算法 $A$ 都能输出 $f(x)$，即：

$$A(x) = f(x)$$

（2）难以反演：对于任意概率多项式时间算法 $A’$，任意正多项式 $\mathrm{poly}(\cdot)$ 以及所有充分大的 $n$，都有：

$$P[A'(f(U_n),1^n) \in f^{(-1)}(f(U_n)) ] < \frac{1}{\mathrm{poly}(n)}$$

则称该函数被称为强单向函数（Strong One-way Function）。其中，$U_n$ 表示 $\{0,1\}^{n}$ 上均匀分布的随机变量

需要注意的是，如果 $f(x)$ 是单射函数，那么 $x$ 是唯一原像。但在一般情况下，$f(x)$ 未必是单射函数，同一函数值可能对应多个原像。因此，反演算法 $A’$ 不一定要输出最初的输入 $x$ 本身，其只需要输出任意一个原像就算反演成功，即只要输出某个 $x’$，满足：

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

辅助输入 $1^n$ 的作用

在上述定义中，反演算法 $A’$ 的输入不仅包括函数 $f(x)$，还包括 $1^n$，这里的 $1^n$ 是用一元表示法给出的输入长度信息，其作用是告诉反演算法期望输出的原像长度

引入 $1^n$ 的主要原因，是为了排除一种不合理情况：某个函数之所以难以反演，并不是因为它真的具有计算困难性，而只是因为它把输入长度大幅压缩，导致反演算法连输出原像的时间都不够

例如，考虑函数 $f_{len}$，其将输入 $x$ 映射为 $|x|$ 的二进制表示：

$$f_{len}(x)=|x|$$

由于输出长度为 $|f_{len}(x)|=\log_2 |x|$，反演算法的运行时间只能是关于 $|f_{len}(x)|$ 多项式，它甚至没有足够时间输出长度为 $|x|$ 的原像。因此，这种难以反演并不是真正的密码学困难性，而只是由输出过短造成的形式困难

因此，在给定辅助输入 $1^{|x|}$ 后，反演算法可以在关于主输入 $f(x)$ 和目标输出长度的总长度多项式时间内运行。这样，定义就避免了把极端压缩导致无法输出误认为真正的单向性

如果函数 $f$ 是长度保持函数（Length Preserving Function），即对所有 $x$ 都有：

$$|f(x)|=|x|$$

那么辅助输入 $1^n$ 就是冗余的。更一般地，如果仅根据 $f(x)$ 就能在关于 $|x|$ 的多项式时间内生成 $1^{|x|}$，那么该辅助输入同样可以省略

反演困难性的概率空间

单向函数中的难以反演应理解为：对所有高效反演算法，其成功概率都有一个可忽略的上界

这个成功概率不是只对算法本身的随机性取概率，而是同时对两类随机性取概率：

1. 输入分布的随机性：先从 $\{0,1\}^{n}$ 中均匀随机选取 $x$，再计算 $f(x)$ 作为反演算法的输入
2. 算法内部的随机性：反演算法 $A’$ 可能是概率算法，因此它自身也有随机性

如果函数 $f$ 在 $\{0,1\}^n$ 上诱导一个置换，那么 $f(U_n)$ 仍然是在 $\{0,1\}^n$ 上均匀分布的。但一般情况下，函数 $f$ 未必是单向函数，因此 $f(U_n)$ 的分布可能与均匀分布相差很大

故而无论是哪种情况，定义都要求反演算法在上述概率空间中的成功概率是可忽略的

可忽略概率与显著概率

显著函数

在概率多项式实际模型中，介绍了可忽略函数。与其相对的，若对于任意多项式 $\mathrm{poly}(\cdot)$，均 $\exists N\in\mathbb{N}$，使得 $\forall n>N$，都有：

$$\nu(n)>\frac{1}{\mathrm{poly}(n)},\quad \nu: \mathbb{N}\to \mathbb{R}$$

则 $\nu(\cdot)$ 称为显著函数（Noticeable Function）。

可忽略概率与显著概率

单向函数定义中的成功概率必须是可忽略概率（Negligible Probability），即当输入长度 $n$ 增大时，攻击算法成功的概率必须小于任意多项式倒数。与可忽略概率相对的是显著概率（Noticeable Probability），即当输入长度 $n$ 增大时，攻击算法成功的概率必须大于任意多项式倒数

需要注意的是，一个函数可能既不是可忽略的，也不是显著的。也就是说，不可忽略与显著在这里并不完全等价，二者之间还可能存在中间情形

这种定义方式与多项式时间计算自然对应：如果一个事件以可忽略概率发生，那么即使把实验重复多项式次，它发生的概率仍然是可忽略的

因此，在密码学中，把可行计算定义为多项式时间计算，把不可接受的攻击成功率定义为非可忽略成功率，二者是相互匹配的

反演算法的碰撞概率

单向函数的定义并不是要求反演绝对不可能，而是要求任何概率多项式时间算法都不能显著优于平凡策略

随机猜测算法

考虑一个平凡算法 $A_1$​，在输入 $(y,1^n)$ 后，均匀随机地输出一个长度为 $n$ 的字符串。也就是说，它并不真正利用 $y$ 的结构，而只是随机猜测一个可能的原像 $x$

令 $U’_n$ 表示另一个独立地、均匀分布在 $\{0,1\}^n$ 上的随机变量，则 $A_1$ 的成功概率为：

$$\begin{aligned} P[A_1(f(U_n),1^n)\in f^{-1}(f(U_n))] &= P[f(U^{'}_n)=f(U_n)] \\ &= \sum_{y} P[ f(U_n)=y \wedge f(U_n^{'})=y ] \\ &= \sum_{y} P[ f(U_n)=y] P[f(U_n^{'})=y ] \\ &= \sum_{y} P[ f(U_n)=y]^2 \\ \end{aligned}$$

这个概率被称为 $f(x)$ 的碰撞概率（Collision Probability）

进一步，考虑其下界。令 $p_y=P[f(U_n)=y]$，由于 $U_n$ 均匀分布在 $\{0,1\}^{n}$ 上，而 $\{0,1\}^n$ 中共有 $2^n$ 个输入，故 $f(U_n)$ 最多有 $2^n$ 个可能的输出。为使碰撞概率 $\sum\limits_{y} p_y^2$ 尽可能小，那就应该使这些概率尽量平均。最理想的一种情况是，一共有 $2^n$ 个可能输出，每个输出的概率都是 $\frac{1}{2^n}$，此时碰撞概率为：

$$\sum\limits_{y} p_y^2=2^n \cdot (\frac{1}{2^n})^2 = 2^n \cdot \frac{1}{2^{2n}} = 2^{-n}$$

所以一般情况下必有：

$$P[A_1(f(U_n),1^n)\in f^{-1}(f(U_n))] = \sum_{y} P[ f(U_n)=y]^2 \geq 2^{-n}$$

也就是说，哪怕 $A_1$ 只是随机猜测一个与原像相同的长度的输出，它的成功概率至少是 $2^{-n}$，因此单向函数的定义不能要求反演算法成功概率等于 $0$，因为平凡随机猜测总有非零成功概率

由此可以得到三个结论：

1. 对于任意函数 $f$，随机猜测算法 $A_1$ 的成功概率都严格大于 $0$。因此，单向函数的定义不能要求所有高效算法永远反演失败
2. 如果 $f$ 是单射函数，那么 $A_1$ 反演成功的概率是可忽略的。但这并不能说明 $f$ 是单向函数，只能说明 $A_1$ 本身是一个很弱的平凡算法
3. 由于 $A_1$ 本身是一个概率多项式时间算法，它的成功概率也必须满足单向函数定义中的可忽略上界。即如果 $f$ 是单向函数，那么 $f(U_n)$ 的碰撞概率必须是可忽略的

固定输出算法

再考虑另一个平凡算法 $A_2$，其对所有相同长度的输入都输出同一个固定字符串，例如：

$$A_2(y,1^n)=0^n$$

那么，对于任意函数 $f$，该算法的成功概率为：

$$P[A_2(f(U_n),1^n)\in f^{-1}(f(U_n))] = P[f(0^n)=f(U_n)]$$

由于 $U_n$ 在 $2^n$ 个字符串中均匀随机选择，其中有 $|f^{-1}(f(0^n))|$ 个字符串满足条件，因此有：

$$P[U_n\in f^{-1}(f(0^n))] = \frac{|f^{-1}(f(0^n))|}{2^n}$$

故有：

$$P[A_2(f(U_n),1^n)\in f^{-1}(f(U_n))] = \frac{|f^{-1}(f(0^n))|}{2^n}$$

进一步，考虑其下界。按照原像集合的定义：

$$f^{-1}(f(0^n)) = \{x: f(x)=f(0^n) \}$$

显然，令 $x=0^n$，即有：

$$0^n \in f^{-1}(f(0^n))$$

因此，原像集合中至少有一个元素，故：

$$|f^{-1}(f(0^n))| \geq 1$$

于是，对于 $\frac{|f^{-1}(f(0^n))|}{2^n}$，有：

$$\frac{|f^{-1}(f(0^n))|}{2^n} \geq \frac{1}{2^n} = 2^{-n}$$

即：

$$P[A_2(f(U_n),1^n)\in f^{-1}(f(U_n))] = \frac{|f^{-1}(f(0^n))|}{2^n} \geq 2^{-n}$$

也就是说，哪怕 $A_2$ 只是固定的输出 $0^n$，它的成功概率至少是 $2^{-n}$，即在真实输入本来就是 $0^n$ 时成功。如果还有其他的 $x\neq 0^n$ 也满足 $f(x)=f(0^n)$，那么 $A_2$ 的成功概率会更大

由此，也可以得到三个结论：

1. 对于任意函数 $f$，固定输出算法 $A_2$ 的成功概率也严格大于 $0$
2. 如果 $f$ 是单射函数，那么 $A_2$ 反演成功的概率是可忽略的
3. 如果 $f$ 是单向函数，那么被 $f$ 映射到 $f(0^n)$ 的输入所占比例必须是可忽略的

【弱单向函数】

定义

若函数 $f:\{0,1\}^{*} \to \{0,1\}^{*}$ 满足：

（1）容易计算：存在一个确定性多项式时间算法 $A$，使得对于任意输入 $x$，算法 $A$ 都能输出 $f(x)$，即：

$$A(x) = f(x)$$

（2）轻微难以反演：存在一个正多项式 $\mathrm{poly}(\cdot)$，使得对任意概率多项式时间算法 $A’$，以及所有充分大的 $n$，算法 $A’$ 反演 $f(U_n)$ 的失败概率至少为 $\frac{1}{\mathrm{poly}(n)}$，即

$$P[A'(f(U_n),1^n) \notin f^{(-1)}(f(U_n)) ] > \frac{1}{\mathrm{poly}(n)}$$

则称该函数被称为弱单向函数（Weak One-way Function）。其中，$U_n$ 表示 $\{0,1\}^{n}$ 上均匀分布的随机变量

等价地，对于失败概率，可以写为成功概率的上界形式：

$$P[A'(f(U_n),1^n) \in f^{(-1)}(f(U_n)) ] < 1 - \frac{1}{\mathrm{poly}(n)}$$

需要注意的是，不是说每个算法 $A’$ 都可以有自己对应的多项式 $\mathrm{poly}_{A’}(\cdot)$，而是存在一个统一的多项式 $\mathrm{poly}(\cdot)$，可以同时约束所有高效反演算法的成功概率与失败概率

与强单向函数的区别

两者的差异主要体现在对反演成功概率的要求不同。对强单向函数来说，要求任意高效反演算法的成功概率都必须是可忽略的，即对任何概率多项式时间算法都几乎不可能成功反演

$$P[\mathrm{反演成功}] < \frac{1}{\mathrm{poly}(n)}$$

而弱单向函数不要求所有高效反演算法的成功概率都是可忽略的，只要求所有高效反演算法都会以某个显著概率失败

$$P[\mathrm{反演失败}] > \frac{1}{\mathrm{poly}(n)}$$

简单来说，强单向函数要求高效算法几乎总是失败，而弱单向函数只要求高效算法不能总是成功