语义安全

形式陈述 ​

语义安全是一项计算安全公理库计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。定义，建立在通用加密方案公理库加密方案Encryption scheme · Encryption syntax · 加密语法由密钥生成、加密和解密算法及其消息、密文与失败接口组成的通用密码方案语法。

$$\mathrm{\Pi }=(\mathrm{Gen},\mathrm{Enc},\mathrm{Dec})$$

之上。令 $(ek,dk)\leftarrow \mathrm{Gen}(1^{\lambda })$；私钥方案取 $ek=dk=K$，但不会把 $K$ 公开给攻击者，公钥方案则取 $ek=pk,dk=sk$ 并公开 $pk$。记公开视图为 $pub$：私钥被动窃听实验中它为空，公钥实验中它包含 $pk$ 及方案声明的公共参数。

以下统一采用 uniform PPT：算法由单台概率图灵机处理所有安全参数，不允许为每个输入长度另带多项式大小 advice。消息族由 uniform PPT sampler 产生；公钥分支允许 sampler 读取 $pub$，并要求每个 $\lambda$ 的输出具有同一个多项式有界长度 $\ell (\lambda )$。对任意 uniform PPT 攻击者 $\mathcal{A}$，必须存在一个不接收挑战密文的 uniform PPT 模拟器 $\mathcal{S}$，使对任意这样的消息分布族 $\{D_{\lambda }\}$，以及任意 uniform 多项式时间可计算的目标函数 $f$ 和辅助信息函数 $h$，令 $M\leftarrow D_{\lambda }(pub)$ 后都有

$$\begin{array}{rl}|& \text{Pr}[\mathcal{A}(1^{\lambda },pub,1^{|M|},{\mathrm{Enc}}_{ek}(M),h(M))=f(M)]\\ & -\text{Pr}[\mathcal{S}(1^{\lambda },pub,1^{|M|},h(M))=f(M)]|\le \mathrm{negl}(\lambda ).\end{array}$$

函数的输入、输出编码同样由 $\lambda$ 的多项式界定；$1^{|M|}$ 把允许泄漏的长度同时交给攻击者和模拟器。概率取自密钥生成、消息采样、加密随机性以及两台算法的随机性。量词顺序是“对每个攻击者，存在一个模拟器，再对所有允许的消息分布和信息函数成立”；模拟器可以使用公开视图，却不能依赖某次抽到的明文或挑战密文。

在这组 uniform、有效可采样、等长消息约定下，私钥被动窃听分支 SEM-EAV 与对应的 IND-EAV 等价。Goldwasser–Micali 1984 的 Section 5.2、Theorem 5.2 给出原始公钥语境中 polynomial security 推出 semantic security 的方向；现代教材再以反向构造得到公钥语义安全与 IND-CPA 的等价。改变为 nonuniform 对手、不可有效采样消息族或不同辅助输入接口时，需要重新陈述等价定理，不能只保留“SEM = IND”四个字。

私钥加密公理库对称加密Symmetric encryption · Secret-key encryption发送方与接收方共享密钥的加密、解密算法体系。若改为 SEM-CPA，攻击者还应在挑战前后获得加密 oracle，此时对应 IND-CPA。公钥加密公理库公钥加密Public-key encryption加密密钥公开而解密密钥保密的加密体系。中公开的 $pk$ 本来就允许攻击者自行加密任意消息，因此其基础接口已经包含这种选择明文能力。两条分支复用同一“密文不增加可计算信息”定义，却必须把公开视图和 oracle 权限分别写清，不能把私钥 EAV、公钥基础实验与私钥 CPA 直接互换。

直觉

攻击者可能本来就知道消息来自哪个分布、消息长度或其他公开侧信息；语义安全不试图抹掉这些先验，而只要求密文不再提供可高效利用的新信息。模拟器把这句话变成可检验的比较：如果某件事不看密文也能以几乎相同概率完成，就不能把它算作密文泄漏。安全目标因此远强于“难以恢复整条明文”：只要密文额外帮助预测一个 bit、某个关系或某个谓词，就已经失败。

例子与边界

确定性私钥加密通常无法在多次加密或选择明文模型中达到标准语义安全：攻击者可比较候选消息的密文。一次一密具有更强的完美保密；计算语义安全允许分布在信息论上不同，只要求高效对手无法利用这种差异。消息长度若由密文长度直接暴露，通常需把长度纳入允许泄漏，或在等价的不可区分游戏中限制挑战消息等长。

若密文总泄露明文奇偶位，即使其余 $n-1$ bit 无法恢复，攻击者仍能预测谓词 $f(m)=m_1$，不满足语义安全。IND 游戏中攻击者选两个等长消息，若能区分挑战密文，就可提取某种语义信息；反向可把语义预测器转为区分器。

长度通常被视为允许泄露，因此挑战消息要求等长。语义安全不保证完整性、匿名性或隐藏访问模式；确定性加密在高熵消息的特定模型下可讨论别的安全概念，但不满足标准任意消息 IND-CPA。

推论与应用

语义安全是现代加密的核心保密目标，但“语义安全”必须连同攻击接口一起阅读。对私钥方案，仅证明 SEM-EAV 不能推出 SEM-CPA，更不能推出选择密文安全；公钥方案由于加密算法公开，基础语义安全通常已经按 CPA 接口理解。继续开放解密查询则进入更强的 CCA 模型。

不可区分性公理库不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。 是等价、易用的游戏表达，CPA 安全公理库选择明文安全Chosen-plaintext attack security · CPA security对手可自适应查询所选明文加密时仍不能区分挑战消息的安全定义。 是常见攻击接口。面对解密查询需提升到 CCA 安全公理库选择密文安全Chosen-ciphertext attack security · CCA security对手还可查询非挑战密文解密时仍保持消息不可区分的安全定义。；一次一密则以信息论强度实现比计算语义安全更强的完美保密。

参考资料

• Shafi Goldwasser and Silvio Micali, “Probabilistic Encryption,” Journal of Computer and System Sciences 28(2), 1984, pp. 270–299，Section 5.2 and Theorem 5.2。
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，Ch. 3。