Page 38 - 《软件学报》2025年第10期

米瑞琪 等: 基于 Kyber 公钥加密的高效认证密钥交换协议 4435

1 后量子认证密钥交换构造相关工作与研究现状

抗量子 AKE 有两种主要的设计思路.
第 1 种设计思路是通过抗量子的数字签名进行身份认证, 并通过抗量子的公钥加密 (KEM/PKE) 替代 DH 密
钥交换建立会话密钥. 这种思路的代表性工作是 Paquin 等人 [12] 在 TLS 中进行的实验, 该实验中测试了全部 NIST
后量子算法征集中的签名算法与公钥加密组合的表现, Sosnowski 等人 [13] 做了类似的工作, 他们发现在同一证书
链中混合使用不同的签名可以提升握手性能.
第 2 种 AKE 设计思路是仅使用抗量子的公钥加密 (PKE/KEM) 完成身份认证并建立会话密钥. 由于后量子的
数字签名方案通常具有较长的公钥和签名长度, 而公钥加密或者密钥封装机制的公钥和密文长度通常较小, 因此
构造的认证密钥交换计算效率更高, 且传输的代价更小. 第 2 种设计思路可以更加细分为: 1) 使用密钥封装机制
(KEM) 构造 AKE; 2) 通过被动安全的公钥加密方案 (PKE) 构造 AKE. 使用密钥封装机制 (KEM) 构造 AKE 的代
表性工作为 Schwabe 等人 [14] 提出的 KEMTLS, 该工作是在 TLS 1.3 协议的基础上, 通过 IND-CCA 安全的 KEM
构造的后量子 TLS 协议, 认证通过密钥封装机制完成, 其基本思想是, 能够成功解密对方发来的密文即可证明自
己是私钥的持有者. 作者测试了 NIST 算法征集中的所有 KEM 在 KEMTLS 的表现. 此外, 作者还给出了 KEMTLS
的安全性证明. 另一个代表性工作是 Hülsing 等人 [11] 提出的 PQ-WireGuard 协议, 这是一个虚拟专用网络 (VPN) 协
议, 作为 WireGuard [15] 协议的后量子版本. PQ-WireGuard 使用了 IND-CCA 安全的 Classic McEliece 替代使用长期
DH 密钥交换用于身份认证, 使用了 Saber 变体 [9] 的 IND-CPA 安全的 Dagger KEM 替代临时 DH 密钥交换. PQ-
WireGuard 实现了 WireGuard 的所有安全属性, 例如享受单程密钥交换的好处, 固定的密码套件, 并在性能上优于
IPsec 和 OpenVPN. PQ-WireGuard 比 WireGuard 慢不到 60%. 此外, 李子臣等人 [16] 提出了基于环上的 LWE 假设
(RLWE) 的认证密钥交换, 并在 eCK 模型下给出了安全性证明. 这是一个两轮的密钥交换, 根据文献 [6] 分析, 两
轮的 AKE 无法做到完美的前向安全性.
对于通过 PKE 构建 AKE 的研究, 代表性工作包括 Xue 等人 [17] 提出的 AKE, 该工作从所谓的“2-key” KEM 出
发, 提供了一个通用的构造方法. 直接从弱安全 (IND-CPA) 的 PKE 构造 AKE, 因此可以去除一些冗余操作 (例如
哈希函数). 另一项具有类似思路的工作是由 Hövelmanns 等人 [18] 提出的一种通用的方法, 主要技术是将一些 FO
变换的机制移入 AKE, 这是一个两轮的密钥交换. 作者并未对这种通用框架进行实例化, 此外, 该构造的安全性证
明使用的模型要弱于 eCK-PFS-PSK 模型, 无法达到完美的前向安全性.

2 基础知识

Kyber-PFS-AKE 主要基于公钥加密 (PKE), 下面就相关概念和基本安全性定义予以介绍.
$
,
x x ←− D
给定 n ∈ N [n] 表示 {1,2,...,n}. 对于有限集 S, |S | 表示其基数. x ←− S 表示从 S 中均匀随机选择元素 . $
?
表示从分布 D 中随机采样元素 x. = 为布尔表达式, 如果等式成立则值为 1, 否则为 0. 对于一个确定性算法 A, 其
$
输入为 x, 输出为 y, 记作 y ←− A(x). 对于一个概率算法 A, 其输入为 x, 输出为 y, 记作 y ←− A(x). 如果敌手 A 可以访
O
问预言机 O, 记作 A . 如没有特殊说明, 算法均默认为概率算法.
定义 1. 公钥加密方案. 密钥空间为 K 的公钥加密方案 PKE = (KeyGen,Enc,Dec) 由以下算法组成: (1) 密钥生
n (pk, sk). 密钥生成过程表示为
成算法 KeyGen: 给定安全参数 1 和公共参数 pp, 概率算法 KeyGen 输出一对公私钥
n m, 输出其加密
:
(pk, sk) ← KeyGen(1 ; pp). (2) 公钥加密算法 Enc Enc 输入公共参数 pp、公钥 pk 以及待加密明文
结果 ct. 公钥加密过程表示为 ct ← Enc(pp; pk,m). (3) 解密算法 Dec: 确定性算法 Dec 输入私钥 sk 和密文 ct, 输出
′ m ← Dec(sk,ct).
′
解密结果 m . 解密过程表示为
● 公钥加密方案的正确性. 解密过程存在一定的错误概率, 如果对于明文空间中任意 m ∈ M, 满足 Pr[m =
n , Enc 中的随机采样,
Dec(sk,ct)] ⩾ 1−δ, 其中 (pk, sk) ← KeyGen(1 ; pp) ct ← Enc(pp; pk,m), 概率来自于 KeyGen 和
则称公钥加密方案是 δ -正确的.