应用于格密码的可重构多通道数论变换硬件设计

刘冬生 赵文定 刘子龙 张 聪 刘星杰

(华中科技大学光学与电子信息学院 武汉 430074)

1 引言

传统的公钥密码体制所基于的数学难题，如RSA(Rivest-Shamir-Adleman)和椭圆曲线密码(Elliptic Curve Cryptography, ECC)，早在1997年便被证明在量子计算下毫无安全性可言[1]。因此传统公钥密码体制构建的信息安全系统及各种应用将面临着严峻的安全问题，甚至是被完全破解的危险。因而能够抵御量子攻击的下一代密码方案及其实现技术，即后量子密码成为学界研究的热点。

2019年9月，谷歌宣布实现“量子霸权”：一台53量子比特的量子计算机在200 s内执行的运算任务需要经典计算机运行10000年[2]。2020年7月，美国国家标准与技术研究所宣布了后量子密码的第3轮候选方案。预计在2023年前后，后量子密码标准将被确立。同年12月，中国信息协会发布《量子安全技术白皮书(2020)》[3]，从多个角度对量子时代下的信息安全进行了阐述。在后量子密码标准的评选中，基于格难题的公钥密码，即格密码方案处于优势地位：在现有的7种候选方案中，CRYSTALSKYBER[4]、数论研究单元算法(Number Theory Research Unit, NTRU)和SABER都是基于格的后量子密码方案，因此格密码有着重大的研究与应用价值。

在诸多格密码方案中，多项式生成与多项式乘法运算是通用的核心算子，占用了绝大多数的时间资源开销[5]。以基于环误差学习(Ring-Learning With Error, Ring-LWE)格难题而构造的密码方案[5]为例，多项式乘法运算占整个加解密时间的80%以上，对格密码的实现与应用有着显著影响。在现有的研究中，数论变换(Number Theoretic Transform,NTT)、快速傅里叶变换(Fast Fourier Transform,FFT)和School-book都能够用于实现多项式乘法运算[5]。在时间方面进行比较，FFT和NTT的计算复杂度均为O(nlogn)，而School-book多项式乘法的计算复杂度为O(n2)[5,6]，随着n增大，School-book所消耗的时间会以指数上升；在运算方面进行比较，FFT涉及复数和浮点运算，NTT只在整数域中进行运算。综上所述，在格密码的多项式乘法运算中，采用NTT来计算模内多项式乘法，更易于硬件的高效实现，能够提升格密码的整体运算性能。

目前对NTT的研究主要集中在以下3个方面：

(1) 降低资源消耗与功耗：通过混合基与多通道延迟换向器，以及单口存储器合并多个内存部分，实现面积较小的NTT大整数乘法[7]。通过NTT非耦合结构，分别使用按时间抽取(Decimation In Time, DIT)与按频率抽取(Decimation In Frequency, DIF)的蝶形运算单元来实现低功耗的NTT与数论逆变换(Inverse Number Theoretical Transform, INTT)运算[8,9]。

(2) 降低运算时间、减小内部时延：通过脉动阵列，将多个蝶形运算单元串行组合起来，以快速完成连续多个NTT运算[6,10]。通过多通道技术，优化多通道地址分配方法与整体架构，以实现低时延[11,12]。

(3) 提高吞吐量：通过存储优化算法，对于单通道与多通道分别设计，以取得更高的吞吐量[13-15]。

本文从模乘算法和数论变换算法出发，研究基于随机存取存储器(Random Access Memory,RAM)的可重构模乘运算单元与多通道NTT架构。本文首先介绍了数论变换算法与多项式乘法，然后提出了基于RAM的模乘单元与多通道蝶形运算单元地址生成的硬件设计，进一步实现了支持4个不同参数n和15个不同参数q可重构NTT运算单元，最后给出了仿真验证的结果。

2 负包裹卷积与数论变换算法

3 NTT硬件设计

3.1 基于RAM的可重构模乘单元

蝶形运算单元(Butterfly Arithmetic Unit, BAU)是NTT运算的核心。本文设计了用于BAU的基于RAM的模乘器(RAM-based Modular Multiplier,RMM)如图1所示。该模乘器支持最高32 bit与32 bit的乘法，并可通过可重构操作改变模q的值，以实现不同模下的模乘运算，通过以下3步实现：

表1 基2 DIT-NTT算法

(1) 更新RAM内的值：Ref_din[31:0], Ref_addr[9:0]和Ref_ramchoose[1:0]用于为RMM中的两个双端口RAM提供数据与控制信号以进行更新。通过将乘法器MUL的积截取后作为地址信号输入RAM，能够直接得到RAM中存入的计算机预先计算好的求模结果。

(2) 改变积的截取方式：根据Ref_q_choosed[3:0]信号，IO_Ctrl模块分解MUL_out[63:0]，将其按位传送给RAMs和MOD_q(对输入的数据进行判断是否)。例如，当q为32 bit时，MUL_out[63:0]将被分解为{[63:56], [55:48], [47:40], [39:32],[31:0]}；当q为14位时，信号被分解为{8’d0, {2d’0,[27:22]}, [24:14], [13:0]}。

(3) 采用位截取模加法器：ADD0, ADD1,ADD2和ADD3对输入的信号进行求和，并将结果分为两路，一路减去模q、一路直接输出，根据减法运算中的进位信号选择一路，最后根据Ref_q_choosed [3:0]信号对数据按照模的位数截取、高位置0，输出模加结果。

为了达到高性能与资源开销的平衡，根据模q的最大位数，选择RAM的数量，以实现资源与性能的适配。因而本设计采用两个双口RAM实现，如图1所示。如使用1个双口RAM构成模运算器，则不需要模加法器，但需要消耗32×2×216位的内存容量。因而本设计采用4个模加法器，消耗内存容量为32×4×28位，显著减少了内存消耗，做到了较好的平衡。

根据所提出RMM结构可以实现任意q的模运算，随着q位的增加，RAM消耗的资源将呈指数级增长。相比而言，针对特定参数优化的模乘器在资源消耗方面具有明显的优势，但不适用于多参数可重构设计。

3.2 多通道蝶形运算地址生成的硬件设计

位反转(bit-reversed)能够简化DIT-NTT的地址生成。然而在多通道DIT-NTT的硬件实现中，地址的生成会变得十分复杂。因而本文设计了多通道蝶形运算地址架构，并采用Block RAM(BRAM)存储数据以取得更高的速度与利用效率。对于d通道DIT-NTT(长度n)，则2d为BRAM数量。DITNTT运算有3个步骤：

(1)数据应按照顺序存入BRAMs中，例如{0,1, cdots, n/d-1}于BRAM0, {n/d, n/d+1, cdots, 2n/d-1}于BRAM1, cdots,{(d −1)×n/d,...,n −1}于BRAMd-1。

(2)如图2所示，所有的BRAM被分为两部分，低位部分地址为0～k/2-1 (k=n/d)，高位地址部分为k/2～n-1。然后，BRAM0的一个端口和BRAM_d/2的端口连接到BAU0的a和b端口；BRAM0的b端口和BRAM_d/2的b端口连接到B A U 1 的a 和b 端口。B A U 2 的输入端口连接BRAM1的a端口和BRAM_d/2+1的a端口，依此类推。BAUd-1对应于BRAM_d/2-1和BRAM_d-1。

图1 基于RAM的模乘器结构图

图2 4通道NTT数据流向图

(3)每一轮结束后，输入Four_BRAMs和输出Four_BRAMs进行交换。在所有回合结束后，NTT结果将被存储到BRAM中，并以地址顺序递增的方式存储。

3.3 可重构NTT结构

高性能、可重构的多通道NTT结构如图3所示。BAUs包括RMM、位截取模加法器和位截取模减法器以及用于执行NTT蝶形运算的寄存器阵列。Ctrl包括状态机和一些控制信号的生成和反馈。ADDR生成Four_BRAMs和Wn_BRAMs的地址。NTT可重构设置将在多项式乘法之前进行：

(1) RAM中的数据更新。通过Ref_din[31:0],Ref_addr[11:0]和Ref_ramchoose[3:0]，连接到Wn_BRAMs与BMM中的RAM，对其进行数据更新。Ref_ramchoose[3:0]从低到高，分别为R M M 中的R A M 0, R A M 1 与W n_B R A M 0,Wn_BRAM1的读写控制信号。

(2) 参数n与q的设置：Ref_n[1:0]和Ref_q[3:0]分别按表2的顺序设置参数n和q。n传递至状态机；模q传递至RMM、模加/减器中，参与运算或对根据模q的位数对信号取最低位。

为了获得最大的吞吐量和最少的时钟周期消耗，两个双口BRAM分别进行读写操作来减少NTT操作所消耗的时钟周期至1/2。初始数据存储在Four_BRAMs_0中。多项式乘法包含以下6个步骤(n=2048)：

(1) Four_BRAMs_0将多项式a和b分别存储在2048低位地址和2048高位地址。

(2)执行NTT(a)。NTT(a)的结果存储在Four_BRAMs_1的低位2048地址中。在这个过程中，Four_BRAMs_0和Four_BRAMs_1都被用来存储中间变量。

(3) 执行NTT(b)。NTT(b)的结果存储在4个Four_BRAMs_1的高2048地址中。

(4) F o u r_B R A M s_1 输出N T T(a)和NTT(b)到BAU中计算的模内点乘(NTT(a)与Wn_in相连，NTT(b)与b_in相连，如图1所示)。结果N T T(a)⊙N T T(b)将被存储在F o u r_BRAMs_0的2048低位地址中。

(5) 执行INTT(NTT(a)⊙NTT(b))。结果c将存储在Four_BRAMs_1中。

(6) 执行inv⊙c运算。结果c将存储在Four_BRAMs_0中。

对于不同的n和q，q不会改变存储最终结果的BRAM。当n=256或1024时，结果将存储在Four_BRAMs_0中；当n=512或2048时，结果将存储在Four_ BRAMs_1中。所有的模q可以在不需要改变硬件结构的前提下改变，只需要更新相应BRAM中存储的数据即可。本设计可以从13 bit到32 bit实现任意15种模q参数的可重构。该设计在不同参数下具有相同的速度和资源消耗。为了满足最大n和q下NTT运算的需要，当n和q为其他的值时会有一部分存储空间与数据线路的高位被闲置。

图3 可重构NTT结构图

表2 可重构参数表

当q需要更改时，BRAM中的所有数据都需要更新以实现新的NTT操作。从理论上讲，该设计可以推广到任意参数n和q的可重构NTT的实现，所消耗的资源仅与最大的n和q有关。与Feng等人[11]提出的多通道Stockham结构相比，本设计具有参数灵活、动态可配置的优点。除此之外，本设计采用DIT-NTT结构，合并了负包裹卷积引入的参数，减少了1次多项式的点乘运算。因此本设计有很强的可拓展性与研究价值。

4 实现结果及对比

本文在Xilinx Artix-7(xca35tftg256)FPGA上实现了可重构多通道NTT设计。对于不同的参数，该设计消耗相同的资源(4780 Luts,1744 Slices,16 DSPs和24 BRAMs)，通过更新设置以及模乘器中的数据实现可重构操作。每个BAU包含6个32 bit模加法器、2个32 bit模减法器和1个32 bit×32 bit乘法器。BAU平均消耗资源为454 Slices。

多项式乘法的实现结果如表3所示。通过对传统NTT的优化，在单通道BAU下，1.5nlgn+2n时钟周期是极限值。本设计与NTT[5], NTT[6],NTT[11], FFT[12]进行了比较。与17 bit NTT的流水线结构[6]相比，该设计实现了32 bit NTT运算与可重构操作。由于模q的数据位数对资源消耗有显著影响，在ATP接近时，本设计的设计效率较NTT[6]而言更高。

表3 多项式乘法结果比较表

与采用FFT结构[12]进行多项式乘法相比，该设计在时间和资源消耗方面具有明显的优势。本设计采用4通道，理论需要(1.5nlgn+2n)/4个时钟周期。值得注意的是，多通道NTT[11]的(nlgn+2n)/d (d=16)时钟周期是由NTT(常数多项式a)的结果预存来实现的。这只能用于带误差的环学习(Ring-LWE)应用，在基于格的后量子加密方案中并不具备普适性。在n=512的情况下，16通道NTT设计[11]消耗了约本设计10倍的资源，延迟时间为(1.5n×9+2n)/(n×9+2n) ×1.77 = 2.49 μs。因此，所提4通道NTT结构具有第2小的ATP。根据实现结果，在n=1024时(时钟周期为4.3 ns)，1次NTT操作的延迟为6.71 μs(256为2.01 μs，512为3.57 μs，2048为13.43 μs)。

5 结论

为了解决NTT时延长与应用于不同加密环境的问题，本文提出一种可重构多通道NTT硬件设计。通过对多通道蝶形运算进行改进，设计了多通道NTT架构与基于RAM的可重构蝶形运算单元，以实现简单高效的可重构NTT运算，并在Xilinx Artix-7 FPGA平台上进行了验证。本设计的最大工作频率为232 MHz，能在6.71 μs内完成多项式长度为1024的NTT运算，并拥有第2小的ATP，具备很高的研究与应用价值。