Paillier同态加密算法

Paillier加密是一种公钥加密算法，基于复合剩余类的困难问题。其满足于加法同态，即密文相乘等于明文相加，即：

密钥生成

快速生成私钥

在密钥相同的情况下，可以快速生成密钥：

,为欧拉函数，即

加密

解密

加法同态

Paillier加密的两个密文消息相乘的结果解密后得到两个消息相加的结果。

对于两个密文 和

其中 和都是 中的元素，因此也属于 , 并具有相同的性质，所以 可以看作是 加密的密文， 的解密结果为 。

总结

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

https://en.wikipedia.org/wiki/Paillier_cryptosystem

https://blog.csdn.net/sinianluoye/article/details/82855059

http://www.cs.tau.ac.il/~fiat/crypt07/papers/Pai99pai.pdf

Paillier加密算法是Pascal Paillier在1999年发明的公钥加密算法，该算法基于复合剩余类的困难问题，是一种满足加法的同态加密算法。

作为一种半同态加密方案，Paillier方案在隐私计算的各个场景中有着广泛的应用。

比如在联邦学习中，对特征提供方提供的特征需要进行统计分析、处理，比如WOE分析、分箱处理等，都需要用到标签方持有的样本标签，而标签是需要重点保护的。应用Paillier算法，对标签进行加密，然后交由对方基于密文标签进行加和计算。

一开始有个疑惑，在常见的二分类场景，标签通常是0和1。即使加密，其密文也就是两个值，这样岂不是还是会泄露标签信息（起码会泄露正负样本的分布情况）？

这里就需要提到Paillier算法的随机化特性，算法在加密过程中，会选取一个符合条件的随机数参与加密，这样对于相同的明文，就产生了不同的密文。而在解密过程中，这个随机数会自动消除。

这里对该随机化特性背后的原理做简单理解性的描述。算法细节可参见Paillier论文及相关介绍。

费马小定理是数论中著名的一个定理：若 是一个整数， 是一个质数，那么 是 的倍数，可以表示为 ；若 不是 的倍数，该定理可以写成： 。

也就是说， 的 次方之后模 ，就变成了单位。在乘法运算中，相当于把 的效果给消解掉了。

Paillier算法中的随机化特性基本就是这样一个原理。

在Paillier算法中，使用了卡迈克尔函数 和卡迈克尔定理，对于正整数 ， ，其中 ，即 与 互质。算法中，会选择两个大素数 和 ，令 ，此时 ，即 和 的最小公倍数，该值会作为私钥。

费马小定理的扩展 - 费马欧拉定理和卡迈克尔定理可做对比：设 是一个正整数， ，则 ； 是欧拉函数，表示小于 的正整数中，和 互素的数的个数；当 是一个素数时，即为费马小定理。

近年来，随着大数据与人工智能的盛行，针对个人的个性化的推荐技术的不断发展，人们在享受便利的同时，也深深的感觉到无处不在的监控与监事，比如刚刚浏览了一个网站的商品，当去其他网站访问的时候就会推荐类似的产品；刚刚搜索了某件商品，在很多其他的场景中都会给你推荐。这种体验，谈不上不好，也谈不上多坏，但是如果仔细想想，就感觉自己的网上进行裸奔，个人隐私，一清二楚，毫无隐私可言，细思极恐。

不过随着广大用户对于个人隐私的重视程度不断加强，以及法律法规的不断完善，针对个人隐私的保护提出了更高的要求，什么样的数据可以采集、收集与使用，如何使用都是一个比较敏感的问题。十三届全国人大常委会第三十次会议表决通过了《 中华人民共和国个人信息保护法 》，并与2021年11月1日起施行。确立个人信息保护原则、规范处理活动保障权益、禁止“大数据杀熟”规范自动化决策、严格保护敏感个人信息、赋予个人充分权利等。新规施行后，违法的主体将 最高可处五千万以下或者上一年度营业额百分之五 以下的罚款。

鉴于上述情况，近年来隐私计算技术被不断的提及，源于其有优秀的数据保护作用，使得 “数据不出域、数据可用不可见、数据可算不可见” ，限定了数据的使用场景，防止了数据的泄露，而引起了业界的热捧。

隐私计算技术的演进历程如下图描述，以下是杨强教授在KDD 2021中国区的分享材料：

可以看到，隐私计算技术从1979年就开始了，最开始是安全多方计算、到差分隐私、到TEE， 再到最近火的不能再火的联邦学习 ，一系列的技术应运而生。那为啥现在隐私计算这么火呢。

注：隐私计算技术成熟度曲线

但是这些技术本身的安全加密都是采用共同的方法与策略，下面讲述下隐私计算的加密技术。

本文主要介绍同态加密，

众所周知，优秀的程序员需要 严谨的逻辑思维与具象能力 ，当然在材料的时候，可能需要适当的渲染。但是对于技术的理解，对技术的探索，严谨的逻辑与坚实的推理是非常重要的。所以，对于“数据加密”这个命题，需要进行一番探索。

如此三态合一，即可保障数据的全链路的生命周期安全 。

那么有没有办法解决数据计算的安全问题呢？答案就是 同态加密技术 。保障数据的运行态的安全，那么同态加密技术具体是如何实现，如何应用，并且有哪些限制呢？

什么是同态加密？ ，引用Gentry大佬的原话：

同态加密（Homomorphic Encryption, HE），指满足密文同态运算性质的加密算法，即数据经过同态加密之后，对密文进行某些特定的计算，得到的密文计算结果在进行对应的同态解密后的明文等同于对明文数据直接进行相同的计算， 实现数据的“可算不可见” 。同态加密的实现效果如图所示。

举个例子： 国内某家大型的三甲医院，由于历史悠久，并且医术精湛，历史遗留了大量的用户病例数据 。如今思考基于这些病例数据进行建模分析。但是由于数据量特别巨大，医院本身的IT资源有限，计算能力不足。

这个时候，云厂商找了过来。但是对于医院来说，这些数据本身是用户的隐私信息，并且也是医院的核心价值，所以尽管云厂商再三保证数据安全， 但是医院还是不能够放心的将数据上传到云厂商进行计算 。

正当这个事情推进不下去的时候，云厂商从密码行业花大价钱招来某个大牛，大牛提出一个方案，这样吧，我们现在有 这样一门技术，不需要传输明文数据，只需要传输密文就好，而且加密秘钥由医院自己保存，我们基于上传的密文数据做不解密的密态运算（ 并计算函数医院提供就好），这样数据不会泄露，云厂商对数据无感知，之后传回密文结果，医院自己解密就好 。医院一听非常高兴，那就这么办吧。

下面将核心流程描述下。

这里，大家可能有个问题，这个f应该是什么样的函数，有什么样的限制条件？HE方案是支持任意的数据处理方法f，还是说只支持满足一定条件的f呢？根据f的限制条件不同，HE方案实际上分为了两类：

Paillier加密算法是Pascal paillier[1]在1999年发明的概率公钥加密算法，该算法 基于复合剩余类的困难问题，是一种满足加法的同态加密算法 ，已经广泛应用在加密信号处理或第三方数据处理领域。

前面我们分析过 同态加密的核心流程 ，大家可以一起回忆一下。核心的函数包括：秘钥生成、明文加密、密文解密，下面我们来一步一步的分析，并且描述下，

秘钥的生成主要有如下的步骤，

下面介绍一个完整的同态运算，m由 组成，介绍下同态加密的是如何使用密文计算的。

---