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

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

定理 1. Kyber-PFS-AKE 在满足清洁谓词的情况下, 是 eCK-PFS-PSK 安全的. 即任意敌手 A 在密钥不可区分

游戏中的优势 Adv eCK-PFS-PSK (λ) 都被限制在敌手 A 在对偶-PRF, IND-CPA 以及 auth-aead 游戏中的优势, 具体
clean eCK-PFS-PSK,n P ,n S ,A
来说:

( )
2
Adv eCK-PFS-PSK (λ) ⩽ n n S n S + Adv(A )+6· Adv pr f (λ)+ Adv pr f swap (λ)+ Adv auth-aead (λ)
′
2
clean eCK-PFS-PSK,n P ,n S ,A P λ KDF,R KDF,R AEAD,R
( )
2 n S ′ pr f pr f swap auth-aead
+n n S + Adv(A )+3· Adv (λ)+ Adv (λ)+ Adv (λ)
P λ KDF,R KDF,R AEAD,R
2
 2 2 pr f pr f swap
 n n (2· Adv (λ)+ Adv (λ))
 P S KDF,R KDF,R



 pr f swap
 2 2 IND-CPA pr f
 n n (Adv (B)+4· Adv (λ)+ Adv (λ))

 P S
 CPAPKE,R KDF,R KDF,R




 2 2 ′ pr f
 n n (Adv(A )+7· Adv (λ))
+max  P S KDF,R ,


 pr f swap
 2 2 pr f
′
 n n (Adv(A )+3· Adv (λ)+ Adv (λ))

 P S
 KDF,R KDF,R


 ( )


2
 n S pr f
 n n 2 + Adv(A )+7· Adv (λ)
′

P S λ KDF,R
2
其中, Adv IND-CPA (B) 是任意敌手 B 对 IND-CPA 安全的 PKE 游戏中获胜的概率. 在多用户设置中 (即存在多个拥有
PKE
不同公钥的接收者, 将同一个消息 m 使用对应的公钥发送给这些接收者, 随后敌手尝试解密该消息. 在特定的参
数设置下, 敌手可以解密出 RSA 密文. 考虑攻击者破解多个用户密文的优势. 在量子随机预言模型 (QROM) 下, 敌
′
手 A 的优势为:

√ √
√ q C ·n n 2 n q 2
2
′
Adv(A ) ⩽ 2 qAdv (n,q c )-IND-CPA (B)+4q + +4(q F +1) +16q δ(n)+ C ,
PKE l l
|M| 2 2 |M|
,
其中, q := q F +q D +1 n 是用户的数量, q C 是挑战密文的个数, q F 是 (Q)ROM 查询的最大次数, q D 是解密查询的最
大次数.
5 算法实现性能评估
我们使用 Kyber-768 进行实验, 用于对比 Kyber-PFS-AKE 和 Kyber-AKE 的性能. Kyber-768 是 Kyber 向
NIST 算法竞赛提交的算法实现代码中, 安全级别为 III (其经典安全强度为 182 比特, 其量子安全强度为 165 比
特). 我们参照 NIST 颁布的标准, 使用 Kyber 的第 3 轮提案提供的 AVX2 指令集上实现的代码基础上进行实验.
注意到 Kyber-768 提供了两个版本, Kyber-768 和 Kyber-768-90s, 两者的区别在于随机数发生器不同. 尽管 Kyber-
768-90s 拥有更高的计算性能, 但根据 NIST 给出的报告, Kyber-768-90s 不会被标准化, 因而我们只选用了 Kyber-
768 的实现代码. 此外, 由于 Kyber-AKE 来自 Fujioka 等人给出的通用构造 [5] , 其用于生成临时公私钥对 (epk i ,esk i )
的 KEM 可以为 IND-CPA 安全的 KEM, 在实验中我们采用 IND-CPA 安全的 KEM 进行该部分计算.
协议中存在的其他模块, 对于密钥导出运算 (即 KDF), 我们使用 BLAKE2s 算法 [21] , 对于 AEAD, 我们采用了
ChaCha20-Poly1305 算法 [22] . 这两种算法的也在 WireGuard、Noise 中使用. 因此我们采取了与其一致的代码. 所有
基准测试均在 Intel Core i7-6700 处理器上进行, 时钟频率为 900 MHz (查询/proc/cpuinfo 获得), 关闭了 TurboBoost
和超线程, 基准测试机器具有 16 GB 的 RAM, 运行 Ubuntu 操作系统, 内核版本为 5.4.0. 报告的所有循环计数均为
各自函数的 10 000 次执行的中值. 对比结果如表 1 所示.

表 1 实验数据集

性能指标 Kyber-AKE Kyber-PFS-AKE 计算性能提升百分比 (%)
发起者计算时间 258 464 158 445 38.6
响应者计算时间 234 297 162 289 30.7

如表 1 所示, 与 Kyber-AKE 相比, 我们的设计在发起方和响应方设备上均节省了近 30% 的计算工作量. 影响
握手时间的另一个重要因素是数据传输, 而在我们的构建和 Kyber-AKE 中传输的数据长度相同, 这意味着两个协