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

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

算法 5. CTRU-Prime.KEM.Encaps.

pk ;
′
输入: 公钥
K
输出: 密文 c, 共享密钥 .
1. m ← M
2. (K,coin) = H(ID(pk),m)
3. c = CTRU-Prime.PKE.Enc(pk,m;coin)
4. return (c,K)

算法 6. CTRU-Prime.KEM.Decaps.
′
输入: 私钥 sk = (sk,z), 密文 c;
输出: 共享密钥 K.

′
1. m = CTRU-Prime.PKE.Dec(sk,c)
2. (K ,coin ) = H(ID(pk),m )
′
′
′
3. ˆ K = H 1 (ID(pk),z,c)
4. if m ,⊥ and c = CTRU-Prime.PKE.Enc(pk,m ;coin) then
′
′
5. return K ′
6. else
7. return ˆ K
2.4 GPU 简介
GPU 的线程组织形式是其强大计算能力的关键. 与 CPU 的少数几个复杂核心不同, GPU 拥有成千上万个较
简单的核心, 这些核心可以并行执行大量的线程. 在 CUDA 中, 线程被组织成线程块 (block) 和线程网格 (grid). 一
个线程块包含多个线程, 这些线程共享一个小的、快速的本地存储器 (称为共享内存), 可以高效地进行线程间的
数据交换和协作. 而多个线程块则组成一个线程网格, 线程网格可以覆盖整个 GPU 的计算资源. 这样的组织方式
允许 GPU 同时处理大量的数据块, 极大地提升了并行处理能力. 此外, GPU 还采用了一种称为 SIMT (single
instruction multiple threads) 的执行模式, 即多个线程同时执行相同的指令, 但操作的数据不同, 这种模式进一步提
高了计算效率. GPU 的内存结构也是其高效运算的重要因素之一. GPU 的内存层次结构包括全局内存、常量内存、
纹理内存、共享内存和寄存器等. 全局内存是容量最大但访问速度较慢的内存, 所有线程都可以访问. 常量内存和
纹理内存是只读的, 访问速度较快, 适合存储不变的数据. 共享内存则是一个线程块内的所有线程共享的内存, 具
有非常快的访问速度, 非常适合需要频繁访问的数据. 寄存器是每个线程独享的高速存储器, 用于存储临时变量和
数据. 通过这种层次化的内存结构, GPU 能够在不同的存储需求下优化数据访问效率, 从而提高整体计算性能.
GPU 拥有多个流式处理器 (streaming multiprocessor, SM). 在 SM 上, 寄存器、共享内存等资源有限, 且规定了最
大并行线程束数和最大并行线程块数. 基于此, 占用率 (occupancy) 是评估 SM 上活跃线程束比例的关键指标, 用
于衡量线程对 GPU 资源的利用是否合理. 具体来说, 核函数的占用率指的是在任意给定周期内, 每个 SM 上活跃
的线程束平均数量与该处理器支持的最大线程束数量的比率. 占用率分为理论占用率和实际占用率两种类型. 通
常情况下, 实际占用率应尽可能接近理论占用率, 而理论占用率则是基于核函数理论上所需的资源进行计算得出
的. 通过优化核函数设计以提高实际占用率, 可以更有效地利用 GPU 的并行处理能力.

3 素阶数域上多项式乘法的 GPU 设计与实现

多项式乘法是格基密码中最为耗时的操作之一, 一个通用的优化方式是使用 NTT 来加速这个过程, NTT 对于