什么是全同态加密(FHE)中的自举(Bootstrapping)?

原创
2023/12/06 10:50
阅读数 46

PrimiHub一款由密码学专家团队打造的开源隐私计算平台,专注于分享数据安全、密码学、联邦学习、同态加密等隐私计算领域的技术和内容。

全同态加密(Fully Homomorphic Encryption,FHE)中经常提到的一个术语是“自举”(Bootstrapping)。任何读过FHE初级材料的人都知道,自举是FHE方案中最复杂和计算密集的组成部分。然而,除了在领域内工作的密码学家之外,很少有人真正理解自举操作是什么,以及存在各种不同的自举方法,每种方法都有其自己的权衡考虑。本文将揭开自举概念的神秘面纱,纠正该领域常见的误解,并比较常见FHE方案中的自举方法。

全同态加密的概念最早由Rivest、Adleman和Dertouzos于1978年首次提出,并提出了以下问题:“是否可能具有一种带有大量操作的隐私同态,其安全性非常高?”

然而,这个问题在30年内都没有得到解决,直到2008年底,斯坦福大学的博士生克雷格·根特里(Craig Gentry)提出了第一个全同态加密方案。这不仅是密码学领域的重大突破,还是理论计算机科学领域的突破;而自举操作则是它的关键组成部分。

现在,让我们来回答三个基本问题来介绍自举操作:“它是什么?”,“为什么需要它?”以及“它是如何工作的?”

什么是自举操作?

首先,让我们看一下牛津词典对自举(bootstrap)的定义:“通过自己的靴带将自己拉起”。当我们说一个HE方案是可自举的时,这意味着它可以在至少进行一项额外操作的同时,同态地评估自己的解密过程。

如图所示,在经典意义上评估解密过程需要一个密文和一个秘密密钥作为输入,并确保输出明文。然而,在FHE中,我们处理的是解密过程的同态评估,即自举操作,它使用了一个加密的秘密密钥和一个密文来生成一个“等效”的密文,我们可以进一步进行计算。加密的秘密密钥,也称为自举密钥或刷新密钥,是由秘密密钥持有者作为公钥材料的一部分提供的。

为社么在FHE中使用自举操作?

所有常见的FHE方案都基于嘈杂的加密(噪音是保证新加密安全性的因素),在其中进行同态操作会增加噪音幅度并降低密文的质量,即计算预算。自举操作的主要用途是将一个用尽的密文转换为“等效”的刷新密文。用尽的密文包含高噪音,无法进一步操作,而刷新的密文可以支持进一步的同态操作。自举操作的次要目的是在自举操作期间对加密消息评估函数。在这种情况下,自举操作的输出密文加密了明文消息的函数,而不仅仅是消息本身,除了减小输入密文的噪音。这种形式的自举操作被称为功能性或可编程自举操作。

自举操作在FHE中的作用

在FHE中的作用是验证加密方案的正确性。常见的自举方法遵循Craig Gentry引入的相同框架,即对自己的解密过程进行同态计算。然而,FHE方案中的自举机制在不同的方案之间有所不同。在我们的白皮书中,我们描述了DM(FHEW)/ CGGI(TFHE),CKKS和BGV/BFV FHE方案中的自举机制,突出了各种方法之间的主要区别,并基于OpenFHE库的计时实验结果和同行评议科学文献报告评估了它们的性能。

基于这一分析,我们提供了一些实践指南。请注意,截至撰写本文前,OpenFHE已经包括了CKKS、DM和CGGI方案的自举实现。BFV/BGV的自举实现目前正在开发中,并将包含在未来的OpenFHE版本中。

实践指南

我们总结了我们对CGGI、CKKS和BGV方案的自举性能分析,有关性能结果的更详细分析可在白皮书中找到。之所以选择CGGI而不是DM,是因为对于均匀三元秘密分布的典型安全设置,CGGI比DM稍快。BGV和BFV自举的复杂性非常相似,因此只需考虑BGV即可。在使用OpenFHE中的CGGI和CKKS实现运行实验后,对于BGV,我们使用了报告的结果,也就是安全参数的选择与128位安全级别相对应。

建议和总结

经过详细的实验,对于不同的自举操作进行建议总结:

  • 当密文包含大量槽位(超过100个)和/或需要更高精度(超过3-8位)时,CKKS自举操作性能最佳。

  • 当槽位数量较少(最多100个)且需要低精度(最多3-8位)时,DM/CGGI自举操作更有效率。

  • DM/CGGI自举操作可以用于高效地评估小整数上的任意函数(使用查找表),而CKKS可以评估相对平滑的函数(使用多项式,如切比雪夫插值)。

  • BGV/BFV自举操作在槽位摊销时间上略快于DM/CGGI,但比CKKS慢。但是,BGV自举操作不支持本来就具有任意函数评估的功能。

  • 硬件加速可以应用于所有这些自举方法,可用的文献表明,对于所有这些方法,预期的加速速度应该相似。在更高层次上,我们可以使用以上的见解来制定关于每个FHE方案何时最有用的建议:

  • CKKS对于处理实数的应用效率最高,实际上通常以浮点数表示。因此,CKKS是许多实际机器学习问题的最佳选择,如逻辑回归训练、卷积神经网络推断和统计计算等。

  • DM和CGGI(也称为FHEW和TFHE)是需要在小整数上进行任意函数评估的应用的最佳选择。一个常见示例是评估布尔电路。另一个示例是某些模型的机器学习推断。

  • BGV和BFV通常用于处理大量小整数的应用。常见示例包括私人信息检索和私人集合交集,这些应用经常用于安全数据库查询应用程序。

许多应用可能需要处理大问题规模(CKKS效果好)和任意函数评估(CGGI效果好),例如,决策树训练。在这种情况下,从CKKS切换到CGGI方案,然后再切换回来可能是有益的。OpenFHE团队目前正在向库中添加这种功能,并将在2023年提供。

原文地址:Bootstrapping in Fully Homomorphic Encryption (FHE)
原文作者:Yuriy Polyakov and Ahmad Al Badawi
翻译 & 整理:开放隐私计算 & PrimiHub

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部