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

胡晓雯 等: 基于 CUDA Core 和 Tensor Core 的 CTRU-Prime 高吞吐量实现 3015

SNTRU-Prime-761 参数已经在 OpenSSH 中默认应用, 成为 KEM 事实标准.
CTRU-Prime [12] 在 CNTR 的基础上使用 LPPNF 代数结构, 在安全性、带宽、实现效率方面比 NTRU-Prime 更
有优势, 其目前已在国家密码标准化委员会作为制定类标准进行了立项. 然而, 像 CTRU-Prime 这样基于格的方案
存在高计算、内存开销大以及 IO 传输大的问题, 在查询量巨大的服务器端场景中, 这会导致其成为性能瓶颈. 此
外, 同基于非素阶数域的代数结构相比, CTRU-Prime 提供了更高的安全性, 但由于素阶数域不具备 NTT 友好性其
代码实现更为复杂.
此外, 图形处理单元 (graphics processing unit, GPU) 凭借其大规模并行计算能力和高吞吐量, 常被用于加速计
算密集型任务 [13] . 目前已经存在密钥封装、签名算法等基于 GPU 平台的优化实现, 例如, 文献 [14–16], 该类工作
通过释放 GPU 的 CUDA (compute unified device architecture) Core 和 Tensor Core 的计算潜力以进一步提高格基
密码的吞吐量. 目前, GPU 已广泛应用于需要后量子保护的云服务、物联网等场景, 因此基于 GPU 实现 CTRU-
Prime 是高效性和适用性的综合考量.
本文提出 CTRU-Prime-653、CTRU-Prime-761、CTRU-Prime-1277 的 GPU 高吞吐量实现. 该方案综合考虑
并行处理任务、高效访存、加速计算和优化算法等方面, 充分发挥 GPU 的计算能力, 加速算法的运行效率, 达到
高吞吐量的目标. 本文的主要贡献有以下几点.
(1) 素阶数域由于非 NTT 友好性, 在 GPU 设计上存在挑战. 提出两种素阶数域上多项式乘法的 GPU 实现方
案. 基于 CUDA Core 的伪梅森数不完整 NTT 的多项式乘法使用层融合技术优化访存模式, 在 n=653, 761, 1277 这
3 组参数下与 C 实现基线测试结果相比, 分别达到了 1.09–11.08 倍、2.02–256.13 倍和 2.86–256.98 倍的吞吐量.
基于 Tensor Core 的教科书式多项式乘法, 将多项式乘法转化为矩阵操作, 利用低精度 MMA (matrix-multiply-and-
accumulate) 操作实现, 其中通用的 tensor 乘实现和面向相同公私钥的 tensor 乘实现分别达到了 1.19–2.04 倍和
10.36–177.24 倍的吞吐量.
(2) 结合批量模式、单一模式、多流技术和多线程技术, 给出了 GPU 平台上面向吞吐量的 CTRU-Prime 总体
架构. 进一步地, 使用融合内核、合并全局内存访问、优化访存模式等优化策略, 加快各个核函数的访存和计算速
度. 通过实验验证上述优化思路的合理性: 在不同批处理大小上, 融合内核策略有效减少了 31.25%–73.17% 的内
核执行时间; 当并行度为 768, CUDA 流数量为 8 时, 使用多流技术能够减少 72.83% 的 CTRU-Prime-761 密钥解
封装算法的执行时间.
(3) 实验结果表明, 基于 RTX 3060 平台, CTRU-Prime-653、CTRU-Prime-761、CTRU-Prime-1277 每秒可以分
别进行密钥生成 6.3 万、5.4 万、1.6 万次, 密钥封装 63.5 万、274.5 万、160.1 万次, 密钥解封装 35.1 万、262.2 万、
152.4 万次, 是 C 实现版密钥生成吞吐量的 68.85、79.78、66.84 倍, 密钥封装吞吐量的 10.32、46.57、46.81 倍,
密钥解封装吞吐量的 11.43、89.19、90.32 倍. 同最新实现的 Kyber 相比, 密钥封装吞吐量达到 1.46 倍, 密钥解封
装达到 1.74 倍, 是其他 NTRU 格基 GPU 高吞吐实现的 26 倍.

1 相关工作

GPU 平台上的后量子密码加速可大致分为基于 CUDA Core 和基于 Tensor Core 两类.
基于 CUDA Core 设计并实现后量子密码是 GPU 后量子密码加速的主流方向. 例如, Gupta 等人 [15] 探索了后
量子密钥交换算法的 GPU 实现, 提出了 FrodoKEM-976、NewHope-1024 和 Kyber-1024 的 GPU 实现, 并设计了
简单模式和批处理模式以适应不同应用场景. Sun 等人 [17] 研究了基于多核平台的 SPHINCS 优化方法, 依据
SPHINCS 内部结构设计并行化版本, 并结合多种优化技术将其应用于 GPU 平台. Gao 等人 [18] 提出并比较了
NewHope 的基准实现、细粒度实现和多流实现, 探讨了不同优化策略在降低整体延迟和提高吞吐量方面的效果.
Shen 等人 [19] 提出了第 1 个面向服务器的高吞吐量 ML-DSA 签名设计, 通过稀疏三元多项式乘法技术实现深度优
先且提早拒绝的采样过程, 实现了显著的性能提升.
Tensor Core 主要用于 MMA 运算, 不少工作探讨了 Tensor Core 在后量子密码上的加速效果. Lee 等人 [16] 提出