京東雲開發者｜經典同態加密演算法Paillier解讀 – 原理、實現和應用

• 2022 年 11 月 4 日
• 筆記
• 京東雲技術, 安全, 技術分享

摘要

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

本文對經典同態加密演算法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.