《表2 全同态加密在整数域和实数域上的研究进展》

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

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

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

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

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

在Gentry体制之后，基于整数的FHE方案迅速成型。基于整数的FHE方案完全遵循Gentry的设计思路，其安全性基于AGCD困难问题。2010年Smart等人[26]基于整数与多项式设计了FHE方案，缩短了密钥和密文尺寸。同年，Dijk等人[27]提出了基于整数环上的FHE方案DGHV方案，这某种意义上是第1个基于整数的FHE方案，并且提出能够同时加密多个bit位数据的思路，但其缺点是计算过程比较复杂。此后很多人从DGHV方案入手，对整数上的FHE方案进行了优化。在EUROCRYPT2013上，Cheon等人[28]引入批处理技术，允许并行处理多比特数据（以向量形式存储），在EUROCRYPT2015上Nuida等人[29]将方案的明文空间从Z 2扩展至ZQ，其中Q为任意素数，同时当Q=2时，同态乘的算法复杂度从O（λ(log2λ）2)降为O（λ），该方案同样可以扩展为批处理FHE方案。目前FHE方案所基于的困难问题主要有两类，分别是Regev提出的RLWE问题和Howgrave-Graham[3 0]提出的AGCD问题。Cheon等人[31]在EUROCRYPT2015上将LWE问题归约为AGCD问题的一个变体，并在此基础上提出了一种新的基于AGCD的FHE方案，该方案的安全性不再依赖稀疏子集和的问题假设，且其性能优于此前所有的基于AGCD的FHE方案。现有的基于整数的FHE方案是针对两个参与者“一方加密，一方解密”（一对一）设计的，王彩芬等人[32]提出一种“多方加密，一方解密”（多对一）的FHE方案，与已有方案相比扩展了数据传输量，且提高了效率。除了基于整数的FHE方案以外，大量研究开始关注在实数域上的密文计算，Jaschke等人[33]提出一个有理数通过与2的幂迭代相乘可以近似表示为整数，不过相应也带来了额外的计算负担。另一方面，Dowlin等人[34]提出一种更高效的表示定点小数的方法，即将定点小数编码为整系数多项式，然而要想进行精确的小数运算，明文模需随电路深度的增加呈指数增大。在ASIACRYPT2017上，Cheon等人[35]构造了一种实数域上的FHE方案CKKS方案，可以对浮点数进行近似计算，方案加密时对明文进行舍入，解密时输出满足精度要求的近似值，通过使用Rescaling技术，在保证计算精度的同时将密文模数增长从指数增长变为线性增长，并通过使用批处理技术提高算法的计算效率。方案分别给出了在乘法逆、指数函数、逻辑运算和离散傅里叶变换这4种运算电路下的效率分析，效率都较为可观，但是该方案为层次型同态加密方案，不能通过Bootstrapping转化为全同态加密方案。随后在EUROCRYPT2018上，Cheon等人[36]基于Bootstrapping提出了一种更新低层级密文的新技术，将上述的层次型同态加密方案扩展为了全同态加密方案，该技术使用正弦函数近似代替模数约减操作，每次迭代操作仅包含1次同态乘运算，若对加密后的128个数字（精度为12 bit）进行密文更新，共耗时139.8 s。表2总结了利用全同态加密技术在处理整数和实数域上的研究进展。