形式陈述

哈希族 $H_k$$H_k$ 抗碰撞，若随机选参数或密钥 $k$$k$ 后，任意概率多项式时间对手输出 $x\ne x'$$x\ne x^{\prime }$ 且 $H_k(x)=H_k(x')$$H_k(x)=H_k(x^{\prime })$ 的概率可忽略。它允许对手同时选择两条消息，通常强于对固定目标的第二原像抗性。有限输出空间必然存在碰撞，安全只要求高效找不到。

直觉

压缩必会把某些不同输入映到同一摘要，但希望这些碰撞藏得足够深，现实算法无法发现。

例子与边界

生日攻击使理想 $n$$n$ 位哈希碰撞成本约 $2^{n/2}$$2^{n/2}$。MD5 已有实用碰撞，因此不能用于需要抗碰撞的签名场景。碰撞抗性不自动蕴含伪随机性或抗长度扩展，也不保证对低熵口令的原像安全。

推论与应用

抗碰撞性支撑数字签名的 hash-then-sign、Merkle 树、承诺和内容完整性。

参考资料

• 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。