一种基于基22MDC NTT结构的高性能环多项式乘法器

技术领域

本发明涉及格密码环多项式乘法，提出了一种基于基2

背景技术

在量子计算机诞生之后，现有的RSA、椭圆曲线等公钥密码体制的安全性将可能会被动摇，但格密码学的安全性基于最坏情况下的格上困难问题，所以其安全性有很强的保证，能够抵抗量子计算机的攻击。此外，格密码学上的计算非常简单，对于理想格和模格，所有算法都在多项式环中进行，许多情况下只需要多项式乘积模累加运算。

常规的多项式乘法不用考虑数域问题，但是在环上的多项式对多项式的系数和次数都有限制，例如给定两个环上的多项式a(x)和b(x)，设R

对于环上的多项式对系数大小受模值q限制，次数不超过n。

当两个环上的多项式相乘时，得到的多项式也要做相应处理使：

c(x)∈R

多项式乘法有几种有效的算法，而数论变换(Number Theoretic Transform，NTT)算法因其O(nlogn)的拟线性时间复杂度相比于其他算法更加高效、快速，是一种广泛应用于基于格密码的算法。NTT算法实际上是FFT的一个变体，相比FFT，其替代了复杂的浮点数和复数乘法的计算。因此，NTT算法的所有计算被执行在有限域或多项式环R

对于NTT变化，多项式a(x)的系数a

逆NTT(INTT)的操作是还原NTT的值，其变换规则如下：

变换式中的＝

1、对a(x)和b(x)中的系数进行预处理，即a＝a

2、将预处理后的系数进行NTT变换，即

3、多项式

4、对多项式

5、后处理多项式c(x)，即c

其中，预处理因子φ，后处理因子φ

若直接采用NTT/INTT变换公式,其计算复杂度并没有降低，研究者根据旋转因子的周期性，提出将输入序列或输出序列分解成更短序列的表达形式按域或频域抽取(常常被称做蝶形变换的一种分解算法)的迭代基2NTT结构，但是当多项式系数较大时，基2NTT的时间周期将会成倍增加，例如当n＝256＝2

发明内容

发明目的：为了进一步提高NTT/INTT核的处理速度，本发明提出了一种基于基2

为实现上述目的，本发明通过以下技术方案来实现：一种基于基2

每级处理单元均包括一个蝶形单元、多个具有不同延时周期的数据延时单元、多个用于存储NTT变换所需的旋转因子的存储单元和一个用于按照NTT算法将数据按正确时序往下传递的交换单元；所述蝶形单元和交换单元均包括四个输入通路和四个输出通路，从上至下依次定义为第一至第四输入通路和第一至第四输出通路，其中，第一级蝶形单元的第二输出通路的数据通过数据延时单元延时n×(y-3)/16个周期接入第一级交换单元的第二输入通路，蝶形单元的第三输出通路的数据通过数据延时单元延时n×(y-2)/16个周期接入第一级交换单元的第三输入通路，蝶形单元的第四输出通路的数据通过数据延时单元延时n×(y-1)/16个周期接入第一级交换单元的第四输入通路，第一级蝶形单元的第一输出通路直接接入第一级交换单元的第一输入通路；

第一级交换单元的第一输出通路的数据通过数据延时单元延时n×(y-1)/16个周期后接入第二级蝶形单元的第一输入通路，第一级交换单元的第二输出通路的数据通过数据延时单元延时n×(y-2)/16个周期后接入第二级蝶形单元的第二输入通路，第一级交换单元的第三输出通路的数据通过数据延时单元延时n×(y-3)/16个周期后接入第二级蝶形单元的第三输入通路；第一级交换单元的第四输出通路的数据直接接入第二级蝶形单元；

所述第k级蝶形单元的第二输出通路的数据通过数据延时单元延时(n×(y-3)/16)/4

其中，k＝2,3，…y-1；

所述第y级蝶形单元的四个输出通道输出的数据为NTT变换结果。

进一步的，蝶形单元的四个输入数据定义为第一输入数据、第二输入数据、第三输入数据和第四输入数据；所述蝶形单元包括多个模加单元、多个模减单元和多个模乘单元；

第一输入数据与第二输入数据通过模加单元、模减单元进行两两相加相减，分别得到第一中间相加结果和第一中间相减结果；

第三输入数据与第四输入数据通过模加单元、模减单元进行两两相加相减，分别得到第二中间相加结果和第二中间相减结果；

第二中间相减结果通过模乘单元与固定系数

第一中间相加结果与第二中间相加结果通过模加单元、模减单元相加相减，分别得到蝶形单元的第一输出通路的输出数据和第三中间相减结果；该第三中间相减结果通过模乘单元与旋转因子ω

第一中间相减结果与第二中间相减结果通过模加单元、模减单元相加相减，分别得到第四中间相加结果和第四中间相减结果；第四中间相加结果通过模乘单元与旋转因子ω

所述旋转因子ω

进一步的，在所述蝶形单元内设置寄存器单元，使蝶形单元的第一至第四输出通路同时输出数据。

进一步的，所述模乘单元为基于巴雷特约减算法的模乘单元。

进一步的，所述数据延时单元为不同容量的移位寄存器。

进一步的，当进行NTT正变换时，还包括用于按照NTT算法对输入序列进行预处理的前处理模块；所述前处理模块包括：

分组模块，用于将输入序列按顺序分成4组子序列；

预处理模块，用于将4组子序列分别与预先存储的对应的预处理因子φ相模乘，得到4组输出数据；

所述多路延迟转接电路对4组输出数据进行NTT正变换。

进一步的，当进行NTT逆变换时，还包括将输入数据与预先存储的后处理因子φ

本发明还公开了一种利用基2

步骤1：将输入序列分成4路并行序列，将各并行序列与对应的预处理因子φ相模乘，完成前处理，将前处理后的数据作为蝶形运算的输入数据；

步骤2：进行第一级蝶形运算，第一级蝶形运算后的第一输出数据按照NTT算法以正确时序延时n×(y-1)/16个周期后进行第二级蝶形运算；第一级蝶形运算后的第二输出数据延时n×(y-3)/16个周期后，按照NTT算法将延时后的数据按正确时序延时n×(y-2)/16个周期后进行第二级蝶形运算；第一级蝶形运算后的第三输出数据延时n×(y-2)/16个周期后，按照NTT算法将延时后的数据按正确时序延时n×(y-3)/16个周期后进行第二级蝶形运算；第一级蝶形运算后的第四输出数据延时n×(y-1)/16个周期后，按照NTT算法将延时后的数据按正确时序直接进行第二级蝶形运算；

第k级蝶形运算后的第一输出数据按照NTT算法以正确时序延时(n×(y-1)/16)/4

以此类推，第y级蝶形单元的输出数据为NTT正变换结果；

步骤3：根据NTT逆变换规则，变更参与蝶形运算的旋转因子值后执行步骤2，得到NTT逆变换结果；

步骤4：将NTT逆变换结果与后处理因子φ

有益效果：与现有的技术相比，本发明具有以下优点：

(1)本发明通过高基的NTT算法减少NTT变换的级数，进一步提高NTT/INTT在处理格密码中环多项式乘法器的速度；

(2)本发明调整输入序列的顺序，优化基2

附图说明

图1是26位巴雷特约减算法的电路结构图；

图2是基2

图3是基2

具体实施方式

现结合附图和实施例进一步阐述本发明的技术方案。

结合具体格密码参数，本实施例采用模数q＝7681，n＝256的参数，考虑到格密码两个多项式系数，一个是在上的均匀分布的公钥项，另一个是在上高斯分布或二项分布的数据，该数据位宽为13位。为了在硬件电路层面实现格密码中最关键的单元环多项式乘法的同时，进一步提高NTT/INTT核的处理速度，本实施例提出了如图3所示的基2

由图3可知，每一路的输出数据在两个蝶形单元之间的延时都应该相同，在本实施例中，数据延时单元为不同容量的移位寄存器，在第一级处理单元PE1中输入点数为256分为四路数据，每路有64个数据，这64个数据经过基2

本实施例对基2

从图2中可以直观看出优化后的蝶形单元的规律，在基2

参见图2，输入序列x(n)按照4r，4r+1，4r+2，4r+3分成四个子序列，则变换公式可以写成下式：

其中，i＝0,1,2...,n-1；r＝0,1,2,....,n/4-1，n为输入点数，可转化为：

整个输入序列被划分成4个子序列，使得整个变换的计算时间变短，减少变换所需的时钟周期，从而加速。

在用NTT算法运算环多项式乘法时，NTT正变换得到的数据只是中间顺序，多项式相乘的最终的多项式系数还需要NTT逆变换，在本实施例中集成了NTT正变换和逆变换单元，NTT和INTT在进行数据处理时候步骤一样，在进行NTT逆变换时候只需按照NTT逆变换规则改变旋转因子的值，并增加后处理模块，即后处理多项式c(x)，即c