Page 331 - 《软件学报》2026年第7期

3016 软件学报 2026 年第 37 卷第 7 期

使 Tensor Core 能够处理灵活的矩阵大小和临时密钥对的几种并行算法以加速格基密码的多项式卷积操作, 并将
该技术应用于 NTRU. Wan 等人 [20] 探讨了 Tensor Core 在精度和性能之间的权衡, 提出了密码原语到 AI 加速器运
算的转化框架和基于 Tensor Core 的 NTT 盒, 最终在 Kyber 上实施与评估. ConvKyber [21] 进一步优化了 Kyber 基
于 Tensor Core 的实现, 提出了两种将 Kyber NTT 转化为迭代矩阵乘法的创新方法, 使用汇编级代码精确操作
Tensor Core 内部资源. Hafeez 等人 [22] 引入单周期多公钥处理技术和乘法与约减分离技术, 利用 Tensor Core 加速
多项式乘法以提高密钥封装的性能, 并将该技术应用于 Sable 和 Florete. Hafeez 等人 [13] 提出了一种并行 Toeplitz
矩阵向量积版本以加速 GPU 上实现的多项式乘法, 在 CUDA Core 和 Tensor Core 上进行比较, 方案的有效性在
Saber 和 Sable 上得到验证.
NTRU 格基密码算法的 GPU 加速研究发展如下. 2010 年, Kamal 等人 [23] 使用 GPU 加速具有良好数据并行特
性的 NTRU-Encrypt. 2010 年, Hermans 等人 [24] 针对 CUDA 平台详细分析了确切的实现, 通过查看对分支、内存访
问、块和线程的潜在影响来解释每个选择的影响. 2014 年, Bai 等人 [25] 针对 NTRU 的大数据问题, 提出了单 GPU
零拷贝、单 GPU 数据传输和多 GPU 版本这 3 种策略来分别实现设备、块和线程级别的数据并行, 并使用流优化
技术来实现设备计算重叠. 2016 年, Dai 等人 [14] 利用 GPU 在大型向量处理上的优势对签名方案 NTRU-MLS 的底
层操作算子进行研究并加速, 通过 GPU 同时生成大量候选来进一步提高拒绝采样的效率. 2018 年, Akleylek 等人 [26]
提出了 NTRU-encrypt 的高吞吐量实现, 其提出的 Karatsuba 多项式乘技巧与通用实现相比具有 20.6% 的提升, 该
研究能够为 IoP 的两实体间通信提供有效安全保护.

2 基础知识

2.1 符号与定义
在本文中, R 表示实数集, Z 表示整数集, n,q 表示某些正整数, Z q = Z/qZ {0,1,...,q−1} 表示模 q 剩余系. 算
n n−1 次多项式且系数都
法实现中的多项式运算均在多项式环 R q = Z q [x]/(x − x−1) 上进行, 其中的元素均为最高
∑
n−1
f = i f i ∈ Z q .
在 Z q 中. 一般使用 f i x 来表示这个多项式环中的元素, 其中
i=0
设 D 为一个集合, 则符号 x ← D 表示从集合中均匀随机选取一个元素 x, 若 D 为一个概率分布, 则符号 x ← D
2η 中均匀随机采样得到
表示根据这一概率分布选取元素 x. 以整数 η 为参数的中心二项分布 B η 的定义为: 从 {0,1}
∑ η
(a 1 ,a 2 ,...,a η ,b 1 ,b 2 ,...,b η ), 输出 (a i −b i ). 而采样多项式 f ← B η 表示对每个系数进行采样.
i=1
2.2 数论变换
[6]
数论变换 (number theoretic transform, NTT) 是计算有限域上多项式乘法的高效实现, 它是快速傅里叶变换
n q 为
(fast Fourier transform, FFT) 在有限域上的特殊版本. 考虑多项式环 R q = Z q [x]/(x −1) 上的多项式乘法, 其中
ˆ
素数且满足 n|q−1, 那么可以在 Z q 中找到 n 次本原单位根 ω. 设 f 为 R q 上任意多项式, 则数论变换为 NTT(f) = f =
∑ n−1
ˆ
ij
ˆ ˆ ˆ f i = f j ω mod q, 这本质上是将多项式转化成点值表示, 从而将多项式乘法转化为向量对
( f 0 , f 1 ,..., f n−1 ), 其中
j=0
应位置元素的乘积, 本文使用“ ◦ ”表示这一乘积. 则 NTT 将 h = f ·g 转化为 NTT(h) = NTT( f)◦ NTT(g). 数论变换
∑ n−1
ˆ f i = n −1 ˆ −i j
的逆变换定义为 f = INTT( f), 其中 f j ω , 注意 f = INTT(NTT( f)), 因此 h = INTT(NTT(f)◦ NTT(g)).
j=0
基于中国剩余定理 (Chinese remainder theorem, CRT), 可以利用 FFT-trick 进一步加速 NTT. 如果多项式 f和g
互素, 则可以得到同构关系 Z q [x]/( fg) Z q [x]/( f)×Z q [x]/(g), 这一结论可以推广至任意多个两两互素的多项式. 一
N
m
m
m
般的基 N-NTT 对应的同构为: Z q [x]/(x Nm −ζ ) Z q [x]/(x −ζ)×Z q [x]/(x −ρζ )×...×Z q [x]/(x −ρ N−1 ζ ), 其中 ρ 为 Z q
N 次本原单位根. 正向 FFT trick 使用 CT (Cooley-Tukey) 蝴蝶操作 [6] , 逆向 FFT trick 使用 GS (Gentleman-
上的
Sande) 蝴蝶操作 [27] .
2.3 CTRU-Prime 算法描述
由梁志闯等人 [12] 提出的 CTRU-Prime 是基于素阶数域和尺度化 E 8 格编码设计的 NTRU 格基密钥封装方案.