2.1 基于同态加密的安全机制

同态加密（HE）的概念最初由Rivest等人在1978年提出^[243]。同态加密提供了一种对加密数据进行处理的功能，是一种允许对密文进行计算操作并生成加密结果的加密技术。在密文上获得的计算结果被解密后与在明文上的计算结果相匹配，就如同对明文执行了一样的计算操作，该流程如图2-1所示。

作为一种不需要将密文解密就可以处理密文的方法，同态加密是目前联邦学习系统里最常用的隐私保护机制，例如横向联邦学习里基于同态加密的安全聚合方法^{[36，284，285]}、基于同态加密的纵向联邦学习^{[124，284，285]}、基于同态加密的联邦迁移学习^[188]。

同态加密机制能够在不对密文进行解密的情况下计算密文（这样计算方就不需要了解明文内容，只要获得密文就可以了），可以很好地保护敏感数据和信息，同时又可以执行计算操作（例如在加密状态下的加减乘除四则运算）。也就是说，其他人可以对加密数据进行处理，但是处理过程不会泄露任何原始内容。同时，拥有解密密钥的参与方解密处理过的数据后，得到的结果正好是处理相应的明文的结果。

2.1.1 同态加密的定义

同态加密方案H是一种通过对密文进行有效计算操作（计算方不需要获知解密密钥），从而允许在加密内容上进行特定代数运算的加密方案。一个同态加密方案H由一个四元组组成：

各元组表示的含义如下：

• KeyGen表示密钥生成函数。对于非对称同态加密，一个密钥生成元g被输入KeyGen，并输出一个密钥对{pk，sk}=KeyGen（g），其中pk表示用于对明文进行加密的公钥（public key），sk表示用于对密文进行解密的私钥（secret key）。对于对称同态加密，只生成一个密钥sk=KeyGen（g），用于加密和解密操作。

• Enc表示加密函数。对于非对称同态加密，一个加密函数以公钥pk和明文m作为输入，并产生一个密文c=Enc_pk（m）作为输出。对于对称同态加密，加密过程会使用公共密钥sk和明文m作为输入，并生成密文c=Enc_sk（m）。

• Dec表示解密函数。对于非对称和对称同态加密，私钥sk和密文c被用来作为计算相关明文m=Dec_sk（c）的输入。

• Eval表示评估函数。评估函数Eval将密文c和公共密钥pk（对于非对称同态加密）作为输入，并输出与明文对应的密文，用于验证加密算法的正确性。

我们用Enc_pk（•）表示使用公钥pk作为加密密钥的加密函数，用M表示明文空间，用C表示密文空间。一个安全密码系统若满足以下条件，则可被称为同态的（homomorphic）：

其中，⊙_M和⊙_C分别表示操作符⊙在明文空间M和密文空间C上的运算。式（2.2）表示，对于在明文空间M中的任意两个元素m₁和m₂，在对它们执行运算符⊙_M操作后，对得到的结果进行加密，其结果与m₁和m₂分别先进行加密再执行运算符⊙_C操作的结果一致；←符号表示左边项等于或可以直接由右边项计算出来，而不需要任何中间解密运算。

为了简化表述，用[[v]] 来表示对明文v的同态加密结果。我们来定义同态加密的两个基本操作，即加法同态加密和乘法同态加密（这里为了表述的方便，不区分运算符在明文空间和密文空间上的写法，例如明文加法运算+_M和密文加法运算+_C，我们统一使用+来表示，乘法运算符同理）。

定义2-1 加法同态运算 对于在明文空间M中的任意两个元素u和v，其加密结果分别为[[u]]和[[v]]，满足：

同理，我们定义乘法同态加密如下。

定义2-2 乘法同态运算 对于在明文空间M中的任意两个元素u和v，其加密结果分别为[[u]]和[[v]]，满足：

2.1.2 同态加密的分类

同态加密方法可以分为三类：部分同态加密（Partially Homomorphic Encryp-tion，PHE），些许同态加密（Somewhat Homomorphic Encryption，SHE），全同态加密（Fully Homomorphic Encryption，FHE）。不同的同态加密方案的计算复杂度区别很大。本节对不同种类的同态加密方案进行简要的介绍。感兴趣的读者可以查阅文献[39][30]获取不同种类的同态加密方案的更多内容。

1.部分同态加密（PHE）

对于部分同态加密（也称为半同态加密，PHE），（M，⊙_M）和（C，⊙_C）都属于一个群。以（C，⊙_C）为例，它满足下面四个性质。

• 封闭性：即对于任意的两个元素c₁，c₂∈C以及操作符⊙_C，满足（c₁ ⊙_C c₂）∈C。

• 结合律：即对于任意的三个元素c₁，c₂，c₃∈C以及操作符⊙_C，满足（c₁ ⊙_C c₂） ⊙_C c₃=c₁ ⊙_C（c₂ ⊙_C c₃）。

• 单位元：存在C中的一个元素e，使得对于所有C中的元素a，总有等式（e ⊙_C a）=（a ⊙_C e）=a成立。

• 逆元：对于每个C中的元素a，总存在C中的一个元素b，使得总有（a ⊙_C b）=（b ⊙_C a）=1成立。

操作符⊙_C能够无限次地用于密文。PHE是一种群同态（group homomorphism）技术。

加法同态。若在明文上的运算符⊙_M是加法运算符，且满足定义2-1，则该方案可被称为加法同态的（additively homomorphic）。Paillier在1999年提出了一种可证的安全加法同态加密系统^[224]，且对应的密文上的运算符⊙_C也是加法运算符。满足加法同态的加密算法一般也满足标量乘法同态，因为标量乘法运算可以转换为有限次的加法运算。

乘法同态。若在明文上的运算符⊙_M是乘法运算符，且满足定义2-2，则该方案被称为乘法同态的（multiplicative homomorphic）。文献[244][96]中分别提出了两种典型的乘法同态加密方案，即RSA加密算法和ElGamal加密算法，且对应的密文上的运算符⊙_C也是乘法运算符。

PHE的特点是，要求其加密操作符运算只需要满足加法同态或者乘法同态中的一个即可，不需要两个同时满足。

2.些许同态加密（SHE）

些许同态加密（SHE）是指经过同态加密后的密文数据，在其上执行的操作（如加法、乘法等）只能是有限的次数。一些文献中也定义SHE为只有包含有限数量的某些电路（如跳转程序^[139]，混淆电路^[289]）能够支持进行任意次数的运算，例如BV^[55]、BGN^[52]和IP^[139]。SHE方案为了安全性使用了噪声（noise）数据。密文上的每一次操作都会增加密文上的噪声量，而乘法操作是增长噪声量的主要技术手段。当噪声量超过一个上限值之后，解密操作就不能得出正确结果了。这就是为什么绝大多数的SHE方案会要求限制计算操作次数的原因，正是这些缺点导致它在实际应用中受到很多限制。

3.全同态加密（FHE）

全同态加密算法允许对密文进行无限次的加法和乘法运算操作。我们知道，要实现任意的函数计算，加法和乘法运算是仅需的操作，即任意一个函数都可以转化为只包含加法和乘法的形式。设A，B ∈F₂（即取值空间为0，1域），与非门（NAND gate）可以通过公式“1+A×B”计算得到。由于功能上的完备性，与非门能够用来构建任何逻辑门电路，因此，FHE能够计算任何函数功能。

但值得注意的是，虽然FHE从理论上能够解决任何函数的加密计算问题，但是要设计一个真正意义上的全同态加密算法是非常困难的，直到2009年才由斯坦福大学的博士生Craig Gentry提出了世界上第一个FHE算法^[106]。自此之后，全同态加密算法的设计成为密码学的热门研究方向。从整体上看，FHE算法的设计又可以进一步分为以下四种^[30]。

• Ideal Lattice-based FHE：基于理想格的全同态加密，也就是由Gentry设计的第一个全同态加密算法^[106]。

• Approximate-GCD based FHE：由Van Dijk等人提出的一种全同态加密方案，与Gentry的实现相似，该方案的安全性基于AGCD假设和稀疏子集和假设^[85]。

• （R）LWE-based FHE：与上面两种方案相比，该实现也被称为第二代全同态加密技术，典型的实现方案见于文献[193，54]等。与基于理想格的实现不同，该方案基于（R）LWE构造，通过引入再线性化技术与维数模约减技术实现了乘法的同态加密，效率比第一代的加密方案有了很大提升。

• 基于近似特征向量技术实现的FHE：前面的加密方案都需要借助计算密钥的辅助来实现全同态加密，但计算密钥的大小制约了全同态加密的性能。为此，在2013年，Gentry等人利用近似特征向量技术设计了无须计算密钥的全同态加密方案GSW^[105]，标志着第三代全同态加密方案的诞生。

当前，FHE的研究仍在高速发展，在高效的自举算法^{[34，53，89]}、多密钥全同态加密^[189]等领域都有许多人在进行研究。目前的FHE建立在些许同态加密（SHE）方法的基础上，并通过代价高昂的自助法（bootstrap）操作实现。由于自助法的代价高昂，FHE方案计算十分缓慢且在实践中往往并不比传统的安全多方计算方法更好，因此，许多研究人员目前正着眼于发现满足特定需求的更有效的SHE方案，而非去发掘FHE方案。