形式陈述

函数族 $f_n$$f_n$ 易于多项式时间计算，但对均匀随机输入 $x$$x$，任意概率多项式时间算法给定 $f_n(x)$$f_n(x)$ 后输出任一原像 $x'$$x^{\prime }$ 使 $f_n(x')=f_n(x)$$f_n(x^{\prime })=f_n(x)$ 的概率可忽略，则称单向函数。它不要求单射，也不要求对每个输出都难逆；难度是在指定输入分布上的平均情形。

直觉

顺着函数算很容易，而从典型结果反推任何有效起点都计算困难。

例子与边界

候选包括整数分解或离散对数相关映射，但其单向性未被无条件证明。把输入直接附在输出中显然不是单向函数。最坏情形困难问题不自动给出平均情形单向函数；密码学需要对随机实例的逆向困难。

推论与应用

单向函数被视为最基础的密码学存在性假设，可推出伪随机生成器、承诺和多种对称原语。

参考资料

• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，Chs. 2–12。
• Oded Goldreich, Foundations of Cryptography, Vol. 1, Cambridge University Press, 2001，Chs. 1–4。