单向函数

单向函数的不对称不来自“公式只能向一个方向写”，而来自计算资源：任何人都能迅速把随机输入映到像，看到像的高效攻击者却几乎从不找到有效原像。这里采样的是输入 $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把短均匀种子扩展为计算上不可与均匀串区分的长输出。的等价专指标准模型中的存在性：生成算法与对手采用统一多项式时间，安全性采用可忽略的反演成功率或区分优势，并把输入长度、种子长度与安全参数按标准多项式参数化对齐。上面的一般函数族不要求保长、单射或可逆；这个存在性结论也不声称某个给定 $f_{\lambda }$ 的原始输出已经伪随机。

从单向函数到 PRG 的方向由 Håstad–Impagliazzo–Levin–Luby 定理给出，见原论文 Theorem 6.3。该构造包含非平凡的计算熵与归约步骤；本页引用这一存在性定理，不把“正向容易、反向困难”当作完整构造。[1]

反方向可以直接见证。先按伸长放大理路伪随机生成器的伸长放大PRG stretch amplification将长度加一生成器迭代为状态链，用从早到晚替换的混合证明多项式伸长安全，说明最终状态何时能输出及为什么不能与未来输出同时公开。把安全 PRG 化为 $G_n:\{0,1{\}}^n\to \{0,1{\}}^{2n}$。若统一 PPT 算法 $A$ 以概率 $\epsilon (n)$ 反演 $G_n(U_n)$，令判别器在输入 $(1^n,y)$ 上运行 $A$，仅当它返回长度为 $n$ 的 $s$ 且 $G_n(s)=y$ 时接受。在生成器世界，接受概率就是 $\epsilon (n)$；在均匀世界，接受必然意味着 $y\in \mathrm{im}{G}_n$，所以概率至多 $2^n/2^{2n}=2^{-n}$。因此

右侧可忽略，故这个加长后的 $G_n$ 本身就是单向函数族。这里验证的是任意有效原像，未假设 $G_n$ 单射。两个方向合起来才支持存在性等价；承诺、认证与签名等进一步原语仍各有自己的构造和归约。

难以恢复整个输入，不代表输入的每一位都难以预测。硬核谓词理路单向函数的硬核谓词Hard-core predicate · Hard-core bit区分整份输入难反演与某一位难预测，定义带公开像的硬核谓词，并证明单向置换加一枚硬核位得到长度加一生成器。要求在给出函数像后，某个指定比特仍只能以接近一半的概率猜中。Goldreich–Levin 定理理路Goldreich–Levin 硬核位定理Goldreich–Levin theorem把随机内积预测器的平均优势转为好输入比例、带独立随机响应的重Fourier列表及原像验证，完整证明通用硬核位的反演归约。用公开随机向量与秘密输入的模二内积构造这种比特；证明把有偏预测器变成少量候选原像，再逐一计算函数进行验证。

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