长度规则单向函数与长度保持单向函数

【长度规则函数】

定义

对于单向函数，有一个常用的约定：假设函数 $f$ 是长度规则的（Length Regular）

具体来说，对于 $\forall x,y\in\{0,1\}^{*}$，若输入长度相同，那么它们经过函数 $f$ 后的输出长度也相同，即：

$$|x|=|y| \Rightarrow |f(x)|=|f(y)|$$

则函数 $f$ 称为长度规则函数（Length Regular Function）

也就是说，长度规则函数不要求输出长度一定等于输入长度，但要求相同长度的输入必须产生相同长度的输出

单向函数的长度约束中关于部分长度单向函数 $f$ 向普通单向函数 $g$ 和 $g’$ 的转化，都会保持长度规则性

长度规则函数的构造

给定一个强单向函数或弱单向函数 $f$，由于其是多项式时间可计算的，因此其输出长度不可能超过输入长度的某个多项式界，即存在一个多项式 $\mathrm{poly}(\cdot)$，使得：

$$|f(x)|\leq \mathrm{poly}(|x|)$$

定义函数 $f’$，其先输出 $f(x)$，然后在后面补上一段形如 $10^{*}$ 的填充串，即：

$$f'(x)\overset{\mathrm{def}}{=}f(x)10^{\mathrm{poly}(|x|)-|f(x)|}$$

填充部分以一个 $1$ 开头作为分隔标记，后面接若干个 $0$，，从而方便从 $f’(x)$ 中解析出原来的 $f(x)$ 以及后面的填充部分

这个构造使得 $f’$ 对于任意长度相同的输入 $x$，填充后的输出长度都变为固定的：

$$\begin{aligned} |f'(x)| &= |f(x)| + |10^{\mathrm{poly}(|x|)-|f(x)|}| \\ &= |f(x)| + 1 + \mathrm{poly}(|x|) -|f(x)| \\ &= \mathrm{poly}(x) + 1 \end{aligned}$$

此时，函数 $f’$ 即为长度规则函数，其使得相同长度的输入会得到相同长度的输出

【长度保持函数】

定义

若对于每一个 $x\in\{0,1\}^{*}$，都有：

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

则称函数 $f$ 为长度保持函数（Length Preserving Function），其要求输入和输出的长度完全相同

需要注意的是，长度保持比长度规则更强：

1. 长度规则：只要求相同长度输入对应相同长度输出
2. 长度保持：在长度规则的基础上，要求每个输入的输出长度等于输入长度

因此，长度保持函数是长度规则函数的一个特殊情形，长度保持函数一定是长度规则函数，但长度规则函数不一定是长度保持函数

长度保持函数的构造

设输入写为 $x’x’’$，并满足：

$$|x'x''|=\mathrm{poly}(|x'|)+1$$

则可在长度规则函数 $f’$ 与长度为 $\mathrm{poly}(x) + 1$ 的字符串上定义函数：

$$f''(x'x'')\overset{\mathrm{def}}{=}f'(x')$$

由于 $f’(x’)$ 的长度正好是 $\mathrm{poly}(|x’|)+1$，而输入 $x’x’’$ 的长度也被规定为 $\mathrm{poly}(|x’|)+1$，因此：

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

即 $f’’$ 为长度保持函数

直观来说，$f’’$ 的做法是：输入虽然是一个较长字符串 $x’x’’$，但函数真正处理的只有前缀 $x’$；剩余部分 $x’’$ 的作用是把输入长度补到与 $f’(x’)$ 的输出长度一致，从而保证整个函数是长度保持的

综上所述，当给定一个普通单向函数时，可以构造出一个新的强单向函数或弱单向函数 $f’’$，并且其是长度保持的

【长度规则化与长度保持化不破坏单向性】

命题描述

上述长度规则化和长度保持化的过程，不会破坏单向函数的求逆困难性，即有命题：

Proposition：若函数 $f$ 是强单向函数或弱单向函数，那么按照上述定义得到的 $f’$ 和 $f’’$ 也分别是强单向函数或弱单向函数

多项式时间可计算性

对于函数 $f’$ 和 $f’’$，有：

• 函数 $f’$：只需要计算 $f(x)$，再根据 $\mathrm{poly}(|x|)-|f(x)|$ 补上相应长度的填充串即可
• 函数 $f’’$：只需要把输入解析为 $x’x’’$，然后计算 $f’(x’)$

由于这些操作都可以在多项式时间内完成，所以 $f’$ 和 $f’’$ 都是多项式时间可计算的

那么，只需要证明它们仍然难以求逆，即可证明上述命题

求逆困难性

证明方法单向函数的长度约束中的可归约性论证类似，以函数 $f’$ 为例，假设存在一个算法 $B’$ 能够高效对函数 $f’$ 求逆，那么可以构造一个算法 $A’$ 来高效原函数 $f$

算法 $A’$ 在输入 $(y,1^n)$ 时，$y$ 被认为来自 $f(U_n)$，构造 $y10^{\mathrm{poly}(n)-|y|}$，然后调用 $B’(y10^{\mathrm{poly}(n)-|y|},1^n)$，如果 $B’$ 能够对函数 $f’$ 求逆，那么就能找到某个 $x$，使得：

$$f'(x)=y10^{\mathrm{poly}(n)-|y|}$$

根据函数 $f’$ 的定义，这意味着：

$$f(x)=y$$

于是，算法 $A’$ 就得到了函数 $f$ 的一个合法原像

因此，如果函数 $f’$ 可以被高效求逆，那么函数 $f$ 也可以被高效求逆，这与 $f$ 是单向函数的假设矛盾，所以 $f’$ 仍然是单向函数

对 $f’’$ 的证明也是类似的，如果能够高效对函数 $f’’$ 求逆，就可以利用这个求逆算法恢复出使 $f’(x’)$ 等于目标输出的前缀 $x’$，从而进一步对函数 $f’$ 求逆，最终得到对 $f$ 的求逆算法，因此，函数 $f’’$ 也保持单向性

综上所述，函数 $f’$ 和 $f’’$ 都保持了函数 $f$ 的强单向性或弱单向性

【辅助长度输入的省略】

在单向函数的求逆定义中，求逆算法通常除了得到 $f(x)$ 之外，还会得到一个表示原始输入长度的辅助输入 $1^{|x|}$

但是，如果函数 $f$ 是长度保持函数，那么这个辅助输入就是多余的，因为根据定义，有：

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

所以只要看到 $f(x)$ 的长度，就已经知道 $x$ 的长度

类似地，如果函数 $f$ 是长度规则函数，并且不会把输入压缩得过多，即存在一个多项式 $\mathrm{poly}(\cdot)$，使得：

$$\mathrm{poly}(|f(x)|)\geq |x|$$

那么辅助输入 $1^{|x|}$ 也可以省略，因为此时输入长度 $|x|$ 虽然不一定等于输出长度 $|f(x)|$，但仍然可以由输出长度在多项式范围内控制

后文主要，尤其大多是长度保持函数。

因此，在讨论长度规则且不会过度压缩输入的单向函数或长度保持函数时，可以不失一般性地假设求逆算法只以 $f(x)$ 作为输入，而不再额外提供 $1^{|x|}$

【单射单向函数】

对于单向函数 $f$，若其是单射函数，那么构造得到的长度规则函数 $f’$ 仍是单射函数，这是由于 $f’(x)$ 中包含完整的 $f(x)$，并且填充方式是确定的，不同输入不会因为填充而混淆

但是，构造得到的长度保持函数 $f’’$ 不一定是一一函数，这是由于 $f’’(x’x’’)$ 只依赖于前缀 $x’$，而不同的后缀 $x’’$ 可能对应相同的输出，因此不同输入可能被映射到同一个值

所以，对于单射单向函数，可以不失一般性地假设它是长度规则的，但是不能不失一般性地假设它是长度保持的