形式陈述

设安全参数为 $\lambda$$\lambda$。密码方案具有计算安全性，通常指对每个概率多项式时间攻击者 $\mathcal A$$\mathcal{A}$，其在指定安全实验中的优势

$$ \operatorname{Adv}_{\Pi,\mathcal A}(\lambda) $$$${\mathrm{Adv}}_{\mathrm{\Pi },\mathcal{A}}(\lambda )$$

都是关于 $\lambda$$\lambda$ 的可忽略函数。量词次序是

$$ \forall\mathcal A\in\mathrm{PPT},\ \exists\mu_{\mathcal A}\text{ negligible},\quad \operatorname{Adv}_{\Pi,\mathcal A}(\lambda)\le\mu_{\mathcal A}(\lambda) $$$$\mathrm{\forall }\mathcal{A}\in \mathrm{PPT},\mathrm{\exists }{\mu }_{\mathcal{A}}\text{ negligible},{\mathrm{Adv}}_{\mathrm{\Pi },\mathcal{A}}(\lambda )\le {\mu }_{\mathcal{A}}(\lambda )$$

对充分大的 $\lambda$$\lambda$ 成立。安全实验、攻击接口和优势基线必须明确规定。

直觉

计算安全不要求密文在信息论上毫无泄漏，而要求任何现实抽象为高效算法的攻击者都无法把泄漏转化为非可忽略优势。安全参数让资源、密钥长度与失败概率随规模共同增长。

例子与边界

一次穷举 $2^\lambda$$2^{\lambda }$ 个密钥的攻击可能成功，却不是多项式时间攻击，因而不否定计算安全。固定为 $2^{-80}$$2^{-80}$ 的优势不随 $\lambda$$\lambda$ 衰减，按渐近定义并非可忽略；工程中仍可在固定参数下单独评估具体安全强度。

推论与应用

计算安全把密码学结论组织为“实验 + 对手类 + 优势界”，支持归约证明：若攻击方案可构造出破解底层假设的高效算法，则底层困难性推出方案安全。结论只覆盖实验允许的攻击能力，不能自动扩展到选择密文、侧信道或密钥泄漏模型。

参考资料

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