语义安全 | Codeboy's Blog

形式陈述

语义安全是一项计算安全定义，建立在通用加密方案 $\Pi=(\operatorname{Gen},\operatorname{Enc},\operatorname{Dec})$ 上。以下先固定无状态、每次使用新鲜随机币的接口，并统一采用 uniform PPT。令 $(ek,dk)\leftarrow\operatorname{Gen}(1^\lambda)$ ；公开视图 $pub$ 在私钥分支中仅含安全参数和与所采样秘密密钥独立的公共设置，在公钥分支中含 $pk=ek$ 及公共参数。

需要保留的不只是消息分布，还包括生成消息时留下的辅助状态。一个 uniform PPT 联合采样器运行

(M,Z,T)\leftarrow\mathsf{Samp}^{\mathcal O}(1^\lambda,pub).

其中 $M$ 是合法消息， $Z$ 是交给预测者的辅助信息， $T$ 是要预测而不直接公开的目标。三者的编码长度都受 $\lambda$ 的多项式控制；消息长度可随公钥、采样随机性和第一阶段状态变化，不要求每个参数下始终为同一个长度。实际 $|M|$ 在两个分支中都公开； $Z,T$ 可以来自采样器的随机状态，不要求是单独由 $M$ 决定的函数。普通语义目标 $Z=h(M),T=f(M)$ 是其中一个特例。预测者 $A$ 与模拟器 $S$ 使用同一声明的多项式有界输出类型， $T$ 也属于该类型；例如分析一个谓词时三者的目标输出都是一个 bit。

oracle $\mathcal O$ 随攻击模型固定：私钥 SEM-EAV 不提供加密 oracle；私钥 SEM-CPA 向采样器、预测者和模拟器开放同一密钥下的加密接口；公钥分支可由 $pub$ 自行加密，不必另给 oracle。采样器先运行，随后才生成挑战密文，oracle 权限与此前状态不能在两个世界间暗中改变。

对每个 uniform PPT 预测者 $A$ ，要求存在一个不接收挑战密文的 uniform PPT 模拟器 $S$ ，使对每个允许的联合采样器，下列差值均可忽略：

\begin{aligned} \Big|&\Pr[A^{\mathcal O}(1^\lambda,pub,1^{|M|}, \operatorname{Enc}_{ek}(M),Z)=T]\\ &-\Pr[S^{\mathcal O}(1^\lambda,pub,1^{|M|},Z)=T]\Big|. \end{aligned}

两项概率各自包含密钥生成、联合采样和相应算法的随机性，第一项还包含新鲜的挑战加密随机币。量词顺序是“对每个预测者，存在同一个模拟器，再对所有允许的联合采样器成立”；可忽略界可依赖这些固定算法。模拟器只知道公开视图、长度和 $Z$ ，不会另外得到 $M,T$ 或挑战密文。

与不可区分实验的双向对应

下述等价结论还固定共同的消息接口：允许的长度公开确定；对每个允许长度 $\ell$ ，有公开的 uniform 多项式时间算法 $\operatorname{dummy}(1^\lambda,pub,1^\ell)$ 输出同长度合法消息。全 bit 串消息空间可取 $0^\ell$ 。受约束消息空间若没有这种高效替代，需要另作证明，不能省略该条件。

IND 推出 SEM。 模拟器把真实密文替换为合法 dummy 消息的加密，然后运行同一个 $A$ 。公钥分支使用 $pk$ ；私钥 SEM-CPA 使用获准的加密 oracle；私钥 SEM-EAV 则在相同公共设置下自行生成同分布的独立密钥后加密 dummy。在 EAV 分支中，公开视图与秘密密钥独立，采样器又无密钥 oracle，因此 $(pub,M,Z,T)$ 与该密钥独立；重新采样密钥保持它们与 dummy 密文的联合分布。若真实与模拟预测成功率相差非可忽略，IND 对手先运行联合采样器，提交 $(M,\operatorname{dummy})$ ，再以“ $A$ 的输出是否等于已采样的 $T$ ”作为区分事件，便得到相同的接受概率差。

SEM 推出 IND。 给定 IND 对手的第一阶段，联合采样器先取得它自适应选出的等长 $(m_0,m_1)$ 及保留状态 $st$ ，再独立均匀选择 $B\in\{0,1\}$ ，输出

M=m_B,\qquad Z=(m_0,m_1,st),\qquad T=B.

预测者用挑战密文和 $Z$ 继续运行 IND 对手的第二阶段。无密文模拟器看到的 $pub,Z,|M|$ 与后续允许的加密查询都不依赖 $B$ ；因为两条候选等长，长度也不泄漏 $B$ 。它必须输出一个 bit，所以猜中率恰为 $1/2$ 。SEM 因而迫使真实预测者的猜测优势可忽略。这条构造明确保留了随机、依赖公钥或加密查询的消息对与第一阶段状态，不把它们误压成确定函数 $h(M)$ 。

因此，私钥 SEM-EAV 与对应 IND-EAV 等价；私钥 SEM-CPA 与IND-CPA等价；公钥分支因加密公开，其基础语义实验也与 IND-CPA 对应。nonce、关联数据、状态化接口或 nonuniform advice 必须在两端重新匹配，不能直接套用本节的无状态证明。

Goldwasser–Micali 的原始公钥工作给出 polynomial security 推出 semantic security 的经典方向；本页上面的双向构造另外写明了采用的 uniform、联合有效采样、辅助状态与消息接口条件。

直觉

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

例子与边界

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

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

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

推论与应用

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

不可区分性是等价、易用的游戏表达，CPA 安全是常见攻击接口。面对解密查询需提升到 CCA 安全；一次一密则以信息论强度实现比计算语义安全更强的完美保密。

参考资料

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。

形式陈述 ​

与不可区分实验的双向对应 ​

反向链接

形式陈述

与不可区分实验的双向对应