计算安全基础

安全模型

• 计算安全：仅抵抗多项式时间 (PPT) 的敌手，且允许有可忽略 (Negligible) 的被攻破概率。
• IND-CPA (不可区分性-选择明文攻击)：
  • 敌手提交 $m_0,m_1$。
  • 挑战者随机选 $b$，返回 $c^{\ast }=En{c}_k(m_b)$。
  • 敌手猜测 $b$。若优势 $|Pr[Success]-1/2|\le negl(n)$，则方案安全。
  • 重要结论：确定性加密方案（如不带随机数的 RSA、ECB 模式）不可能是 IND-CPA 安全的。

核心原语

• PRG (伪随机生成器)：将短的随机种子扩展为长的伪随机串。$G:\{0,1{\}}^n\to \{0,1{\}}^{l(n)},l(n)>n$。
• PRF (伪随机函数)：区分者无法区分 $F_k(\cdot )$ 和真正的随机函数 $f(\cdot )$。
• PRP (伪随机置换)：区分者无法区分 $F_k(\cdot )$ 和随机置换 $P(\cdot )$。$F_k$ 必须是双射（可逆）。
  • 强 PRP：敌手还可以访问逆置换查询 $F^{-1}$（对应分组密码解密）。