[转载] 同态加密：实现数据的“可算不可见”
同态加密是密码学领域自1978年以来的经典难题，也是实现数据隐私计算的关键技术，在云计算、区块链、隐私计算等领域均存在着广泛的应用需求和一些可行的应用方案。
本文首先介绍同态加密的基本概念、研究进展以及标准化进展，然后对主流的乘法/加法半同态加密算法和全同态加密算法及其工程实现情况进行概述，最后对同态加密在各领域的应用场景进行分析。
一、同态加密概述 1、基本概念 同态加密（Homomorphic Encryption, HE）是指满足密文同态运算性质的加密算法，即数据经过同态加密之后，对密文进行特定的计算，得到的密文计算结果在进行对应的同态解密后的明文等同于对明文数据直接进行相同的计算，实现数据的“可算不可见”。同态加密的实现效果如图1所示。
图1：同态加密原理
如果一种同态加密算法支持对密文进行任意形式的计算，则称其为全同态加密（Fully Homomorphic Encryption, FHE）；如果支持对密文进行部分形式的计算，例如仅支持加法、仅支持乘法或支持有限次加法和乘法，则称其为半同态加密或部分同态加密，英文简称为SWHE（Somewhat Homomorphic Encryption）或PHE（Partially Homomorphic Encryption）。一般而言，由于任意计算均可通过加法和乘法构造，若加密算法同时满足加法同态性和乘法同态性，则可称其满足全同态性。
目前，同态加密算法已在区块链、联邦学习等存在数据隐私计算需求的场景实现了落地应用。由于全同态加密仍处于方案探索阶段，现有算法存在运行效率低、密钥过大和密文爆炸等性能问题，在性能方面距离可行工程应用还存在一定的距离。因此，实际应用中的同态加密算法多选取半同态加密（如加法同态），用于在特定应用场景中实现有限的同态计算功能。
2、研究进展 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 3、标准化进展 （1）半同态加密标准化