计算安全

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

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

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

若攻击成功率仅比随机猜测高 $2^{-\lambda }$，该优势可忽略；固定 $2^{-80}$ 虽在工程上很小，却作为关于 $\lambda$ 的常数并不可忽略，因为最终会大于 $1/{\lambda }^c$。一个从破坏方案的攻击者构造求解困难问题的归约，若优势损失为查询数 $q$，则需把 $q$ 纳入参数选择。

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

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

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