摘要

随着云计算和人工智能的衰亡，如何平安无效地利用数据，对持有大量数字资产的企业来说至关重要。同态加密，是解决云计算和分布式机器学习中数据安全问题的关键技术，也是隐衷计算中，横跨多方平安计算，联邦学习和可信执行环境多个技术分支的热门钻研方向。

本文对经典同态加密算法Pailier算法及其相干技术进行介绍，重点剖析了Paillier的实现原理和性能优化计划，同时对基于公钥的加密算法中的热门算法进行了横向比照。最初介绍了Paillier算法的一些理论利用。

【关键词】：同态加密，多方平安计算，联邦学习，隐衷计算

1 背景常识

1.1 同态加密

同态加密（Homomorphic Encryption，HE）[1]是将数据加密后，对加密数据进行运算解决，之后对数据进行解密，解密后果等同于数据未进行加密，并进行同样的运算解决。同态加密的概念最后在1978年，由Ron Rivest，Leonard Adleman和Michael L. Dertouzos独特提出，旨在解决在不接触数据的前提下，对数据进行加工解决的问题。

目前，同态加密反对的运算次要为加法运算和乘法运算。依照其反对的运算水平，同态秘密分为半同态加密（Partially Homomorphic Encryption, PHE）和全同态加密（Fully Homomorphic Encryption, FHE）。半同态加密在数据加密后只持加法运算或乘法运算中的一种，依据其反对的运算的不同，又称为加法同态加密或乘法同态加密。半同态加密因为机制绝对简略，绝对于全同态加密技术，领有着更好的性能。全同态加密对加密后的数据反对任意次数的加法和乘法运算。

1.2 复合残余类问题

如果存在一个数

那么合乎公式z ≡ yn (mod n2)的数z，称为y的模n2的n阶残余。复合残余类问题（decisional composite residuosity assumption , DCRA)，指的是给定一个合数n和整数z，很难确定模n2的n阶残余数z是否存在。

1.3 中国残余定理

中国残余定理（Chinese Remainder Theorem, CRT），又称为孙子定理，源于《孙子算经》，是数论中的一个对于一元线性同余方程组的定理，阐明了一元线性同余方程组有解的准则以及求解办法。

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
翻译为数学语言为：

其通用方程为：

中国残余定理的解法流程为：

2 Paillier算法原理

2.1 Paillier简介

在Paillier算法呈现之前，基于公钥加密的算法次要有两个分支：

  • 以RSA为代表的，基于大数因数分解难题的公钥加密算法
  • 以ElGama为代表的，基于大数离散对数难题的公钥加密算法

Paillier加密算法，由Pascal Paillier于1999年发表，给出了公钥加密算法的一个新的分支畛域。Paillier基于复合残余类难题，满足加法同态和数乘同态，具备十分高效的运行时性能。

2.2 一个典型的利用场景

图1 传统联邦学习

同态加密算法使得密文数据，在没有额定数据泄露的状况下，能够在第三方平台进行进一步加工解决。随着大规模云计算的衰亡，尤其是波及到敏感数据的云计算，同态加密算法将是其中至关重要的技术根底。咱们以一个典型的联邦学习的例子为切入点，看看Paillier算法的原理和在实践中利用的问题。

假如Alice和Bob想独特训练一个网络模型，Alice和Bob各自持有一部分训练数据，并且他们不想把本人的数据泄露给对方。那么在训练期间，Alice和Bob须要交互各自训练的梯度数据，并依据单方的梯度数据，独特计算一个对单方都适合的梯度值，用来执行联结梯度降落过程。

2019年，Ligeng Zhu等人发表的“Deep Leakage from Gradients”论文中给出了一种算法，能够从几次迭代的梯度数据中，推断出训练的数据，标签，模型等一系列隐衷信息。这使得在分布式机器学习中，通过传输梯度数据来进联结模型训练变得不再平安。那么如果在梯度数据传输的过程中，传输的是加密后的梯度数据，并且这些加密数据能够进行二次计算，那么便能够躲避梯度数据传输过程带来的平安危险。

2.3 Paillier算法

2.3.1 密钥生成

相似于RSA算法，Paillier也领有公钥和私钥对。

在上述过程中，Alice总计生成了6个数字：

p = 11q = 19n = 209 = 90g = 147 = 153

Alice将 n 和g 封装成公钥public-key = (n, g)
将和封装成私钥:private-key = (, )

2.3.2 加密

假如Bob须要加密明文m， 0 <= m < n. 且Bob收到了Alice发送过去的公钥（n, g）

  • Bob抉择一个随机数r,满足0 < r < n
  • Bob计算加密后的密文 c = gm.rn mod n2
m = 8r = 3n_square = pow(n, 2) # n_square = 43681c = gmpy2.mod(pow(g, m)*pow(r, n), n_square) # c = 32948

2.3.3 解密

假如c是Bob发送过去的密文，且$c\\in {\\mathbb Z}_{{n^{{2}}}}^{{*}}$
Alice计算明文
m = L(c mod n2) * mod n

c = 32948m  = gmpy2.mod(L(gmpy2.mod(pow(c, lam), n_square), n) * mu, n) # m =  8

正确性证实

为了证实解密操作的正确性，咱们把加密的公式代入：

依据卡米切尔定理（Carmichael’s function）有：

持续化简得：

因为g ∈ Zn2, n + 1 ∈ Zn2, 那么肯定存在惟一一对（a, b）使得：
② g mod n2 = (1 + na) * bn mod n2 = 1 + a__n mod n2

把上述公式带入，高阶多项式按二项式定理开展，得：
DEC(c) = L( (1 + na) bn mod n2 ) mod n = L(1 + a_m_*n mod n2) * mod n

这里咱们再看下的取值，同样依照公式②开展，得
= L(g mod n2)-1 mod n = L(1 + a__n mod n2)-1 mod n

最初把函数L开展，得：
DEC(c) = (a_m_ mod n2) (a mod n2)-1 mod n = m

2.3.4 同态加

假如Alice计算的梯度数据为m1, Bob计算的梯度数据为m2，Bob须要计算单方梯度数据的均值（m1 + m2）/ 2, 作为分布式梯度降落的梯度数据。

同态加的原理是利用了幂函数的ax1 * ax2 = ax1+x1的个性。对于Alice持有的数据m1的密文c1和Bob持有数据m2的密文c2,Bob应用如下公式计算同态加法运算：

c = c1 * c2 mod n2

Alice应用私钥计算DEC(c) = m1 + m2

正确性证实

为了证实同态加的正确性, 咱们把加密的公式代入同态加运算：
c = ((gm1rn mod n2) * (gm2rn mod n2)) mod n2 = (gm1rngm2rn) mod n2 = (gm1 + m2r2n) mod n2 = ENC(m1 + m2)
解密c等价于：
DEC(c) = DEC(ENC(m1 + m2)) = m1 + m2

对于密文和明文相加的同态运算，咱们当然能够先对明文加密，之后再对两个密文进行同态加运算的形式来计算。不过从下面的公式能够看出，扰动数据rn中的r是一个任意值。那么咱们能够把计算密文c1和明文m2的和的计算转换为：
c1 + m2 = (gm1_rn mod n2 * gm2 mod n2) mod n2 = gm1+k_rn mod n2 = E(m1+m2)

这样少了一次计算rn的运算量，晋升了明文和密文相加运算的效率。

2.3.5 同态数乘

Paillier算法目前只反对明文和密文相乘的计算形式，不反对密文和密文相乘。

同态数乘的原理是利用了幂函数的axk = akx的个性。
Bob应用Alice对明文m1加密后的密文c1和明文k，计算
c = c1k mod n2
Alice应用私钥计算DEC(c) = k*m1

正确性证实
为了证实同态数乘的正确性, 咱们把加密的公式代入同态数乘运算：
c = c1k mod n2 = (gm1*rn mod n2)k mod n2 = gk*m1 r1n mod n2 = E(km1)
解密c等价于：
DEC(c) = DEC(ENC(k m1)) = k m1

2.4 算法优化

2.4.1 参数g优化

在原始Paillier计划中，g的取值只需满足

。Ivan和Mads在论文中给出了应用g = n + 1 的优化计划[3]，并且证实了应用此计划后，能够和原始Paillier算法放弃雷同的安全性。
在应用g = n + 1后，实现密钥生成和加密过程的性能晋升。

密钥生成：
把g = n + 1带入的生成公式,得
= L(g mod n2)-1 mod n = L((n + 1)} mod n2)}-1 mod n = L((1 + * n) mod n2)-1 mod n = -1 mod n
生成能够间接取 对 n的模反元素。

加密：
把g = n+1，带入加密公式，得c = gmrn mod n2 = (n + 1)mrn mod n2 = (n m + 1) rn mod n2

加密过程把计算g的m次幂的操作，变成了简略的乘法操作：
c = (n*m+1)*rn mod n2

2.4.2 高阶幂运算优化

在优化了原始Paillier加密过程的gm幂运算后，加密操作中最耗性能的操作就是对rn高阶幂函数的计算。2010年，Ivan Damgard, Mads Jurik 和 Jesper Buus Nielsen给出了优化rn这个高阶幂函数计算的计划[5]，并证实了应用此计划后，能够和原始Paillier算法放弃雷同的安全性。

密钥生成：
要求p ≡ q ≡ 3 (mod 4), 且gcd(p – 1, q – 1) = 2.
= (p - 1)(q - 1) / 2
抉择一个随机数x，且$x ∈Zn*, h = -x2 mod n。
抉择一个自然数s，对于原版Paillier, 相当于为s设定了s = 1
hs = hns mod ns + 1
优化后，新的公钥为public-key=(n, hs)

加密：
生成一个随机数，

, 其中k是密钥长度
优化后应用如下公式进行加密操作：
c = (n * m + 1)hs mod ns + 1
因为取值 << n, 使得加密计算过程中，计算hs的性能，优于计算rn的性能.

2.4.3 应用中国残余定理

用中国残余定理，能够把诸如 ax mod n模式的高阶幂函数取模操作，合成为低阶幂函数对n的因子取模的操作。

因为合成操作，须要应用到生成私钥的要害数据p和q，所以应用中国残余定理对高阶幂函数取模操作的优化，只能利用在应用私钥的解密操作中。

解密：
应用中国残余定理优化解密算法的步骤如下：

  1. 定义合成因子p和q对应的函数 Lp(x) = (x-1) / p, Lq(x) = (x - 1) / q
  2. 计算hp ≡ (p - 1) q (mod p), hq ≡ (q - 1) p (mod q)
  3. 计算mp = Lp(cp - 1 mod p2) hp mod p, mq = Lq(cq - 1 mod q2) hq mod q
  4. 计算m = CRT(m\_p, m\_q) mod n, m 即为应用中国残余定理优化的解密后的明文

2.4.4 性能优化比照

算法应用Python代码实现，密钥长度取2048bit, s参数取1，取模之前的幂运算均采纳模幂办法优化。其中前面的优化均是在后面优化的根底上进行的优化。

图2 paillier性能优化比照

从表1和图2中能够看到，通过参数g优化和幂运算优化后，加密运算的效率较之原版计划晋升了约3.26倍。通过应用中国残余定理优化后，解密运算的效率较之原版计划晋升了约3.32倍。在密钥生成上，应用了幂运算优化后，密钥生成的工夫减少了约42%。思考到密钥生成运算的次数，通常远小于加解密运算的次数，相比之下密钥生成的性能损失通常能够忽略不计。

2.5 来自多方计算的平安问题

在下面Alice和Bob应用Paillier同态加密来进行分布式梯度值计算时，Alice持有私钥，对Bob加密后的梯度数据，进行同态运算，并生成最终分布式梯度计算的梯度值。这里有一个问题，在这个场景下，尽管Alice没有取得Bob的间接或加密后的梯度数据，但Alice晓得最终的梯度值，这使得Alice能够依据差分后果，猜测出Bob本次计算的梯度数据，从而产生平安问题。

在多方平安计算中，因为同态计算的算法，不肯定可能提供平安保障，使得咱们必须应答计算过程中可能呈现的平安问题。对于Alice和Bob的计算分布式梯度值的场景，能够依据以后的学习率引入适合的扰动数据来躲避差分隐衷问题，或者参加计算的多方至多是三方。

3 性能扩大

在原版Paillier中，明文m的定义域是[0, n)。在Alice和Bob的进行的分布式机器学习场景中，须要可能对浮点和正数进行加密运算。在理论利用中，如果只能加密正整数，那么Paillier的利用场景会受到较大的限度。实际上，计算机的布尔电路只能对0和1的二进制数据进行计算，无论是浮点数还是正数，甚至是整数的计算，都是通过特定的计算规定来实现的，咱们能够参照这些规定，实现Paiiler算法对浮点数和正数的反对。

3.1 浮点数反对

IEEE 754规范中，单精度浮点示意采纳1位符号，8位阶码和23位分数。

对于浮点数，咱们能够将所有参加计算的数值，编码为更小的单位，在计算实现后再解码。比方浮点数3.14，能够事后乘以100， 即3.14 = 314 * 10-2。之后计算过程中，整数局部和指数局部别离运算。

在计算机中，浮点数以符号位（Sign），阶码（Exponent）和分数（Fraction）三局部联结来标识，底数(Base)固定为2。咱们仍旧以3.14为例，3.14 = 0.785 * 22 = [11.0010001]2。理论应用中，为了示意更大的范畴，分数局部的取值范畴要求 1 <= fraction < 2, 这样保障了分数局部的首位总是为1，这样小数局部能够暗藏首位的1。为了使阶码能够应用正数，浮点标准规定了指数局部应用一个偏移值（Bias），这样浮点数的值的计算形式为：
x = -1sign (1 + Fraction) 2(Exponent - Bias)

在裁减Paillier算法定义域到浮点数时，浮点数各个局部的计算，均需程序来实现。这里咱们参照浮点数的表示法，且不应用暗藏位，假如给定Bias=8，那么3.14就能够编码为（E = 2，F=200(0.785 * 28)）。咱们再把整数2，通过同样的编码，失去(E=2, F=128)

在Paillier计算中，因为阶码雷同，3.14 + 2 = （E = 2, F = 328）。最终执行解码，失去328 2-8} 22 = 5.125。计算结果存在较大的精度损失，理论利用中，咱们能够通过增大Bias的值，来晋升计算结果的精度。

对于同态数乘来说，因为不须要阶码对齐，那么只需对F值做数乘，即可失去正确的后果。同样对于3.14， 乘以3后失去（E = 2， F = 600），之后解码，失去600 2-8 22 = 9.375。同样因为示例中Bias取值问题，计算结果呈现了较大的误差。

3.2 正数反对

在计算机中，正数是以补码的形式标识的。整数和正数相加，是通过溢出来使得计算结果合乎预期值，如果咱们把正数的字节裁减，那么会失去一个原有字节空间的最大值和对应正数之和的负数，在此基础上应用此负数进行四则运算，之后再缩容到原来的字节空间，那么失去的仍旧是正确的后果。

相似的，为了使Paillier可能反对正数的计算，咱们能够给正数m\_1减少一个周期值n, 来把正数m\_1转换为正整数。那么对于同态加运算来说，计算结果c=ENC(m1 + m2 + n)。
此时同态加计算的后果为：

  • 当 m1 + m2 >= 0时，DEC(c) = m1 + m2
  • 当-n <= m1 + m2 < 0时， DEC(c) = m1 + m2 + n
  • 当m1 + m2 < -n 时，计算结果不正确

同态数乘的计算结果为：

  • 当k m1 >= 0 , 时DEC(c) = k m1
  • 当-n <= k m1 < 0时，DEC(c) = k m1 + n
  • 当k * m1 < -n时，计算结果不正确

为了对立以上呈现的各种场景，咱们能够做如下限定：

  1. 操作数在参加同态计算前对n取模，用来对立负数能够直接参与计算，正数则须要补n再进行计算的问题。
  2. 设定操作数的最大值MAX\_VALUE，比方32位整型的最大值。并使得n的取值大于3 * MAX\_VALUE，这样使得对于非法的m1和m2，不存在m1+ m2 < -n的场景，且m1 + m1 < 0时，计算结果总是大于MAX_VALUE。

至此，咱们能够应用对立的规定，来解决正数参加同态运算时的各种场景。

4 次要公钥加密算法比照

Paillier，RSA和ELGamal算法均为典型的基于公钥的加密算法，咱们从性能指标和性能指标两个方向，来比照这些加密算法的区别和分割。

4.1 性能指标比照

4.2 性能指标比照

对4096-bit大小的明文进行加密：

对1-bit大小的数据进行加密和解密运算，统计数据单位为ms。

5 同态加密的利用

图3 同态加密的利用

同态加密使得云计算和人工智能时代的数据，算法，算力能够解耦，对于一家企业来说，无需残缺具备以上三个条件也能够在云计算和人工智能时代获取一席之地。

咱们能够假如这样一个场景，协和医院领有大量的高价值医疗行业数据，并想通过京东云服务的云计算和人工智能来进行数据分析。在同态加密之前，可能采取的计划要么时协和将隐衷数据的明文提供给京东云计算来进行数据分析，使得隐衷数据外泄；要么是京东为持有敏感数据的企业，采纳传统的On-Premise模式，放弃云计算带来的各种便当。而同态加密，使得协和能够以平安的形式向京东云服务提供隐衷数据，京东云计算也能够在不解密的状况下应用这些数据进行数据分析，从而解决了这个两难问题。依附同态加密，使得基于数理统计相干的算法和数据能够独立开来，既能够依靠于云计算的算法和算力，又完满地爱护了客户的隐衷数据。

同态加密的利用不止限于简略的数据分析，在以下很多场景下都有其用武之地：

隐衷汇合求交
在隐衷汇合求交中，其中一个参与方构建如下的多项式

其中ri为随机数，ci 是另一参与方提供的求交数据的同态加密之后的密文，x是己方持有的求交数据同态加密后的密文。如果ci 和x中任一数据雷同，那么失去的di，在解密后的值为0，否则不为0。

联邦学习
在联邦学习过程中，联邦学习的参与者之间应用同态加密传递学习过程中的两头信息，从而防止信息接管方推断出其它参加联邦学习的参与方的私密信息，保障了联邦学习过程中的信息安全性。

门限签名
门限签名是机密共享和数字签名技术的一种联合。传统的签名技术，私钥被保留在一个可信的核心节点中。（t, n）门限签名计划，把机密分发给n个成员，组成一个签名群体。在这个群体中，单个成员不再具备签名的权限，只有集齐了t个或更多诚恳的成员，能力对数据进行数字签名，这个的t即是门限值。门限签名避免了单个核心节点导致的机密泄露或职权滥用，在证书颁发，多方身份辨认，资产托管，电子投票等诸多畛域具备利用价值。

联结风控
在银行或金融机构进行危险评估时，须要大量对于企业和集体的隐衷信息。对于参加联结风控的数据提供方来说，不心愿本身的隐衷数据裸露给银行或金融机构，而银行和金融机构也不心愿风控规定在三方环境下执行。参加联结风控的数据提供方，通过对本身数据进行同态加密，使得银行或金融机构可能失常进行危险评估，同时又不泄露数据提供方的数据信息。

同态加密技术被誉为隐衷计算技术“皇冠上的明珠”，这项技术使得咱们在不须要信赖云服务提供商的前提下，应用云服务提供商的计算和存储能力，从而解决了云计算中的隐衷数据保护问题。同态加密技术的特点，使其在数字货币，金融利用，医疗保健等畛域有着十分宽泛的利用场景和实际价值。同态加密技术为云计算和云存储在应答隐衷数据时，提供了一种牢靠的解决方案。对同态加密技术的关注和钻研，使得企业具备更多的实践和计划，来应答和解决私密信息的计算和存储问题，为数据的全面互联互通，提供了一种卓有成效的解决方案。

作者：孙晓军

参考文献

[1] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in Proceedings of Advances in Cryptology (EUROCRYPT’99),pp. 223–238, Prague, Czech Republic, May 1999.

[2] Zhu, L., Liu, Z., Han, S.: Deep leakage from gradients. In: Annual Conference on Neural Information Processing Systems (NeurIPS) (2019)

[3] D. Choi, S. Choi, and D. Won, “Paillier’s cryptosystem revisited,” in Proceedings of the 8th ACM Conference on Computer and Communications Security(CCS’01), pp. 206–214, Philadelphia, Pennsylvania, USA, Nov. 2001

[4] I. Damgard and M. Jurik. A generalization, of Paillier's Eurocrypt '99, volume 1592 of LNCS. IACR,Springer-Verlag, 1999.

[5] I. Damgard, J. Jurik, and J. Nielsen, “A generalization of paillier’s public-key system with applications to electronic voting,” International Journal of Information Security, no. 9, pp. 371–385, 2010.

[6] Cao, Z. and Liu, L., "The Paillier's Cryptosystem and Some Variants Revisited." arXiv preprint arXiv:1511.05787,2015.