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

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

Abstract: The rapid development of quantum computers poses significant threats to existing cryptographic systems. The implementation
and migration of post-quantum cryptographic algorithms are therefore of utmost importance. Among these, NTRU lattice-based
cryptographic schemes have gained attention due to their simplicity and computational efficiency. The CTRU-Prime scheme, based on
NTRU lattices, stands out for its excellent performance in security, bandwidth, and implementation efficiency. Given the powerful
capabilities of GPUs in handling large-scale parallel processing tasks, this study presents the first high-throughput implementation of
CTRU-Prime using Tensor Core and compute unified device architecture (CUDA) Core. The underlying algebraic structure of CTRU-
Prime is large-Galois-group prime-degree prime-ideal number field (LPPNF), which not only resists attacks targeting cyclotomic rings but
also presents challenges for the implementation of polynomial multiplication. First, two GPU implementations of polynomial multiplication
over LPPNF are proposed. The CUDA Core-based Pseudo-Mersenne incomplete NTT polynomial multiplication uses layer fusion
techniques to optimize memory access patterns, achieving a throughput of 256.98 times. The Tensor Core-based schoolbook polynomial
multiplication converts polynomial multiplication into matrix operations, leveraging low-precision matrix-multiply-and-accumulate (MMA)
operations, achieving a throughput of 177.24 times. Next, an overall architecture for CTRU-Prime on the GPU platform is presented,
focusing on throughput. This architecture combines batch mode and single mode, multi-stream technology, and multi-thread techniques.
Optimization strategies such as fused kernels, coalesced global memory access, and optimized memory access patterns are employed to
accelerate memory access and computation speeds of various kernel functions. Experimental results show that, on the RTX 3060 platform,
CTRU-Prime-653, CTRU-Prime-761, and CTRU-Prime-1277 can perform key generation at rates of 63 000, 54 000, and 16 000 times per
second, respectively; key encapsulation at rates of 635 000, 2 745 000, and 1 601 000 times per second, respectively; and key decapsulation
at rates of 351 000, 2 622 000, and 1 524 000 times per second, respectively. These rates are 68.85, 79.78, and 66.84 times higher for key
generation, 10.32, 46.57, and 46.81 times higher for key encapsulation, and 11.43, 89.19, and 90.32 times higher for key decapsulation
compared to the C implementation. Compared to the latest Kyber implementation, the key encapsulation throughput is 1.46 times higher,
and the key decapsulation throughput is 1.74 times higher, making it 26 times more efficient than other high-throughput NTRU lattice-
based GPU implementations.
Key words: post-quantum cryptography; NTRU Lattice-based cryptography; key encapsulation mechanism (KEM); parallel processing;
graphics processing unit (GPU)

随着量子技术的突飞猛进, 传统的公钥密码系统正面临重大威胁. 量子敌手能够利用 Shor 算法 [1] 在多项式时
间破解当前公钥密码体制所基于的大整数分解和离散对数等经典困难问题. 因此, 研究能够抵抗量子攻击的新型
公钥密码算法——后量子密码, 得到了学术界和工业界的广泛关注.
当前, 出现了许多后量子密钥封装方案 (key encapsulation mechanism, KEM). 美国国家标准与技术研究院
(National Institute of Standards and Technology, NIST) 在向社会各界发出的新密码体制征求提案中, 就包括 KEM.
在征集的方案中, 基于 NTRU 格的密码体制备受瞩目. Hoffstein 等人 [2] 于 1998 年正式提出了 NTRU 加密方案, 如
今 NTRU 已成为各种密码学原语 (如提议标准化的数字签名方案 Falcon) 的基础组成部分. 基于分圆环的 CNTR [3]
首次将高维 NTRU 格密码与底层格编码联系起来, 它使用单个密文多项式来压缩密文, 并针对 NTRU 型 KEM 在
安全性、带宽、错误率和实现效率方面实现了均衡的性能. 此外, 基于 NTRU 格的方案早已走上标准化和商业化
的道路. 早在 2009 年, IEEE 标准 1363.1 就包括了基于格的密码方案, 包括 NTRUEncrypt . 2011 年, X9.98 标准采
[4]
用了 NTRUEncrypt 用于金融服务 [5] . 2016 年, Schanck 等人 [6] 尝试通过使用 NTRUEncrypt 生成额外的临时密钥与
临时 ECDH 密钥一起使用, 以增强 Tor 协议在量子时代的前向保密性. 国际标准 OpenSSH 在 2022 年 4 月发布的
9.0 版 [7] 及以后版本中, 采用了 NTRU-Prime 与 X25519 ECDH 相结合的混合模式, 以抵御“解密后捕获”攻击. 然而,
大多数现有的基于格的密码方案, 包括 NTRU, 都是基于分圆环构造的. 如文献 [8–10] 中所强调的, 分圆环的丰富
代数结构使这些方案容易受到攻击. Bernstein 等人 [11] 提出了一个具有“高安全性、素数阶、大 Galois 群和惰性模
数”的基础代数结构, 本文将这类大 Galois 群、素数阶、基于素理想的数域 (large-Galois-group prime-degree prime-
ideal number field, LPPNF) 简称为素阶数域. Bernstein 等人 [11] 还建议将现有的基础代数结构从分圆环迁移到素阶
数域, 以抵御已知和潜在的针对分圆环的攻击, 从而提供更保守的安全性方案. 基于素阶数域设计各种基于格的密
码方案是格密码学中安全、可靠、高效且实用的路线. 因此, NTRU-Prime 方案在这种背景下被提出 [11] , 并且其