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

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

更优的性能, 提供了高达 26 倍的吞吐量. Kyber 是 LWE 路线的代表性格基密钥封装方案, 目前已被 NIST 标准
化, 其底层代数结构为分圆环. 素阶数域使得 CTRU-Prime 能够抵御子域攻击等针对分圆环的攻击, 也引入了额
外的性能开销, 例如多项式求逆无法被转移到子环上进行, 这使得无法有效提升最为耗时的多项式求逆的运算
速度, 因此, 同 RTX 3080 平台上实现的 Kyber-768 相比, 具有相当安全性且基于 RTX 3060 平台实现的 CTRU-
Prime-761 的密钥生成吞吐量较低. 除此之外, 在密钥封装和密钥解封装上同样展现出更优的性能, 与 Kyber-768
的 GPU 实现相比, 密钥封装吞吐量达到 1.46 倍, 密钥解封装达到 1.74 倍.

表 7 CTRU-Prime 的多平台实现对比和相关工作的吞吐量对比 (kOP/s)

吞吐量
方案 测试平台
密钥生成 密钥封装 密钥解封装
CTRU-Prime-653 [12] CPU 0.924 61.614 30.764
CTRU-Prime-761 [12] CPU 0.681 58.954 29.401
CTRU-Prime-1277 [12] CPU 0.243 34.204 16.883
CTRU-Prime-653 RTX 3060 63.639 (68.849×) 635.590 (10.316×) 351.532 (11.427×)
CTRU-Prime-761 RTX 3060 54.359 (79.779×) 2 745.392 (46.569×) 2 622.441 (89.197×)
CTRU-Prime-1277 RTX 3060 16.236 (66.843×) 1 601.174 (46.812×) 1 524.825 (90.317×)
Kyber-768 [20] RTX 3080 2 036 1 880 1 501
NTRUEncrypt [26] GTX 1080 － － 508
NTRU-HRSS [35] RTX 2080 － 105 114
注: 括号内的数值为吞吐量相较于CPU平台基线的倍数

6 总 结

本文提出了一种基于 CUDA Core 和 Tensor Core 的 CTRU-Prime 高吞吐量实现. 针对素阶数域的非 NTT 友
好性导致的 GPU 设计挑战, 本文提出两种素阶数域上多项式乘法的 GPU 实现方案. 基于 CUDA Core 的伪梅森数
不完整 NTT 多项式乘法使用层融合技术优化访存模式, 在 n=653, 761, 1277 的 3 组参数下, 分别实现了 1.09–11.08
倍、2.02–256.13 倍和 2.86–256.98 倍的吞吐量提升; 基于 Tensor Core 的教科书式多项式乘法将多项式乘法转化
为矩阵操作, 利用低精度 wmma 操作实现, 分别达到了 1.19–2.04 倍和 10.36–177.24 倍的吞吐量提升. 此外, 本文
结合批量模式和单一模式、多流技术和多线程技术, 给出了 GPU 平台上面向吞吐量的 CTRU-Prime 总体架构, 并
通过融合内核、合并全局内存访问、优化访存模式等优化策略, 显著加快了各核函数的访存和计算速度. 实验结
果表明, 基于 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 的 GPU 实现相比, 密钥封装吞吐量达到 1.46 倍, 密钥解封装
达到 1.74 倍, 是其他 NTRU 格基 GPU 高吞吐量实现的 26 倍.

References
[1] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Review, 1999,
41(2): 303–332. [doi: 10.1137/S0036144598347011]
[2] Hoffstein J, Pipher J, Silverman JH. NTRU: A ring-based public key cryptosystem. In: Proc. of the 3rd Int’l Algorithmic Number Theory
Symposium. Berlin: Springer, 1998. 267–288. [doi: 10.1007/BFB0054868]
[3] Liang ZC, Fang BY, Zheng JY, Zhao YL. Compact and efficient KEMs over NTRU lattices. Computer Standards & Interfaces, 2024, 89:
103828. [doi: 10.1016/J.CSI.2023.103828]
[4] IEEE standard specification for public key cryptographic techniques based on hard problems over lattices. IEEE Std 1363.1-2008, 2009.
[doi: 10.1109/IEEESTD.2009.4800404]
[5] NTRUEncrypt history. 2011. https://en.wikipedia.org/wiki/NTRUEncrypt