单向函数

如果函数f 可以通过多项式时间算法来计算，但是任何试图计算f 的伪逆的多项式时间的随机化算法F成功的概率极其渺小，那么称函数 f :{0，1}^* → {0，1}^* 是 单向的 。^[2] 也就是说，对于所有随机算法F, 所有正整数c 和足够大的n =length(x)，都有

其中概率超过在{0，1}上ⁿ的离散均匀分布上选择x 和F的随机性。^[3]

请注意，根据这个定义，函数在平均情况，而f非最坏情况下必须“难以逆向”。这不同于许多复杂性理论(例如， NP-hardness)，这里“hard”一词是指最坏的情况。这就是为什么即使单向函数的一些候选函数(如下所述)已知是 NP-complete，但并不意味着它们是单向函数。后一种性质只是基于缺乏已知的算法来解决问题。

仅仅使一个函数“有损”(而非一对一)而具有单向函数的性质是不够的。特别是，对于任意长度为n的输入，输出n 个0组成的字符串的函数不是一个单向函数，因为很容易得到一个可以产生相同输出的输入。更准确地说: 对于这样一个只输出一串零的函数，一个对于输入f(x)输出长度n的任意字符串的算法F 将“找到”一个适合于函数f输出的原像，即使它不是最初用于产生输出字符串的输入。

单向排列是一个单向函数，也是一个置换，也就是说，一个单向函数双射的。单向排列是很重要的密码原语，并且无从得知它们的存在是否隐含在单向函数的存在中。

陷门单向函数或陷门排列是一种特殊的单向函数。这种函数很难反转，除非有一些被称为 活板门的函数是已知的。

无冲突散列函数f是一个单向函数，并且是耐碰撞的；的也就是说，不存在一个随机多项式时间的算法可以找到一个冲突—不同的值x, y 使得f(x)= f(y)—微小概率不可忽略。^[4]

如果f 是一个单向函数，那么f 的逆向函数将是很难计算(根据定义)但很容易验证(只需在f 上计算它的值)的问题。 因此，单向函数的存在意味着 FP≠FNP，这反过来意味着P≠NP。然而，P≠NP是否意味着单向函数的存在是未知的。

单向函数的存在意味着许多其他有用概念的存在，包括:

• 伪随机生成器
• 伪随机函数族
• 比特承诺方案
• 防止自适应选择密文攻击的私钥加密方案
• 消息验证码
• 数字签名方案(防止自适应选择消息攻击)

单向函数的存在也意味着没有自然证据证明P≠NP。

以下是单向函数的几个候选函数(截至2009年4月)。显然，这些函数是否确实单向是未知的；但是广泛的研究中至今还没有为它们中的任何一个产生有效的反相算法。

4.1 乘法和因式分解

函数 f 将两个质数p和q以二进制表示法的形式作为输入并返回它们的乘积。这个函数可以在很容易地O(b²)时间内计算，其中b是输入的总位数。反转此函数需要寻找给定整数N的因子。已知的最佳因子分解算法可以在   时间复杂度内运行，其中b是需要用于表示N的位数。

这个函数可以通过允许p 和q超过一个合适的半素数集合的范围。请注意f 对于随机选择的整数 p，q>1不是单向的，因为乘积将有2作为因子的概率为3/4(因为任意p 是奇数的概率是1/2，对q也一样，所以如果它们是独立选择的，那么两者都是奇数的概率是1/4；因此p或q是偶数的概率是1 - 1/4 = 3/4)。

4.2 拉宾函数(模平方)

拉宾函数,^[5] 或平方模   ，其中p和q 是素数并被认为是单向函数的集合。我们写作

表示平方模N：一个拉宾集的特定成员。可以看出，提取平方根，即反转拉宾函数，在计算上等同于因式分解N (在多项式时间规约的意义上)。因此，可以证明拉宾集是单向的，当且仅当计算因子很困难。这也适用于特殊情况，其中p和q具有相同的比特长度。拉宾密码系统是基于拉宾函数是单向函数的假设。

4.3 离散指数和对数

模幂运算可以在多项式时间内完成。反转此函数需要计算离散对数。目前有几个知名的群组，其中没有已知的算法来计算多项式时间内的离散对数。这些群体都属于有限阿贝尔群，并且一般离散对数问题可以这样描述。

设G 是的有限阿贝尔群，基数为n。表示它的群作用乘法运算。考虑一个基本元素α ∈ G 和另一个元素 β ∈ G。离散对数问题是寻找正整数k，其中1 ≤ k ≤ n，使得:

α^k = β的整数解k被称为β以α为底的离散对数。写作 k =log_α β。

群组G 在离散对数密码系统的一个热门选择是环状基团（Z_p)^×(例如ElGamal加密, diffie–赫尔曼密钥交换，以及数字签名算法)和椭圆曲线在有限域上的循环子群（见 椭圆曲线密码学）。

椭圆曲线是满足y² = x³ + ax + b的域上的元素对的集合。曲线的元素在一个称为“点加法”的操作下形成一个组(这与域的加法操作不同)。某一点P与整数k的乘法kP （即，整数的加法组的群作用)被定义为点对其自身的重复加法。如果 k 和 P 是已知的，计算 R = kP是很容易的，但是如果 r 和 P 都是已知的，一般认为很难计算 k。

4.4 加密安全散列函数

有许多能够快速计算的加密散列函数，例如SHA 256。一些简单的版本已经着手复杂的分析，但是最强大的版本继续为单向计算提供快速、实用的解决方案。对这些函数的大多数理论支持更多都是用来阻止一些先前成功过的攻击的技术。

4.5 其他候选函数

单向函数的其他候选是基于随机线性解码、子集和问题（(Naccache-Stern背包密码系统)、或其他问题的困难性。

当且仅当单向函数存在时，会有一个显式函数f 被证明是单向函数。^[5] 换句话说，如果任何函数都是单向的，那么f 也是。因为这个函数是第一个被证明的组合完全单向函数，所以它被称为“通用单向函数”。因此，寻找单向函数的问题被简化为证明一个这样的函数存在。