摘要

隨著云計算和人工智能的興起，如何安全有效地利用資料，對持有大量數字資產的企業來說至關重要，同態加密，是解決云計算和分布式機器學習中資料安全問題的關鍵技術，也是隱私計算中，橫跨多方安全計算，聯邦學習和可信執行環境多個技術分支的熱門研究方向，

本文對經典同態加密演算法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 一個典型的應用場景

同態加密演算法使得密文資料，在沒有額外資料泄露的情況下，可以在第三方平臺進行進一步加工處理，隨著大規模云計算的興起，尤其是涉及到敏感資料的云計算，同態加密演算法將是其中至關重要的技識訓礎，我們以一個典型的聯邦學習的例子為切入點，看看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 + amλ*n mod n2) * μ mod n

這里我們再看下μ的取值，同樣按照公式②展開，得
μ = L(gλ mod n2)-1 mod n = L(1 + aλn mod n2)-1 mod n

最后把函式L展開，得：
DEC(c) = (amλ 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 = (gm1rn mod n2 * gm2 mod n2) mod n2 = gm1+krn 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，取模之前的冪運算均采用模冪方法優化，其中后面的優化均是在前面優化的基礎上進行的優化，

從表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 同態加密的應用

同態加密使得云計算和人工智能時代的資料，演算法，算力可以解耦，對于一家企業來說，無需完整具備以上三個條件也可以在云計算和人工智能時代獲取一席之地，

我們可以假設這樣一個場景，協和醫院擁有大量的高價值醫療行業資料，并想通過京東云服務的云計算和人工智能來進行資料分析，在同態加密之前，能夠采取的方案要么時協和將隱私資料的明文提供給京東云計算來進行資料分析，使得隱私資料外泄；要么是京東為持有敏感資料的企業，采用傳統的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.

標籤：其他

上一篇：前綴和與差分prefix_sum and difference

下一篇：全球名校AI課程庫（39）| 馬里蘭大學 · 資料結構課程『Data Structures』