基于NTT和INTT结构的多项式乘法运算方法和多项式乘法器

摘要

本发明公开了一种基于NTT和INTT结构的多项式乘法运算方法和多项式乘法器。该方法包括将预处理步骤与NTT变换进行合并，得到合并NTT变换，并分别对输入的多项式a(x)和b(x)进行合并NTT变换，得到多项式A(x)和B(x)；对多项式A(x)和B(x)的系数执行点乘运算，得到点乘运算结果C(x)：C(x)＝A(x)⊙B(x)modq，其中，q表示多项式环R

说明书

技术领域

本发明涉及格密码环多项式乘法，尤其涉及一种基于NTT和INTT结构的多项式乘法运算方法和多项式乘法器。

背景技术

随着云计算技术的飞速发展，针对云端数据的隐私保护问题日益突显。全同态密码因为具有良好的密文同态计算性质，能够对密文直接进行密态计算而不需要解密，已经广泛应用于云计算隐私保护和外包计算。其中基于环上的错误学习问题(Ring LearningWith Error，RLWE)的全同态密码算法因具有更高的效率，得到了更为广泛的发展。而多项式乘法运算是基于RLWE的全同态密码运算中最为复杂和耗时的计算单元，是制约全同态密码运算性能的关键模块。

目前主流的面向全同态密码运算的多项式乘法器主要采用数论变换(NumberTheoretic Transform,NTT)算法实现，相比于教科书式的多项式乘法器和基于Karatsuba算法的多项式乘法器，基于NTT的多项式乘法器的计算复杂度可以降低为次线性复杂度O(nlogn)。对于给定的两个环上的多项式a(x)和b(x)，假设环为

如图9所示，采用传统的基于负折叠卷积(Negative Wrapped Convolution,NWC)的NTT多项式乘法器的运算步骤如下：

1、对输入多项式a(x)和b(x)执行预处理步骤，多项式a(x)和b(x)的每个系数分别乘以预处理因子ψ

2、对

其中，旋转因子项

3、对A(x)和B(x)的系数执行点乘运算，即

4、对C(x)的系数执行反向NTT(INTT)变换：

其中，旋转因子项

5、对

基于负折叠卷积的NTT多项式乘法器在继承了NTT多项式乘法器低线性复杂度的同时，避免了对多项式a(x)和b(x)进行零填充操作，有效缩短了参与NTT变换的多项式长度。但是，代价是引入了对多项式a(x)和b(x)的预处理步骤和对结果多项式b(x)的后处理步骤，带来了额外的计算开销。另外，对于多项式乘法器的硬件设计，通常需要为NTT变换、INTT变换、点乘以及点乘加运算分别设计单独的硬件结构，带来了额外的硬件资源开销。

发明内容

本发明实施例提供了一种基于NTT和INTT结构的多项式乘法运算方法和多项式乘法器，旨在解决现有技术中基于负折叠卷积的NTT多项式乘法器存在额外计算开销的问题。

第一方面，本发明实施例提供了一种基于NTT和INTT结构的多项式乘法运算方法，其包括：

将预处理步骤与NTT变换进行合并，得到合并NTT变换，并分别对输入的多项式a(x)和b(x)进行合并NTT变换，得到多项式A(x)和B(x)；

对多项式A(x)和B(x)的系数执行点乘运算，得到点乘运算结果C(x)：C(x)＝A(x)⊙B(x)mod q，其中，q表示多项式环R

将后处理步骤与INTT变换进行合并，得到合并INTT变换，对C(x)进行合并INTT变换，得到c(x)。

第二方面，本发明实施例提供了一种多项式乘法器，包括可重构乘法器模块，所述可重构乘法器模块执行如上述任一项所述的基于NTT和INTT结构的多项式乘法运算方法。

本发明实施例提供了一种基于NTT和INTT结构的多项式乘法运算方法和多项式乘法器。该方法包括将预处理步骤与NTT变换进行合并，得到合并NTT变换，并分别对输入的多项式a(x)和b(x)进行合并NTT变换，得到多项式A(x)和B(x)；对多项式A(x)和B(x)的系数执行点乘运算，得到点乘运算结果C(x)：C(x)＝A(x)⊙B(x)mod q，其中，q表示多项式环R

附图说明

为了更清楚地说明本发明实施例技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本发明实施例基于NTT和INTT结构的多项式乘法运算方法的多项式乘法器结构示意图；

图2是当N＝8时，本发明实施例基于NTT和INTT结构的多项式乘法运算方法中将预处理步骤和后处理步骤合并到NTT和INTT变换后的结构图，(a)表示将预处理步骤合并到NTT变换后的NTT结构图，(b)表示将后处理步骤合并到INTT变换后的INTT结构图；

图3是本发明实施例中多项式乘法器的总体电路示意图；

图4是本发明实施例中可重构乘法器模块的电路示意图；

图5是本发明实施例中1/2模乘器电路图；

图6是本发明实施例中可重构Barrett模乘器电路图；

图7为传统的基于负折叠卷积的NTT多项式乘法器结构图；

图8为当N＝8时，传统的NTT变换和INTT变换结构图，(a)NTT变换结构图，(b)INTT变换结构图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

应当理解，当在本说明书和所附权利要求书中使用时，术语“包括”和“包含”指示所描述特征、整体、步骤、操作、元素和/或组件的存在，但并不排除一个或多个其它特征、整体、步骤、操作、元素、组件和/或其集合的存在或添加。

还应当理解，在此本发明说明书中所使用的术语仅仅是出于描述特定实施例的目的而并不意在限制本发明。如在本发明说明书和所附权利要求书中所使用的那样，除非上下文清楚地指明其它情况，否则单数形式的“一”、“一个”及“该”意在包括复数形式。

还应当进一步理解，在本发明说明书和所附权利要求书中使用的术语“和/或”是指相关联列出的项中的一个或多个的任何组合以及所有可能组合，并且包括这些组合。

如图1所示，一种基于NTT和INTT结构的多项式乘法运算方法，包括：

将预处理步骤与NTT变换进行合并，得到合并NTT变换，并分别对输入的多项式a(x)和b(x)进行合并NTT变换，得到多项式A(x)和B(x)；

对多项式A(x)和B(x)的系数执行点乘运算，得到点乘运算结果C(x)：C(x)＝A(x)⊙B(x)mod q，其中，q表示多项式环R

将后处理步骤与INTT变换进行合并，得到合并INTT变换，对C(x)进行合并INTT变换，得到c(x)。

在一实施例中，分别对输入的多项式a(x)或b(x)进行合并NTT变换，得到A(x)和B(x)，包括：

步骤1：对输入的多项式a(x)的向量a执行比特逆序操作，得到比特逆序后的多项式向量a；

步骤2：当合并NTT变换的运算级数s满足1≤s≤log

步骤3：当合并NTT变换的蝶形运算步数j满足0≤j＜N/2时，执行步骤4；

步骤4：计算旋转因子幂次项指数

步骤5：计算蝶形运算步骤：

步骤6：执行s＝s+1，并判断s是否等于log

本实施例将预处理步骤合并到NTT变换的方法可以避免输入多项式和再单独执行预处理步骤，而是直接将a(x)和b(x)分别代入上述步骤1中的，并执行合并预处理步骤后的NTT变换，从而直接得到变换后的多项式A(x)和B(x)。该方法避免了预处理步骤中涉及到的乘法运算，有效减小多项式乘法器的计算复杂度。进一步的，将预处理步骤合并到NTT变换的方法用于基于恒定几何(Constant Geometry,CG)算法的DITNTT算法。

具体的，当把预处理步骤合并到正向NTT变换之后，对于输入多项式a(x)，原始的NTT正向变换公式可以变换为式(5)，并得到转换后的多项式

采用时域抽取(DecimationinTime,DIT)的方法，将合并预处理步骤后的NTT变换拆分成基本的蝶形运算单元可以有效加速NTT变换的运算速度，包括如下步骤，根据a

将得到的

令

由式(8)判断出

根据以上公式的推导，则将预处理步骤合并到NTT变换后，基于恒定几何(Constant Geometry,CG)算法的DITNTT变换蝶形运算结构可由原来的式(3)转换为式(9)：

其中，

在一实施例中，对C(x)进行合并INTT变换，得到c(x)，包括：

步骤(1)：对输入的多项式A(x)的向量A，当INTT变换的运算级数1≤s≤log

步骤(2)：当INTT变换的蝶形运算步数j满足0≤j＜N/2时，执行步骤(3)；

步骤(3)：计算旋转因子幂次项指数

步骤(4)：计算蝶形运算步骤：

a[2j]←(A[j]+A[j+N/2])·2

步骤(5)：执行s＝s+1，并判断s是否等于log

步骤(6)：对输出的多项式向量a执行比特逆序操作，得到比特逆序后的多项式向量a，得到多项式a(x)，其中，C(x)代入上述步骤(1)中A(x)。

本实施例将后处理步骤合并到INTT变换的方法可以避免输出多项式C(x)再单独执行后处理步骤，而是直接将C(x)代入上述步骤(1)中的A(x)，并执行合并后处理步骤后的INTT变换，从而直接得到变换后的多项式c(x)。避免了后处理步骤中涉及到的乘法运算，有效减小多项式乘法器的计算复杂度。进一步的，所述的将后处理步骤合并到INTT变换的方法用于基于恒定几何(Constant Geometry,CG)算法的DIF INTT算法。

具体的，当把后处理步骤合并到INTT变换之后，对于输入多项式A(x)，原始的INTT反向变换公式变换为式(10)，并得到转换后的多项式

采用频域抽取(Decimation in Frequency,DIF)的方法，将合并后处理步骤的INTT变换拆分成基本的蝶形运算单元可以有效加速INTT变换的运算速度。具体的，将式(10)中的A

根据

由于多项式维度N是2的幂次，因此，式(12)进一步表示为式(13)：

令

由式(14)判断出

根据以上公式的推导，则将后处理步骤合并到INTT变换后，基于恒定几何(Constant Geometry,CG)算法的DIF INTT变换蝶形运算结构可由原来的式(4)转换为式(15)：

其中，

第二方面，本发明还公开一种多项式乘法器，包括可重构乘法器模块，该可重构乘法器模块执行如上述任一项所述的基于NTT和INTT结构的多项式乘法运算方法。该多项式乘法器在执行多项式乘法时已经合并了预处理和后处理步骤，因此不再需要为预处理和后处理步骤设计单独的乘法运算单元，减小了硬件资源开销且提高了运算性能。

如图3所示，在一实施例中，多项式乘法器还包括存储块1(即第一存储块)、存储块2(即第二存储块)、NTT旋转因子存储器、INTT旋转因子存储器、数据选择器1(即第一数据选择器)、数据选择器2(即第二数据选择器)。该乘法器模块采用一套公共的硬件电路即可同时实现NTT变换、INTT变换、点乘以及点乘加运算，具备较高的硬件灵活性和面积效率。优选的，多项式乘法器的输入数据、输出数据、模数q的位宽为32比特，且模数q是满足q＝1mod2N条件的奇素数，从而能够在NTT和INTT变换中找到正确的单位本原根。其中，NTT旋转因子存储器和INTT旋转因子存储器分别用于存储NTT和INTT变换时的旋转因子参数ω

需要知道的是，多项式乘法器还包括全局控制模块以及数据分配器。全局控制模块包括地址生成模块和控制信号生成模块。地址生成模块用于生成存储块1和存储块2中存储单元的读写地址信号，存储单元根据这些读写地址信号从对应地址中将数据读取到可重构乘法器模块，或是将可重构乘法器模块运算完的数据写入到对应地址中。地址生成模块还用于生成NTT旋转因子存储器和INTT旋转因子存储器的地址，并将对应地址中的旋转因子读取到可重构乘法器模块参与NTT变换或INTT变换。控制信号生成模块主要用于生成存储块1、存储块2、NTT旋转因子存储器、INTT旋转因子存储器以及可重构乘法器模块内部的数据选择器的控制信号，通过这些控制信号，多项式乘法器可以对存储单元数据进行正确读写，同时对可重构乘法器模块的功能进行正确配置。数据分配器在实际电路中采用译码电路实现。

在一实施例中，数据选择器1进一步由多个数据选择器构成，主要用于在存储块1和存储块2中选择所需要的数据进行读取或写入，而数据选择器2仅由一个数据选择器构成，它根据可重构乘法器模块的具体功能，用于选择参与可重构乘法器模块运算的数据cons[31:0]是来自于NTT旋转因子存储器(即ω

在一实施例中，存储块1和存储块2用于存放外部输入的位宽为32比特的多项式系数，或是用于存储输出到外部的位宽为32比特的多项式系数。存储块1包括存储单元MEM_L

在一实施例中，当多项式乘法器执行NTT变换时，默认输入多项式X

当多项式乘法器执行INTT变换时，多项式X

当多项式乘法器执行点乘或点乘加运算时，参与点乘加运算的加法项多项式X

在一实施例中，如图4所示，可重构乘法器模块包括可重构Barrett模乘器、1/2模乘器、模加器、第一模减器、第二模减器、若干第三数据选择器以及若干个级连寄存器。其中，可重构Barrett模乘器采用一套公共的硬件电路即可实现多项式系数与(NTT或INTT)旋转因子的模乘运算，或是两个多项式系数的点乘(也是模乘)运算。此外，可重构Barrett模乘器也可以单纯用于一个数的模约减运算，或是两个数的乘法运算，能够为全同态密码算法提供除多项式乘法运算以外的其他运算类型。可重构Barrett模乘器具备较高的硬件灵活性和面积效率。1/2模乘器主要用于实现INTT变换中多项式系数与1/2的模乘运算。由于默认情况下多项式模数q为32比特以内的奇素数，因此，1/2mod q就等于(q+1)/2。对于多项式系数x，要实现x/2mod q运算，可以区分两种不同的情况：当x偶数时，x/2mod q就等于x＞＞1；当x奇数时，x/2mod q需要通过式(16)化简得到：

其中，

在一实施例中，1/2模乘器电路如图5所示，包括右移电路1、右移电路2、模加器和数据选择器。右移电路1主要实现对多项式系数右移1位的运算。右移电路2用于实现对多项式模数除以2的运算。模加器采用基本的无符号数的模加电路实现。数据选择器的控制信号为x[0]，当x[0]等于0时，表示x为偶数，选择输出x＞＞1，否则表示x为奇数，选择输出(x＞＞1)+(q+1)/2。1/2模乘器电路仅采用移位器、模加器和数据选择器即可实现，相比于普通的模乘器电路，有效提升了所述的可重构乘法器模块的运算性能，同时节约了硬件资源开销。

进一步的，可重构乘法器模块中的模加器、模减器1和模减器2均采用无符号数的模加和模减电路实现。可重构乘法器模块的数据选择器MUX1-MUX7用于选择可重构乘法器模块执行NTT变换、INTT变换、点乘运算或点乘加运算，而控制信号{sel_ntt,sel_cons,sel_mult}则分别用于控制数据选择器MUX1-MUX7以输出不同的功能，如表1所示，具体的：

当控制信号{sel_ntt,sel_cons,sel_mult}＝{0,0,0}时，可重构乘法器模块被配置为点乘运算单元，用于执行两个多项式系数的模乘运算。例如图6，系数b[31:0]经过MUX1的选择被传输至重构Barrett模乘器，而系数c[31:0]则通过外部的数据选择器选择被同时传输至可重构Barrett模乘器，接着通过可重构Barrett模乘器对b[31:0]和c[31:0]执行模乘运算，并将运算结果Z[31:0]经过MUX5和MUX6的选择输出到C[31:0]端，最终的输出结果C[31:0]＝b[31:0]×c[31:0]modq。

当控制信号{sel_ntt,sel_cons,sel_mult}＝{0,0,1}时，可重构乘法器模块被配置为点乘加运算单元，用于执行两个多项式系数的点乘运算以及与另一个系数的模加运算。例如图6，系数a[31:0]经过级连寄存器被送入模加器，系数b[31:0]经过MUX1被送到可重构Barrett模乘器作为其中一个输入，而系数c[31:0]同样通过外部数据选择器选择被送到可重构Barrett模乘器作为另一个输入，接着通过可重构Barrett模乘器对b[31:0]和c[31:0]执行模乘运算，其结果经MUX2被送往模加器，并与a[31:0]执行模加运算，模加的运算结果可以经过MUX4和MUX6的选择输出到C[31:0]端，最终的输出结果C[31:0]＝a[31:0]+b[31:0]×c[31:0]modq。

当控制信号{sel_ntt,sel_cons,sel_mult}＝{0,1}时，无论sel_mul信号为0或1，可重构乘法器模块配置为DIT NTT变换的蝶形运算单元，并用于执行多项式系数与旋转因子ω

当控制信号{sel_ntt,sel_cons,sel_mult}＝{1,1}时，无论sel_mul信号为0或1，可重构乘法器模块配置为DIF INTT变换的蝶形运算单元，并用于执行两个多项式系数间的模加再模乘1/2的运算以及两个系数间的模减再模乘旋转因子ω

表1可重构乘法器模块控制信号功能

需要知道的是，可重构乘法器模块中的输入z[63:0]和输出Z[63:0]主要用于扩展可重构Barrett模乘器的功能而增加的输入和输出，其中z[63:0]是可重构Barrett模乘器在执行一个64比特的模约减时的输入数据，而Z[63:0]是可重构Barrett模乘器在执行两个数的乘法时的输出数据。此外，级连寄存器由多个32比特的寄存器级连实现，用于实现多项式系数a[31]和b[31]的部分支路的流水线级数与可重构Barrett模乘器内的流水线级数相等，从而使二者的电路时序达到匹配。默认情况下，模加器、模减器1和模减器2内部不包含额外的流水线寄存器。

在一实施例中，如图6所示，可重构Barrett模乘器包括整数乘法器1(即第一整数乘法器)、整数乘法器2(即第二整数乘法器)、整数乘法器3(即第三整数乘法器)、加法器、减法器1(即第一减法器)、减法器2(即第二减法器)、减法器3(即第三减法器)、第四数据选择器(MUX1-MUX4)、流水线寄存器1(即第一流水线寄存器)、流水线寄存器2(即第一流水线寄存器)、流水线寄存器3(即第一流水线寄存器)。其中，整数乘法器1用于实现输入系数x[31:0]和y[31:0]之间的整数乘法运算，并输出一个64比特的乘法运算结果。整数乘法器2用于实现中间运算结果Q[32:0]和与模数q相关的参数T[32:0]之间的整数乘法运算，并输出一个66比特的乘法运算结果。其中参数T[32:0]由具体运算得到，并作为常量参与电路运算。整数乘法器3用于实现中间运算结果S[32:0]和模数q[31:0]之间的整数乘法运算，并输出一个65比特的乘法运算结果。整数乘法器1、整数乘法器2和整数乘法器3在FPGA上均综合为DSP36E1实现。

在一实施例中，加法器用于实现中间运算结果P[32:0]与常量2

在一实施例中，数据选择器MUX1-MUX4用于选择可重构Barrett模乘器执行两个32比特整数的模乘运算、两个32比特整数的乘法运算或一个64比特整数的模约减运算，从而为全同态密码算法提供更丰富的运算的功能。而控制信号{sel_mod,sel_AB}则分别用于控制数据选择器MUX1和MUX4以输出不同的功能。如表2所示，具体的：

当控制信号{sel_mod,sel_AB}＝{0,0}时，可重构Barrett模乘器配置为一个模乘器，用于执行两个32比特整数的模乘运算。多项式系数输入x[31:0]和y[31:0]传输至整数乘法器1执行整数乘法运算，得到的64比特结果X[63:0]经过MUX1和流水线寄存器1后取X[63:31]作为Q[32:0]传输至整数乘法器2作为其中一个输入，同时取X[32:0]作为U[32:0]经过流水线寄存器1、流水线寄存器2、流水线寄存器3传输至减法器1。取参数T[32:0]作为整数乘法器2的另一个输入，并由整数乘法器2完成Q[32:0]和T[32:0]的整数乘法运算，得到的66比特结果R[65:0]经过流水线寄存器2取R[65:33]作为S[32:0]传输至整数乘法器3作为其中的一个输入，同时取模数q[31:0]作为整数乘法器3的另一个输入，并由整数乘法器3完成S[32:0]和q[31:0]的整数乘法运算，得到的65比特结果Y[64:0]经过流水线寄存器2取Y[32:0]作为V[32:0]送入减法器1，由减法器1完成U[32:0]和V[32:0]之间的无符号数减法运算，并得到结果P[32:0]。接下来，判断P[32:0]是否小于0，如果小于0，则将P[32:0]和常量参数233传输至加法器执行加法运算，并将运算结果经过MUX2赋值给W[32:0]；如果P[32:0]不小于0，则将P[32:0]经MUX2直接赋值给W[32:0]。根据Barrett约减算法，得到的W[32:0]最大值为3q-1，因此要将W[32:0]约减至0到q-1的区间，需要判断W[32:0]是否大于2q，如果大于2q，则将W[32:0]模减2q作为模乘的最终结果；如果W[32:0]小于2q，则继续判断W[32:0]是否大于q，如果大于q，则将W[32:0]模减q作为模乘的最终结果；如果W[32:0]小于q，则直接将W[32:0]作为模乘的最终结果。为了减小这两级条件减法的时钟开销，使两个条件减法在同一个时钟内完成，W[32:0]可以同时传输至减法器2和减法器3，分别实现W[32:0]与参数2q的减法运算和W[32:0]与模数q的减法运算，并将两个减法运算结果的符号位作为MUX3的控制信号来选择输出哪一路。若W[32:0]与2q的减法结果为正，则将该减法结果经MUX3输出作为Z1[31:0]；若W[32:0]与2q的减法结果为负，则判断W[32:0]与q的减法结果是否为正，若为正，则将W[32:0]与q的减法结果作为Z1[31:0]，若W[32:0]与2q的减法结果和W[32:0]与q的减法结果均为负，则直接将W[32:0]作为Z1[31:0]。最终Z1[31:0]经MUX4l输出到Z[63:0]的低32比特，即Z[31:0]＝x[31:0]×y[31:0]modq。

当控制信号{sel_mod,sel_AB}＝{0,1}时，可重构Barrett模乘器配置为一个整数乘法器，用于执行两个32比特整数的乘法运算。多项式系数输入x[31:0]和y[31:0]先传输至整数乘法器1执行整数乘法运算，得到的64比特结果X[63:0]经过MUX1、流水线寄存器1、流水线寄存器2、流水线寄存器3、MUX4后直接传输至Z[63:0]，即Z[63:0]＝x[31:0]×y[31:0]。

当控制信号{sel_mod,sel_AB}＝{1,0}时，可重构Barrett模乘器配置为一个模约减器，用于执行一个64比特整数的模约减运算。整数输入z[63:0]首先经过MUX1直接赋值给X[63:0]，X[63:0]经过流水线寄存器1后取X[63:31]作为Q[32:0]并传输至整数乘法器2，接下来对Q[32:0]执行与模乘器类似的约减运算，直到输出Z[63:0]的低32比特，即Z[31:0]＝z[63:0]modq。

表2可重构Barrett模乘器控制信号功能

此外，结合具体的全同态密码算法参数，虽然本发明实施例中采用的多项式系数和模数q的位宽为32比特，但是本发明公开的可重构多项式乘法器总体电路、可重构乘法器模块电路以及可重构Barrett模乘器电路也支持更大系数位宽和模数位宽的扩展。

本发明将负折叠卷积的NTT多项式乘法器的预处理步骤和后处理步骤分别合并到NTT变换和INTT变换，极大的降低了算法的计算复杂度。此外，在将负折叠卷积的NTT多项式乘法器的预处理步骤和后处理步骤分别合并到NTT变换和INTT变换的基础上，设计了结构高度统一的多项式乘法器，多项式乘法器可以同时支持NTT变换、INTT变换、点乘以及点乘加运算，避免了额外预处理和后处理步骤，同时提高了硬件的性能和面积效率。此外，还涉及了一种可重构Barrett模乘器，在同一套硬件上可以同时实现两个32比特整数的模乘、两个32比特整数的乘法运算以及一个64比特整数的模约减运算，为全同态密码运算提供了灵活高效的硬件和算法单元支撑。

本发明可以广泛应用于各类全同态密码算法的硬件加速，尤其能够为BGV、BFV、CKKS、FHEW以及TFHE等基于RLWE型的全同态密码算法提供高效的多项式乘法运算支撑。通过构建高效的全同态加密算法，本发明能够进一步为云计算隐私保护、安全多方计算、安全外包计算等场景提供性能高效、面积优化的硬件平台支撑。

所属领域的技术人员可以清楚地了解到，为了描述的方便和简洁，上述描述的设备、装置和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

在本发明所提供的几个实施例中，应该理解到，所揭露的设备、装置和方法，可以通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为逻辑功能划分，实际实现时可以有另外的划分方式，也可以将具有相同功能的单元集合成一个单元，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另外，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口、装置或单元的间接耦合或通信连接，也可以是电的，机械的或其它的形式连接。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本发明实施例方案的目的。

另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以是两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

所述集成的单元如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分，或者该技术方案的全部或部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储块(ROM，Read-Only Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到各种等效的修改或替换，这些修改或替换都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应以权利要求的保护范围为准。