全同态密码芯片的研究与设计

Fully Homomorphic Encryption (FHE) is a cryptography metric which allows evaluation on its cipher texts. FHE offers a fundamental solution to the confidential problems when delegating data processing to an untrusted third party. FHE has a great significance for cloud computing. However, the core issue of FHE is that there is a large number of multiplications of integers, vectors or polynomials in its algorithm which lead to a particularly slow computational speed. It is an effective way to use chip to accelerate FHE computations. Our objective of this project is to design a FHE chip. Based on this purpose, we specify our research work as follows: (1) Study and optimize the integer-based fully homomorphic encryption/decryption algorithm for hardware implementation. (2) Study and improve the large integer multiplication algorithm for FHE: including Fast Fourier Transform (FFT) based multiplication algorithm, modular multiplication algorithm based on Residue Number System (RNS). (3) Research into the hardware architecture of FHE: including Cached butterfly FFT multiplication architecture, Cox-Rower modular multiplication architecture based on RNS, memory architecture for public key compression algorithm. (4) Accomplish the design and verification of a FHE cryptography chip which can perform one single encryption/decryption in 10 milliseconds and one Bootstrapping operation in 2 seconds. These two targets outperform the performance of its current competitors in China and abroad.

全同态密码是一种可以对加密后的数据进行运算的密码体制。它从根本上解决了将数据委托给第三方处理时的信息泄密问题，对云计算的安全具有重大意义。全同态密码的核心问题是：算法中存在着庞大的整数、向量或多项式的乘法导致了全同态密码运算速度过慢。采用芯片实现全同态密码算法是提高全同态密码运算速度行之有效的方法。本项目围绕着全同态密码芯片研究与设计开展以下工作：（1）研究并优化面向硬件实现的大整数体制下的全同态加解密算法。（2）研究和改进全同态密码的大数乘法算法：包括改进快速傅里叶变换（FFT）的乘法算法及余数系统（RNS）下的模乘算法。（3）研究实现全同态密码的硬件架构：包括Cache的蝶形FFT乘法架构、余数系统下的舵桨模乘架构及公钥压缩算法的存储架构。（4）完成一款全同态密码芯片设计及验证，芯片拟达到单次加解密时间不超过10毫秒，单次重加密时间不超过2秒，这两项指标均优于当前国内外同类设计。

四年前立项启动的“全同态密码芯片的研究与设计”非常有必要，一是同态密码学的研究已经成为国内外密码界的研究热点，二是美国国防高级研究项目局（DARPA）于2020年3月启动了“同态计算芯片”项目（DPRIVE）招标程序，总投入3300万美元，再次证明的同态研究的重要。开展该课题以来，课题取得了6项重要的学术成果和1项FPGA硬件实现：（1）证明了离散分布生成树的结构和节点高度，据此提出基于Knuth-Yao的高速恒定时间离散高斯采样算法及硬件架构（2）提出了多蝶形运算内核的NTT并行计算硬件架构及并行蝶形内核的访存模式设计，采用数据排序权重的并行排序网络技术优化了多蝶形运算内核的输入输出硬件选择分配的通路（3）提出了负包络卷积的面向同态加密的循环卷积大整数乘法器及加速技术（4）分析并证明了Schönhage–Strassen乘法算法，建立了乘法的基本结构，完成了基于Schönhage–Strassen的双模数NTT乘法算法优化的硬件实现，（5）提出了一种基于Toom-Cook乘法的免除法的Montgomery算法并完成了其硬件设计（6）提出了一种NTT多通道并行多项式乘法及其并行的负包络卷积NTT算法（7）基于以上方法和证明，完成了基于BFV的同态密码FPGA系统设计与验证，该系统相比于软件的实现，性能提高了148倍。在本基金课题的支持下，共发表高水平论文42篇，其中有40篇第一标注，有2篇第二标注，其中高IEEE transaction期刊论文12篇，SCI论文11篇；国际会议论文30篇，专利申请受理6项，并获2017年度党政机要密码二等奖一项，培养研究生18人，其中博士生 7人，硕士生11人。