摘要

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

本文对经典同态加密算法 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
μ = 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 = 8
r = 3
n_square = pow(n, 2) # n_square = 43681
c = 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 = 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(k*m1)

解密 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，所以使用中国剩余定理对高阶幂函数取模操作的优化，只能应用在使用私钥的解密操作中。

解密：

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

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. 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.京东云开发者｜经典同态加密算法 Paillier 解读 - 原理、实现和应用