一种环上多项式乘法在GPU上的实现方法

一种环上多项式乘法在gpu上的实现方法
技术领域
1.本发明属于密码算法技术领域，具体涉及一种环上多项式乘法在gpu上的实现方法。


背景技术：

2.随着计算机网络的迅速普及以及互联网技术的不断发展，计算机在我们的日常生活中成为了一个重要的媒介来承担数据的传输和共享。同时，这也会带来一系列的信息安全问题。数字签名和加密技术提供了网络通信双方的身份认证和保密，这可以在一定程度上保证网络的安全。
3.然而随着量子理论的快速发展，基于传统数论的密码算法可能会在一定时间内被攻破，而基于格的密码体制通常被认为能够抵抗量子计算机的攻击。由于当前许多应用需要高效的签名和加密算法，如物联网、云计算、大数据等，这些应用对于实时性、延迟和响应时间要求较高。所以如何实现更加高效的格密码算法并将其集成在现有的业务系统中成为了研究的重中之重。
4.作为格密码算法的核心组件，环上多项式乘法是密码学中常用的基本操作之一，它在许多加解密、数字签名算法中都有广泛的应用，环上多项式乘法的效率和准确性对于格密码方案的实用性和安全性至关重要。ntt及kntt等现有的环上多项式乘法算法具有较高的并行性，其在cpu上运行时很难完全发挥优势。kntt算法中涉及到大量的并行结构，但现有的cpu版本代码只是对其简单的做了串行处理，计算效率较低。


技术实现要素：

5.为了解决现有技术中存在的上述问题，本发明提供了一种环上多项式乘法在gpu上的实现方法。本发明要解决的技术问题通过以下技术方案实现：
6.本发明提供了一种环上多项式乘法在gpu上的实现方法，包括：
7.步骤1：在cpu端对需要进行kntt算法的两个多项式分别进行拆分，将每个多项式拆分为包括多个低次多项式的一组多项式，将每一组多项式的系数重排后拷贝到gpu端；
8.步骤2：在gpu端，对每一组多项式中的多个低次多项式的系数，通过多个线程块实现ntt变换的并行运算，运算完成后将每个线程块对应的共享内存中存储的数据拷贝到全局内存中；
9.步骤3：根据全局内存中存储的两组多项式对应的ntt变换后的点值，利用pointwise核函数和knttmul核函数进行点乘运算，得到点乘运算结果；
10.步骤4：对点乘运算结果通过多个线程块实现逆ntt变换的并行运算，运算完成后将每个线程块对应的共享内存中存储的数据拷贝到全局内存中；
11.步骤5：将全局内存中存储的逆ntt变换后的系数拷贝到cpu端，在cpu端对所述系数重排后得到kntt算法的最终结果；
12.其中，在ntt变换运算和逆ntt变换运算时，线程块的数量配置为低次多项式的个
数，在线程块内一个线程对两组数据进行处理，每个线程块内线程数量配置为低次多项式长度的1/2；在点乘运算时，在一个线程块内使用一个线程对两组数据进行处理。
13.在本发明的一个实施例中，所述步骤1包括：
14.步骤1.1：在cpu端对需要进行kntt算法的两个多项式f(x)和g(x)分别进行拆分，得到包括多个低次多项式的两组多项式，拆分后的两个多项式f(x)和g(x)表示为：
[0015][0016][0017]
式中，f(i)表示多项式f(x)的低次多项式，g(i)表示多项式g(x)的低次多项式，f(i)和g(i)均∈环γ为上的n次本原单位根，q是一个满足2n|(q-1)的质数，2
α
表示多项式被拆分为低次多项式的个数；
[0018]
步骤1.2：将每一组多项式的系数对相应的原始多项式f(x)和g(x)的系数依次覆盖实现重排，将重排后的系数拷贝到gpu端。
[0019]
在本发明的一个实施例中，所述步骤2包括：
[0020]
步骤2.1：使用系统内置函数得到核函数配置时的线程模型，根据线程模型计算得到当前运行线程的全局id和线程块内id；
[0021]
步骤2.2：根据所述全局id和线程块内id对传入的重排后的系数进行分块，将每个低次多项式的系数存入对应的线程块的共享内存中；
[0022]
步骤2.3：对于每一个线程块，利用线程块内id计算得到当前线程操作的数据索引j，根据数据索引j确定运算的数据，按照下式进行该数据的组合以完成一轮计算：
[0023][0024]
其中，表示第i层变换后第j个系数的结果，brv(i)表示数字i做比特翻转后的结果，多项式在环上选取，n表示模多项式xn+1的次数；
[0025]
步骤2.4：重复步骤2.3直至log2n组运算完成后，将每个线程块对应的共享内存中存储的数据拷贝到全局内存中。
[0026]
在本发明的一个实施例中，所述步骤3包括：
[0027]
步骤3.1：调用pointwise核函数进行p
i,i
的计算，
[0028][0029]
式中，表示ntt运算结果，表示点乘；
[0030]
步骤3.2：调用pointwise核函数进行p
i,j
的计算，
[0031][0032]
式中，0≤i《j≤2
α-1，
[0033]
步骤3.3：调用pointwise核函数进行额外的点乘运算，
[0034][0035]
式中，k＝2
α-1，
[0036]
步骤3.4：根据计算得到的p
i,j
和zk调用knttmul核函数，计算得到点乘运算结果
[0037]
在本发明的一个实施例中，所述步骤4包括：
[0038]
步骤4.1：使用系统内置函数得到核函数配置时的线程模型，根据线程模型计算得到当前运行线程的全局id和线程块内id；
[0039]
步骤4.2：根据所述全局id和线程块内id对传入的点乘运算结果进行分块，将多组逆ntt的并行计算分配在不同的线程块中；
[0040]
步骤4.3：对于每一个线程块，利用线程块内id计算得到当前线程操作的数据索引j，根据数据索引j确定运算的数据，按照下式进行该数据的组合以完成一轮计算：
[0041][0042]
其中，表示第i层变换后第j个系数的结果，brv(i)表示数字i做比特翻转后的结果；
[0043]
步骤4.4：重复步骤4.3直至log2n组运算完成后，将每个线程块对应的共享内存中存储的数据拷贝到全局内存中。
[0044]
与现有技术相比，本发明的有益效果在于：
[0045]
1.本发明的环上多项式乘法在gpu上的实现方法，通过gpu的大量并行计算单元，实现了kntt算法的并行运算，可以在相同的时间内进行更多的计算，加快计算速度，提高计算性能。
[0046]
2.本发明的环上多项式乘法在gpu上的实现方法，可以通过简单地增加gpu的计算单元的数量来提高计算性能，在需要处理大量数据或进行大规模计算时，使得gpu实现的环上多项式乘法具有更好的可扩展性。
[0047]
3.本发明的环上多项式乘法在gpu上的实现方法，与专用fpga相比，可以节省大量的成本，可以编程实现，可以灵活地调整算法的参数和实现方式，更具灵活性。
[0048]
上述说明仅是本发明技术方案的概述，为了能够更清楚了解本发明的技术手段，而可依照说明书的内容予以实施，并且为了让本发明的上述和其他目的、特征和优点能够更明显易懂，以下特举较佳实施例，并配合附图，详细说明如下。
附图说明
[0049]
图1是本发明实施例提供的一种环上多项式乘法在gpu上的实现方法的示意图；
[0050]
图2是本发明实施例提供的一种进行多项式的点值表示的运算过程；
[0051]
图3是本发明实施例提供的一种2-kntt的算法流程图；
具体实施方式
[0052]
为了进一步阐述本发明为达成预定发明目的所采取的技术手段及功效，以下结合附图及具体实施方式，对依据本发明提出的一种环上多项式乘法在gpu上的实现方法进行详细说明。
[0053]
有关本发明的前述及其他技术内容、特点及功效，在以下配合附图的具体实施方式详细说明中即可清楚地呈现。通过具体实施方式的说明，可对本发明为达成预定目的所采取的技术手段及功效进行更加深入且具体地了解，然而所附附图仅是提供参考与说明之用，并非用来对本发明的技术方案加以限制。
[0054]
首先对kntt算法进行简单说明，kntt算法中主要涉及到了三个组件：ntt数论变换、intt逆向数论变换以及组合中间结果时使用的点乘运算，而gpu因其特有的“众核”特性在并行数据的处理方面表现突出，利用gpu对kntt环上多项式乘法运算进行实现的本质就是使用gpu的多个核心的高并行特点对算法中涉及到的数据进行并行处理，从而提高算法的运行效率。基于此，本发明提出了一种的环上多项式乘法在gpu上的实现方法。
[0055]
实施例一
[0056]
请参见图1，图1是本发明实施例提供的一种环上多项式乘法在gpu上的实现方法的示意图，如图所示，本实施例的环上多项式乘法在gpu上的实现方法，包括：
[0057]
步骤1：在cpu端对需要进行kntt算法的两个多项式分别进行拆分，将每个多项式拆分为包括多个低次多项式的一组多项式，将每一组多项式的系数重排后拷贝到gpu端；
[0058]
在一个可选地实施方式中，步骤1包括：
[0059]
步骤1.1：在cpu端对需要进行kntt算法的两个多项式f(x)和g(x)分别进行拆分，得到包括多个低次多项式的两组多项式，拆分后的两个多项式f(x)和g(x)表示为：
[0060][0061][0062]
式中，f(i)表示多项式f(x)的低次多项式，g(i)表示多项式g(x)的低次多项式，f(i)和g(i)均∈环γ为上的n次本原单位根，q是一个满足2n|(q-1)的质数，2
α
表示多项式被拆分为低次多项式的个数；
[0063]
步骤1.2：将每一组多项式的系数对相应的原始多项式f(x)和g(x)的系数依次覆盖实现重排，将重排后的系数拷贝到gpu端。
[0064]
步骤2：在gpu端，对每一组多项式中的多个低次多项式的系数，通过多个线程块实现ntt变换的并行运算，运算完成后将每个线程块对应的共享内存中存储的数据拷贝到全局内存中；
[0065]
在本实施例中，在ntt变换运算时，线程块的数量配置为低次多项式的个数，即，一个线程块对应一个低次多项式的ntt变换运算。在线程块内一个线程对两组数据进行处理，每个线程块内线程数量配置为低次多项式长度的1/2。
[0066]
在一个可选地实施方式中，步骤2包括：
[0067]
步骤2.1：使用系统内置函数得到核函数配置时的线程模型，根据线程模型计算得到当前运行线程的全局id和线程块内id；
[0068]
步骤2.2：根据全局id和线程块内id对传入的重排后的系数进行分块，将每个低次
多项式的系数存入对应的线程块的共享内存中；
[0069]
步骤2.3：对于每一个线程块，利用线程块内id计算得到当前线程操作的数据索引j，根据数据索引j确定运算的数据，按照下式进行该数据的组合以完成一轮计算：
[0070][0071]
其中，表示第i层变换后第j个系数的结果，brv(i)表示数字i做比特翻转后的结果，多项式在环上选取，n表示模多项式xn+1的次数；
[0072]
步骤2.4：重复步骤2.3直至log2n组运算完成后，将每个线程块对应的共享内存中存储的数据拷贝到全局内存中。
[0073]
步骤3：根据全局内存中存储的两组多项式对应的ntt变换后的点值，利用pointwise核函数和knttmul核函数进行点乘运算，得到点乘运算结果；
[0074]
在本实施例中，为了与ntt算法适配，在点乘运算时，在一个线程块内同样使用一个线程对两组数据进行处理，保证在配置相同时，算法运行的正确性。
[0075]
在一个可选地实施方式中，步骤3包括：
[0076]
步骤3.1：调用pointwise核函数进行p
i,i
的计算，
[0077][0078]
式中，表示ntt运算结果，表示点乘；
[0079]
步骤3.2：调用pointwise核函数进行p
i,j
的计算，
[0080][0081]
式中，0≤i《j≤2
α-1，p
j,j
和p
i,i
均是储存中间结果的一个变量；
[0082]
步骤3.3：调用pointwise核函数进行额外的点乘运算，
[0083][0084]
式中，k＝2
α-1，
[0085]
步骤3.4：根据计算得到的p
i,j
和zk调用knttmul核函数，计算得到点乘运算结果
[0086]
步骤4：对点乘运算结果通过多个线程块实现逆ntt变换的并行运算，运算完成后将每个线程块对应的共享内存中存储的数据拷贝到全局内存中；
[0087]
其中，逆ntt算法是ntt算法的逆变换，即将多项式的点值表示转换为系数表示，其分治过程和ntt算法原理类似，流程相反。在本实施例中，在线程块内一个线程对两组数据进行处理；
[0088]
在一个可选地实施方式中，步骤4包括：
[0089]
步骤4.1：使用系统内置函数得到核函数配置时的线程模型，根据线程模型计算得到当前运行线程的全局id和线程块内id；
[0090]
步骤4.2：根据全局id和线程块内id对传入的点乘运算结果进行分块，将多组逆ntt的并行计算分配在不同的线程块中；
[0091]
步骤4.3：对于每一个线程块，利用线程块内id计算得到当前线程操作的数据索引j，根据数据索引j确定运算的数据，按照下式进行该数据的组合以完成一轮计算：
[0092][0093]
其中，表示第i层变换后第j个系数的结果，brv(i)表示数字i做比特翻转后的结果；
[0094]
步骤4.4：重复步骤4.3直至log2n组运算完成后，将每个线程块对应的共享内存中存储的数据拷贝到全局内存中。
[0095]
步骤5：将全局内存中存储的逆ntt变换后的系数拷贝到cpu端，在cpu端对系数重排后得到kntt算法的最终结果。
[0096]
在本实施例中，将全局内存中存储的逆ntt变换后的系数拷贝到cpu端，在cpu端进行步骤1的逆过程，对系数重排后得到kntt算法的最终结果。
[0097]
需要说明的是，在ntt上的工作主要是利用gpu的共享内存进行加速，但共享内存只能在同一个块内共享。ntt算法中一个线程可以处理两组数据，块内最多存在1024个线程，当多项式次数过大时，数据存在无法有效分配到线程以及分配时并行性降低等问题。使用kntt算法可以很好的解决这个问题，算法会对多项式进行拆分，这相当于降低了多项式的次数。
[0098]
进一步地，以α取2为例，对完成一次2-kntt算法的gpu版本实现的步骤和算法代码进行具体说明。2-kntt算法的具体配置及调用过程如算法4.1，算法的代码如下所示：
[0099][0100][0101]
2-kntt算法中两个多项式f(x)和g(x)分别被拆分为4个低次多项式，每个低次多项式次数为原始次数的1/4，记为length。在ntt算法中使用一个线程计算两组数据，因此，使用4个线程块，并将块内线程数量配置为低次多项式次数的1/2，即length/2，以完成低次项多项式的ntt以及intt算法的并行处理。对pointwise核函数进行配置时需要和ntt保持一致，以免当多项式次数较大时，运行出错。2-kntt算法中的2knttmul核函数的配置较为灵活，但是需要保证一共存在length个线程参与计算。
[0102]
kntt算法的核心为多项式的点值表示和系数表示的切换，即出的ntt变换运算和逆ntt变换运算
[0103]
请结合参见图2和图3，图2本发明实施例提供的一种进行多项式的点值表示的运算过程，图3是的本发明实施例提供的一种2-kntt的算法流程图。
[0104]
在进行多项式的点值表示的运算，即ntt运算过程中，每轮变换均需要进行n/2组数据的处理，组外数据互不干扰，所以ntt算法具有天然的并行性。可以将gpu的n/2个核心分配给不同的数据进行并行处理，并将ntt算法每轮计算中涉及到的2n次单位根的次幂存储在预制表中，进一步减少算法在执行过程中对其再计算产生的开销。
[0105]
其中，ntt算法在gpu上实现的具体步骤如算法4.2，算法的代码如下所示：
[0106][0107][0108]
每个低次多项式都需要进行ntt的运算。由于gpu版本的实现中引入了共享内存来优化全局内存的读写开销，所以一个多项式的ntt计算需要在块内进行，多组ntt的并行计算可以分配在不同的块中。算法4.2中的1、2两行使用系统内置函数得到核函数配置时的线程模型，从而计算得出当前运行线程的全局id和线程块内id，并利用其对传入的数据进行分块，在共享内存中存储该线程块运行过程中需要计算点值表示的多项式系数，实现上述所说的一个多项式对应一个线程块的效果。ntt的每轮变换只需要n/2组并行计算，为了避免线程浪费，在配置线程模型时将块内线程数量配置为n/2个，使得每个线程负责两个数据的读取和写入，如第5和6行所示。第7行的循环是ntt算法的主体部分，首先利用线程块内id
计算得出当前线程操作的数据索引j，再利用公式(3)进行该数据的组合以完成一轮计算。log2n组运算完成后需要将共享内存中的数据拷贝到全局内存中，以便进行后续与cpu的数据交互过程。
[0109]
当所有低次多项式的点值表示运算完成后，调用pointwise核函数用来进行p
i,i
和的计算，调用2knttmul核函数用来进行最终的的计算。
[0110]
具体地，2-kntt算法对中间结果进行点乘运算包括以下步骤：首先，计算以下4个点乘运算对于其余的下标0≤i《j≤3，分别计算下列的6个点乘运算最后对于每一个q
(k)
,k∈[0,3]，还需要再进行一次额外的点乘运算共计3次点乘计算。根据计算得到的p
i,j
和zk调用knttmul核函数，计算得到点乘运算结果此时点乘运算计算部分完成，上述步骤对核函数进行配置时需要和ntt保持一致，以免当多项式次数较大时，运行出错。
[0111]
pointwise点乘运算和2knttmul算法在gpu上实现的具体步骤如算法4.3和4.4，算法的代码如下所示：
[0112][0113][0114]
[0115]
逆ntt(intt)算法在gpu上实现的具体步骤如算法4.5，算法的代码如下所示：
[0116][0117][0118]
在逆ntt算法中同样使用一个线程计算两组数据，因此，将块内线程数量配置为低次多项式次数的1/2，即length/2。intt算法是ntt算法的逆变换，即将多项式的点值表示转换为系数表示。预制表中存储的是涉及到的2n次单位根的逆的次幂。其分治过程和ntt算法原理类似，流程相反。由于每轮计算时没有对中间结果的倍数2进行处理，所以共享内存中该值累积到了n。如20和21行所示，在最终拷贝结果到全局内存中时，需要对其乘以n-1
以消除该倍数。
[0119]
本实施例的环上多项式乘法在gpu上的实现方法，通过gpu的大量并行计算单元，实现了kntt算法的并行运算，可以在相同的时间内进行更多的计算，加快计算速度，提高计算性能。而且，可以通过简单地增加gpu的计算单元的数量来提高计算性能，在需要处理大量数据或进行大规模计算时，使得gpu实现的环上多项式乘法具有更好的可扩展性。
[0120]
本实施例的环上多项式乘法在gpu上的实现方法，与专用fpga相比，可以节省大量的成本，可以编程实现，可以灵活地调整算法的参数和实现方式，更具灵活性。
[0121]
应当说明的是，在本文中，术语“包括”、“包含”或者任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的物品或者设备不仅包括那些要素，而且还包括没有
明确列出的其他要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的物品或者设备中还存在另外的相同要素。
[0122]
以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。

技术特征：
1.一种环上多项式乘法在gpu上的实现方法，其特征在于，包括：步骤1：在cpu端对需要进行kntt算法的两个多项式分别进行拆分，将每个多项式拆分为包括多个低次多项式的一组多项式，将每一组多项式的系数重排后拷贝到gpu端；步骤2：在gpu端，对每一组多项式中的多个低次多项式的系数，通过多个线程块实现ntt变换的并行运算，运算完成后将每个线程块对应的共享内存中存储的数据拷贝到全局内存中；步骤3：根据全局内存中存储的两组多项式对应的ntt变换后的点值，利用pointwise核函数和knttmul核函数进行点乘运算，得到点乘运算结果；步骤4：对点乘运算结果通过多个线程块实现逆ntt变换的并行运算，运算完成后将每个线程块对应的共享内存中存储的数据拷贝到全局内存中；步骤5：将全局内存中存储的逆ntt变换后的系数拷贝到cpu端，在cpu端对所述系数重排后得到kntt算法的最终结果；其中，在ntt变换运算和逆ntt变换运算时，线程块的数量配置为低次多项式的个数，在线程块内一个线程对两组数据进行处理，每个线程块内线程数量配置为低次多项式长度的1/2；在点乘运算时，在一个线程块内使用一个线程对两组数据进行处理。2.根据权利要求1所述的环上多项式乘法在gpu上的实现方法，其特征在于，所述步骤1包括：步骤1.1：在cpu端对需要进行kntt算法的两个多项式f(x)和g(x)分别进行拆分，得到包括多个低次多项式的两组多项式，拆分后的两个多项式f(x)和g(x)表示为：包括多个低次多项式的两组多项式，拆分后的两个多项式f(x)和g(x)表示为：式中，f
(i)
表示多项式f(x)的低次多项式，g
(i)
表示多项式g(x)的低次多项式，f
(i)
和g
(i)
均∈环γ为上的n次本原单位根，q是一个满足2n|(q-1)的质数，2
α
表示多项式被拆分为低次多项式的个数；步骤1.2：将每一组多项式的系数对相应的原始多项式f(x)和g(x)的系数依次覆盖实现重排，将重排后的系数拷贝到gpu端。3.根据权利要求2所述的环上多项式乘法在gpu上的实现方法，其特征在于，所述步骤2包括：步骤2.1：使用系统内置函数得到核函数配置时的线程模型，根据线程模型计算得到当前运行线程的全局id和线程块内id；步骤2.2：根据所述全局id和线程块内id对传入的重排后的系数进行分块，将每个低次多项式的系数存入对应的线程块的共享内存中；步骤2.3：对于每一个线程块，利用线程块内id计算得到当前线程操作的数据索引j，根据数据索引j确定运算的数据，按照下式进行该数据的组合以完成一轮计算：
其中，表示第i层变换后第j个系数的结果，brv(i)表示数字i做比特翻转后的结果，多项式在环上选取，n表示模多项式x
n
+1的次数；步骤2.4：重复步骤2.3直至log2n组运算完成后，将每个线程块对应的共享内存中存储的数据拷贝到全局内存中。4.根据权利要求3所述的环上多项式乘法在gpu上的实现方法，其特征在于，所述步骤3包括：步骤3.1：调用pointwise核函数进行p
i,i
的计算，式中，表示ntt运算结果，表示点乘；步骤3.2：调用pointwise核函数进行p
i,j
的计算，式中，0≤i<j≤2
α-1，步骤3.3：调用pointwise核函数进行额外的点乘运算，式中，k＝2
α-1，步骤3.4：根据计算得到的p
i,j
和z
k
调用knttmul核函数，计算得到点乘运算结果5.根据权利要求4所述的环上多项式乘法在gpu上的实现方法，其特征在于，所述步骤4包括：步骤4.1：使用系统内置函数得到核函数配置时的线程模型，根据线程模型计算得到当前运行线程的全局id和线程块内id；步骤4.2：根据所述全局id和线程块内id对传入的点乘运算结果进行分块，将多组逆ntt的并行计算分配在不同的线程块中；步骤4.3：对于每一个线程块，利用线程块内id计算得到当前线程操作的数据索引j，根据数据索引j确定运算的数据，按照下式进行该数据的组合以完成一轮计算：其中，表示第i层变换后第j个系数的结果，brv(i)表示数字i做比特翻转后的结果；步骤4.4：重复步骤4.3直至log2n组运算完成后，将每个线程块对应的共享内存中存储的数据拷贝到全局内存中。

技术总结
本发明涉及一种环上多项式乘法在GPU上的实现方法，使用GPU优化KNTT算法，将GPU线程模型中的线程块与KNTT算法中拆分出的低次多项式一一对应，使得每个线程块负责一个低次多项式的NTT并行运算。同时调度GPU中的多个线程块完成低次多项式之间的并行处理，提高了KNTT算法在GPU上的实现效率。并且由于NTT算法的GPU版本在实现过程中使用到了共享内存进行读写的效率优化，当多项式次数较大时，硬件限制下的块内线程无法有效的分配数据进行处理，导致后续结果出错或效率降低，使用KNTT算法的GPU版本实现可以最大程度上解决这个问题。版本实现可以最大程度上解决这个问题。版本实现可以最大程度上解决这个问题。


技术研发人员：赵新颖 王保仓 赵臻
受保护的技术使用者：西安电子科技大学
技术研发日：2023.03.17
技术公布日：2023/7/12