1：什么是同态加密？

同态加密（HE，homomorphic encryption）是密码学里一种特殊的加密模式， 是指满足密文同态运算性质的加密算法，即数据经过同态加密之后，对密文进行特定的计算，得到的密文计算结果在进行对应的同态解密后的明文等同于对明文数据直接进行相同的计算，实现数据的“可算不可见”。同态加密的实现效果如图所示。

添加图片注释，不超过 140 字（可选）

同态加密使我们可以将加密后的密文发给任意的第三方进行计算，并且在计算前不需要解密，即：在密文上进行计算。 虽然同态加密的概念最早出现于 30 年前，但是第一个支持在密文上进行任意运算的全同态加密框架出现较晚，在 2009 年由 Craig Gentry 提出。

同态加密的数学定义为：

添加图片注释，不超过 140 字（可选）

其中 E 为加密算法，M 是所有可能信息的集合。如果加密算法 E 满足公式(1)，那么我们称 E 在★运算上符合同态加密的性质。目前的同态加密算法，主要支持两种运算上的同态：加法和乘法。

需要注意的是，以上公式(1)只是为了让我们更加清晰地理解同态加密的性质，实际中的同态加密算法可能会有一些不同。比如 Paillier 算法对加法同态，那么根据公式 (1)，其密文的求和应该等于求和后的密文，但实际情况是密文的乘积等于求和后的密文，所以我们一般只要求得到的密文结果和我们预期的计算相同，但是对密文上的计算不作具体要求（一般由加密算法决定）。

2：同态加密算法原理

同态加密算法分为全同态加密和半同态加密算法。

• 如果一种同态加密算法支持对密文进行任意形式的计算，则称其为全同态加密（Fully Homomorphic Encryption, FHE）；

• 如果支持对密文进行部分形式的计算，例如仅支持加法、仅支持乘法或支持有限次加法和乘法，则称其为半同态加密或部分同态加密，英文简称为SWHE（Somewhat Homomorphic Encryption）或PHE（Partially Homomorphic Encryption）。

一般而言，由于任意计算均可通过加法和乘法进行构造，若加密算法同时满足加法同态性和乘法同态性，则可称其满足全同态性。

目前，同态加密算法已在区块链、联邦学习等存在数据隐私计算需求的场景实现了落地应用。由于全同态加密仍处于方案探索阶段，现有算法存在运行效率低、密钥过大和密文爆炸等性能问题，在性能方面距离可行工程应用还存在一定的距离。

因此，实际应用中的同态加密算法多选取半同态加密（如加法同态），用于在特定应用场景中实现有限的同态计算功能。

3：标准化进展

1）半同态加密标准化

2019年5月，国际标准化组织ISO发布了同态加密标准（ISO/IEC 18033-6:2019）。该标准仅涉及半同态加密，具体包含两种较为成熟的半同态加密机制：ElGamal乘法同态加密和Paillier加法同态加密，并规定了参与实体的参数和密钥生成、数据加密、密文数据解密、密文数据同态运算等步骤的具体过程。

（2）全同态加密标准化

2017年7月，来自学术界、工业界和政界的相关领域研究人员组成了全同态加密标准化开放联盟HomomorphicEncryption.org，在微软研究院举办了首届全同态加密标准化研讨会，开始共同推进全同态加密标准草案的编写工作，并发布了全同态加密安全标准、API标准、应用标准三份白皮书。迄今为止， HomomorphicEncryption.org在三年内已举办五届全同态加密标准化会议，参与成员包括微软、三星SDS、英特尔、IBM、谷歌、万事达卡等企业，以及NIST、ITU等机构的代表和各大高校的学者。在标准化进展方面， HomomorphicEncryption.org已分别于2018年3月和11月发布和更新了全同态加密标准草案。

4:主流方法

常见的同态加密算法中，Paillier算法和Benaloh算法仅满足加法同态，RSA算法和ElGamal算法只满足乘法同态，而Gentry算法则是全同态的。

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算法

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.