单向函数

单向函数的不对称不来自“公式只能向一个方向写”，而来自计算资源：任何人都能迅速把随机输入映到像，看到像的高效攻击者却几乎从不找到有效原像。这里采样的是输入 $x$，挑战像 $y$ 因而服从 $f_{\lambda }(x)$ 诱导的分布；它一般不是值域上的均匀随机元素。

攻击者不必猜回挑战者最初抽到的那个 $x$。若函数是多对一的，输出任意 $x^{\prime }$ 满足 $f_{\lambda }(x^{\prime })=y$ 就已成功。因此单向性既不要求函数为单射，也不把“原像唯一”当作安全来源。它要求随机生成的典型挑战难逆，而不是仅存在一批人工挑选的最坏实例。

RSA 函数公理库RSA 函数与 RSA 假设RSA function · RSA inversion assumption以模幂置换定义带陷门的 RSA 函数族，并假设随机像对高效对手难以求逆。给出带公开索引的候选例子：实验先随机生成公开参数 $(N,e)$，再在其定义域内抽取 $x$ 并给出 $x^{e}modN$。公开参数允许高效模幂，知道陷门可反演，而不知道陷门时对随机像求逆被假设为困难。这是上述定义的索引化版本，概率还覆盖参数生成。这里“候选”很重要；具体函数族的单向性依赖未经无条件证明的计算假设，不能从正向公式复杂或模数很大直接推出。

考虑一个反例族：一半输入以首位 $0$ 开头，函数在这些输入上直接输出剩余各位；另一半输入进入某个极难反演的分支。攻击者看到透明分支的像时可以立即恢复原像，整体成功概率至少为常数，因此该族不是强单向函数。少量极难实例无法抵消一大块容易实例，这正是平均情形量词的作用。

最坏情形困难也不自动蕴含单向性。一个 NP 困难问题可能只有罕见实例困难，而反演实验要求按指定随机生成过程得到的实例对所有高效算法都难。已知具体单向函数的存在会推出 $P\ne NP$，反方向却没有从 $P\ne NP$ 到标准单向函数的一般结论。

多对一还带来另一条边界：难找原像不等于难找碰撞。碰撞抗性要求攻击者自行找出两个不同输入 $x\ne x^{\prime }$ 且像相同；单向性则由挑战者先给随机像，要求攻击者反演。两种实验的输入来源和成功事件不同，任何一方都不能只凭名称替代另一方。

强、弱与分布边界 ​

强单向性要求每个 PPT 对手的成功概率可忽略。弱单向性只要求存在多项式 $p$，使每个 PPT 对手在充分大的参数上至少以 $1/p(\lambda )$ 的概率失败；它允许对手在大部分实例上成功，却保留不可忽略的困难份额。通过对多个独立实例作直接积可以把弱单向性放大为强单向性，但副本数、输入独立性与成功事件必须进入证明，不能把“重复几次”当成自动结论。

定义也可以从均匀输入推广到高效可采样分布，此时采样器是函数族接口的一部分。改变输入分布可能把质量移到容易原像或困难原像上，从而改变单向性真假；因此安全主张必须连同参数生成和输入采样方式一起陈述。

单向函数是计算安全公理库计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。的基础存在性假设之一。经典结果表明，由单向函数可以构造伪随机生成器公理库伪随机生成器Pseudorandom generator · PRG把短均匀种子扩展为计算上不可与均匀串区分的长输出。，并进一步支撑承诺、消息认证与数字签名等原语；每一步仍需要单独的构造与归约，不能把普通函数输出直接当作现成密钥或密文。

陷门单向函数额外生成一份秘密陷门，使持有者能够高效反演；普通单向函数没有这项接口，也不自动提供公钥加密公理库公钥加密Public-key encryption加密密钥公开而解密密钥保密的加密体系。所需的解密能力。单向置换还要求每个 $f_{\lambda }$ 是置换，是比一般多对一单向函数更强的结构条件。