检索
E-mail
RSS

网络空间安全科学学报 >

2024 , Vol. 2 >Issue 3: 41 - 52

DOI: https://doi.org/10.20172/j.issn.2097-3136.240304

基于GPU加速的快速全同态加密算法设计与实现

  • 谭泽玖 1 ,
  • 赵鑫 1 ,
  • 万俊平 1 ,
  • 刘虎成 1 ,
  • 蒋琳 , 1, 4, 5, * ,
  • 徐金明 2 ,
  • 纪守领 3 ,
  • 王轩 1, 5
展开
  • 1. 哈尔滨工业大学（深圳）计算机科学与技术学院，深圳 518055
  • 2. 浙江大学控制科学与工程学院，杭州 310058
  • 3. 浙江大学计算机科学与技术学院，杭州 310058
  • 4. 鹏城国家实验室，深圳 518000
  • 5. 广东省安全智能新技术重点实验室，深圳 518055
蒋琳（）。

网络出版日期: 2024-11-16

基金资助

国家重点研发计划项目（2022YFB3102100）

版权

版权所有©《网络空间安全科学学报》编辑部 2024
收起

Design and implementation of fast fully homomorphic encryption algorithm based on GPU acceleration

  • TAN Zejiu 1 ,
  • ZHAO Xin 1 ,
  • WAN Junping 1 ,
  • LIU Hucheng 1 ,
  • JIANG Lin , 1, 4, 5, * ,
  • XU jinming 2 ,
  • JI Shouling 3 ,
  • WANG Xuan 1, 5
Expand
  • 1. School of computer science and technology, Harbin Institute of Technology, Shenzhen, Shenzhen,518055, China
  • 2. College of control science and engineering, Zhejiang University, Hangzhou,310058, China
  • 3. College of Computer Science and Technology, Zhejiang University, Hangzhou,310058, China
  • 4. Pengcheng National Laboratory, Shenzhen 518000, China
  • 5. Guangdong Key Laboratory of New Security and Intelligence Technology, Shenzhen 518005, China

Online published: 2024-11-16

Copyright

Copyright ©2024 Journal of Aeronautical Materials. All rights reserved.
Fold

摘要

全同态加密算法支持直接对加密数据（密文）执行代数运算，但其密文评估中的数论变换（NTT）涉及大量高维度整系数多项式环运算，限制了其在隐私计算中的应用。针对CPU实现方案对NTT算法计算并行度较低的问题，提出一种CPU+GPU异构的CKKS全同态加密实现方案。首先，根据NTT算法数据内存访问规律，设计一种数据暂存共享内存策略，有效减少频繁的全局内存访问。其次，针对数据规模可变导致内核出现部分空闲线程的问题，设计线程工作负载动态分配机制，并采用不同基数的蝴蝶变换结构，提高数据输入的灵活性并优化并行策略。再次，提出单—多内核混合调用模式，通过NTT算法蝶形变换分组大小动态切换内核调用模式，充分利用GPU多核调用的并行潜力。最后，设计并实现并行程度更高、计算复杂度更低的NTT算法，利用该算法实现并行的同态乘法运算，并基于HElib库实现CPU+GPU异构的CKKS全同态加密算法。实验结果表明，与使用AVX-512加速的HElib库相比，所提的NTT/INTT计算时间减短近65%。

关键词： 隐私计算; 全同态加密; GPU并行加速; 数论变换; 缓存策略; 卷积神经网络

本文引用格式

谭泽玖 , 赵鑫 , 万俊平 , 刘虎成 , 蒋琳 , 徐金明 , 纪守领 , 王轩 . 基于GPU加速的快速全同态加密算法设计与实现[J]. 网络空间安全科学学报, 2024 , 2(3) : 41 -52 . DOI: 10.20172/j.issn.2097-3136.240304

Abstract

Fully homomorphic encryption supports direct algebraic operations on encrypted data (ciphertext), with the foundation of its ciphertext evaluation phase involving numerous high-dimensional integer coefficient polynomial ring additions and multiplications. This limits its widespread application in the field of privacy computing. The CPU implementation scheme offers low parallelism for the Number Theoretic Transform （NTT） algorithm calculations. A CPU+GPU heterogeneous fully homomorphic encryption implementation scheme was proposed. Firstly, a cache strategy of data temporarily stored in shared memory was introduced, which stored repeatedly read and unchanging data, including NTT input data and rotation factors, in shared memory to reduce frequent global memory access. Secondly, to address the issue of partially idle threads caused by variable data sizes, it dynamically allocates thread workloads based on data size and hardware resources, adopting butterfly transformation structures of different radices to achieve optimal parallel strategies while enhancing the flexibility of data input. Thirdly, it introduces a single-multi-core mixed invocation mode, dynamically switching the kernel invocation mode based on the group size of butterfly transformations in each NTT iteration, to fully utilize the parallel potential of multi-core invocations on GPU. Finally, it designs and implements a higher parallelism, lower computational complexity NTT algorithm for GPU, uses this algorithm to perform parallel homomorphic multiplication operations, and implements a CPU+GPU heterogeneous CKKS fully homomorphic encryption algorithm based on the HElib library. Experimental results show NTT/INTT computation time is reduced by nearly 65% compared to HElib library using AVX-512 acceleration technology.

Key words： Privacy computing; Fully homomorphic encryption; GPU acceleration; Number theoretic transform; Caching strategy; Convolutional neural networks

0 引言

随着计算机技术的不断发展，世界已跨入了互联网+大数据时代，大数据的长足发展改变了从金融到医疗再到网络安全的各个行业。然而，数据的隐私保护问题仍未解决。2018年，欧盟引入《通用数据保护条例》（General Data Protection Regulation，GDPR）法案，用以保护用户的隐私数据安全，该法案堪称史上最严厉的用户数据安全保护法。2021年，我国通过了《中华人民共和国数据安全法》，以保护个人信息和重要数据安全，并于同年9月1日正式实施。由此可见，重视数据隐私和安全已经成为了世界性的趋势。
隐私计算（Privacy Computing）又称隐私增强计算（Privacy-Enhancing Computing）或机密计算（Confidential Computing），是一种在不转移或者泄露原始数据的前提下，实现对密文数据计算的技术和系统，具有“可用不可见”的特性。在众多隐私计算技术中，全同态加密（Fully Homomorphic Encryption，FHE）是支持直接对加密数据（密文）执行代数运算的一种加密算法，无需在运算前先解密密文。相较于其他隐私计算技术，全同态加密算法具有更通用的数据隐私保护能力，更适用于同网密态计算。然而，全同态加密算法自身存在密钥体积大和计算效率低等性能问题，大大限制了它的实用性和进一步推广应用。具体来讲，全同态加密算法将整数域或实数域上的明文映射到多项式环上的密文，密文下的同态评估运算需要执行非常高次数的超大整数多项式乘法，导致同态评估运算效率极低。针对全同态加密算法的效率瓶颈，本文从图形处理器（Graphics Processing Unit，GPU）并行加速的方向入手，基于GPU并行能力设计并实现了快速全同态加密算法。

1 相关研究

1.1 全同态加密算法加速研究现状

自2009年Gentry提出第一个全同态加密算法（fully homomorphic encryption，FHE）[1]起，全同态加密算法在自举、批处理、无噪声等方向有多种加速方案。
Ducas等[2]通过设计新的同态与非门，将HElib库中自举操作的运行时间从6 min缩短至1 s以内，并相应提出了FHEW算法。随后Chillotti等[3]将FHEW算法的自举操作的运行时间从1 s以内缩短至0.1 s 以内，并将其密钥大小从1 GB减小至24 MB。Chen等[4]通过应用“低位删除”多项式简化开方运算，此举对FV算法和BGV算法中的自举都能起到加速作用。
另一种为全同态“提速”的有效手段是批处理（Batch）技术，也称为封装（Pack）技术，即允许将多个数据值加密为一个密文，并能够同态执行单指令多数据操作SIMD。Smart等[5]通过中国剩余定理（Chinese Remainder Theorem，CRT）分解明文空间，构造了支持SIMD操作的FHE算法。Castryck等[6]通过引入劳伦多项式编码技术对Smart的算法进行了改进，极大提高了明文封装容量以及在效率或安全性方面优化系统参数的灵活性。
除了不断优化自举技术和引入批处理技术提升FHE效率外，构造无噪声FHE成为当前全同态加密研究的另一个重要思路[7]。噪声加入是为了保证FHE的安全性，但降噪运算计算复杂度较高，而无噪声FHE[8]不需要自举等降噪运算，并且能显著提高算法效率。

1.2 全同态加密异构平台加速研究现状

IBM和微软等开发了各种FHE库和工具包。由于基于LWE（Learning With Errors）或者RLWE（Ring Learning With Errors）困难问题的全同态加密算法基本操作都会涉及维数较大的整系数多项式的加法和乘法，平凡算法计算两个$ N $次多项式加法的复杂度为$ O\left(N\right) $，乘法的复杂度为$ O\left({N}^{2}\right) $。为了降低计算复杂度，常用方法是数论变换[9]（Number Theoretic Transforms，NTT），该方法可以将乘法复杂度降为$ O\left(N\mathrm{l}\mathrm{o}\mathrm{g}_2N\right) $。然而，CPU内核计算过程需要大量数据，因此这些库和工具包在现有CPU上性能较差。
基于上述原因，硬件加速计算开始被广泛关注，不同厂商在硬件加速领域选择的架构和解决方案也各不相同，主要分为GPU、FPGA和ASIC三类。
随着GPU的快速发展，GPU在通用计算领域的应用越发广泛，统一计算架构（Compute Unified Device Architecture，CUDA）平台也使GPU并行计算具有更好的可编程性[10]，程序开发更为高效灵活，因此使用GPU硬件加速成为提升全同态加密效率的一个重要手段。Wang等[11]通过大数乘法、FFT算法的GPU并行计算和Barrett模约简算法实现百万比特的同态乘法，并利用对基于窗口的评估函数的预计算对GH-FHE算法进行提速。Dai等[12]利用GPU提供的大量并行性和高内存带宽加速约简大系数多项式及其离散傅里叶库实现的剩余空间中模乘法，构造了GPU加速的NTRU算法，并实现LTV层次同态加密算法的GPU优化。Lei等[13]利用多核CPU和GPU结合同态全加器将FHEW-V2的自举提升了1.67倍。Bertels等[14]在高端FPGA上利用大量LUT和DSP将FHEW自举速度提升了7.5倍。
近几年，针对主流全同态加密算法如BFV、CKKS[15]、BGV[16]和TFHE的不同加速方案被不断提出。2020年，面向CKKS算法的HEAX加速方案[17]被提出，该方案在FPGA平台上相较于单线Intel Xeon(R) Silver 4108处理器有164~268倍的性能提升。2021年，Cheetah[18]加速方案和F1[19]加速方案被相继提出，它们分别在40 nm ASIC和14 nm ASIC平台上对BFV等算法进行了加速，其中F1方案速度相较于HEAX方案快172~1866倍不等。2022年，在14 nm/12 nm ASIC平台上的CraterLake[20]加速方案和在7 nm ASIC平台上的ARK[21]加速方案对CKKS算法进行加速，两个方案分别相较于CPU方案实现了4600倍和18214倍的速度提升。同年，面向TFHE算法的2个加速方案MATCHA[22]和FPT[23]分别在16nm ASIC平台和FPGA平台实现了TFHE吞吐量的提升，其中MATCHA方案将TFHE门处理吞吐量提高了2.3倍，FPT方案相较于MATCHA方案提高了2.5倍。2023年，Poseidon方案[24]和FxHENN方案[25]在FPGA平台上对CKKS算法进行了加速，Poseidon相较于现有的单线程CPU的加速比高达370倍，FxHENN与最先进的基于CPU的HE-CNN推理方案LoLa[26]相比，实现了13.49倍的推理延迟加速。同年，TensorFHE方案[27]在GPU平台上对BFV、BGV算法进行了加速，该方案在特定工作负载下的速度可以比F1方案快2.9倍。
专用计算平台也可以显著提升全同态加密算法效率，但将现有算法直接移植到专用处理器上并不能有效地挖掘其并行潜力以及硬件平台的性能优势。本文面向CKKS算法在GPU平台上进行加速，并将结果与单线程CPU实现的Helib库进行比较。

2 预备知识

2.1 CKKS全同态加密算法

CKKS[15]全同态加密算法主要包括密钥生成算法$ ({\mathrm{pk,sk,evk}})\leftarrow {\mathrm{KeyGen}}\left(\lambda \right) $、加密算法$ c\leftarrow {\mathrm{Enc}}(m,{\mathrm{pk}}) $、解密算法$ m\leftarrow {\mathrm{Dec}}(c,{\mathrm{sk}}) $，以及同态评估算法$ {{c}{{'}} \leftarrow {\mathrm{Eva}} } $$(c,{\mathrm{evk}}) $4个子算法。CKKS全同态加密算法是一种支持浮点数进行近似值计算的全同态加密算法。相较于传统的全同态加密算法，CKKS全同态加密算法在解密时将噪声视作明文的一部分，以预定的精确度输出明文的近似值。CKKS算法在加密前需将消息编码成明文，编码算法$ {\mathrm{Ecd}}(z,\mathrm{\Delta }) $将消息$ z $编码为环上的明文多项式$ m $，即CKKS算法的同态评估运算大部分为多项式之间的运算。

2.2 基于中国剩余定理的NTT算法并行性优化

CKKS算法产生的密文多项式维度和系数都非常大，密文评估非常耗时，平凡算法计算两个$ N $次多项式加法的复杂度为$ O\left(N\right) $，乘法的复杂度为$ O\left({N}^{2}\right) $。由于同态评估计算是基于多项式环上的计算，所以会有大量整数多项式之间的计算，例如模乘和模加。尽管大部分计算可以在点值表达式下进行，但是一些计算如模交换和密钥交换等仍需要在系数表达式下进行，所以整个过程中多项式需要在这两种表达式下来回转换，这也是最为耗时的部分。实现两种多项式表达式转换的方法有牛顿插值法、拉格朗日插值法和快速傅里叶变换等。本文采用的NTT是定义在有限整数域Zp=$ Z/pZ $上的离散傅里叶变换（Discrete Fourier Transform，DFT），即定义在环$ {\mathbb{Z}}_{\mathrm{p}} $上的DFT。
大整数乘法是影响NTT计算复杂度的一个重要因素，因此采用CRT对NTT进行计算复杂度优化。中国剩余定理表明，若有$ L $个素数$ {p}_{1},{p}_{2},\cdots ,{p}_{L} $，$ p={\mathrm{\Pi }}_{i=1}^{L}{p}_{i} $，则映射：
$ {\mathbb{Z}}_{p}\to {\mathbb{Z}}_{{\mathrm{p}}_{1}}\times {\mathbb{Z}}_{{\mathrm{p}}_{2}}\cdots \times {\mathbb{Z}}_{{\mathrm{p}}_{L}} $
$x\;\;\mathrm{m}\mathrm{o}\mathrm{d}\;\;p\mapsto (x\;\;\mathrm{m}\mathrm{o}\mathrm{d}\;\;{p}_{1},\;x\;\;\mathrm{m}\mathrm{o}\mathrm{d}\;\;{p}_{2},\cdots ,\;x\;\;\mathrm{m}\mathrm{o}\mathrm{d}\;\;{p}_{{\mathrm{L}}}) $是一个环同构，即对于环${\mathbb{Z}}_{p} $执行的运算，可以分解为对多个环${\mathbb{Z}}_{{\mathrm{p}}_{1}}，{\mathbb{Z}}_{{\mathrm{p}}_{2}}，\cdots ，{\mathbb{Z}}_{{\mathrm{p}}_{L}} $的运算，从而达到以多次小整数环上运算实现超大规模整数环上运算的目的。
对于CKKS全同态加密算法中的密文多项式$ P\left(x\right)={a}_{0}+{a}_{1}x+\cdots +{a}_{N-1}{x}^{N-1} $，基于CRT的NTT计算过程如下（见图1）：
图 1 基于中国剩余定理的密文多项式快速数论变换

Fig.1 Fast number theory transformation of ciphertext polynomials based on Chinese Remainder Theorem

（1）用系数向量$ \boldsymbol{a}=({a}_{0},{a}_{1},\cdots ,{a}_{N-1}) $表示密文多项式$ P\left(x\right) $；
（2）生成$ k $个素数$ {p}_{1},{p}_{2},\cdots ,{p}_{k} $，其中$ {p}_{k}=c{2}^{k}+1 $，$ {\mathrm{\Pi }}_{i=1}^{k}{p}_{i} > q $，$ q $为多项式环的模数；
（3）用每一个素数$ {p}_{i} $分别分解系数向量$ \boldsymbol{a} $中的每一项$ {a}_{j}({a}_{j}\in \boldsymbol{a}) $得到系数矩阵$ \boldsymbol{A} $；
（4）对$ \boldsymbol{A} $的每一行进行NTT操作得到点值矩阵$ \boldsymbol{B} $；
（5） 对B的每一列用中国剩余定理逆变换ICRT恢复出最终计算结果，得到密文多项式的点值表达式。

2.3 基于负闭包卷积的NTT算法计算效率优化

设有两个多项式$ f\left(x\right)、g\left(x\right)\in {R}_{\mathrm{p}}， {R}_{\mathrm{p}}={Z}_{\mathrm{p}}\left[x\right]/ ({x}^{N}+1) $，其中$ N $为$ 2 $的整数次幂，且$ p $为形如$ k\times {2}^{m}+1 $的素数，$ \boldsymbol{a}=\left({a}_{0}，{a}_{1}，\cdots ，{a}_{N-1}\right)，\boldsymbol{b}=({b}_{0}，{b}_{1}，\cdots ， {b}_{N-1}) $分别为多项式$ f\left(x\right)、g\left(x\right) $的系数向量。
在整数域上有：
$ h^{\prime}(x)=f(x) g(x)=\sum_{i=0}^{N-1}\left(c_i+c_{i+N}\right) x^i $
在有限域的多项式环上有：
$ h\left(x\right)=f\left(x\right)g\left(x\right)=\sum _{i=0}^{N-1}\left({c}_{i}-{c}_{i+N}\right){x}^{i} $
由于NTT是定义在有限域$ \mathit{Z}_{\mathrm{p}}=Z/pZ $上的离散傅里叶变换，有别于整数域上的计算，如果用点值形式表示$ N-1 $阶多项式，则需$ N $个点，若不经过处理，$ N $个点的两个多项式相乘有：
$ \begin{aligned} {h}^{\prime}\left(x\right)&=f\left(x\right)g\left(x\right)={\mathrm{INTT}}\left({\mathrm{NTT}}\left(a\right)\times {\mathrm{NTT}}\left(b\right)\right)\\&=\sum\limits_{i=0}^{N-1}\left({c}_{i}+{c}_{i+N}\right){x}^{i}\end{aligned} $
为了将NTT算法在整数域上相乘的结果$ \displaystyle\sum_{i=0}^{{N-1}}({c}_{i}+{c}_{i+N}){x}^{i} $修正为多项式环上相乘的结果$ \displaystyle\sum_{i=0}^{{N-1}}({c}_{i}-{c}_{i+N}){x}^{i} $，通常需要用$ 2N $个点来表示$ N-1 $阶的多项式$ f\left(x\right)\mathrm{、}g\left(x\right) $，即将系数向量从$ 0 $扩充到$ 2N $阶，使得$ \displaystyle\sum_{N-1}^{{2N-1}}{c}_{i}=0 $来修正结果，这样做会额外消耗一倍的存储和计算资源。本文采用负闭包卷积（Negative Wrapped Convolution，NWC）技术优化数论变换，通过生成预处理序列对多项式向量进行预处理来修正结果。具体步骤如下：
（1） 计算$ \psi $，$ \psi $为$ {Z}_{p} $的$ 2N $阶单位根，即$ \omega ={\psi }^{2} $为$ N $阶单位根。生成列表中的旋转因子序列数组$ {\mathrm{psis}} $为：
$ \{{\psi }^{-\left(2N-1\right)},{\psi }^{-\left(2N-2\right)},\cdots ,{\psi }^{-1},\psi ,\cdots ,{\psi }^{2N-2},{\psi }^{2N-1}\} $
首先完全分解$ q-1=k{2}^{p}={p}_{1}{p}_{2}\cdots {p}_{k}{2}^{p} $，并收集其因数集$ \{2,{p}_{1},{p}_{2},\cdots ,{p}_{k}\} $。仅当对每个$ {p}_{i}\in \{2,{p}_{1},{p}_{2},\cdots , {p}_{k}\} $时$ a\in \left(1,q\right),{a}^{\tfrac{q-1}{{p}_{i}}\ne 1\;\mathrm{m}\mathrm{o}\mathrm{d}\;q} $是$ {Z}_{p} $的一个候选一阶原根。找到了$ {Z}_{p} $的一阶原根$ a $，可以推导出$ 2N $阶单位的原根为：
$ \psi ={a}^{k 2\left(p-m-1\right)}\mathrm{m}\mathrm{o}\mathrm{d}\;q $
（2） 用$ \boldsymbol{a}=\left({a}_{0},{a}_{1},\cdots ,{a}_{N-1}\right),\boldsymbol{b}=\left({b}_{0},{b}_{1},\cdots , {b}_{N-1}\right)\in {Z}_{p} $两个向量表示多项式$ f\left(x\right)\mathrm{、}g\left(x\right) $，计算$ \widehat{a}=\left[{a}_{0},\psi {a}_{1}, {\psi }^{2}{a}_{2},\cdots , {\psi }^{N-1}{a}_{N-1}\right],\widehat{b}=[{b}_{0},\psi {b}_{1},{\psi }^{2}{b}_{2},\cdots ,{\psi }^{N-1}{b}_{N-1}] $。
（3） 使用负闭包卷积的NTT算法：
$ \begin{aligned} h\left(x\right)=&\left(1,{\psi }^{-1},{\psi }^{-2},\cdots ,{\psi }^{-\left(N-1\right)}\right)\circ\\& {\mathrm{INTT}}\left({\mathrm{NTT}}\left(\widehat{a}\right)\circ {\mathrm{NTT}}\left(\widehat{b}\right)\right)\\=&\sum _{i=0}^{N-1}\left({c}_{0}-{c}_{i+N}\right){x}^{i}\end{aligned} $
式中$ \circ $表示元素相乘。

2.4 GPU硬件架构

计算统一设备架构（Compute Unified Device Architecture，CUDA）是一种由NVIDIA推出的通用并行计算架构，CUDA上下文中的内核是由主机（CPU）调用以在设备（GPU）上执行的函数。
内核中有3个重要的概念：网格（Grid）、块 （Block）和线程（Thread），如图2所示。网格由块组成，而块又由线程组成。每个网格可以包含一定数量的块（实际数量取决于GPU型号），这些块可以在网格内部抽象成一维或二维数组，每个块都有一个由维数确定的ID。与网格类似，块可以包含一定的线程数（最大线程数同样取决于GPU型号），块中的线程也有索引，用于访问块内的特定线程。
图 2 GPU层次结构

Fig.2 GPU hierarchical structure

GPU实际上是一个流处理器簇（Streaming Multiprocessors，SM）的阵列，每个块都对应一个流处理器簇，每个流处理器簇由流处理器（Streaming Processor，SP）、共享内存（Shared Memory）、寄存器文件（Register File）、特殊功能单元（Special Function Units）和Warp调度器（Warp Scheduler）组成。其中，每个流处理器簇所包含的流处理器数量根据GPU架构而不同，相同架构GPU包含的流处理器簇数量由GPU中高低端来决定。线程束（Warp）为GPU执行程序时的调度单位，在调度后，块被分割成Warp，每个Warp由32个线程组成，对应同一个流处理器簇同在一个Warp的每个线程有自己的指令计数器和寄存器，在自己的数据上执行相同的指令。
全局内存（Global Memory）是GPU中最大的内存分区，所有线程都可以访问，与GPU上的其他内存通信相比，全局内存的通信最耗时，因此应该尽可能减少对全局内存的访问。常量内存（Constant Memory）中存储的数据是只读的，在操作执行过程中不能改变。常量内存比全局内存快得多，适用于线程束中所有线程都需要从相同的内存地址中读取数据的情况，比如所有线程都需要的常量参数。与常量内存不同，共享内存（Shared Memory）可以在执行期间进行修改，它比全局内存快，但只能由同一块内的线程访问。每个流处理器簇都有一定数量由线程块分配的共享内存，它们在内核函数内进行声明，生命周期伴随整个线程块。寄存器（Register）是线程私有的最快但最小的存储单元，寄存器是GPU中访问速度最快的内存空间，但是一个流处理器簇中寄存器的数量比较有限，当内核函数使用的寄存器数量超过了硬件限制，则会使用本地内存来代替多占用的寄存器，从而导致寄存器溢出，这种情况会对性能产生不利影响，实际编程过程中应该避免这种情况。一个线程既不能读也不能写其他线程的寄存器，只能在同一线程束中读取彼此的寄存器。

3 GPU加速密文乘法方案

第2节从算法设计上介绍了降低NTT算法计算复杂度、契合并行计算流的方法，本节将提出GPU上基于NTT算法的访存策略、动态分配线程、混合调用内核以实现并行优化方案。

3.1 GPU上基于NTT的访存策略

内存访问模式的优化是GPU上实现全同态加速的关键部分，GPU内存层次结构的有效使用对实现全同态加密算法的整体性能起着重要作用。在第2.3节中，对NTT/INTT输入的多项式$ f\left(x\right)\mathrm{、}g\left(x\right) $系数数组$ a\mathrm{、}b $（后续以$ a $为例进行讨论）和旋转因子序列数组$ \mathrm{p}\mathrm{s}\mathrm{i}\mathrm{s} $不同元素的访问，最朴素的解决方案是都使用全局内存。
共享内存仅支持同一块中的线程访问，但访问速度远高于全局内存。由于数组$ a $的元素只在GPU的块（Block）中处理，也称线程块，本方案提出采用共享内存处理NTT算法输入的系数数组$ a $。因此，在NTT/INTT的计算过程中，$ a $的元素被访问$ {\mathrm{log}}_{2}n $次。我们向全局内存发出一个请求，将$ a $的一个元素复制到共享内存，随后为该元素访问共享内存$ {\mathrm{log}}_{2}n $次，从而避免为单个元素向全局内存发出$ {\mathrm{log}}_{2}n $次请求。
常量内存类似全局内存，可以跨块访问其数据存储在只读的高速缓存中，访问速度快且不存在写操作。由于旋转因子序列数组$ {\mathrm{psis}} $的每个元素只被每个块访问一次且值不变，因此本方案提出在GPU核启动前将$ \mathrm{p}\mathrm{s}\mathrm{i}\mathrm{s} $装载到常量内存中。
基于上述对多项式$ f\left(x\right)\mathrm{、}g\left(x\right) $系数数组$ a $和旋转因子序列数组$ {\mathrm{psis}} $访问方式的设计，接下来以$ N $个点且基为$ 2 $的NTT算法为例来讨论如何实现。该算法实际上由$ {\mathrm{log}}_{2}n $次迭代组成，并且每次迭代中有$ N/2 $个蝶形运算操作，NTT组数在每次迭代后减半。当前大多数GPU技术支持每个块的最大线程数为1024个，当输入数组长度N=2048时，数组$ a $的两个元素只需使用1个GPU线程调度。当处理N > 2048数组时，本文提出将该数组划分为多个包含2048个元素的组，并使用多个GPU块在不同的NTT计算迭代中处理。
但是，由于不同的GPU块不能互相访问共享内存，因此需要从慢速全局内存中访问。本文提出采用暂存共享内存的方法提高共享内存的利用率，同时降低共享内存与全局内存的读写次数。如图3所示，在一个N=4096的Radix2-NTT迭代访存实例中，将数组$ \mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}\_\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{u}{\mathrm{p}}_{1} $划分为两个2048个元素的操作组$ \mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}\_\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{u}{\mathrm{p}}_{2} $和$ \mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}\_\mathrm{g}\mathrm{r}\mathrm{o}\mathrm{u}{\mathrm{p}}_{3} $，并分别使用线程块0和线程块1来处理。可以看到在第2轮迭代中，线程块0和线程块1只有1024个元素发生了变化（见红色标识），因此在多个线程块处理1个操作组时，根据NTT算法的访存规律，将不变的元素暂存共享内存，变化的元素写回全局内存，从而避免对全局内存的频繁读写。
图 3 N=4096的Radix2-NTT迭代访存实例

Fig.3 Radix2-NTT iterative memory access instance with N=4096

对于N=4096的Radix2-NTT而言，完成整个 NTT算法需要12轮迭代，不做优化的每轮迭代需要访问全局内存4096次，写回4096次，完成1次4096点的NTT算法需要49152次的全局内存读取操作。如图3所示，采用暂存共享内存法，第1轮迭代访问全局内存4096次将数据读入共享内存，完成第1轮蝶形变换后，将数据写回，即写回全局内存2048次。后续10轮迭代每轮读取全局内存2048次，写回2048次，最后1轮迭代读取全局内存2048次，写回4096次。采用暂存共享内存法完成1次4096点的NTT算法仅需要用26624次全局内存读取。

3.2 GPU上动态分配工作负载

除了高效利用GPU内存外，在GPU中实现NTT/INTT算法的另一个挑战是高效地分配线程以实现高利用率，即确保每个线程都保持繁忙，且工作负载均衡。本方案里每个线程独立地处理$ 1 $个蝶形运算操作，在每次迭代中为每个线程分配所需的操作数和对应的旋转因子。单个蝶形运算抽取的操作数个数为NTT算法的基，如图4所示。对于基为$ 2 $的NTT算法的每个蝶形运算操作，数组$ a $的两个元素参与计算，对数组$ a $的两个元素使用1个GPU线程。线程使用target_idx变量计算该线程在每次迭代中要处理的第1个数组元素的索引，变量step用于确定分配给同一线程的数组$ a $的第2个数组元素，每个线程使用step_group变量来跟踪访问旋转因子序列集$ {\mathrm{psis}}\leftarrow {\mathrm{Ps{i}}}_{\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}} $数组中的对应旋转因子$ \mathrm{P}\mathrm{s}\mathrm{i} $。
图 4 Radix2-NTT step_group 分组迭代图

Fig.4 Radix2-NTT step_group group iteration

为了充分利用每个GPU块中的计算资源以及降低线程与共享内存间的读写操作，本方案在GPU 上实现了Radix2-NWC-NTT、Radix4-NWC-NTT、Radix8-NWC-NTT以及Radix16-NWC-NTT$ 4 $种不同基数的负闭包卷积NTT算法。如表1所示，NTT基数越大，迭代次数越少，对内存的总访问次数越少，但是单次迭代的计算越多，对单次蝶形变换操作所需的计算资源也越多。相反地，NTT基数越小，迭代次数越多，对内存的总访问次数越多，单次迭代的计算越小，对单次蝶形变换操作所需的计算资源也越小。因此，需要通过不同基数的NTT算法来匹配GPU硬件性能，以充分利用可并行的最大资源。本方案设计了不同基数混合调用的NTT结构，对 N个点基为k的NTT结构，当第i次迭代$ N < {k}_{i} $时，调用1轮基$ k^\prime $（$ k^\prime{\left(k\right)}^{i-1}=N $）的NTT结构即可完成迭代。图5为N=8的混合调用实例。混合调用的蝴蝶结构在获取最优并行策略的同时提高算法灵活性。
表 1 不同基数的NTT对比

Table 1 Comparison of NTT with different cardinals

NTT基数计算规模迭代次数单次迭代访存次数蝶形变换乘法次数
Radix2$ N={2}^{n} $$ {\mathrm{log}}_{2}N $$ N $$ 1 $
Radix4$ N={4}^{n} $$ 1/2{\mathrm{log}}_{2}N $$ N $$ 4 $
Radix8$ N={8}^{n} $$ 1/3{\mathrm{log}}_{2}N $$ N $$ 8 $
Radix16$ N={16}^{n} $$ 1/4{\mathrm{log}}_{2}N $$ N $$ 16 $
图 5 Radix2-NTT step_group 分组迭代图

Fig.5 Radix2-NTT step_group grouping iteration graph

3.3 GPU上动态调用内核

在GPU体系结构中，线程分布在多个GPU块中，GPU块由内核（Kernel）调用，而GPU的工作模式可以分为单核模式（Single-Kernel Mode）和多核模式（Multi-Kernel Mode）。在单核模式下，GPU的计算任务主要由一个核心（或少数几个核心）执行。多核模式是现代GPU的常用和标准操作模式，在这种模式下，GPU的多个核心可以并行工作，共同处理复杂的计算任务。
在单核模式中，每个GPU块分配1024个线程，并将输入数组$ a $的一组连续$ {\mathrm{step}}\times 2 $的元素分配给同一个GPU块，每个GPU块无需等待其他GPU块处理数组$ a $的其他部分。该思路按照算法调度的顺序调度，突破了GPU本身提供的有限并行性，避免了结果合并中的访存竞争。在多核模式中，为每个内核调用安排2048个GPU块，所有这些块同时运行，对内核的每次调用都会产生一定的开销，导致在处理数组较小时性能比单核模式更差。我们在GTX 1050ti上分别就单核模式、多核模式和混合模式进行了实验，如图6所示。结果表明，当$ N > {2}^{12} $时，多核模式性能更优。
图 6 内核调用模式性能对比

Fig.6 Comparison of kernel call mode performance

结合实验结果，为了充分利用多核调用的并行潜力，本文提出GPU内核混合调用方法。以$ N $个点基为2的负闭包卷积的NTT算法Radix2-NWC-NTT为例。从多核模式开始，以$ {\mathrm{step}} $的大小对待处理的数组$ a $的元素进行分组。在NTT算法开始时$ {\mathrm{step}}=N/2 $，分组$ {\mathrm{step}}\_{\mathrm{grou{p}}}_{1}\leftarrow a $，随着算法每次迭代$ {\mathrm{step}}\_{\mathrm{group}} $的大小减小一半。当$ |{\mathrm{step}}\_{\mathrm{grou{p}}}_{i}|\leqslant{2}^{12} $时，从多核模式切换到单核模式。
如图7所示，在多核阶段，因为共享内存不能在内核间相互访问，整个输入数组从全局内存中访问；在单核阶段，需要被访问的数组元素被复制到共享内存一次，并在剩余的迭代次数内在共享内存中被访问。INTT操作与NTT略有不同，因为它从$ {\mathrm{step}} $较小的位置开始，并在每次迭代后合并。因此，INTT的内核调用模式与NTT的内核调用模式完全相反，即从单核模式切换到多核模式。
图 7 NTT step_group混合调用迭代图

Fig.7 NTT step_group mixed call iteration graph

4 实验结果及分析

4.1 实验环境与框架介绍

本文以全同态运算的基础算子NTT算法的硬件加速为研究目标，从高效利用GPU内存、高效分配GPU线程的工作负载和高效利用GPU内核角度，提出混合访存策略、动态工作负载分配、混合内核调用思想和方案，充分利用GPU大规模并行计算的优势，实现面向GPU计算硬件的全同态加密算法，其核心算法基于C++和CUDA实现。CUDA是建立在NVIDIA的CPU上的一个通用并行计算平台和编程模型，需要与CPU协同工作。基于CPU+GPU的异构计算平台可以优势互补，CPU负责处理逻辑复杂的串行程序，而GPU重点处理数据密集型的并行计算程序，从而发挥最大功效。
HElib是IBM用C++写成的一个开源的全同态加密库，实现了BGV[16]和CKKS全同态加密（FHE）算法，有效地使用Smart-Vercauteren密码文本打包技术和Gentry-Halevi-Smart优化。在使用HElib库时，首先要设置相关的参数。目前CKKS算法包含以下参数：
（1）$ n$：分圆多项式次数，即$ {x}^{n}+1 $中$ n $的值，对于CKKS，$ n $必须是$ 2 $的幂，通常取值为$ {2}^{10} $和$ {2}^{15} $。$ n $越大，各种计算等操作速度越慢，性能会下降，密文的大小也会增加。明文多项式或密文多项式中最高次数为$ n-1 $。$ n $取值越大则RLWE加密方案越安全，但对应的密文也越大。
（2）$ {\mathrm{bits}} $：指定“密文模”的位数。随着比特的增加，安全性降低，是决定密文噪声容忍度的重要参数。bits值越大则噪声容忍度越大，密文可支持更大的运算深度，同时密文的大小也会增加。$ {\mathrm{bits}} $值越大，RLWE加密算法越不安全（需要增大$ n $值来“中和”），但可以执行更深层次的同态计算。
（3）$ {\mathrm{precision}} $：指定对数据进行编码、加密或解密时的精度位数。更准确地说，每一个操作都被设计为向每个槽添加一个最多为$ {2}^{–\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}} $的错误项。随着精度的增加，同态计算的允许深度减小，但这不影响安全性和性能。
（4）$ c $：密钥切换矩阵的列数。随着$ c $的增加，安全性提高，但是性能下降，对公钥的内存需求增加。$ c $必须至少为$ 2 $，最好不超过$ 8 $。
实验参数设置如表2所示。
表 2 CKKS参数

Table 2 Parameters of CKKS

分圆多项
式次数${n} $		 密文模位数
bits		 精度位数
precision		 密钥切换矩
阵的列数c
216 1 445 20 8
基于GPU加速的NTT和INTT模块分别在3个不同GPU上对比：NVIDIA GTX 980、NVIDIA GTX 1050ti和Quadro RTX 8000，测试参数如表3所示。
表 3 GPU参数

Table 3 GPU parameters

GTX 980 GTX 1050ti Quadro RTX 8000
CUDA核心 2048 768 4068
显存/GB 4 4 48
核心频率/MHz 1127 1291 1395
显存带宽/GB·s−1 224 112 672

4.2 GPU上NTT算法测试与分析

为了评估单个优化的效果，针对不同的数据规模对NTT/INTT操作进行了相应的方案设计，并在NVIDIA GTX 1050ti GPU上进行了性能验证。如第3节所述，将NTT/INTT操作设计为如下情况：（1）使用单核；（2）使用多核；（3）使用单核，并利用共享内存；（4）使用建议的混合方法。所有设计的性能结果如表4所示。
表 4 GTX 1050ti 上优化的性能结果

Table 4 Performance results optimized on GTX 1050ti 单位：μs

操作 方案 计算规模（log2N）
11 12 13 14 15 16
NTT 1 12 21 38 73 149 309
2 95 98 103 109 117 127
3 10 16 32 − − −
4 $ 10 $ 16 32 42 49 61
INTT 1 14 24 40 75 151 315
2 88 102 108 111 114 118
3 13 17 33 − − −
4 13 17 21 30 36 46
其中方案2和方案4的时间包含了内核启动开销，与方案1相比，当$ n $的值分别为2048、4096和8192时，方案3可将NTT/INTT实现的单内核性能分别提高10%、25%和17%。由于GPU共享内存容量有限，该优化仅适用于计算规模为8192及以下的多项式。当$ n $值分别为2048、4096和8192时，方案3的设计比方案2的设计性能分别提升了9.4倍、6.1倍和3.2倍。在n > 8192的情况下，每个NTT/INTT操作使用多内核的性能更好。当n值分别为16384、32768和65536时，使用方案2的性能相对方案1的性能分别提升1.5倍、1.5倍和2.4倍。因此，将这两种方法结合起来，并利用了共享内存的混合方法4。混合方法设计在不同$ n $值下的性能比方案1设计提升1.2~5倍。类似的比较结果也适用于INTT操作。由于采用混合方法的设计效果最佳，本文针对3种不同GPU平台上对采用混合方法的NTT和INTT操作进行了实验，得到了在不同模数大小下的性能结果，如表5所示。
表 5 NTT和INTT实现的性能结果

Table 5 Performance results of NTT and INTT 单位：μs

操作 平台 模数大小($ {\mathrm{log}}_{2}q $) 计算规模（log2N）
$ 11 $ $ 12 $ $ 13 $ $ 14 $ $ 15 $
NTT GTX 980 $ 30 $ $ 10 $ $ 16 $ $ 32 $ $ 42 $ $ 49 $
$ 60 $ $ 20 $ $ 36 $ $ 43 $ $ 51 $ $ 73 $
GTX 1050ti $ 30 $ $ 7 $ $ 15 $ $ 16 $ $ 23 $ $ 24 $
$ 60 $ $ 11 $ $ 21 $ $ 27 $ $ 33 $ $ 36 $
RTX 8000 $ 30 $ $ 7 $ $ 11.5 $ $ 22.5 $ $ 25.5 $ $ 27.7 $
$ 60 $ $ 12.5 $ $ 22.5 $ $ 27 $ $ 29 $ $ 39 $
INTT GTX 980 $ 30 $ $ 13 $ $ 17 $ $ 21 $ $ 30 $ $ 36 $
$ 60 $ $ 25 $ $ 31 $ $ 35 $ $ 41 $ $ 52 $
GTX 1050ti $ 30 $ $ 7 $ $ 9 $ $ 12 $ $ 14 $ $ 16 $
$ 60 $ $ 12 $ $ 15 $ $ 18 $ $ 20 $ $ 24 $
RTX 8000 $ 30 $ $ 7.5 $ $ 13 $ $ 14.5 $ $ 16.3 $ $ 18.3 $
$ 60 $ $ 12.5 $ $ 15.5 $ $ 18 $ $ 21 $ $ 23 $
HElib使用NTL数论库以及HEXL加速。HEXL 是Intel 2022年提出的同态加速库，它利用英特尔 AVX-512加速指令中的优化来加速全同态加密中的 NTT算法，本文结合第3节的3种策略在GPU上实现的NTT和INTT算法与HElib库中的NTT算法性能进行比较，实验结果如图8所示。
图 8 GPU加速与HElib库中NTT & INTT对比

Fig.8 GPU acceleration compared to NTT&INTT in HElib library

本文在GPU上实现的NTT/INTT算法计算时间相比使用了AVX-512的HElib库减少了近65%。从图中可以看到，多项式阶数的增加对GPU上NTT性能的影响明显，原因是多项式阶数的增加会带来迭代次数的增加，从而多核调用的开销增加。在第3节中，采用了不同基数的NTT方案，将每次迭代进行一轮蝶形变换增加为两轮甚至多轮蝶形变换，进一步减少迭代次数，提升计算性能。

4.3 GPU优化的CKKS密文乘法测试与分析

本文在不同参数设置下分别测试了HElib库和本方案的单次密文乘法所需时间，如表6所示，测试结果为平均时间，其中$ n $为分圆多项式次数，在CKKS方案中，$ n $值需为2的幂。
表 6 不同方案密文乘法时间

Table 6 Ciphertext multiplication time of different schemes

参数$ (n,{\mathrm{log}}_{2}q,{\mathrm{slots}}) $ 乘法时间/ms
HElib库 本方案
$ (16\;384，119，4\;096) $ $ 102 $ $ 97 $
$ (32\;768，119，8\;192) $ $ 269 $ $ 190 $
$ (65\;536，725，16\;384) $ $ 2\;422 $ $ 1\;800 $
从实验结果可以看出，当多项式阶数和明文向量大小较小时，相较于HElib库，本方案对CKKS密文乘法效率的提升并不明显，这是因为密态计算时CPU与GPU之间的数据传输时延占比较大。然而随着多项式阶数与明文向量大小的上升，本方案在密文乘法上相较于HElib库的优势逐渐凸显。

4.4 GPU 提速的卷积神经网络密文推理

实验中所采用的推理模型结构如下。
（1）conv2d_1：卷积层，卷积核$ \left(\mathrm{5,5}\right) $，步长$ \left(\mathrm{2,2}\right) $，输出32×14×14。
（2）conv2d_2：卷积层，卷积核$ \left(\mathrm{5,5}\right) $，步长$ \left(\mathrm{2,2}\right) $，输出64×5×5。
（3）flatten_1：输出1600×1。
（4）dense_1：全连接层，输出100×1，激活函数squareReLu。
其中，$ \mathrm{s}\mathrm{q}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{u}\left({x}\right)=\left\{\begin{array}{c}{x}^{2},x > 0\\ 0,x\leqslant0\end{array}\right. $
（5）dense_2：全连接层，输出10×1，激活函数softmax。
其中，$ \mathrm{s}\mathrm{o}\mathrm{f}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{x}\left(x\right)=\dfrac{{\mathrm{e}}^{{x}_{i}}}{{\sum }_{i}{\mathrm{e}}^{{x}_{i}}} $
推理采用MNIST手写数字数据集，共1024张灰度图，图像特征为1×28×28。
实验分别计算了HElib库和本方案下卷积神经网络密文推理各主要计算层所需的时间和推理所需的总时间，如表7所示，表中数值为计算所得平均值。
表 7 不同参数下密文推理时间

Table 7 Ciphertext inference time under different parameters 单位：s

计算层$ {\mathrm{log}}_{2}n=13 $$ {\mathrm{log}}_{2}n=14$$ {\mathrm{log}}_{2}n=15$
HElib库本方案HElib库本方案HElib库本方案
conv2d_1$ 3.22 $$ 3.14 $$ 5.83 $$ 4.68 $$ 11.99 $$ 5.73 $
conv2d_2$ 10.77 $$ 6.45 $$ 48.38 $$ 23.54 $$ 164.83 $$ 41.33 $
flatten_1$ 1.19\times 10^{-6} $$ 1.17\times 10^{-6} $$ 1.45\times 10^{-6} $$ 1.23\times 10^{-6}$$ 9.69\times 10^{-6} $$ 1.06\times 10^{-6} $
dense_1$ 1.06 $$ 1.00 $$ 6.45 $$ 4.79 $$ 21.84 $$ 7.25 $
dense_2$ 0.054 $$ 0.052 $$ 0.062 $$ 0.067 $$ 0.099 $$ 0.101 $
总时间$ 15.11 $$ 10.64 $$ 60.73 $$ 33.42 $$ 198.78 $$ 54.41 $
从计算结果可以看出，本方案在计算较密集的conv2d_2层时相较于HElib库可将计算时间缩短一半，其他大部分计算层的计算效率也有提升。而在dense_2全连接层，加法计算占比较高，乘法计算占比较低，导致该层计算所需时间与HElib库下所需时间相近。随着分圆多项式次数的增加，本方案的计算效率提升逐渐明显。

5 结束语

全同态加密作为隐私计算的最佳实现方案，相较于其他隐私计算技术，具有更通用的数据隐私保护能力，更适用于同网密态计算。然而在计算效率方面，全同态加密的密钥生成、加密、解密以及密文同态乘法运算等基本操作涉及维数较大的整系数多项式运算，导致全同态加密计算效率低。从通用计算平台到专用计算平台，全同态加密算法的效率显著提高，但将现有算法直接移植到专用处理器上并不能有效地挖掘全同态加密算法的并行潜力以及硬件平台的性能优势。针对以上问题，本文根据NTT算法数据内存访问规律优化内存访问模式，采用暂存共享内存的方法提高了共享内存的利用率，并降低了共享内存与全局内存的读写次数。根据计算规模和硬件资源动态分配线程工作负载，采用混合调用的蝴蝶结构在获取最优并行策略的同时提高算法灵活性。根据NTT算法每次迭代的蝶形变换分组动态调用内核，充分利用GPU上多内核调用的并行潜力。
虽然本文在以上场景中取得了一些研究成果，但在整个研究过程中，仍发现了许多难点值得进一步发掘。目前在GPU上实现的NTT优化算法在数据装载上有着较高的时延，如何降低异构硬件之间数据传输的时延是需要考虑的问题。此外，在GPU上实现的全同态加密算法只考虑单任务执行的情况，在GPU上有多任务执行的时候，如何根据现有资源动态调度线程仍待研究。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
1
GENTRY C. A fully homomorphic encryption scheme[M]. California:Stanford University,2009.

2
DUCAS L,MICCIANCIO D. Fhew:Bootstrapping homomorphic encryption in less than a second[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer,2015:617-640.

3
CHILLOTTI I,GAMA N,GEORGIEVA M,et al. Faster fully homomorphic encryption:Bootstrapping in less than 0.1 seconds[C]// Advances in Cryptology - ASIACRYPT 2016:22nd International Conference on the Theory and Application of Cryptology and Information Security,Hanoi,Vietnam,December 4-8,2016,Proceedings,Part I,2016:3-33.

4
CHEN H,HAN K. Homomorphic lower digits removal and improved FHE bootstrapping[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham:Springer International Publishing,2018:315-337.

5
SMART N P, VERCAUTEREN F. Fully homomorphic SIMD operations[J]. Designs, Codes and Cryptography, 2014, 71, 57- 81.

DOI

6
CASTRYCK W,ILIASHENKO I,VERCAUTEREN F. Homomorphic SIM D operations:Single instruction much more data[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham:Springer International Publishing,2018:338-359.

7
王励成, 李婧. 无噪声全同态加密浅析[J]. 密码学报, 2017, 4 (6): 579- 595.

WANG L C, LI J. Simple snalysis on noiseless fully homomorphic encryptions[J]. Journal of Cryptologic Research, 2017, 4 (6): 579- 595.

8
NUIDA K,KUROSAWA K. (Batch) fully homomorphic encryption over integers for non-binary message spaces[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin,Heidelberg:Springer Berlin Heidelberg,2015:537-555.

9
AGARWAL R C, BURRUS C S. Number theoretic transforms to implement fast digital convolution[J]. Proceedings of the IEEE, 1975, 63 (4): 550- 560.

DOI

10
PANDEY M, FERNANDEZ M, GENTILE F, et al. The transformational role of GPU computing and deep learning in drug discovery[J]. Nature Machine Intelligence, 2022, 4 (3): 211- 221.

DOI

11
WANG W,HU Y,CHEN L,et al. Accelerating fully homomorphic encryption using GPU[C]//2012 IEEE Conference on High Performance Extreme Computing. IEEE,2012:1-5.

12
DAI W,DORÖZ Y,SUNAR B. Accelerating NTRU based homomorphic encryption using GPUs[C]//2014 IEEE High Performance Extreme Computing Conference (HPEC). IEEE,2014:1-6.

13
LEI X,GUO R,ZHANG F,et al. Accelerating homomorphic full adder based on fhew using multicore CPU and GPUS[C]//2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS). IEEE,2019:2508-2513.

14
BERTELS J,VAN BEIRENDONCK M,TURAN F,et al. Hardware acceleration of FHEW[C]//2023 26th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS). IEEE,2023:57-60.

15
CHEON J H,KIM A,KIM M,et al. Homomorphic encryption for arithmetic of approximate numbers[C]//Advances in Cryptology - ASIACRYPT 2017:23rd International Conference on the Theory and Applications of Cryptology and Information Security,2017:409-437.

16
BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. （Leveled） fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory （TOCT）, 2014, 6 (3): 1- 36.

17
RIAZI M S,LAINE K,PELTON B,et al. HEAX:An architecture for computing on encrypted data[C]//Proceedings of the Twenty-fifth International Conference on Architectural Support for Programming Languages and Operating Systems,2020:1295-1309.

18
REAGEN B,CHOI W S,KO Y,et al. Cheetah:Optimizing and accelerating homomorphic encryption for private inference[C]//2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE,2021:26-39.

19
SAMARDZIC N,FELDMANN A,KRASTEV A,et al. F1:A fast and programmable accelerator for fully homomorphic encryption[C]//MICRO-54:54th Annual IEEE/ACM International Symposium on Microarchitecture,2021:238-252.

20
SAMARDZIC N,FELDMANN A,KRASTEV A,et al. Craterlake:A hardware accelerator for efficient unbounded computation on encrypted data[C]//Proceedings of the 49th Annual International Symposium on Computer Architecture,2022:173-187.

21
KIM J,LEE G,KIM S,et al. Ark:Fully homomorphic encryption accelerator with runtime data generation and inter-operation key reuse[C]//2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO). IEEE,2022:1237-1254.

22
JIANG L,LOU Q,JOSHI N. Matcha:A fast and energy-efficient accelerator for fully homomorphic encryption over the torus[C]// Proceedings of the 59th ACM/IEEE Design Automation Conference,2022:235-240.

23
VAN BEIRENDONCK M,D'ANVERS J P,TURAN F,et al. FPT:A fixed-point accelerator for torus fully homomorphic encryption[C]//Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security,2023:741-755.

24
YANG Y,ZHANG H,FAN S,et al. Poseidon:Practical homomorphic encryption accelerator [C]//2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE,2023:870-881.

25
ZHU Y,WANG X,JU L,et al. FxHENN:FPGA-based acceleration framework for homomorphic encrypted CNN inference[C]//2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE,2023:896-907.

26
BRUTZKUS A,GILAD-BACHRACH R,ELISHA O. Low latency privacy preserving inference[C]// International Conference on Machine Learning. PMLR,2019:812-821.

27
FAN S,WANG Z,XU W,et al. Tensorfhe:Achieving practical computation on encrypted datausing gpgpu[C]//2023 IEEE International Symposium on High Performance Computer Architecture (HPCA). IEEE,2023:922-934.

Options
文章导航

/

〈 〉

禁止存储和处理涉密及内部敏感信息
网站版权 © 《网络空间安全科学学报》编辑部
地址：北京市西城区月坛北小街2号院1号楼　
邮编：100037　
电话：010-89061756/89061778　
E-mail：wlkjaqkxxb@caasse.cn
技术支持：北京玛格泰克科技发展有限公司

京ICP备16032046号-20