后量子RISC-V：Dilithium和Kyber的定制ALU扩展

### 后量子RISC - V：Dilithium和Kyber的定制ALU扩展 #### 一、引言 近年来，量子计算领域的研究取得了巨大进展，这给密码学领域带来了重大变革。传统公钥密码学（PKC）的安全性基于大整数分解和离散对数计算等数学难题，这些问题在经典计算机上求解困难，但在大规模量子计算机上，使用Shor算法可在多项式时间内解决。这使得后量子密码学（PQC）受到了广泛关注，PQC算法运行于传统硬件上，且被认为能抵御量子攻击。 自2016年起，美国国家标准与技术研究院（NIST）开始对PQC算法进行标准化工作。2022年7月，NIST推荐了两种主要算法：CRYSTALS - Kyber和CRYSTALS - Dilithium。Dilithium是数字签名算法，用于验证消息或文档的真实性和完整性，保障数字交易安全；Kyber是密钥封装机制（KEM），用于安全地建立密钥，如用于安全网页浏览和电子邮件加密。这两种算法都基于理想格理论中的难题。 格基密码算法因其安全性、效率和通用性而备受关注，但在资源受限系统上实现时会面临挑战。例如，在pqm4基准测试框架中，Dilithium签名验证超过80%的运行时间和Kyber解封装超过75%的时间都花在了Keccak（SHAKE - 256）上。不过，由于（加固的）Keccak加速器已有大量研究，本文聚焦于下一个瓶颈——多项式运算。数论变换（NTT）作为离散傅里叶变换（DFT）的一种特殊形式，被许多格基算法用于降低多项式乘法的时间复杂度，但多项式运算仍然耗时，因此高效的硬件实现至关重要，尤其是在资源受限的环境中。 资源受限设备（如物联网设备、医疗设备、汽车处理器等）在实现密码算法时面临独特挑战。为了适应这些设备的限制，需要低面积的PQC算法实现，但这些实现因操作复杂而成本高昂。因此，硬件/软件（HW/SW）协同设计策略应运而生，旨在结合硬件实现的高速性能和软件设计的灵活性。 RISC - V作为一种开源指令集架构（ISA），支持自定义扩展，为实现各种算法（包括格基算法）提供了灵活的平台。开发者可以添加专门的指令来满足特定应用需求，这些指令可以在典型处理器数据路径、与主处理器相连的协处理器或集成了自定义加速器的修改后处理器数据路径上运行。 本文的目标是为Dilithium和Kyber的NTT及其他多项式运算设计并实现一个自定义硬件加速器，主要目的是优化加速器的资源利用，尽量减少对RISC - V核心的改动，同时提高NTT计算速度。具体贡献如下： - 一个轻量级自定义算术逻辑单元（ALU），适用于两种方案的NTT计算需求。该ALU无缝集成到一个4级流水线32位RISC - V处理器中，支持模块化操作（加法、减法和乘法）以及NTT和逆NTT蝶形运算（Cooley - Tukey和Gentleman - Sande）。 - 对RISC - V ISA进行扩展，引入十条新指令，每种方案五条。这些指令访问自定义ALU并执行上述操作，每条指令只需一个时钟周期即可执行。 - 我们的ALU是文献中最小的，仅使RI5CY核心的资源利用率增加13 - 17%（取决于工作频率）。我们在特定时钟频率（100 - 400 MHz）下进行了测量，证实自定义RISC - V核心与新定制ALU在这些频率下运行时，性能与原始RISC - V核心相比没有下降。 - 我们实现并对各种操作进行了基准测试，证实PQVALUE使Kyber和Dilithium的NTT周期数比优化汇编减少了80%以上，并显著提高了完整算法的运行时间。 #### 二、预备知识 ##### 2.1 数论变换（NTTs） Ring - 和Module - LWE的引入将算术运算从一般格转移到了形式为$R = Z_q[X]/(X^n + 1)$的多项式环中，其中$q$是素数，$n$是整数。关键操作包括线性复杂度为$n$的多项式加法和减法，以及多项式乘法。多项式乘法是一个更复杂的操作，使用朴素的学校乘法方法具有二次复杂度，但可以通过Karatsuba、Toom - Cook和数论变换（NTTs）等技术加速。NTT在通用多项式环中不可行，因此格基构造选择了这种特定形式的$R$。素数$q$被选择得较小，例如Kyber的$q$为12位，Dilithium的$q$为23位，而$n$通常选择为2的幂（通常为256）。此外，$q$被选择为具有足够大阶的单位根$\zeta$，即阶为$n$或$2n$。 NTT的形式取决于单位根的选择和实现方式。例如，Kyber环只包含$n$次单位根，而Dilithium环包含$2n$次单位根，这导致了实现NTT的策略略有不同。对于Kyber，给定输入多项式$f$，NTT计算（最多重新排序）： $R \to \sum_{i = 0}^{127} Z_q[X]/(X^2 - \zeta^{2i + 1})$ $f \to [f \mod (X^2 - \zeta), \cdots, f \mod (X^2 - \zeta^{255})]$ 这是通过中国剩余定理（CRT）实现的同构。逆NTT计算逆同构。对于Dilithium，NTT计算（最多重新排序）： $R \to \sum_{i = 0}^{255} Z_q[X]/(X - \zeta^{2i + 1})$ $f \to [f \mod (X - \zeta), \cdots, f \mod (X - \zeta^{511})]$ 逆运算根据CRT计算逆同构。 NTT的实际实现类似于离散傅里叶变换（DFT）的策略。NTT可以构造为一个包含$\log_2(n)$层的序列，每层包含$n/2$个蝶形运算，每个蝶形运算由一个基域乘法、加法和减法组成。这些被称为正向NTT的Cooley - Tukey（CT）蝶形运算。算法的总复杂度为$n \log(n)$，比其他现有方法快得多。正向NTT中的蝶形运算序列会导致系数重新排序，这与CRT同构不同，但只要在逆NTT操作中考虑到这一点（通常不会影响性能）就不是问题。例如，可以通过将逆NTT的蝶形结构从Cooley - Tukey改为Gentleman - Sande（GS）来解决。需要注意的是，由于上述不同的同构，Kyber NTT只使用$\log_2(n) - 1 = 7$层，而Dilithium使用$\log_2(n) = 8$层。 ##### 2.2 Barrett约简 Barrett约简是一种使用预计算数据来高效计算模约简的方法，该预计算数据仅取决于所用的模数。给定一个正奇数模数$q$，满足$2^{n - 1} < q < 2^n$，以及输入值$0 \leq c < q^2$，可以计算$c' = c \mod q$为： $c' = c - m \cdot q$，其中$m = \lfloor c/q \rfloor$ 其思想是通过固定精度整数来模拟浮点数据类型，近似$m = \lfloor c/q \rfloor$为： $m_1 = \lfloor c / 2^{2n} \cdot \lfloor 2^{2n} / q \rfloor \rfloor = \lfloor c \cdot \mu / 2^{2n} \rfloor$ 其中$\mu = \lfloor 2^{2n} / q \rfloor$是预计算的常数。由于$m - 1 \leq m_1 \leq m$，这种近似几乎正确，并且只需要高效的整数除以2的幂（即右移）操作。 Dilithium和Kyber中使用的素数模数的Barrett模约