KEM–DEM 混合加密

形式陈述 ​

设 $\mathsf{KEM}=(\mathsf{KGen},\mathsf{Encaps},\mathsf{Decaps})$ 的会话密钥空间与 $\mathsf{DEM}=(\mathsf{DEnc},\mathsf{DDec})$ 的密钥空间相同。混合方案 $\mathsf{HE}$ 复用 KEM 的密钥生成：

$$(pk,sk)\leftarrow \mathsf{KGen}(1^{\lambda }).$$

加密算法接收公钥、消息 $M$ 和协议上下文 $ctx$，执行

$$\begin{array}{rl}(K,c_0)& \leftarrow \mathsf{Encaps}(pk),\\ N& \leftarrow \mathsf{NonceGen}(1^{\lambda }),\\ A& =\mathsf{Encode}(\mathtt{\text{"KEM-DEM"}},\mathsf{suite},\mathsf{pkid},c_0,N,ctx),\\ c_1& \leftarrow {\mathsf{DEnc}}_K(N,A,M),\\ C& =(c_0,N,c_1).\end{array}$$

$\mathsf{Encode}$ 必须无歧义并带域分离；$\mathsf{suite}$ 标识算法套件，$\mathsf{pkid}$ 绑定接收密钥或其规范标识。解密先规范解析 $C$，重算完全相同的 $A$，再执行

$$K\leftarrow \mathsf{Decaps}(sk,c_0),M\leftarrow {\mathsf{DDec}}_K(N,A,c_1).$$

任一步解析、解封装或认证失败都返回统一的 $\mathrm{\perp }$，未经 DEM 认证的明文不得交给上层。实现可以采用 KEM 的 implicit rejection，但外部仍需保持一致的失败语义和尽量恒定的可观察行为。

主模型假设每次 encapsulation 只产生一条 DEM 密文，因此会话密钥是 one-time key；此时可使用固定且域分离的 nonce，或按规范生成一个 nonce。若同一 $K$ 保护多条记录，就必须改用多消息 nonce-respecting AEAD 定义，保证同一密钥下 nonce 唯一，并把记录数、并发、重启与碰撞概率纳入优势界。一次性组合定理不能通过简单循环自动升级为多记录结论。

若 KEM 和 DEM 的密钥长度不同，可插入

$$K_D=\mathsf{KDF}(K,\mathsf{suite},c_0,ctx).$$

此时定理需要额外假设：在 KEM 挑战给出的真实或随机 $K$ 下，派生的 $K_D$ 对 DEM 而言与所需均匀密钥不可区分，且输出长度、域分离和上下文编码符合 DEM 规格。任意截断、复用或未分析的 KDF 不能无条件继承 KEM 安全；为使核心定理清楚，以下先取密钥空间直接匹配。

正确性可由两组件合成。若诚实 KEM 解封装失败或错配概率至多 ${\delta }_K(\lambda )$，DEM 在合法输入上的解密失败概率至多 ${\delta }_D(\lambda )$，且编码与 nonce 规则一致，则联合界给出

$$\text{Pr}[{\mathsf{HDec}}_{sk}({\mathsf{HEnc}}_{pk}(M,ctx),ctx)\ne M]\le {\delta }_K(\lambda )+{\delta }_D(\lambda ).$$

该式不要求两类失败独立；若两项可忽略，混合方案正确性误差也可忽略。

组合结论必须绑定精确的组件接口与攻击实验。以下采用 Shoup 2001 与 ISO/IEC 18033-2 的 KEM–DEM 框架来组织当前的一次性方案，但不把不同文献中的优势定义和常数拼成一条“通用标准界”。目标实验使用公钥加密 IND-CCA 的半偏差

$${\mathrm{Adv}}_{\mathsf{HE},A}^{\mathsf{ind}\mathsf{\text{-}}\mathsf{cca}}(\lambda )=|\text{Pr}[b^{\prime }=b]-\frac{1}{2}|.$$

挑战者把 $pk$ 交给 PPT 对手 $A$，在挑战前后开放混合解密 oracle。$A$ 提交等长 $M_0,M_1$ 与挑战上下文 $ct{x}^{\ast }$，收到 $M_b$ 的挑战密文 $C^{\ast }$；它不得查询完全相同的 $(C^{\ast },ct{x}^{\ast })$，但可提交其他相关封装、nonce、正文密文或上下文。概率覆盖密钥生成、封装、nonce、挑战 bit、DEM 与对手的全部随机币。

在这个实验下，可以陈述如下定性组合命题。它要求四项条件同时成立：

1. KEM 在当前封装编码与 rejection 语义下满足 IND-CCA key indistinguishability。
2. DEM 面对独立均匀且只使用一次的密钥时，针对当前 nonce 与 associated-data 接口同时满足消息保密性，以及足以拒绝相关解密查询的密文完整性。
3. $c_0,N,\mathsf{suite},\mathsf{pkid},ctx$ 都经过无歧义编码，并被 DEM 认证。
4. 混合解密查询可以由上述两个组件实验模拟，错误接口不会额外泄漏信息。

在这些条件下，上述一次性混合方案满足对应实验中的 IND-CCA。这个结论没有涵盖其他 rejection 规则、nonce 管理方式或密钥复用策略。

这里的每个限定都参与定理。KEM 游戏是否允许 implicit rejection，DEM 完整性游戏提供一次还是多次伪造尝试，nonce 是固定、随机还是外部管理，以及解密查询如何比较挑战上下文，都会改变归约。若改成一把密钥保护多条记录，还要把 DEM 假设替换成相应的多消息 AEAD 定义，不能继续引用这条 one-time 命题。

在固定全部定义后，证明账本通常具有下面的示意形状：

$${\mathrm{Adv}}_{\mathsf{HE}}\le {\mathrm{\Delta }}_{\mathsf{KEM}}+{\mathrm{\Delta }}_{\mathsf{DEM}\mathsf{,}\mathsf{conf}}+{\mathrm{\Delta }}_{\mathsf{DEM}\mathsf{,}\mathsf{int}}.$$

$\mathrm{\Delta }$ 表示由该组实验和模拟器实际导出的损失，不是可跨规范复用的优势函数。查询次数因子、猜测事件、rejection 分支和归一化常数都必须在具体归约中证明；上式只展示三类风险如何进入账本，不能替代数值定理。

直觉 ​

混合加密把两种成本曲线不同的工具接在一起：KEM 用一次昂贵公钥运算交付短密钥，DEM 用高吞吐对称运算保护正文。证明也遵循同样分工，先把 KEM 产生的挑战密钥替换成独立均匀值，再在这个理想 key 下调用 DEM 的保密与完整性保证。

组件边界本身必须被认证。封装 $c_0$、nonce、上下文和算法套件若没有进入 $A$，攻击者可能把不同密文的部件重新拼接，或把一个协议中的正文搬到另一个协议解释。Associated data 不隐藏这些字段，却让任何重绑定都在解密前被检测。

例子与边界 ​

考虑文件加密：头部 $c_0$ 封装一次性文件密钥，$N$ 标识唯一数据密文，$ctx$ 包含文件格式版本、接收者标识和内容类型；正文及元数据由 AEAD 在 $K$ 下加密，$A$ 则绑定头部和上下文。接收者只有在解封装成功且 AEAD 标签验证通过后才返回文件内容。攻击者即使复制另一个文件的 $c_0$ 或修改版本字段，也会因为关联数据改变而得到 $\mathrm{\perp }$。

RFC 9180 的 HPKE 是标准化工程对照：它组合 KEM、KDF 与 AEAD，由 key schedule 把 info、模式和封装结果导入上下文，再用序列号派生 nonce，并区分 base、PSK、authenticated 与 authenticated-PSK 模式。这个接口比本页的一次性二组件模型多出密钥派生、模式认证和多记录状态，因此 HPKE 的规范一致性不能充当上面定性组合命题的直接证明；分析具体 HPKE 套件时，应使用 RFC 9180 的算法与安全上下文，而不是把本页公式逐字段套入。

只提供保密性的 DEM 不够。设 DEM 密文可被可预测地翻转，攻击者便能保持挑战 $c_0^{\ast }$ 不变、修改 $c_1^{\ast }$，再把不同于完整挑战密文的 $(c_0^{\ast },N^{\ast },c_1^{\prime })$ 合法提交解密 oracle。若修改结果泄漏 $M_b$ 的关系，KEM 的 CCA 安全也无法阻止，因为攻击发生在同一个已封装 key 下的数据层。

反过来，只有 IND-CPA KEM 加认证 DEM 通常也不足以推出整体 IND-CCA。攻击者可修改 $c_0$ 并利用混合解密 oracle 的解封装结果或失败模式；组合归约若没有 KEM 的挑战后 decapsulation 安全，就无法回答这些查询。原语攻击模型必须与目标 PKE 的主动查询能力匹配。

Nonce 规则也不会被 KEM 自动修复。若每个封装只加密一条消息，one-time key 使固定 nonce 可在严格域分离下成立；若一个 $K$ 被缓存后加密多个记录，重复 nonce 可能复用密钥流或破坏认证。此时需要多消息 AEAD 定理和会话状态，不能继续引用 one-time DEM 界。

缺少 ciphertext binding 会产生组合与跨协议风险。若 $A$ 不包含 $c_0$、$ctx$ 或 suite，某些组件可能各自在孤立游戏中安全，完整系统却允许把密文头、正文或标签移动到另一接收者、另一算法解释或另一协议阶段。规范编码、域分离和接收密钥绑定是组合条件，不是可选工程注释。

错误处理是最后一条边界。显式的 KEM $\mathrm{\perp }$、DEM 标签错误、解析错误若产生不同响应、长度或时间，可能形成超出抽象 CCA 游戏的分类 oracle。统一外部错误、验证全部字段并避免在认证前处理正文，才能让实现接近证明中的单一失败接口；混合定理不覆盖未建模侧信道。

推论与应用 ​

在满足上述接口条件时，证明可按四个游戏组织。$G_0$ 是真实 IND-CCA 实验；$G_1$ 把挑战 KEM key 换成独立均匀值。对非挑战封装的查询能否交给 decapsulation oracle、对挑战封装的等价编码如何处理，都由所选 KEM 游戏决定，不能只检查字节串 $c_0\ne c_0^{\ast }$。

接着，$G_2$ 拒绝那些复用挑战封装却修改 $N,c_1$ 或 $ctx$ 的查询。$G_1$ 与 $G_2$ 的差距由 DEM 完整性控制；若组件定义只允许一次伪造尝试，模拟器可能需要猜中某次查询并产生查询次数损失，若定义本身允许多次验证，则损失形式又不同。$G_3$ 再把挑战 DEM 密文中的 $M_b$ 换成与 $b$ 无关的等长消息，差距由当前 one-time 保密实验控制。只有每一步都能在选定接口中实现时，最终游戏才与 $b$ 独立。

这条混合论证公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。说明“安全 KEM 加安全 DEM”仍不是无条件公式。密钥分布与长度必须衔接，KEM/DEM 的查询模型和 key 使用次数必须匹配，挑战封装与数据密文必须绑定，nonce、context 和失败语义也必须进入接口。满足这些前提后，KEM–DEM 才把模块化工程结构转化为可核算的端到端公钥加密结论。

参考资料

• Victor Shoup, “A Proposal for an ISO Standard for Public Key Encryption,” version 2.1, 2001，KEM/DEM composition and hybrid encryption。
• Ronald Cramer and Victor Shoup, “Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack,” SIAM Journal on Computing 33(1), 2003。
• ISO/IEC 18033-2, Encryption Algorithms — Part 2: Asymmetric Ciphers, KEM and DEM composition framework。
• Richard Barnes et al., RFC 9180: Hybrid Public Key Encryption, 2022，KEM/KDF/AEAD 标准协议实例；用于接口对照，不作为本页抽象组合命题的直接证明。
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，hybrid public-key encryption and CCA security。