原文标题：Fully Homomorphic Encryption Introduction and UseCases

原文作者：Nicolas Gama 和Sandra Guasch，SandBoxAQ

编译：Faust，极客web3

当提到加密时，人们最先联想到的应用程式场景通常是静态加密和传输中加密。前者将资料加密后储存在硬体设备中，如硬碟、行动设备，或是基于云端的伺服器，在这种模式下，只有被授权的人能查看或改写解密后的明文内容。而传输中加密，目的是让透过网路传输的资料只能被指定的人解读，即便资料透过公共路由器或通道来传输，中间人也无法私自解密出明文。

上述两个场景都依赖加密演算法，同时也会额外保证资料的完整性，即资料在传输过程中没有被中间人篡改，这称为认证加密：一旦资料被加密后，资料传输过程中的参与者无法私自解密出明文保密性，任何中间人都不能随意篡改原始的密文完整性/真实性。

至于某些多方协作的场景，需要对密文进行一些复杂的处理，这属于隐私保护技术的范畴，全同态加密FHE就是其中之一。我们可以举出一个线上投票的案例：假设在一次总统选举中，选民可以将自己的投票结果进行加密，然后提交给某个中间实体，该中间人将所有投票结果统一收集起来，算出每个总统候选人的得票数，最后只公布一个最终选举结果。

但不幸的是，当我们使用前面提到的认证加密方案时，负责统计投票结果的中间人要解密出所有人的投票资料明文，才能执行统计票数的任务，但这样就会让每个人的投票结果都暴露出来，无法保护隐私。理论上，我们可以对大家的投票数据进行混洗某些电子投票协议确实会这么做，但与纸质选票不同，传统密码学机制在保证数据完整性不被篡改的同时，很很难把加密后的选票资料与对应的选民身分分开。

在线上投票方案中，我们可以在负责计票的中间人周围添加一道硬体隔离墙，例如TEE(可信赖执行环境)。这种技术使得恶意攻击者很难与计票程式展开互动，但硬体层面的漏洞可能让解密密文的金钥从TEE中泄漏出来，而且与软体中包含的错误不同，硬体设计上的漏洞无法轻易修复。

综上，为了应对上述场景，我们可以引入全同态加密FHE技术。 FHE是一种特殊形式的加密方案，允许在不解密密文的情况下直接对密文进行函数计算，以获得该函数输出的加密后的结果，这样就可以保护隐私。

在FHE的场景下，函数 的数学构造是公开的，因此输入密文 输出结果() 的处理流程是公开信息，可以在云端执行，而不会泄露任何隐私。这里要注意， 和() 都是被加密过的密文，需要由金钥来解密，大多数时候两者对应的解密金钥是相同的。

上图展示了线上投票的三种加密/解密方案，其中E( ) 表示加密操作，而D( ) 表示解密操作；

左侧图中，一个受信任的中间人在公布投票结果前，会对各个投票资料进行混淆和解密，我们必须假设该中间人不会泄露隐私，且投票统计结果是正确无误的；

在中间的图中，使用了TEE，TEE能保证资料完整性和隐私保护；

而在最右边的图中，使用了同态加密技术：加密后的投票资料可以被公开加总求和，然后再解密得到结果，算出最终的投票数

FHE全同态加密是紧凑型加密方案，输出结果() 的密文资料大小，以及解密该结果所需的工作量，仅取决于输入资料 对应的原始明文，并不依赖所采用的计算过程，这与那些非紧凑型的加密系统截然不同，后者往往简单地把 与函数 的源码连接起来，然后让接收者自己解密 并输入到 中来完成计算任务。

在现实中，FHE外包模式通常被视为TEE等安全执行环境的替代方案，FHE的安全性是基于密码学演算法，而不依赖硬体等实体设备。因此，FHE完全不受被动侧通道攻击或云端伺服器被攻击的影响。想像一下，当某人需要外包出去一些运算任务，但资料非常敏感，他可能不愿意使用搭建在AWS上的虚拟机器VM，因为这类基于云端的伺服器背后往往存在更高级的控制人。他也可能对SGX或TEE这类东西犹豫不决，因为运行TEE的主机可以监控该计算任务在执行时产生的功耗或运行时间等，可能透过这些数据来推断出一些资讯。

然而，如果使用FHE，将计算任务外包出去的人就可以安心因为在FHE的系统中要破解私密信息，就必须破解其用到的密码学演算法，但这在目前几乎无法做到。

但是，虽然密码学演算法可以防止攻击者在不知道金钥的情况下破解 对应的明文，但另一方面，通用延展性则允许攻击者对输出结果() 进行修改，这相当于一种主动侧频道攻击：攻击者可以对执行加密演算法的硬体进行针对性的攻击，影响输出结果。这听起来似乎很可怕，但在FHE的设计中，这类恶意攻击可以透过在运算流程中制造冗余来进行规避。

简单总结的话，FHE通常会用到几组密钥，包含以下几部分：

解密金钥Decryption Key：这是整个FHE加密系统中的主金钥，所有其他类型的金钥都可以根据主金钥来汇出。解密金钥通常在用户本地生成，从不传输给外界，只有持有者本人能用它来解密FHE密文。这意味着密文即使在传输中被他人截获，也无法被解密，除非他们拥有解密金钥。

加密金钥Encryption Key：在FHE的公钥模式下，加密金钥是用来将明文转换为密文的金钥。当产生初始密文的人不是解密金钥/主金钥的持有者时，就会使用加密金钥来进行加密。这个密钥通常中等大小，由一些随机的零加密组成。由于FHE支援仿射函数affine functions，足以用于加密任何讯息。

在公钥加密模式中，加密金钥通常是公开的，任何人都可以用它来加密数据，但只有解密金钥的持有者才能针对性的解密。

计算金钥Evaluation Key：计算金钥是用来对密文 进行同态运算的专用金钥，使得FHE系统可以在不对密文 进行解密的情况下，对密文进行同态运算。计算金钥可以像公钥一样被公开发布，即使他人获知了计算金钥，也无法破解出密文 ，而只能对密文进行同态运算得到一个输出结果。

此外，当使用计算金钥进行运算时，密文的结构保持不变，对密文 进行同态运算得到的结果会被重新加密为新的密文，这确保了计算过程中的隐私性，即使计算过程是公开的也不会泄漏机密资料。

在上述几种金钥的持有者中，解密金钥/主金钥持有者是最敏感的，他要确保整个同态操作的执行链/流程有效无误，最终的密文是安全的，然后解密得到明文结果。如果在FHE的操作链条中引入恶意操作，解密金钥有可能会在解密时被泄漏。但幸运的是，同态操作可以公开进行并被任何人验证。

在本节中，我们将描述一些FHE中的常见场景/模式，并讨论每种模式的优缺点。

在此图中，左侧橘色的钥匙符号象征解密金钥及其持有者Alice。 FHE密文透过与解密金钥相同颜色的锁来表示。贡献私密资料的一方以圆柱体表示：

在这里，只有Alice贡献了私密数据。而在Bob这边，同态计算函数和计算密钥是公开的，计算方案由绿色框表示，以确定性的方式进行，每个人都可以在本地重跑计算过程，并检测Bob给出的输出结果是否有错误

上述外包模式也是FHE的第一个历史性应用案例，旨在将普通的云端运算转变为类似SGX和TEE的私密运算，但上述FHE演算法的安全性是基于密码学演算法，而非硬体层面的安全措施。在这种设定下，Alice拥有一些私密数据，但其运算能力有限，Bob拥有运算能力强大的云端伺服器，而Bob不贡献任何额外的私密数据。

Alice可以把计算任务() 的输入参数进行加密，得到密文 并将其传送给Bob，Bob随后以同态加密的方式运算出()的结果，并将加密后的结果送回给Alice。

监于目前的硬体设备性能，FHE外包模式的实际推广比较缓慢如果要执行的计算任务() 的复杂度是非线性的，对() 进行FHE运算的耗时将达到原始计算的100万倍，记忆体开销大概会提高1000倍。目前许多组织正在开发FHE专用硬体以降低其运算成本，例如Darpa DPRIVE专案或CryptoLight。

目前，FHE外包模式实际上主要用于PIR私有资讯检索场景，其中公共伺服器控制者Bob拥有一个大型的公共资料库，客户端Alice会发起读取资料的请求，但又不想让Bob知道自己想查关于哪些人的数据。这类PIR场景受益于同态加密操作的线性和紧凑性，同时计算成本可以保持在合理范围内。

下面这个表格总结了FHE外包模式的优缺点。

该图使用了与之前相同的颜色设定。这次，Bob在计算流程中贡献了一些私密资料。而Bob一方的计算流程不再是公开可验证的，用红色框表示，这种模式应仅限于通讯双方均为honestbutcurious的场景：

也就是说，在协议执行过程中，参与者如Bob会严格按照给定步骤进行计算，不会故意输出错误结果或破坏协议的执行。但Bob是好奇的，会尽可能从接触到的密文或其他中间数据中推断出敏感讯息，但这并不会篡改协议的执行过程

在FHE两方计算的模式中，唯一的差别在于Bob会在计算过程中贡献一些私密数据，也就是把自己的私密数据加入FHE计算过程中。在这种情况下，FHE是很好的两方计算解决方案，具有最小的通信复杂度，并且可以透过其机制设计提供强有力的保证：Bob不会窥探到Alice的私密数据，而Alice也不会窥探到Bob的私密资料。

该场景的一个潜在应用案例是密码学中的“百万富翁问题”，假设Alice和Bob是两位百万富翁，他们想知道谁更富有，但又不想让对方知道自己具体有多少资产。该问题的解决方案通常用于现实的电子商务应用场景。

聚合模式是对外包模式的改进，将来自多个参与者的资料以紧凑输出结果不会随着输入参数数量的增加而增长且公开可验证的方式进行聚合。典型的用例包括联邦学习和线上投票系统。

这种模式是对前面提到的双方计算模式的改进，其中伺服器会为多个拥有独立金钥的客户端提供FHE计算服务。 FHE可以用于私有AI模型运算服务，例如，客户端有私密数据，伺服器端有私有的AI模型或服务。伺服器拥有的私有AI模型是以明文形式储存在本地的，然后每个客户端都有自己的私密数据，希望放到AI模型中进行运算。最终每个客户端可以使用自己的金钥解析出自己所提交资料的运算结果。

同态加密如何确保外部计算结果是有效的？

在多方合作的场景中使用FHE是更容易的，因为每个参与者都有动机诚实地遵循协议规定。例如，FHE可以在位于两个不同国家但属于同一公司/组织内的两个法人实体之间进行加密计算并统计一些数据：诸如GDPR之类的法规允许你对外发布某些统计数据，但会禁止将所有个人资料集中储存在同一实体地点。

在这种情况下，使用FHE是可行的，所有参与者都有动机诚实地遵循协议规定。而在参与者并非彼此合作的场景中，确保计算任务已被正确执行的最简单方法，是引入冗余类似于多签/共识。例如，在前面提到的外包和聚合场景中，同态计算用到的函数公式是完全公开的，并且可以是确定性的，只要两个或更多独立实体得出完全相同的输出密文，那么整个计算过程就是正确的，结果也是可信的。冗余程度越高，最终结果的可信度就越高，但这需要在效率方面进行权衡。

此外，当承包计算任务的计算方透过对输入和输出密文进行数位签章来担保FHE结果有效时，每个人都可以重跑相同的FHE计算流程，并检查计算方给出的证明是否有效。任何计算方的欺骗行为都可以被检测出来并被惩罚，并可以与一个公开可验证的证书相关联，该证书会揭露欺骗行为和欺骗者我们称这种模型为强隐蔽安全模型。

至于完全同态签名，是另一种验证计算正确性的方法，无需第三方验证者，但通常需要更多的软硬体资源来参与。

FHE如何确保最终接收者只解密最终结果而非中间变数？

最简单的方法是确保解密金钥持有者无法存取FHE计算流程中产生的中间密文。在双方运算场景或客户端伺服器场景中，Alice对输入结果进行加密，Bob对密文进行计算并将加密的输出结果传回Alice，显然Alice只能解密最终结果，无法存取中间变数。

在基于云端伺服器的场景，例如线上投票系统中，许多参与者会在AWS等公共的云端伺服器上发送加密后的投票数据，这里会用到一种手段：解密金钥通常不会交给单个接收者，而是以秘密共享的方式分配给不同的人或机构类似MPC。在这种情况下，只有透过执行多方计算并让持有解密金钥的成员之间在线通信，才能对特定密文进行解密。如果其中某些人拒绝配合其他人，则无法进行解密。这样就可以透过设定相应的阈值来提高系统的整体安全性。

同态加密的建置模组

同态加密有三种：部分同态加密PHE、分级同态加密LHE和完全同态加密 FHE。部分同态加密只允许我们对某些计算任务进行同态加密例如求和、线性函数、双线性函数，而分级同态加密和完全同态加密可以支援任意的计算任务。

对于LHE来说，系统用到/产生的参数依赖于要执行的函数计算()，并随着该函数计算复杂性的增加而增长，这反过来导致密文和密钥的大小也跟着增加，会消耗更多的储存和通讯资源。而FHE方案允许我们在给定的一组参数下也就是给定的密钥和密文大小下，计算任何可以表示为二进位逻辑闸电路的函数。也就是说，与LHE不同，即使需要计算的任务变得越来越复杂，FHE方案涉及的参数以及金钥和密文也不会变大。

因此，FHE是唯一能保证同态计算的记忆体消耗和运行耗时都与原始明文/任务成正比的模式。但是，FHE有一个技术上的问题：随着计算的持续进行，密文中包含的杂讯垃圾资料会越来越多。为了避免噪音过多导致解密结果出错，FHE方案会定期执行一种代价较高的操作，称为自举bootstrapping，它可以将噪音减少到可控水平。日后我们将对此进行更多的介绍和科普，大家敬请期待！

原文连结：https//cryptographycaffesandboxaqcom/posts/fhe01/