摘要
随着云计算和人工智能的衰亡，如何平安无效地利用数据，对持有大量数字资产的企业来说至关重要。同态加密，是解决云计算和分布式机器学习中数据安全问题的关键技术，也是隐衷计算中，横跨多方平安计算，联邦学习和可信执行环境多个技术分支的热门钻研方向。
本文对经典同态加密算法 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 = 11
q = 19
n = 209
λ = 90
g = 147
μ = 153Alice 将 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 = 8
r = 3
n_square = pow(n, 2) # n_square = 43681
c = gmpy2.mod(pow(g, m)*pow(r, n), n_square)
# c = 329482.3.3 解密
假如 c 是 Bob 发送过去的密文，且 $c\\in {\\mathbb Z}_{{n^{{2}}}}^{{*}}$
Alice 计算明文
m = L(cλ mod n2) * μ mod n
c = 32948
m = 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 Damg˚ard, 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，所以应用中国残余定理对高阶幂函数取模操作的优化，只能利用在应用私钥的解密操作中。
解密：
应用中国残余定理优化解密算法的步骤如下：
- 定义合成因子 p 和 q 对应的函数 Lp(x) = (x-1) / p, Lq(x) = (x – 1) / q
- 计算 hp ≡ (p – 1) q (mod p), hq ≡ (q – 1) p (mod q)
- 计算 mp = Lp(cp – 1 mod p2) hp mod p, mq = Lq(cq – 1 mod q2) hq mod q
- 计算 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 时，计算结果不正确
为了对立以上呈现的各种场景，咱们能够做如下限定：
- 操作数在参加同态计算前对 n 取模，用来对立负数能够直接参与计算，正数则须要补 n 再进行计算的问题。
- 设定操作数的最大值 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. Damg˚ard, 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.