目录

同态加密（Homomorphic Encryption）

研究进展

主流方法

1、半同态加密算法

2、全同态加密算法

发展现状

---

同态加密（Homomorphic Encryption）

概念： 密文状态下对加密消息进行计算的结果再进行同态解密后的明文结果与明文数据进行加密再解密的处理结果一致。

提出时间：1978年

同态加密分为半同态加密和全同态加密两种。如果一个密码学算法只满足乘法同态或者加法同态，我们就称其为半同态加密，英文称为PHE（Partially Homomorphic Encryption）。常见的乘法同态算法有RSA，ElGamal等，常见的加法同态算法有Pallier、Schorr协议等

如果一个密码学算法既满足乘法同态又满足加法同态，我们就称其为全同态加密，英文称为FHE（Fully Homomorphic Encryption, FHE）。全同态目前正在发展当中，进展最为火热的全同态算法有基于理想格的全同态加密算法等。

研究进展

1978年，Rivest、Adleman（“RSA”中的“R”和“A”）和Dertouzos提出了全同态加密的构想[1]，自此成为了密码学研究领域的一个公开难题。目前，同态加密算法主要分为半同态加密和全同态加密两大类。半同态加密主要包括以RSA算法[2]和ElGamal算法[3]为代表的乘法同态加密、以Paillier算法[4]为代表的加法同态加密以及以Boneh-Goh-Nissim方案[5]为代表的有限次数全同态加密；全同态加密算法主要包括以Gentry方案[6][7]为代表的第一代方案、以BGV方案[8]和BFV方案[9][10]为代表的第二代方案、以GSW方案[11]为代表的第三代方案以及支持浮点数近似计算的CKKS方案[12]等等。上述方案及其基本特性和应用情况总览如表1所示。

表1：各类同态加密算法

类型		算法	时间	说明	实际应用
半同态加密	乘法同态	RSA算法	1977	非随机化加密，具有乘法同态性的原始算法面临选择明文攻击	在非同态场景中应用广泛
		ElGamal算法	1985	随机化加密	DSS数字签名标准基于ElGamal数字签名算法的变体
	加法同态	Paillier算法	1999	应用最为成熟	联邦学习
	有限次数全同态	Boneh-Goh-Nissim方案	2005	仅支持1次乘法同态运算	/
全同态加密		Gentry方案	2009	第一代全同态加密，性能较差	/
		BGV方案	2012	第二代全同态加密，性能相对较好	IBM HElib开源库
		BFV方案	2012	第二代全同态加密，与BGV类似	微软SEAL开源库
		GSW方案	2013	第三代全同态加密，基于近似特征向量	TFHE开源库
		CKKS方案	2017	可实现浮点数近似计算，适合机器学习建模场景	HElib和SEAL

主流方法

1、半同态加密算法

满足有限运算同态性而不满足任意运算同态性的加密算法称为半同态加密。典型的半同态加密特性包括乘法同态、加法同态、有限次数全同态等。

（1）乘法同态加密算法

在实际应用中，密文乘法同态性的需求场景不多，因此乘法同态性通常偶然存在于已有的经典加密算法中。满足乘法同态特性的典型加密算法包括1977年提出的RSA公钥加密算法和1985年提出的ElGamal公钥加密算法等。

① RSA算法

RSA算法是最为经典的公钥加密算法，至今已有40余年的历史，其安全性基于大整数分解困难问题。在实际应用中，RSA算法可采用RSA_PKCS1_PADDING、RSA_PKCS1_OAEP_PADDING等填充模式，根据密钥长度（常用1024位或2048位）对明文分组进行填充，而只有不对明文进行填充的原始RSA算法才能满足乘法同态特性。由于原始的RSA不是随机化加密算法，即加密过程中没有使用随机因子，每次用相同密钥加密相同明文的结果是固定的。因此，利用RSA的乘法同态性实现同态加密运算会存在安全弱点，攻击者可能通过选择明文攻击得到原始数据。

② ElGamal算法

ElGamal算法是一种基于Diffie-Hellman离散对数困难问题的公钥密码算法，可实现公钥加密和数字签名功能，同时满足乘法同态特性。ElGamal是一种随机化加密算法，即使每次用相同密钥加密相同明文得到的密文结果也不相同，因此不存在与RSA算法类似的选择明文攻击问题，是ISO同态加密国际标准中唯一指定的乘法同态加密算法。

（2）加法同态加密算法

Paillier算法是1999年提出的一种基于合数剩余类问题的公钥加密算法，也是目前最为常用且最具实用性的加法同态加密算法，已在众多具有同态加密需求的应用场景中实现了落地应用，同时也是ISO同态加密国际标准中唯一指定的加法同态加密算法。此外，由于支持加法同态，所以Paillier算法还可支持数乘同态，即支持密文与明文相乘。

（3）有限全同态加密算法

2005年提出的Boneh-Goh-Nissim方案是一种基于双线性映射的公钥密码方案，支持任意次加法同态和一次乘法同态运算。方案中的加法同态基于类似Paillier算法的思想，而一次乘法同态基于双线性映射的运算性质。由于双线性映射运算会使得密文所在的群发生变化，因此仅能支持一次乘法同态运算，但仍支持对乘法后的密文进一步作加法同态运算。

2、全同态加密算法

满足任意运算同态性的加密算法称为全同态加密。由于任何计算都可以通过加法和乘法门电路构造，所以加密算法只要同时满足乘法同态和加法同态特性就称其满足全同态特性。

（1）主流算法

全同态加密算法的发展起源于2009年Gentry提出的方案，后续方案大多基于格代数结构构造。目前已在主流同态加密开源库中得到实现的全同态加密算法包括BGV方案、BFV方案、CKKS方案等。

① 第一代全同态加密方案——Gentry方案

Gentry方案是一种基于电路模型的全同态加密算法，支持对每个比特进行加法和乘法同态运算。Gentry方案的基本思想是构造支持有限次同态运算的同态加密算法并引入“Bootstrapping”方法控制运算过程中的噪音增长，这也是第一代全同态加密方案的主流模型。 “Bootstrapping”方法通过将解密过程本身转化为同态运算电路，并生成新的公私钥对对原私钥和含有噪音的原密文进行加密，然后用原私钥的密文对原密文的密文进行解密过程的同态运算，即可得到不含噪音的新密文。但是，由于解密过程本身的运算十分复杂，运算过程中也会产生大量噪音，为了给必要的同态运算需求至少预留足够进行一次乘法运算的噪音增长空间，需要对预先解密电路进行压缩简化，即将解密过程的一些操作尽量提前到加密时完成。

② 第二代全同态加密方案——BGV/BFV方案

Gentry方案之后的第二代全同态加密方案通常基于LWE/RLWE假设，其安全性基于代数格上的困难问题，典型方案包括BGV方案和BFV方案等。

BGV（Brakerski-Gentry-Vaikuntanathan）方案是目前主流的全同态加密算法中效率最高的方案。在BGV方案中，密文和密钥均以向量表示，而密文的乘积和对应的密钥乘积则为张量，因此密文乘法运算会造成密文维数的爆炸式增长，导致方案只能进行常数次的乘法运算。BGV方案采用密钥交换技术控制密文向量的维数膨胀，在进行密文计算后通过密钥交换将膨胀的密文维数恢复为原密文的维数。同时，BGV方案可采用模交换技术替代Gentry方案中的“Bootstrapping”过程，用于控制密文同态运算产生的噪声增长，而不需要通过复杂的解密电路实现。因此，在每次进行密文乘法运算后，首先需要通过密钥交换技术降低密文的维数，然后通过模交换技术降低密文的噪声，从而能够继续进行下一次计算。

BFV（Brakerski/Fan-Vercauteren）方案是与BGV方案类似的另一种第二代全同态加密方案，同样可基于LWE和RLWE构造。BFV方案不需要通过模交换进行密文噪声控制，但同样需要通过密钥交换解决密文乘法带来的密文维数膨胀问题。

目前，最为主流的两个全同态加密开源库HElib和SEAL分别实现了BGV方案和BFV方案。

③ 第三代全同态加密方案——GSW方案

GSW（Gentry-Sahai-Waters）方案是一种基于近似特征向量的全同态加密方案。该方案基于LWE并可推广至RLWE，但其的性能不如BGV方案等其他基于RLWE的方案。GSW方案的密文为矩阵的形式，而矩阵相乘并不会导致矩阵维数的改变，因此GSW方案解决了以往方案中密文向量相乘导致的密文维数膨胀问题，无需进行用于降低密文维数的密钥交换过程。

④ 浮点数全同态加密方案——CKKS方案

CKKS（Cheon-Kim-Kim-Song）方案是2017年提出的一种新方案，支持针对实数或复数的浮点数加法和乘法同态运算，得到的计算结果为近似值，适用于机器学习模型训练等不需要精确结果的场景。由于浮点数同态运算在特定场景的必要性，HElib和SEAL两个全同态加密开源库均支持了CKKS方案。

全同态工程实现开源工具：

1. HElib
2. SEAL

发展现状

目前，全同态加密算法仍处于以学术界研究为主的发展阶段，现有方案均存在计算和存储开销大等无法规避的性能问题，距离高效的工程应用还有着难以跨越的鸿沟，同时面临国际和国内相关标准的缺失。因此，在尝试同态加密落地应用时，可考虑利用Paillier加法同态加密算法等较为成熟且性能较好的半同态加密算法，解决只存在加法或数乘同态运算需求的应用场景，或通过将复杂计算需求转化为只存在加法或数乘运算的形式实现全同态场景的近似替代。

[1] Rivest R L, Adleman L, Dertouzos M L. On data banks and privacy homomorphisms[J]. Foundations of secure computation, 1978, 4(11): 169-180.

[2] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.

[3] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE transactions on information theory, 1985, 31(4): 469-472.

[4] Paillier P. Public-key cryptosystems based on composite degree residuosity classes[C]//International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 1999: 223-238.

[5] Boneh D, Goh E J, Nissim K. Evaluating 2-DNF formulas on ciphertexts[C]//Theory of Cryptography Conference. Springer, Berlin, Heidelberg, 2005: 325-341.

[6] Gentry C. Fully homomorphic encryption using ideal lattices[C]//Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009: 169-178.

[7] Gentry C, Halevi S. Implementing gentry’s fully-homomorphic encryption scheme[C]//Annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2011: 129-148.

[8] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory (TOCT), 2014, 6(3): 1-36.

[9] Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012: 868-886.

[10] Fan J, Vercauteren F. Somewhat Practical Fully Homomorphic Encryption[J]. IACR Cryptology ePrint Archive, 2012, 2012: 144.

[11] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2013: 75-92.

[12] Cheon J H, Kim A, Kim M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]//International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017: 409-437.

[13] Smart N P, Vercauteren F. Fully homomorphic SIMD operations[J]. Designs, codes and cryptography, 2014, 71(1): 57-81.

[14] Gentry C, Halevi S, Smart N P. Homomorphic evaluation of the AES circuit[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012: 850-867.