隐私计算：半同态加密算法实践

对于零基础的隐私计算技术爱好者来说，同态加密（Homomorphic Encryption）算法有着最为神奇的特性：可在密文上进行计算且计算结果解密后所得的结果与明文计算一致。为了帮助大家更好地了解同态加密算法，本文将通过李伟荣老师的新作《深入浅出隐私计算：技术解析与应用实践》里的内容，来见证一下同态加密算法的神奇特性。首先介绍一下同态加密算法的概念和分类。

1. 同态加密算法的概念

同态加密算法是指满足密文同态运算性质的加密算法。而同态运算性质是指数据经过同态加密之后，对密文进行特定的计算，得到的密文计算结果再进行对应的同态解密后所得的结果等同于对明文数据直接进行相同的计算所得的结果，同态加密实现了数据的“可算不可见”。

举例来说，假设有一个加密函数Enc()，对明文A进行加密可得到密文，即，对明文B进行加密可得到密文，即。另外还有一个解密函数Dec()能够将密文解密成加密前的明文，即。对于一般的加密函数，如果，此时用Dec对进行解密的话，得到的结果一般是毫无意义的乱码。但是，如果Enc是个满足同态运算性质的加密函数，对使用Dec进行解密得到结果C将满足。同态加密的实现效果如图 1所示。

图 1 同态加密的实现效果示意图

2. 同态加密算法的分类

同态加密算法按其性质不同，一般可分为以下几类：

半同态加密（Partially Homomorphic Encryption，PHE）：支持对密文进行部分形式的计算，例如仅支持加法或者仅支持乘法。仅支持加法的称为加法同态加密算法，仅支持乘法的称为乘法同态加密算法；

类同态加密（Somewhat Homomorphic Encryption，SWHE）：也可称为有限次同态加密，只支持在密文上进行有限次数的加法和乘法 *** 作（ *** 作次数过多则会导致噪音过大而无法解密）；

全同态加密（Fully Homomorphic Encryption，FHE）：支持对密文进行任意形式的计算（同时支持加法 *** 作和乘法 *** 作，理论上只要支持加法和乘法 *** 作就能支持其他类型的 *** 作）。

根据上述分类，表 1列出了各类同态加密算法下的不同方案。

表 1 各类同态加密算法

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

半同态加密算法

典型的半同态加密特性包括乘法同态和加法同态。

（1）乘法同态加密算法

严格的乘法同态加密是指存在有效算法，使得或者成立，并且不泄露A或者B的信息。满足乘法同态特性的典型加密算法包括1977年提出的RSA公钥加密算法和1985年提出的ElGamal公钥加密算法等。

1）RSA算法。RSA算法是最为经典的公钥加密算法，在《深入浅出隐私计算：技术解析与应用实践》2.1节中已有介绍，其安全性基于大整数分解困难问题。在实际应用中，RSA算法可选择使用RSA_PKCS1_PADDING、RSA_PKCS1_OAEP_PADDING等填充模式，根据密钥长度（常用1024位或2048位）对明文分组进行填充。目前只有未采用填充模式的原始RSA算法才满足乘法同态特性，而由于原始RSA算法在加密过程中没有使用随机因子，相同密钥加密相同明文所得的结果也是相同的，因此，利用RSA的乘法同态性质实现同态加密运算存在安全弱点，攻击者可能通过选择明文攻击得到原始数据。接下来我们就根据之前介绍的RSA算法来检视一下RSA的乘法同态原理。

有了前面的基础，得出RSA的乘法同态原理就非常简单了，通过以下几步就可推理得出：

假设有两个明文数据m1和m2，经RSA加密后的密文数据为c1和c2；

易得；

根据加密计算公式和解密计算公式，很容易得出。

2）ElGamal算法。ElGamal算法是一种基于Diffie-Hellman离散对数困难问题的公钥密码算法，可实现公钥加密以及数字签名功能。ElGamal是一种随机化加密算法（相同密钥、相同明文两次加密所得密文不同），且满足乘法同态特性，是ISO同态加密国际标准中唯一指定的乘法同态加密算法。关于ElGamal算法的原理，本文就不作展开了。

（2）加法同态加密算法

严格的加法同态加密是指存在有效算法，使得或者成立，并且不泄露A或者B的信息。满足加法同态特性的典型加密算法有Paillier算法。

Paillier算法是一种基于合数剩余类问题的公钥加密算法，也是目前最为常用且最具实用性的加法同态加密算法。Paillier算法通过将复杂计算需求以一定方式转化为纯加法的形式来实现，此外，Paillier算法还可支持数乘同态，即支持密文与明文相乘。关于Paillier算法的原理这里就不作展开了。Paillier算法也是ISO同态加密国际标准中唯一指定的加法同态加密算法，目前Paillier算法已在众多具有同态加密需求的应用场景中实现了落地应用。

类同态加密算法

2005年由Boneh、Goh和Nissim提出的Boneh-Goh-Nissim方案是第一个同时支持加法同态和乘法同态的加密算法，它支持任意次加法 *** 作和一次乘法 *** 作。方案中的加法同态基于类似Paillier算法的思想，而一次乘法同态基于双线性映射的运算性质。虽然方案是双同态的（同时支持加法同态和乘法同态），但只能进行一次乘法 *** 作，属于类同态加密算法。

全同态加密算法

由于任何计算都可以通过加法和乘法门电路构造，所以加密算法只要同时满足乘法同态和加法同态特性，且运算 *** 作次数不受限制就称其满足全同态特性。

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

（1）Gentry方案（第一代全同态加密方案）

Gentry方案是一种基于电路模型的全同态加密算法，支持对每个比特进行加法和乘法同态运算。Gentry方案的基本思想是在类同态加密算法的基础上引入“Bootstrapping”方法控制运算过程中的噪音增长（类同态加密算法 *** 作次数过多会导致噪音过大而无法解密），这也是第一代全同态加密方案的主流模型。“Bootstrapping”方法通过将解密过程本身转化为同态运算电路，并生成新的公私钥对对原私钥和含有噪音的原密文进行加密，然后用原私钥的密文对原密文的密文进行解密过程的同态运算，即可得到不含噪音的新密文。也就是说为了避免多次运算使得噪音扩大，采用计算一次就消除一次噪音的方法，而消除噪音的方法还是使用的同态运算。但是，由于解密过程本身的运算十分复杂，运算过程中也会产生大量噪音，因此需要预留足够的噪音增长空间，需要对预先解密电路进行压缩简化，即将解密过程的一些 *** 作尽量提前到加密时完成。

（2）BGV/BFV方案（第二代全同态加密方案）

Gentry方案之后的第二代全同态加密方案通常基于LWE（Learning with errors，容错学习问题）/RLWE（Ring learning with errors，环上容错学习问题）假设，其安全性基于代数格上的困难问题，典型方案包括BGV方案和BFV方案等。BGV（Brakerski-Gentry-Vaikuntanathan）方案是目前主流的全同态加密算法中效率较高的方案。在BGV方案中，密文和密钥均以向量表示。BGV方案可采用模交换技术替代Gentry方案中的“Bootstrapping”过程，用于控制密文同态运算产生的噪声增长，而不需要通过复杂的解密电路实现。BFV（Brakerski/Fan-Vercauteren）方案是与BGV方案类似的另一种第二代全同态加密方案，同样可基于LWE和RLWE构造。BFV方案不需要通过模交换进行密文噪声控制。目前，最为主流的两个全同态加密开源库HElib和SEAL分别实现了BGV方案和BFV方案。

（3）GSW方案（第三代全同态加密方案）

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

（4）CKKS方案（第三代全同态加密方案）

CKKS（Cheon-Kim-Kim-Song）方案支持针对实数或复数的浮点数加法和乘法同态运算，但是得到的计算结果是近似值。因此它适用于不需要精确结果的场景，比如机器学习模型训练等。HElib和SEAL两个全同态加密开源库均支持了CKKS方案。

3. 半同态加密算法实践

Paillier加法同态

Paillier算法是满足加法同态特性的加密算法，且应用比较广泛。各编程语言中都比较容易找到实现该算法的函数库，因此，这里先小试一下这个加法同态加密算法。这里使用Python的Paillier算法实现库phe来演示。为了方便读者快速尝试，展示Dockerfile文件内容供读者参考进行环境搭建，如代码清单1所示。

代码清单 1 构建使用Paillier算法环境的docker镜像的代码

FROM ubuntu:20.04
RUN apt-get update && \
apt-get install -y \
python3-pip
RUN pip3 install phe

通过以下命令构建镜像并启动：

docker build -t paillier .
docker run -it --rm --name paillier paillier python3

这里尝试将两个数字a和b分别使用Paillier算法生成的公钥进行加密，然后在密文上执行加法 *** 作，最后使用私钥进行解密，相关代码以及运行结果如代码清单2所示。

代码清单 2 验证Paillier算法同态特性的代码及其运行结果

>>> from phe import paillier
>>> public_key, private_key = paillier.generate_paillier_keypair()
>>> a = 3.141592653
>>> b = 300
>>> encrypted_a = public_key.encrypt(a)
>>> encrypted_b = public_key.encrypt(b) * 2   # paillier支持数乘
>>> encrypted_c = encrypted_a + encrypted_b  # paillier支持加法同态
>>> print(private_key.decrypt(encrypted_c))
603.141592653

最后的输出结果完全符合我们对加法同态加密算法的预期。

RSA乘法同态

RSA算法是满足乘法同态特性的加密算法，各编程语言中也都比较容易找到实现该算法的函数库。这里使用Python的gmpy2库来演示。为了方便读者快速尝试，展示Dockerfile文件内容供读者参考进行环境搭建，如代码清单3所示。

代码清单3 构建使用RSA算法环境的docker镜像的代码

FROM ubuntu:20.04
RUN apt-get update && \
    apt-get install -y \
    python3-pip python3-gmpy2
RUN pip3 install pycryptodome

通过以下命令构建镜像并启动：

docker build -t rsa .
docker run -it --rm --name rsa rsa python3

这里尝试将两个数字a和b使用RSA算法生成的公钥加密，然后在密文上执行乘法 *** 作，最后使用私钥进行解密，相关代码以及运行结果如代码清单4所示。

代码清单 4 验证RSA算法同态特性的代码及其运行结果

>>> import gmpy2
>>> from Crypto.PublicKey import RSA
>>> RSA_BITS = 2048
>>> RSA_EXPONENT = 65537
>>> private_key = RSA.generate(bits=RSA_BITS, e=RSA_EXPONENT)
>>> public_key = private_key.publickey()
>>> a = 15
>>> b = 5
>>> encrypted_a = gmpy2.powmod(a, public_key.e, public_key.n)
>>> encrypted_b = gmpy2.powmod(b, public_key.e, public_key.n)
>>> encrypted_c = encrypted_a * encrypted_b  # RSA支持乘法同态
>>> decrypted = gmpy2.powmod(encrypted_c, private_key.d, private_key.n)
>>> print(decrypted)
75

最后的输出结果符合我们对乘法同态加密算法的预期。

隐私计算技术作为重大科技趋势正逐渐受到政府和企业的重视，更成为商业世界和资本竞逐的热门赛道。了解并掌握隐私计算技术，将成为立足大数据时代的必备技能。本文实践了半同态加密算法，如果您想要实践全同态加密算法、了解更多有关隐私计算技术的内容，快速了解并上手隐私计算，推荐您详细阅读李伟荣老师的新作《深入浅出隐私计算：技术解析与应用实践》。

关于作者：李伟荣，曾就职于微软、平安、港交所等大型公司，拥有十年以上金融项目架构和信息安全管理经验。精通信息安全、软件研发、项目管理，擅长大型软件架构开发，善于使用创新思维和创新方法解决问题。

曾在港交所深度参与隐私计算相关项目，致力于通过隐私计算技术解决大数据产品的确权、标准化、存证、溯源、定价、信用体系和利益分配等一系列问题，打造数据、金融资产交易的新型基础设施。

视频推荐👇

更多精彩回顾

书讯 | 5月书讯（上）|  元宇宙、因果推断、薛定谔方程...你关注的都在这

书讯 | 5月书讯（下）|设计致物系列+少儿编程好书推荐

书单 | 知乎高赞：有哪些你看了以后大呼过瘾的数据分析书？

干货 | Go语言精进之路：绞尽脑汁，帮你理解方法本质并选择正确的receiver类型

收藏 | 盘点知识图谱在 5 大智能领域的应用

上新 | 产品和运营双视角，9个维度全面讲解用户运营

赠书 | 【第105期】Python将提速2-5倍！你期待吗