《表1 提高全同态加密效率的解决方案》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《同态密码理论与应用进展》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

由于反复调用解密电路使FHE方案效率过低，因此很多人随后针对Bootstrapping进行了优化，Ducas等人[12]在EUROCRYPT2015上将Helib库中Bootstrapping操作的运行时间从6 min缩短至1 s以内，并相应提出了FHEW方案。Chillotti等人[13]随后在ASIACRYPT2016上对FHEW方案进一步优化，将Bootstrapping的运行时间从1 s以内缩短至0.1 s以内，并将其密钥大小从1 GB减小至24MB。在EUROCRYPT2018上，Chen等人[14]通过应用“低位删除”多项式优化了开方运算，此举对下文要提到的FV和BGV方案中的Bootstrapping都有重要作用。若令密钥的1-范数为h=∥s∥1，明文模数为t=pr，则优化算法可以将FV方案的自举深度降至log2h+log2（logp(ht）)，将BGV方案的自举深度从log2h+2log2t降至log2h+log2t。除了优化Bootstrapping以外，另一种为全同态“提速”的有效手段是批处理（batch）技术，也可称为封装（Pack）技术，即允许将多个数据值加密为一个密文，并能够同态执行单指令多数据操作（Single Instruction Multiple Data，SIMD）。2014年，Smart等人[15]通过中国剩余定理分解明文空间，构造了支持SIMD操作的FHE方案。在EUROCRYPT2018上，Castryck等人[16]通过引入劳伦多项式编码技术对Smart的方案进行了改进，极大提高了明文封装容量以及在效率或安全性方面优化系统参数的灵活性。虽然通过不断优化Bootstrapping技术和引入Batching技术大幅提高了FHE方案的实现效率，但是离实际应用的要求还有一定距离，因此构造无噪声的FHE方案成为当前全同态加密研究的一个重要思路[17]。噪声的加入是为了保证FHE方案的安全性，但也带来了噪声控制的困扰，虽然无噪声的FHE方案被认为是不安全的，但该结论也并没有被严格证明，因此研究无噪声的FHE方案仍具有现实意义。2012年Kipnis等人[18]分别基于矩阵和多项式构造了无噪声FHE方案。2014年Nuida[19]在IACR Cryptology e Print上提出了一个构造无噪声FHE方案的框架。同年，Gentry[20]基于完备群概念提出了一个无噪声FHE框架。除上述方案以外，近年来还出现了基于向量空间[21]，基于八元数环[22]，基于非交换环[23]等的无噪声FHE方案。但是目前现有无噪声FHE方案还并不能在可证明安全框架下严格做到安全可行。此外，GPU和FPGA等硬件架构的特点具有大幅度提高同态加密方案效率的潜力，大整数乘法是FHE算法中最为核心的计算环节，施佺等人[24]采用Verilog HDL语言完成了一个16×24 bit有限域FFT算法的FPGA设计，谢星等人[25]提出一种基于Sch?nhage-Strassen算法的768 kbit大整数乘法器FPGA设计，均较CPU平台的运算效率有大幅提速。表1总结了提高全同态加密效率的各类解决方案。