同态加密为什么被称为密码学的圣杯？

同态加密是一种支持数据密态处理的密码学技术，可以广泛应用于云计算、医疗、金融等领域。

1.什么是同态加密？

全同态加密是一种加密技术，允许在不解密的前提下，对密文进行一些有意义的运算，使得解密后的结果与在明文上做 “相同计算” 得到的结果相同。

同态加密被称为密码学的圣杯，原因是同态加密算法功能十分强大，可以支持密文上的任意操作。目前的全同态加密算法效率比较低，只能支持一些简单的代数或逻辑计算，对一些复杂的计算逻辑支持较差。

2.理论到实现

2.1理论

全同态加密的思想早在1978年由Rivest，Adleman和Dertouzos（前两位就是RSA中的R和A）在他们的论文《On Data Banks and Privacy Homomorphisms》中提出。论文中提出了对密文进行一定的计算，可以间接地对原文进行操作的构想。需要指出的是，这离公钥密码学概念的提出，才仅过去两年的时间，由此也凸显了密码大牛的想象力和洞见力。后来，这种技术才被重新命名为同态加密。

传统的一些密码方案具有一些简单的同态性质，如教科书式的RSA算法（支持同态乘法），Paillier算法（支持同态加法）等。然而，这些算法离真正的全同态加密还有很大的距离。

2.2方案

经过30多年的发展，Gentry在其博士论文中提出了第一个真正意义上的全同态加密方案。该方案基于理想格，利用环结构上的同态性质设计。

全同态加密方案：
简单来说，假如I⊂R是环RR的一个理想，x∈R是环中的任意一个元素，则xI⊂I（吸收律），I+I=I（封闭性）。考虑商环R/I。对于任意的x,y∈R,x,y∈R,有

这些就是商环的运算性质，而性质恰好可以用来构造同态加密。不严格地讲，如果把运算想象成 “加密” 过程，上面实际上可以翻译为：

“x的密文” 与 “y的密文” 经过 “加法” 运算 ===> “x+y的密文”

“x的密文” 与 “y的密文” 经过 “乘法” 运算 ===》 “xy的密文”

这正是同态加密所要完成的功能！

然而需要指出的是，这种方案还是只能支持有限次的同态乘法和同态加法，离 “任意运算” 还是有不小的距离，所以仍然不是一个真正的全同态加密方案。因为上述由理想格设计出的方案本质上是基于噪声的，运算过程中噪声的规模会增长。当噪声增长到一定程度后，就不能从密文中将信息恢复出来了。Gentry 将这类可以支持一定程度上的同态加法和同态乘法的加密方案称为 “SomeWhat Homomorphic Encryption” （简称为 SHE 或 SWHE） 。

在 Gentry 之前仅有的类似方案是 05 年提出的 BGN 方案。其基于椭圆曲线上的双线性对构造，可以支持同态加法和一次同态乘法。因此，为了实现真正意义上的全同态加密，Gentry并没有停下前进的脚步。

Gentry 的另一个贡献，也是构造全同态加密的关键，那就是提出了 Bootstrapping 技术：通过同态执行解密电路（即始终保持在密文状态下执行解密电路），对密文进行刷新，将其中所含的噪声减少，使其能够再进行同态乘法和同态加法运算。通过重复执行 Bootstrapping， 便可以将 SWHE 方案转化为 FHE 方案。这就是 Gentry 提出的构造全同态加密的蓝图，也是目前唯一已知的构造全同态加密的方式。

这里有一个比较有意思的点。前面说了 ，SWHE 只能支持有限次的同态乘法操作，而 Bootstrapping 中需要同态执行解密电路，那么一个很显然的推论就是，解密电路中需要执行的乘法运算不能超过 SWHE 中能支持的同态乘法的界限，因为需要在 SWHE 中实现 Bootstrapping 操作。但是，通过分析发现，几乎所有的可用的加密方案，执行其解密电路所需的乘法操作总是超过了 SWHE 中能支持的同态乘法的界限。

这个看似不可逾越的鸿沟，好像给Gentry的同态加密构造蓝图打上了 “不可能” 的标签。但是 Gentry 通过引入一些新的计算假设，成功地将解密电路中所需的乘法操作拉到 SWHE 能支持的乘法操作范围内。从而成功地构造出了第一个全同态加密方案。

三、全同态加密发展历程

此后的第二代（BGV等方案为代表）、第三代（GSW方案为代表）全同态加密方案中，都有Gentry的贡献。可以毫不夸张地说是Gentry大神敲开了全同态体系的大门，并在随后的14年中不断地推动【同态加密算法】的发展。由于在同态加密领域的杰出工作，Gentry获得了2022年的哥德尔奖。有人预测，一旦同态加密获得大规模应用，Gentry很可能获得图灵奖。

花边新闻：Gentry在哈佛获得法学学位后，曾做过一段时间律师。令人津津乐道的跨界成功的教科书式案例，“出道即巅峰”的典型代表。

从Gentry提出第一个全同态加密方案开始，全同态加密算法在设计、分析、优化、实现、应用等研究方向上都取得了很大的进展。而全同态加密算法本身也经历了几轮的迭代升级。

发展历程	同态加密方案
第一代	主要是以 Gentry 基于理想格的方案和 van Dijk 等基于整数环上的 AGCD 困难性的 DGHV 方案为代表。Gentry 的方案涉及了较多的代数数论，方案有些复杂。而 DGHV 方案基于整数，方案简单，便于理解，但计算复杂度高，公钥尺寸非常大，很不实用
第二代	以 Brakerski 和 Vaikuntanathan 等人基于 LWE 问题等设计的 BV 方案为起点，代表性的有 BGV 方案和 BFV 方案。这一类方案主要以层次型（leveled FHE）结构为主，针对一些特定的场景，通过精心设计参数，可以避免在计算过程中引入耗时的 Bootstrapping 操作。此外，同一时间内，López-Alt 等人还基于 NTRU（一个格密码方案）提出了一种称为多密钥 FHE 的同态加密方案的概念，支持对不同密钥加密的密文进行计算。进一步提升了同态加密的功能性，扩展了其在实际中的使用范围
第三代	以 Gentry 等人（GSW）方案为开端。GSW 方案基于近似特征向量构造，设计了一种不同的方法来执行同态运算。该方案一个非常有意思的点是可以用来构造属性基（Attribute-Based）加密。现在一些高级的设计中，很多都以 GSW 方案为组件。与此同时，比较著名的代表方案还包括 FHEW 和 TFHE 等
第四代	以 CKKS 为主要代表。也有学者将其归为第二代，与 BGV、BFV 方案等并列。严格来讲，CKKS 并不是同态加密方案，而是近似同态加密方案。D(E(m1)∘E(m2))≈m1∙m2然而，由于其对浮点数的支持比较好。因此被广泛使用在隐私保护机器学习等场景中。此外，Li 等人还对 CKKS 算法给出了攻击和修复建议

噪声管理是目前全同态加密方案中的一个重要部分，很多方案论文中，考虑的关键点就是更好的噪声管理方式。实际上，也出现过一些无噪声的 “同态加密方案”，主要基于非交换代数设计，但是这类方案安全性很低，基本上每出现一个方案，很快就被攻破了。

引用

什么是同态加密？同态加密为什么能被称为密码学的圣杯？
什么是全同态加密（FHE）中的自举（Bootstrapping）？