全同态加密(FHE)体系概述(初学版)

这篇具有很好参考价值的文章主要介绍了全同态加密(FHE)体系概述(初学版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

同态加密定义

假设有这样一个场景,用户有一组私密数据,被加密存储在了第三方的云平台,现在,该用户想对这组数据进行某种处理,但是处理过程和结果都不想让第三方云平台看到。当然,用户可以选择将数据下载下来,处理后再加密上传,但是,假如这一组数据量很大,那么势必会花费很多的流量。这个时候,全同态加密就有了很大作用,用户不需要将数据下载下来处理后再上传,而是能够直接对云平台的数据进行处理,用户可以直接下载处理后的结果再进行解密就能得到想要的结果了。
全同态加密(FHE)体系概述(初学版)
可以这么理解:通过同态加密算法,用户可以与一个不可信的远程服务器(云端)进行某种安全代理计算(Secure Delegated Computation)。用户可以通过同态加密的技术来把自己敏感的隐私输入加密后托付给云端,然后云端可以在加密过后的数据上进行一定程度的计算,最后得到加密过后的用户想要的结果,并且返还给用户。最后用户就可以用解密密钥来打开得到的结果了。整个协议中,被代理方(云端)始终都无法看到任何和私密输入有关的有用信息。

两种特殊的同态性质:加法同态和乘法同态。
加法同态就是,如果密文累加起来,我们就可以获得把原文相加起来加密过后的新密文。而乘法同态则是,如果将一个乘法同态的算法生成的密文相乘起来,然后获得原文之间相乘之后的结果所对应的密文。

全同态加密(FHE)体系概述(初学版)

几个问题

为什么实现任意次加法和乘法就能实现全同态加密了?
答:电路模型里,传输的是高电平和低电平,也就是0和1。这就和模2的域上进行操作类似,在 Z 2 \mathbb{Z_2} Z2中,模2加法等于异或电路,模2乘法等于与电路,这两个电路能够实现任意电路,从而形成完备集。
为什么采用电路模型?
密码学中所有的方案都需要依赖于一个数学难题,其衡量标准就是计算复杂度,而电路模型就是一个计算复杂度的计算模型,可以用来衡量解决问题所需要的资源(时间、存储量)等。在电路计算模型下,通过含有多少门电路(gate)的数量和电路的深度等来衡量。
电路计算模型需要“接触”到所有输入的数据,不会有泄露信息。所以传统安全计算都是采用电路模型。

四大发展阶段

分别为

  1. 部分同态(Partially Homomorphic Encryption):可以运算的功能只能够要么由加法/线性组合,要么由乘法构成。例如RSA加密(乘法同态)、ElGamal加密(加法同态)
  2. 近似同态(Somewhat Homomorphic Encryption):拥有不完整的同态属性。如基于配对(Pairing)的循环群加密算法(加法同态+少量乘法同态)
  3. 有限级数全同态(Leveled Fully Homomorphic Encryption):可以同态运算任意形式的功能,但是功能所转换成的电路的复杂度不能超过上限,不然就会噪音太大丢失信息。(可以通过bootstrapping来控制噪音)
  4. 完全同态(Fully Homomorphic Encryption):
    可以计算任意复杂度的功能,并且可以完美将噪音控制在可控范围内。

历史回顾

2009年,在斯坦福读书的PhD Craig Gentry突然灵光一现,攻破了FHE算法的难关。在他的博士毕业论文中,他第一次给出了一个合理并且安全的全同态加密系统!这一系统基于理想格(ideal lattice)的假设。Gentry09提出来的全同态系统,我们往往称之为第一代全同态加密系统。

在Gentry的论文中,他还提到了一个至关重要的概念叫做Bootstrapping。Bootstrapping是一种对于密文的特殊处理技巧,处理过后竟然可以把一个噪音接近临界值的密文“重新刷新”成一个噪音很低的新密文。通过Bootstrapping,一个有限级数的系统的噪音可以永远不超过临界值,从而变成了全同态的系统。这样一来,我们就可以同态计算任意大小的 了。

在Gentry的重大突破之后,整个密码圈又一次陷入了疯狂,大家都开始争相基于Gentry提出的想法寻找更加高效率和全能的全同态体系。

在2011年的时候,两位大佬Brakerski和Vaikuntanathan提出了一个新的全同态加密体系,这一体系基于格(lattice)加密的另一种假设Learning With Errors(LWE)。在同一年,Brakerski,Gentry与Vaikuntanathan这三人一起把这个体系做完了,并且正式发表出来。他们发明的全同态系统简称为BGV系统。BGV系统是一个有限级数的同态加密系统,但是可以通过Bootstrapping的方式来变成全同态系统。BGV系统相比起Gentry09提出的系统,使用了更加实际一点的LWE假设。一般来说我们都把BGV系统称之为第二代全同态加密系统。

2013年,Gentry又卷土重来了。Gentry,Sahai和Waters三个大佬推出了新的GSW全同态加密系统。GSW系统和BGV相似,本身具有有限级数全同态性质,基于更加简单的LWE假设,并且通过Bootstrapping可以达到全同态。我们一般把GSW系统称为第三代全同态加密系统。

总结
第一代全同态加密方案,都是遵循 Gentry 复杂的构造方法。本质上这些方案都是在各种环的理想上,首先构建一个部分( somewhat) 同态加密方案( 即方案只能执行低次多项式计算) ,然后“压缩”解密电路( 依赖稀疏子集和问题的假设) ,从而执行自己的解密函数进行同态解密,达到控制密文噪声增长的目的,最终在循环安全的假设下获得全同态加密方案。尽管同态解密是实现全同态加密的基石,但是同态解密的效率很低

第二代全同态加密方案构造方法简单,基于 LWE( 环-LWE) 的假设,其安全性可以归约到一般格上的标准困难问题,打破了原有的 Gentry 构建全同态加密方案的框架。首先构建一个部分同态加密方案,密文计算后,用密钥交换技术控制密文向量的维数膨胀问题,然后使用模交换技术控制密文计算的噪声增长。通过上述方法不需要同态解密技术,就可获得层次型全同态加密方案,即方案可以执行多项式级深度的电路,可以满足绝大多数应用。要想获得“纯”的全同态加密方案,依然要依赖同态解密技术,然而同态解密技术效率低下,而且需要依赖循环安全的假设,实践中不予考虑。

第三代方案就是2013 年Gentry 等人提出的一个基于近似特征向量的全同态加密方案,不需要密钥交换技术和模交换技术就可以实现层次型全同态加密方案。该方案的安全性基于 LWE 问题,密文的计算就是矩阵的加法与乘法,因此是非常自然的一个全同态加密方案。

FHE系统正式定义

四个基本算法

一个完整的全同态加密系统具有四个基本算法:

  1. 密钥生成算法 K e y G e n KeyGen KeyGen,将会生成其他FHE算法将要使用的密钥。
    用于生成公钥和私钥,同时还需要生成另外一个公钥 E v k Evk Evk,该公钥用于密文计算,它的形式与使用的全同态加密算法直接相关。如,

    • 若是通过同态解密来获得全同态加密 ,此时的 E v k Evk Evk就是对密钥的每一位加密后生成的密文。典型代表就是Gentry的理想格方案以及后续的整数上方案。
    • 如果使用密钥交换和模交换来获得全同态的话, E v k Evk Evk就是 L − 1 L-1 L1个矩阵(第一次不需要),这个矩阵用于密钥交换,其中 L L L就是电路深度。每次密文计算后,都需要使用 E v k Evk Evk来将维数扩张的密文转变为正常的。

    此外,第三代方案,也就是近似特征向量的方案,它是不需要 E v k Evk Evk的,这也是它可以产生IBHE和ABHE的原因。

  2. 加密算法 E n c Enc Enc,可以加密用户的输入,输出密文。

  3. 解密算法 D e c Dec Dec,可以把密文还原为原来的明文。但这里的解密不仅要能解密密文,还能对计算后的密文进行解密。但密文计算会存在噪声,当噪声到达一定界限之后就无法正确解密了,所以同态加密的关键是对噪声的控制。

  4. 运算算法 E v a l Eval Eval,可以基于输入的密文,进行任意功能的运算,最后得到加密后的结果。这里的密文计算是在电路中的,电路是分层的,深度越深,层数越多,密文就能进行更多次的计算。注意,电路深度 d d d与密文计算次数 n n n的关系是 d = ⌈ log ⁡ 2 n ⌉ d=\lceil \log_2 n \rceil d=log2n,密文计算次数就是密文乘法的幂次。用乘法来衡量的原因是噪声增加更快。一般的运算算法会有三个参数,即公钥 E v k Evk Evk,计算函数 f f f,密文 C C C

三大属性

  1. 正确性(Correctness):一个FHE系统必须要是正确的。具体来说,也就是加密之后的密文可以被成功解密,并且运算输出的密文也可以成功解密回原文。
  2. 语义安全(Semantic Security):FHE系统输出的密文必须要难以分辨。具体来说,如果有一个网络窃听者看到了所有的密文,那么这个窃听者并不能分辨出哪个密文是对应哪个原文的。
  3. 简短性(Compactness):FHE的运算算法输出的密文的长度一定要独立于功能的所对应的电路的大小。这一属性代表就算运算功能复杂,输出的密文仍然在一个可以控制的长度范围内,确保了FHE系统的实用性。

主流研究方案

全同态加密发展到今天,已经出现了两个分支,一个分支是以计算算数电路为主(BFV, BGV, CKKS),基于RLWE的层次同态加密(LHE),一般来说支持多项式打包技术,可以一次性运算(加法乘法)多个数据,效率上较高,但LHE目前来说Bootstrapping开销比较大,一般来说只当作支持有限次数的运算的同态加密方法使用。

另一个则以计算布尔电路为主(FHEW, TFHE),基于高效自举(Bootstrapping)技术,对于多项式打包并不友好。
下面一些方案的特性:
FHEW、TFHE、GSW为布尔电路上的实现,其特性

  • 快速比较
  • 支持任意布尔电路
  • 快速 bootstrapping(噪声刷新过程,减少因密文计算而产生的噪音,降低失败可能性)

BGV、BFV是算数电路上的实现,其特性

  • 在整数向量上进行高效的SIMD计算(使用批处理)
  • 快速高精度整数算术
  • 快速向量的标量乘法
  • Leveled design(通常不使用bootstrapping)

CKKS则是17年才提出来的,其特性

  • 快速多项式近似计算
  • 相对快速的倒数和离散傅里叶变换
  • 深度近似计算,如逻辑回归学习
  • 在实数向量上进行高效的SIMD计算(使用批处理)
  • Leveled design(通常不使用bootstrapping)

前沿研究

2013年之后,密码圈基本上就百花齐放了。基于原来的三代全同态系统之上,出现了各种各样新的设计,致力于优化和加速BGV与GSW系统的运行效率。
当前的主流前沿研究

  • CKKS的安全性问题

  • FHEW类型与RLWE类型的同态加密结合

  • 快速Bootstrapping

  • 将RLWE类型的同态加密与MPC结合,通过MPC实现Bootstrapping

全同态加密(FHE)体系概述(初学版)

常用的算法库

全同态加密(FHE)体系概述(初学版)
全同态加密(FHE)体系概述(初学版)

参考

同态加密专栏的初心
初探全同态加密:FHE的定义与历史回顾(强推)
全同态加密知识体系整理(强推)
《全同态加密-从理论到实践》 陈智罡文章来源地址https://www.toymoban.com/news/detail-413074.html

到了这里,关于全同态加密(FHE)体系概述(初学版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 全同态加密:BFV

    参考文献: O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In H. N. Gabow and R. Fagin, editors, STOC , pages 84–93. ACM, 2005. Full version in J. ACM 56(6), 2009. V. Lyubashevsky, C. Peikert, and O. Regev. On Ideal Lattices and Learning with Errors over Rings. In Advances in Cryptology - EUROCRYPT 2010 , volume 611

    2023年04月08日
    浏览(36)
  • 隐私计算之全同态加密

    【引】走近任何一个领域,都会发现自己的渺小和微不足道,会越发地敬畏技术和未知,隐私计算也不例外。读了一点儿文章和paper,觉得还是ACM 上的这篇综述(https://queue.acm.org/detail.cfm?id=3561800)可以对全同态加密有一个概貌,从而了解其脉络方向,进而对隐私计算增加一点

    2024年02月07日
    浏览(36)
  • 隐私保护技术之同态加密(转)

    参考链接: https://blog.csdn.net/shn111/article/details/124594241 chapters 同态加密(Homomorphic Encryption)是指将原始数据经过同态加密后,对得到的密文进行特定的运算,然后将计算结果再进行同态解密后得到的明文等价于原始明文数据直接进行相同计算所得到的数据结果。 同态加密与一

    2024年02月12日
    浏览(48)
  • Paillier 加法同态加密算法详细介绍

    Paillier 同态加密算法是一种非对称加密算法,由 Pascal Paillier 在 1999 年提出。它的独特之处在于其同态特性,即能在加密数据上直接进行运算而无需解密。这使得它在数据隐私保护、安全多方计算等领域有着广泛的应用。 Paillier 加密算法主要包括三个部分:密钥生成、加密和

    2024年02月19日
    浏览(39)
  • 关于同态加密算法的原理与应用

    (一)同态加密算法的基本概念   (二)算法特点 (三)算法分类 (一)公钥加密算法 (二)同态加密算法的实现过程 (一)Paillier算法 图4.1 验证同态加正确性 图4.2 验证同态标量乘正确性 (二)RSA算法 (一)数据隐私保护 (二)云计算安全 (一)医疗数据共享与隐私

    2024年02月03日
    浏览(32)
  • TenSEAL库介绍:如何开始同态加密

    TensSEAL是一个python的第三方库,是一个方便的同态加密库。他并不是一个原生库,而是Microsoft SEAL(一个C++库)的python接口。实现了BFV和CKKS两种同态加密算法,可以直接对tensor进行加密,隐藏了很多具体细节,可以很容易上手编写同态加密的代码。是一款新手友好性的同态加

    2023年04月25日
    浏览(35)
  • 同态加密:重塑数据隐私与安全的未来

    同态加密技术是当今信息安全领域的一个重要研究方向,它允许在加密数据上直接进行计算,而无需将数据解密。这种加密方式对于保护数据隐私和增强云计算安全具有重要意义。在这篇文章中,我们将深入探讨同态加密的基本概念、技术特点、应用场景以及面临的挑战。

    2024年04月14日
    浏览(41)
  • 基于量子同态加密的安全多方凸包协议

    摘要 安全多方计算几何(SMCG)是安全多方计算的一个分支。该协议是为SMCG中安全的多方凸包计算而设计的。首先,提出了一种基于量子同态加密的安全双方值比较协议。由于量子同态加密的性质,该协议可以很好地保护量子电路执行过程中数据的安全性和各方之间的交互。结

    2024年02月15日
    浏览(43)
  • 基于量子同态的安全多方量子求和加密

    摘要 安全多方计算在经典密码学中一直扮演着重要的角色。量子同态加密(QHE)可以在不解密的情况下对加密数据进行计算。目前,大多数协议使用半诚实的第三方(TP)来保护参与者的秘密。我们使用量子同态加密方案代替TP来保护各方的隐私。在量子同态加密的基础上,提出了

    2024年02月13日
    浏览(42)
  • 同态加密:一个基于多方计算的CKKS方案

    这篇文章主要介绍LattiGo团队搞出来的一个多方同态加密的工作。个人觉得比较优雅,而且有库支持,方便把玩,所以记一下。 在攒毕业论文的时候整了这么个看上去很烂,但是(个人觉得)有一点意思的烂活,没心思写那么多的公式,各位dalao凑合看,欢迎轻喷。 实现了C

    2024年02月06日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包