计算安全

计算安全不要求密文在信息论上毫无泄漏，也不要求攻击成功概率严格为零；它要求任何可抽象为多项式时间算法的攻击者，都不能获得随安全尺度增长仍非可忽略的优势。攻击者代码可任意固定，但运行时间和查询数必须由参数的多项式界定。具体安全还关心数值损失：归约转换攻击优势和时间时，松散因子会直接影响所需密钥长度。

计算安全只要求多项式时间对手的优势可忽略，允许信息论上存在但计算上不可行的区分；完美保密公理库完美保密Perfect secrecy对每种消息先验，观察密文都不改变消息分布的无条件安全定义。要求密文与消息在分布上完全独立，不限制对手算力。后者更强，也通常付出密钥长度等结构代价。

“足够小”必须随参数判断 ​

一次穷举 $2^{\lambda }$ 个密钥的攻击可能成功，却不是多项式时间攻击，因而不否定计算安全。另一方面，优势 $1/{\lambda }^{100}$ 虽趋于零，却不满足定义：选择比较界 $1/{\lambda }^{101}$，前者对每个 $\lambda >1$ 都更大。定义要求胜过每个逆多项式，而不是只胜过某个预先选定的阈值。

若攻击成功率仅比随机猜测高 $2^{-\lambda }$，该优势可忽略；固定 $2^{-80}$ 虽在工程上很小，却作为关于 $\lambda$ 的常数并不可忽略，因为最终会大于 $1/{\lambda }^c$。设归约给出 ${\mathrm{Adv}}_{\mathrm{\Pi },A}\le q{\mathrm{Adv}}_{F,B}+\delta$。若底层优势至多 $2^{-100}$、$q=2^{20}$、模拟误差 $\delta \le 2^{-90}$，上界便是 $2^{-80}+2^{-90}$，不是 $2^{-100}$。渐近上，多项式 $q(\lambda )$ 乘可忽略函数仍可忽略，但固定参数下不能省略这个因子。

“目前没人破解”不是形式证明；必须给出攻击游戏与量词。多项式时间模型也不涵盖侧信道、实现 bug 或量子攻击，除非相应地扩展攻击者能力和困难假设。

计算安全把统一的实验语言与“所有 PPT 对手的优势可忽略”这一量词结合起来，支持归约证明：若攻击方案可构造出破解底层假设的高效算法，则底层困难性推出方案安全。结论只覆盖实验允许的攻击能力，不能自动扩展到选择密文、侧信道或密钥泄漏模型。

可忽略函数公理库可忽略函数Negligible function比任意逆多项式最终更小的非负函数。 描述残余优势，不可区分性公理库不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。 是常见安全游戏形式，混合论证公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。 用多步替换累积优势。单向函数、伪随机性、加密和签名都在这一框架下通过归约组织。