首页
学习
活动
专区
工具
TVP
发布

全同态加密的三代技术发展与挑战展望

经过近10年的发展,全同态加密方案在效率和安全性等方面都有了大的进展和突破。目前,全同态加密方案按照不同技术阶段大致分成三代。

第一代金特里最初基于理想格的方案以及基于最大近似公因子问题的变种方案DGHV被称为第一代同态加密方案。这一代方案密钥尺寸大、效率低下。它们基于的是非标准的安全假设,并且被发现在量子计算环境下不再安全。尽管如此,第代方案仍对后来的工作带来了极大的启发,具有划时代的意义。

第二代基于格上“带错误学习(Learning with Eror,LWE)”假设是第二代同态加密方案的特点。与第一代相比,基于LWE问题构造的同态加密方案更为简单,其安全性可以归约到标准的格上困难问题。它的缺点是,由于密文是向量,通过张量积的操作实现密文同态乘法运算会导致密文的维数急剧膨胀。BV方案是第二代同态加密方案的代表之一,它通过使用重线性化技术来控制密文的维数,进而通过维数-模数约减技术减少了解密算法的复杂性从而构造出第一个可自举的基于LWE问题的有限同态加密方案。另一个代表方案是Brakerski等人提出的BGV方案。该方案用密钥转换技术来控制密文维数膨胀问题,用模数转换技术来降低密文运算中的噪声增长问题,从而达到无需自举就可以实现多项式深度的同态运算,极大地提高了效率。IBM推出的Helib库和微软推出的SEAL库分别实现了BGV方案的两个不同的变种,它们是全同态研究中最具代表性的两个开源代码库。

第三代是指金特里等人构造的一个基于矩阵近似特征向量的GSW同态加密方案。该方案的特点是密文由一个矩阵构成,可以进行自然的乘法加法运算,避免了密文维数膨胀问题,同时无需密钥转换技术和模数转换技术。GSW方案在功能上也得到了扩展,只需公钥就可以进行同态运算,所以基于该方案可以构造基于身份的和基于属性的同态加密方案。

由于自举是目前实现全同态加密的唯一路径同时也是造成目前全同态加密效率低下的主要原因。最近几年,许多密码学者开始致力于提高自举的效率。在2014年美密会(Crypto)上,AlperinSheriff和Peikert利用对称群和置换矩阵的性质构造了快速自举一个比特的同态加密方案,该技术为后来的方案提供了很大的启发。通过将该技术扩展到环上,Ducas和Micciancio在2015年欧密会(Eurocrypt)上将自举效率降低到1秒/次,给出了自举一个比特只需要0.69秒/次的结果。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190813A0I4C200?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券