常见的单向函数

【概述】

下面介绍密码学中常被视为单向函数的三类函数，但目前并不知道这些函数是否真正是单向函数，它们只能被看作基于大量研究经验提出的猜想，到目前为止，还没有找到能够以明显成功概率高效求逆这些函数的算法

也就是说，这些函数之所以被认为可能是单向函数，并不是因为已经被严格证明难以求逆，而是因为它们对应的求逆问题长期以来没有被有效解决

【基于整数分解的单向函数】

整数分解（Integer Factorization），在数论中是指在可能的情况下，将一个正整数分解为更小整数的乘积。若进一步限制因素为质数，则这个过程称为质数分解（Prime Factorization）

简单来说，给定两个大整数，很容易就能将他们相乘，但给出他们的乘积，很难找出他们的因子

尽管人们已经对整数分解算法进行了大量研究，但目前已知最好的整数分解算法仍然是次指数时间算法，因此，可以合理地猜测如下乘法函数是单向函数

$$f_{\mathrm{mult}}(x,y)=x\cdot y$$

其中 $|x|=|y|$，$x\cdot y$ 表示将二进制串 $x$ 和 $y$ 所代表的整数相乘后得到的整数的二进制表示

这个函数显然可以在多项式时间内计算，因为整数乘法可以高效完成。但是，对该函数求逆意味着：给定乘积 $x\cdot y$，试图恢复出两个因子 $x$ 和 $y$，这正是整数分解问题的形式之一

如果假设整数分解是困难的，例如给定两个均匀选取的 $n$ 比特素数的乘积时，很难找到这两个素因子，再结合素数密度定理，就可以推出 $f_{\mathrm{mult}}$ 至少是弱单向函数

素数密度定理（Density-of-Primes Theorem）：设 $\pi(n)$ 表示不超过 $n\in\mathbb{N}$ 的质数个数，有：

$$\lim_{n\to \infty} \frac{\pi(n)}{n/\ln n} = 1$$

即当 $n$ 趋于无穷大时，质数的数量大约等于 $n$ 除以 $\ln n$ 的值，通常记作：

$$\pi(n)\sim \frac{n}{\ln n}$$

因此，在随机选取整数时，选到质数的概率虽然不是常数，但仍然足够大，使得整数分解困难性可以支持该函数的弱单向性

【基于随机线性码的单向函数】

在编码理论中，一个非常重要的开放问题是：是否存在高效算法能够解码随机线性码（Random Linear Code），尤其是那些具有常数信息率，并且能够纠正常数比例错误的随机线性码。因此，随机线性码解码问题可以作为构造单向函数候选的困难性来源

在线性码的编码理论基础，介绍了 Hamming 球堆积上界与 Gilbert–Varshamov 下界，以及随机线性码的生成。当取常数 $\kappa,\delta,\varepsilon>0$，并满足：

$$\kappa<1-H_2((1+\varepsilon)\delta)$$

时，随机选取一个 $\kappa n\times n$ 的二进制矩阵 $C$，它就大概率生成一个最小距离至少为 $\delta n$ 的线性码

在此基础上，定义函数：

$$f_{\mathrm{code}}(C,x,i)\overset{\mathrm{def}}{=}(C,xC+e(i))$$

其中，

• $C$ 是 $\kappa n\times n$ 的二进制矩阵
• $x$ 是 $\kappa n$ 维二进制向量
• $xC$ 表示原始消息 $x$ 经过随机线性码 $C$ 编码得到的码字

• $i$ 是某个 $n$ 维二进制向量的索引，

• $e(i)$ 是索引 $i$ 对应的 Hamming 重量

• 所有运算都在 $n$ 维二进制向量空间中进行，即按模 $2$ 运算

由于矩阵 $C$ 大概率生成一个最小距离至少为 $\delta n$ 的线性码，所以该码的唯一纠错半径约为：

$$\frac{\delta n}{2}$$

因此，$xC+e(i)$ 可以理解为：在合法码字 $xC$ 上加入了一个处于可纠错范围内的错误向量

函数 $f_{\mathrm{code}}$ 的正向计算是高效的，给定 $C$、$x$ 和 $i$，只需要计算矩阵乘法 $xC$，再根据索引 $i$ 得到错误向量 $e(i)$，最后计算 $xC+e(i)$ 即可

但是，对函数 $f_{\mathrm{code}}$ 求逆则对应随机线性码解码问题。也就是说，给定随机码 $C$ 和带噪声码字 $xC+e(i)$，需要恢复原始消息 $x$ 以及错误向量 $e(i)$，这正是从随机线性码的带噪声码字中解码的过程

如果存在一个高效算法能够求逆 $f_{\mathrm{code}}$，那么就意味着可以高效解码一个不可忽略比例的常数率线性随机码，这将是编码理论中的重大突破

因此， $f_{\mathrm{code}}$ 被合理地看作一个基于随机线性码解码困难性的单向函数候选

【基于子集和问题的单向函数】

子集和问题（Subset Sum Problem）是计算复杂度理论中一个经典的 NP 完全问题，其可以描述为：给定一个整数集合，是否存在某个非空子集，使得子集内中的数字和为某个特定数值。例如，给定集合 $\{-7,-3,-2,5,8\}$，是否存在子集和为 $0$ 的子集？

基于子集和问题，可以定义函数：

$$f_{\mathrm{ssum}}(x_1,\dots,x_n,I) =(x_1,\dots,x_n,\sum_{i\in I}x_i)$$

其中，$|x_1|=\cdots=|x_n|=n$，且 $I\subseteq\{1,2,\dots,n\}$

也就是说，函数 $f_{\mathrm{ssum}}$ 输入一组整数 $x_1,\dots,x_n$ 以及一个下标集合 $I$，输出所有 $x_i$ 本身以及由集合 $I$ 指定的那些数的和，这显然可以在多项式时间内计算

但是，要对这个函数求逆，就需要在给定 $x_1,\dots,x_n$ 和目标和的情况下，找出一个子集 $I$，使得 $\sum_{i\in I}x_i$ 等于给定目标值，这正是子集和问题

需要注意的是，子集和问题是 NP 完全问题的事实，本身不能作为 $f_{\mathrm{ssum}}$ 是单向函数的证据。因为 NP 完全性描述的是最坏情形困难性，而单向函数要求的是平均情形下难以求逆

另一方面，子集和问题在某些特殊情形下是容易的，但这些容易情形也不能直接否定 $f_{\mathrm{ssum}}$ 作为单向函数候选的可能性

因此，$f_{\mathrm{ssum}}$ 被认为是一个可能的单向函数候选