一 简介

1 背景

《数据安全法》已于9月1日起正式实施，两个月后《个人信息保护法》也将开始施行，意味着数据安全和隐私保护方面的监管将会在年内陆续到位。 在合规收紧大背景下，“数据孤岛”现象日渐明显。如何实现安全的数据流通，保护数据隐私并发挥数据的价值，支持多方的联合计算，是各大数据平台亟需解决的问题。而隐私计算技术旨在实现“数据可用不可见”的目标，具有广阔的应用前景。在联合国隐私增强计算技术手册[35]中，列出了同态加密（Homomorphic Encryption, HE）、安全多方计算（Secure Multiparty Computation, MPC）等5种隐私计算技术，其中HE提供了对加密数据进行处理的能力，完美符合隐私计算的计算模式，是当前学术研究的热点，受到了广泛的关注。

2 何为同态加密（HE）？

HE是一种特殊的加密方法，它允许直接对加密数据执行计算，如加法和乘法，而计算过程不会泄露原文的任何信息。计算的结果仍然是加密的，拥有密钥的用户对处理过的密文数据进行解密后，得到的正好是处理后原文的结果。

根据支持的计算类型和支持程度，同态加密可以分为以下三种类型：

• 半同态加密（Partially Homomorphic Encryption, PHE）：只支持加法或乘法中的一种运算。其中，只支持加法运算的又叫加法同态加密（Additive Homomorphic Encryption, AHE）；

• 部分同态加密（Somewhat Homomorphic Encryption, SWHE）：可同时支持加法和乘法运算，但支持的计算次数有限；

• 全同态加密（Fully Homomorphic Encryption, FHE）：支持任意次的加法和乘法运算。

在同态加密概念被Rivest在1978年首次提出[15]后，学术界出现了多个支持PHE的方案，如RSA、GM[13]、Elgamal[14]、Paillier[1]。此后，SWHE方案也相继问世，如BGN[16]。关于FHE如何实现，学术界在很长的时间都没有答案。直到2009年，Gentry[28]使用理想格构造了第一个FHE方案，轰动了整个学术界，并引发了学者们对于FHE方案构造的研究热潮。此后相继涌现出多个优秀的FHE方案，包括BFV[36]、BGV[37]、CKKS[38]等，以及多个优秀的开源算法库如SEAL[39]、HELib[40]等。

3 为何需要半同态加密（PHE）？

通用安全计算方法有所不足

隐私计算的应用场景非常广泛，除满足多方的通用计算（算数或布尔计算）功能外，还有如隐私集合求交(Private Set Intersection, PSI)[17]、隐私保护机器学习[4]、加密数据库查询[9]、门限签名[3]等等更加细分的应用。然而，在几种主要的通用计算技术路线中，每种方法各有各的效率/安全性缺陷。FHE在计算有限次乘法后需要较复杂的去除噪声的操作，经典的通用MPC协议通信开销较大，而TEE的安全性高度依赖于硬件厂商，无法提供密码学上严谨的安全性。在复杂的计算场景中，单独使用某种通用方法通常得不到一个可用的落地方案，这也激发了学者们研究对于特定场景的特定解法。一个可行的方案通常是根据具体场景来进行定制化的设计，通过组合、优化不同的技术组件来得到安全、高效的方案，精准满足该场景需求。

PHE登场：辅助多种隐私计算场景

图1.1. PHE的应用场景

由于通用安全计算方法的一些不足，以及在一些特定场景只需要使用一种HE运算（如加法）即可完成功能，PHE在隐私计算领域得到了大量使用，在多个开源库（如FATE[31]）和大量学术顶会（如S&P、NDSS等[4][7][18][19][11][21]）的方案中都有它的身影。PHE的高效、支持无限次加法或乘法的特点，使其成为隐私计算的重要基本组件，可辅助完成多种隐私计算功能：

1）隐私保护数据聚合

由于加法PHE可以在密文上直接执行加和操作，不泄露明文，在到多方协作的统计场景中，可完成安全的统计求和的功能。

• 在联邦学习中，不同参与方训练出的模型参数可由一个第三方进行统一聚合。使用加法PHE，可以在明文数据不出域、且不泄露参数的情况下，完成对模型参数的更新，此方法已应用在实际应用（如FATE[31]）和多个顶会工作中（如SIGMOD[4]、KDD[7]、ATC[18]）；

• 在在线广告投放的场景中，广告主（如商家）在广告平台（如媒体）投放在线广告，并希望计算广告点击的转化收益。然而，广告点击数据集和购买数据集分散在广告主和广告平台两方。使用PHE加密结合隐私集合求和（Private Intersection-Sum-with-Cardinality, PIS-C)协议[19]可以在保护双方隐私数据的前提下，计算出广告的转化率。 该方案已被Google落地应用[20]；

• 在加密数据库SQL查询场景，在数据库不可信的情况下，可以通过部署协议和代理来保护请求者的查询隐私。其中，PHE可以用来完成安全数据求和和均值的查询[9]。

2）乘法三元组生成

通用安全计算根据计算电路的不同可分为算数计算和布尔计算，对于算数计算来说，其中的难点是如何做乘法。而使用预生成的乘法三元组来辅助乘法运算的方法可以大大降低乘法的在线开销，是目前最为流行的方法。PHE是用于计算乘法三元组的重要工具[2][12]，已在多个顶会方案（如NDSS[11]、S&P[21]）和实际产品（如Sharemind[2]）中得到应用，对于加速安全计算具有重要意义。

3）构造特定的隐私保护协议

在机器学习预测分类场景中，若拥有模型的一方不可信（如外部厂商），在数据方输入样本进行预测分类时，可能需要保护样本数据的隐私。PHE作为building block可以构造出隐私保护比较协议和argmax协议，并可以此进一步构造出隐私保护朴素贝叶斯分类器和超平面决策分类器[24]。此外，用PHE还可构造出不经意选择（Oblivious Selection）协议，来支持隐私保护决策树分类器[25]。

4）门限签名

传统签名方式要求签名时从存储介质（如磁盘）中拉取完整私钥到内存，存在泄露风险（如被木马、病毒窃取，侧信道攻击等）。 使用门限签名可以有效规避此类风险，让多方协作完成签名过程，并确保私钥没有在任何一方被恢复。特定的PHE算法可以用于实现门限签名[3]，相关方案已在集团密钥管理系统落地[22]。

5）同态秘密分享

同态秘密分享是一种前沿的安全计算技术，可以用来大幅降低安全计算的交互通信量。具有特定代数结构的PHE方案经过特殊设计，可以用来实现同态秘密分享[10]，具有广阔的应用前景。

6）隐私集合求交

使用PHE结合多项式的方法可构造出PSI协议[17]。

4 Paillier：最著名的半同态加密方案

Paillier是一个支持加法同态的公钥密码系统 [1]，由Paillier在1999年的欧密会（EUROCRYPT）上首次提出。此后，在PKC'01中提出了Paillier方案的简化版本[26][8]，是当前Paillier方案的最优方案。在众多PHE方案中，Paillier方案由于效率较高、安全性证明完备的特点，在各大顶会和实际应用中被广泛使用，是隐私计算场景中最常用的PHE实例化方案之一。

其他的支持加法同态的密码系统还有DGK [5]、OU [6]和基于格密码的方案[12]等。其中，DGK方案的密文空间相比Paillier更小，加解密效率更高，但由于算法的正确性和安全性在学术界没有得到广泛研究和验证，且我们的实验表明算法的加解密部分存在缺陷，不推荐在工业界代码中使用。OU和基于格的加法同态计算效率更高，也是PHE不错的候选项。其中OU的在方案中的使用频率相对较低，而基于格的方案密文大小较大，在一些特定场景有自身的优势。

数据技术及产品部-数据安全生产平台团队对Paillier加密方案的原理和高效实现方法开展了研究，利用多种优化方法实现了目前最优的Paillier加解密效率，可助力基于Paillier加密的上层协议在集团真实业务场景中落地。

二 Paillier方案原理

1 加法同态加密定义

在描述具体方案之前，我们先定义加法PHE。首先列举方案具有的所有算法。

• KeyGen()：密钥生成算法。用于产生加密数据的公钥PK（Public Key）和私钥SK（Secret Key），以及一些公开常数PP（Public Parameter）；

• Encrypt()：加密算法。使用PK对用户数据Data进行加密，得到密文CT（Ciphertext）；

• Decrypt()：解密算法。用于解密得到数据原文PT（Plaintext）。

HE除了加解密以外，还具有在密文上进行处理的能力，所以还应拥有“处理”算法。对于加法PHE，支持的算法有同态加以及同态标量乘（标量乘法可看作多次加法）。

• Add()：同态加算法。输入两个CT进行同态加运算。

• ScalaMul()：同态标量乘算法。输入一个CT和一个标量PT，计算CT的标量乘结果。

2 Paillier方案描述

原版Paillier方案于论文[1]中提出，下面对方案进行描述：

密钥生成

1 . 随机选择两个大素数p, q满足 g c d ( p q , ( p − 1 ) ( q − 1 ) ) = 1，且满足p,q长度相等

2 . 计算n = pq以及 = lcm(p-1,q-1)，这里lcm表示最小公倍数，|n|为n的比特长度

3 . 随机选择整数

4 . 定义L函数： ，计算

公钥： (n，g)，私钥：( , )

加密

1 . 输入明文消息m， 满足

2 . 选择随机数r满足

3 . 计算密文

解密

1 . 输入密文c，满足

2 . 计算明文消息

同态加

1. 对于密文 和 ，计算

同态标量乘

1. 对于密文 和标量a，计算

3 正确性和安全性

加解密正确性

同态加正确性

同态标量乘正确性

安全性

Paillier方案满足加密方案的标准安全定义：语义安全，即在选择明文攻击下的密文的不可区分性（IND-CPA）。直观地说，就是密文不会泄露明文中的任意信息。方案安全性可以归约到判定性合数剩余假设（Decisional Composite Residuosity Assumption, DCRA），即给定一个合数n和整数z，判定z是否在n^2下是否是n次剩余是困难的。这个假设经过了几十年的充分研究，到目前为止还没有多项式时间的算法可以攻破，所以Paillier加密方案的安全性被认为相当可靠。

详细的安全性证明可以参见论文，这里不再赘述[1][8]。

三 高效实现

1 优化参数选择

根据论文 [23]中的描述，在不影响算法正确性的前提下，为了简化运算，算法在密钥生成阶段可以取g=n+1。此后，加密过程中的计算g^m的部分可进行如下简化：

对于g^m=(n+1)^m， 根据二项定理[43]，由于：

前m-1项均是n^2的倍数，在模n^2下消去，故这里模指数运算简化为了1次模乘，加速了加密过程：

2 使用Paillier-DJN优化方案

论文 [8]（Paillier-DJN，以下简称DJN）描述了Paillier密码系统的一般性结构， 其中包括了Paillier密码系统的一些优化，为当前Paillier的最优方案。优化后算法的不同点如下：

• 密钥生成阶段不同

在密钥生成阶段，生成RSA素数要求，且。随机选择，计算。计算。私钥为，公钥为。

• 加密过程优化

计算密文的过程为，其中计算r^n的部分可被优化：对于r^n，用计算来替换原算法的r^n，可以实现相同的安全性。这里的随机数，相比原算法的，比特长度减小了一半，计算时更加快速。

图3.1 优化1和优化2

3 使用中国剩余定理（CRT）加速模指数

定理介绍

中国剩余定理[44]（Chinese Remainder Theorm, CRT）又称孙子定理，源于中国古代数学著作《孙子算经》。它描述了两个代数空间的同构性，即一个代数空间可以被分解为若干个互相正交的子空间，且原来的空间和分解后的空间保持一一映射，就像是同一个空间的两种表现形式。特别地，当n=pq，p、q互素时，存在代数同构性质：，使得在下的运算可转化为在的运算。在转换到上后，计算效率更高，从而该性质可用于让我们在模下加速模指数运算。

使用CRT计算模指数过程举例

具体举例，当n=pq，p、q互素时，计算模指数时，有以下两种计算方法：1. 直接计算法：计算 。这是在 上的运算，计算量较大。

2 . 使用CRT优化：使用CRT，先把 映射到 上去做计算，再把结果聚合回 上，得到最终结果。

• （映射到 ）计算 在 上的映射 。其中 ；根据欧拉定理[45]， , 这里的 为p的欧拉函数。

• （映射到 ）计算 在 上的映射 ，过程同上。

• （聚合回）使用CRT通项公式，计算

其中，根据裴蜀定理[46]，由于p、q互素，故

代入上式，有：

以上过程，先映射到小空间计算，再聚合回大空间，得到最终结果，让我们以较少的计算量计算出了。

CRT应用到Paillier加解密过程

在Paillier密码系统中，加密和解密的主要开销为在下做的模指数运算。在拥有私钥（n的分解p、q）的情况下，可以使用CRT将下的模指数运算转化到和上，从而提升加解密效率。

图3.2 使用CRT进行优化

若使用CRT进行计算加速，计算方必需要知道模数n^2的分解(p^2、q^2)。而(p^2、q^2)为私钥的部分，故我们可以直接将CRT应用到解密过程。 而对于加密过程来说，我们根据加密者是否拥有私钥，将加密算法设计为两类，分别为公钥加密算法Enc1(pk,m)和私钥加密算法Enc2(pk,sk,m)。若加密消息的一方只拥有公钥，则调用标准的公钥加密算法Enc1(pk,m)进行加密；若加密的一方同时拥有公钥和私钥，则可以调用私钥加密算法Enc2(pk,sk,m)，输入私钥的(p^2、q^2)来使用CRT加速加密过程。

我们对使用CRT后的优化效果进行测试。由于DJN方案严格优于Paillier原版方案，我们只将CRT应用到DJN。经测试，使用CRT后，DJN的私钥加密和解密性能提升约90%，具体数据见表4.2。

4 预计算

• 对于fixed-base情况，进行指数预计算来加速模乘

由于在确定密钥参数后，Paillier的每次加密都是在固定的底数（fixed-base）下做模指数运算（如在DJN方案中，每次加密均需要在底数上计算模指数）。对于这种情况，可以使用预计算的方法，提前算好一些指数运算结果并保存，使得在线加解密的模指数计算转化为模乘运算。

1 . 首先考虑按指数的单个bit拆分的情况。将指数按bit拆分为0/1序列，对于指数的每一个bit，预计算底数^指数的相应结果（如计算 ），并存入列表中。当进行加密解密的模指数运算时，测试指数的每一bit是否为1，使用预计算的列表计算结果。经过此优化，1次模指数转化为|n|/2次（平均）模乘。

在Java上，若使用上述按单个bit展开的方法，|n|/2次（|n|=3072）耗时比1次模指数要长，没有达到优化计算的效果。

2 . 为了进一步提高效率，可考虑将多个bit设为一个窗口（window），按窗口大小w来展开多个指数bit，并进行预计算。经过这样的优化，1次模指数转化为 次（平均）模乘，同时会产生 的预计算List开销。当w设置得越大，在线的模指数计算越快，同时需要预先生成并传输、存储的预计算List也越大。 具体的性能提升结果见表4.2，预计算List的大小随w的变化见表4.3。窗口大小w需要根据场景灵活选择，来获得最佳的性能/通信平衡。> 在存储空间有限时，可以采用更轻量级的预计算方法来减小存储开销[41][42]，在c/c++下预计可以达到一定加速效果。

这里的模乘我们使用Java中的Biginteger.multiply()，模指数使用Biginteger.modpow()。

图3.3 预计算

• 在加解密时会重复用到的变量，都在密钥生成过程提前计算并保存，以避免加解密时的重复运算。

5 使用JNI技术

Java执行复杂计算的效率通常不及C/C++。以密码学计算中常见的模指数为例，在设置模数n、底数b和指数e均为2048bits的情况下，在Java中执行1000次Biginteger.modPow()需要耗时3000ms，而在C++下使用GMP库的mpz_powm()跑只需1800ms，相比Java，性能提升了约60%。 我们希望可以把Paillier中耗时的加解密计算通过调用C++执行来提速。

Java 本地接口（Java Native Interface, JNI）是Java语言的本地编程接口，它提供了若干的API，使得Java可以与其他语言（如C/C++）程序进行互相调用，来实现Java不便实现的功能或难以达到的效率。

有了JNI这座桥梁，我们就可以将复杂耗时的计算模块用效率更高的C/C++实现，通过JNI来实现Java对算法的高效调用。我们对原版Paillier方案和优化后的Djn算法都开发了JNI调用的版本，用C++编写核心算法，并通过Java包装类使用JNI对C++库进行调用。应用JNI后，加解密过程的效率获得了显著提升，具体数据见表4.2。> 使用JNI调用C++库提升效率的代价是会丧失程序的可移植性（C/C++是非跨平台语言），故是否使用JNI要根据场景灵活选择。

图3.4 JNI

6 打包

为了确保安全强度，Paillier方案中的明文空间大小为固定的n（如3072bits），而待加密的明文可能属于较小的空间（如16bits）。在这种情况下，如果按照正常的加密方式，将1个明文加密为1个密文，则明文空间会存在很高的冗余（等同于先在16bits明文的高位填充0，编码到3072bits，再进行加密），在加密时间和空间上效率都很低。

为了避免冗余，在明文较短且定长的情况下，我们充分利用明文空间，将多个明文打包为1个进行加解密 [2][4]。具体过程如下：

• 打包

根据Paillier方案中n的比特长度|n|和单个明文的比特长度 ，计算明文空间可容纳的最大明文数量 。 以k个明文为一组，需要对 进行拼接，得到 。

• 加密

调用Paillier加密算法，对m进行加密，得到c。

• 解密

调用Paillier解密算法，对c进行解密，得到m。

• 拆包

以k个明文为一组，拆分m得到 。

相比原来的1次只加密1个明文，使用打包优化后，密文大小和加解密中的模指数时间消耗降低为原来的1/k。该优化的效果取决于明文长度，本文中暂不作实验测试。

图3.5 打包

四 测试结果

1 测试条件

表4.1. 测试条件

2 性能

表4.2：Paillier密钥生成、加密、解密性能在不同优化下的表现

图4.1 Paillier半同态加密优化效果

从表4.2和图4.1中可以看到，DJN优化方案加解密的效率相比原版方案提升了大约100%。当使用CRT优化后，私钥加密和解密的效率继续提升约90%。当CRT和Fixed-base预计算同时使用时，随着窗口大小w的增大，公钥加密的效率进一步提升；使用JNI调用C同样可以大大降低计算开销，相比纯Java提升幅度达60%以上，提升幅度在结合使用Fixed-base优化时尤为明显。特别地，当同时使用DJN+CRT+Fixed-base（w=8）+JNI优化时，公/私钥加密的时间消耗从原版方案的37ms，分别下降到约2ms/1ms，实现了质的飞跃。随着不同优化的运用，密钥生成（预计算）的时间会随着变长，但该部分为一次性消耗，相比大量数据的加解密时间可以忽略不计。

3 预计算List大小

使用Fixed-base预计算优化需要提前生成预计算list，list占用的空间大小与窗口大小w的大小见表4.3。

表4.3：Paillier预计算List的大小与窗口大小w的关系

五 与现有开源库的对比

表5.1. 本工作与一些现有开源库的对比

六 PHE的应用：一个实际的例子

1 业务场景

在商业广告的在线投放场景中，广告主（如商家）在广告平台（如媒体平台）上投放广告曝光产品，而用户点击广告后可能会产生购买行为，实现广告转化变现。为了评估广告在该平台投放的实际收益，需要统计在点击了广告的用户中，共产生了多少消费金额。然而，“点击广告”的用户数据集在广告平台侧，而“发生购买”的用户数据集在广告主侧。 由于法律合规和商业机密因素的影响，双方可能不愿意分享原文数据进行合作。

2 隐私诉求

1. 不能泄露双方交集的个体用户信息，否则不满足法律规定的“最小够用”原则，故“先进行PSI再求和”的方法不可取。
2. 不能泄露交易金额给广告平台方。

3 解法：Private Intersection-Sum-with-Cardinality （PIS-C）

PIS-C协议[19]于在EuroS&P'20会议上被提出，其核心思想是通过"Tag, Shuffle and Aggregate"过程，将PSI协议和PHE转化为PIS-C协议，使得广告主最终得到交集value的聚合结果，确保没有额外数据泄露（具体过程参见原论文）。

图6.1. 基于DDH的PIS-C协议流程

PHE在该协议中扮演着核心作用。协议中的“隐私保护求和”功能依赖于广告主将自己的交易数据用PHE加密发送给广告平台， 使得广告平台在看不到原始数据的前提下，完成对交集中数据金额的聚合。该方案已被Google落地[20]。除了广告场景外，还可以用于多种“行为数据和效益数据分离”的商业场景，在应用上有着很大的想象空间。