經典同態(tài)加密算法Paillier解讀 - 原理称勋、實現(xiàn)和應用

摘要

隨著云計算和人工智能的興起胸哥，如何安全有效地利用數(shù)據(jù)，對持有大量數(shù)字資產的企業(yè)來說至關重要赡鲜。同態(tài)加密空厌，是解決云計算和分布式機器學習中數(shù)據(jù)安全問題的關鍵技術庐船，也是隱私計算中，橫跨多方安全計算嘲更，聯(lián)邦學習和可信執(zhí)行環(huán)境多個技術分支的熱門研究方向筐钟。

本文對經典同態(tài)加密算法Pailier算法及其相關技術進行介紹，重點分析了Paillier的實現(xiàn)原理和性能優(yōu)化方案赋朦，同時對基于公鑰的加密算法中的熱門算法進行了橫向對比篓冲。最后介紹了Paillier算法的一些實際應用。

【關鍵詞】：同態(tài)加密北发，多方安全計算纹因，聯(lián)邦學習，隱私計算

1 背景知識

1.1 同態(tài)加密

同態(tài)加密（Homomorphic Encryption琳拨，HE）[1] 是將數(shù)據(jù)加密后瞭恰，對加密數(shù)據(jù)進行運算處理，之后對數(shù)據(jù)進行解密狱庇，解密結果等同于數(shù)據(jù)未進行加密惊畏，并進行同樣的運算處理。同態(tài)加密的概念最初在1978年密任，由Ron Rivest颜启，Leonard Adleman和Michael L. Dertouzos共同提出，旨在解決在不接觸數(shù)據(jù)的前提下浪讳，對數(shù)據(jù)進行加工處理的問題缰盏。

目前，同態(tài)加密支持的運算主要為加法運算和乘法運算淹遵。按照其支持的運算程度口猜，同態(tài)機密分為半同態(tài)加密（Partially Homomorphic Encryption, PHE）和全同態(tài)加密（Fully Homomorphic Encryption, FHE）。半同態(tài)加密在數(shù)據(jù)加密后只持加法運算或乘法運算中的一種透揣，根據(jù)其支持的運算的不同济炎，又稱為加法同態(tài)加密或乘法同態(tài)加密。半同態(tài)加密由于機制相對簡單辐真，相對于全同態(tài)加密技術须尚，擁有著更好的性能。全同態(tài)加密對加密后的數(shù)據(jù)支持任意次數(shù)的加法和乘法運算侍咱。

1.2 復合剩余類問題

如果存在一個數(shù) $y∈\mathbb{Z}_{n^2}^\ast$ , 那么符合公式 $z ≡ y^n\ (mod\ n^2)$ 的數(shù)z耐床，稱為y的模 $n^2$ 的n階剩余。復合剩余類問題（decisional composite residuosity assumption , DCRA)楔脯，指的是給定一個合數(shù)n和整數(shù)z撩轰，很難確定模 $n^2$ 的n階剩余數(shù)z是否存在。

1.3 中國剩余定理

中國剩余定理（Chinese Remainder Theorem, CRT），又稱為孫子定理钧敞，源于《孫子算經》，是數(shù)論中的一個關于一元線性同余方程組的定理麸粮，說明了一元線性同余方程組有解的準則以及求解方法溉苛。

有物不知其數(shù)，三三數(shù)之剩二弄诲，五五數(shù)之剩三愚战，七七數(shù)之剩二。問物幾何齐遵？
翻譯為數(shù)學語言為：

$\left\{ \begin{aligned} x ≡ 2 (mod{\,}{\,}3) \\ x ≡ 3 (mod{\,}{\,}5) \\ x ≡ 2 (mod{\,}{\,}7) \end{aligned} \right.$

其通用方程為：
$\left\{ \begin{aligned} x≡a_0(mod{\,}{\,}n_0) \\ x≡a_1(mod{\,}{\,}n_1) \\ ...{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}{\,}\\ x≡a_k(mod{\,}{\,}n_k) \end{aligned} \right.$

中國剩余定理的解法流程為：

計算所有模數(shù)的乘積 $n = \prod_{i\ =\ 0}^{k}n_i$
計算 $m_i = n / n_i, c_i = m_i * m_i^{-1}$
方程組的解為： $x = \sum_{i\ =\ 0}^{k}{a_ic_i\ (mod\ n)}$

2 Paillier算法原理

2.1 Paillier簡介

在Paillier算法出現(xiàn)之前寂玲，基于公鑰加密的算法主要有兩個分支：

以RSA為代表的，基于大數(shù)因數(shù)分解難題的公鑰加密算法
以ElGama為代表的梗摇，基于大數(shù)離散對數(shù)難題的公鑰加密算法

Paillier加密算法拓哟，由Pascal Paillier于1999年發(fā)表，給出了公鑰加密算法的一個新的分支領域伶授。Paillier基于復合剩余類難題断序，滿足加法同態(tài)和數(shù)乘同態(tài)，具有非常高效的運行時性能糜烹。

2.2 一個典型的應用場景

圖1 傳統(tǒng)聯(lián)邦學習

同態(tài)加密算法使得密文數(shù)據(jù)违诗，在沒有額外數(shù)據(jù)泄露的情況下，可以在第三方平臺進行進一步加工處理疮蹦。隨著大規(guī)模云計算的興起诸迟，尤其是涉及到敏感數(shù)據(jù)的云計算，同態(tài)加密算法將是其中至關重要的技術基礎愕乎。我們以一個典型的聯(lián)邦學習的例子為切入點阵苇，看看Paillier算法的原理和在實踐中應用的問題。

假設Alice和Bob想共同訓練一個網絡模型妆毕，Alice和Bob各自持有一部分訓練數(shù)據(jù)慎玖，并且他們不想把自己的數(shù)據(jù)泄露給對方。那么在訓練期間笛粘，Alice和Bob需要交互各自訓練的梯度數(shù)據(jù)趁怔，并根據(jù)雙方的梯度數(shù)據(jù)，共同計算一個對雙方都合適的梯度值薪前，用來執(zhí)行聯(lián)合梯度下降過程润努。

2019年，Ligeng Zhu等人發(fā)表的“Deep Leakage from Gradients”論文中給出了一種算法[2]示括，可以從幾次迭代的梯度數(shù)據(jù)中铺浇，推斷出訓練的數(shù)據(jù)，標簽垛膝，模型等一系列隱私信息鳍侣。這使得在分布式機器學習中丁稀，通過傳輸梯度數(shù)據(jù)來進聯(lián)合模型訓練變得不再安全。那么如果在梯度數(shù)據(jù)傳輸?shù)倪^程中倚聚，傳輸?shù)氖羌用芎蟮奶荻葦?shù)據(jù)线衫，并且這些加密數(shù)據(jù)可以進行二次計算，那么便可以規(guī)避梯度數(shù)據(jù)傳輸過程帶來的安全風險惑折。

2.3 Paillier算法

2.3.1 密鑰生成

類似于RSA算法授账，Paillier也擁有公鑰和私鑰對。

Alice選擇兩個大素數(shù)p=11惨驶，q=19(目前已知512bit的非對稱密鑰已經可以破解白热，實際應用中通常選用非常大的素數(shù))
Alice計算p和q的乘積n = p * q = 209, 并計算λ = lcm(p – 1, q - 1)
Alice選擇一個隨機整數(shù)g, $g\in {\mathbb Z}_{{n^{{2}}}}^{{*}}$
Alice定義函數(shù) $L(x) = \frac{x-1}{n}$ , 并計算模反元素 $μ = {L(g^\lambda\ mod\ n^2)}^{-1} mod{\,}{\,}n$

在上述過程中，Alice總計生成了6個數(shù)字：

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發(fā)送過來的公鑰（n, g）

Bob選擇一個隨機數(shù)r,滿足0 < r < n
Bob計算加密后的密文 c = g^m.rⁿ mod n²

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發(fā)送過來的密文屋确，且 $c\in {\mathbb Z}_{{n^{{2}}}}^{{*}}$
Alice計算明文 $m = L(c^\lambda\ mod\ n^2)*μ\ mod\ n$

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

正確性證明

為了證明解密操作的正確性，我們把加密的公式代入：
$DEC(c) = L(c^\lambda\ mod\ n^2) * μ mod n = L({{(g}^mr^n\ mod\ n^2)}^\lambda\ mod\ n^2) * μ\ mod\ n = L{(g}^{\lambda m}r^{\lambda n}\ mod\ n^2) * μ\ mod\ n$

根據(jù)卡米切爾定理（Carmichael’s function）有：
① $\ \ r^{\lambda n} ≡1\ mod\ n^2$

繼續(xù)化簡得：
$DEC(c) = L{(g}^{\lambda m}\ mod\ n^2) * μ\ mod\ n$

由于 $g ∈ Z_{n^2}^\ast, n + 1 ∈ Z_{n^2}^\ast$ , 那么一定存在唯一一對（a, b）使得：
② $\ g^\lambda\ mod\ n^2 = {(1\ +\ n}^{a\lambda}) * b^{n\lambda}\ mod\ n^2 = 1 + a*λ*n\ mod\ n^2$

把上述公式帶入休建，高階多項式按二項式定理展開乍恐，得：
$DEC(c) = L({{((1\ +\ n}^{a\lambda})b^{n\lambda})}^m\ mod\ n^2 ) * μ\ mod\ n = L(1 + a*m*λ*n\ mod\ n^2) * μ\ mod\ n$

這里我們再看下μ的取值，同樣按照公式②展開测砂，得
$μ = {L(g^\lambda\ mod\ n^2)}^{-1} mod n = {L(1 + a*λ*n\ mod\ n^2)}^{-1}\ mod\ n$

最后把函數(shù)L展開茵烈，得：
$DEC(c) = (a*m*λ\ mod\ n^2) * {(a\ast\lambda\ mod\ n^2)}^{-1}\ mod\ n = m$

2.3.4 同態(tài)加

假設Alice計算的梯度數(shù)據(jù)為m1, Bob計算的梯度數(shù)據(jù)為m2，Bob需要計算雙方梯度數(shù)據(jù)的均值（m1 + m2）/ 2, 作為分布式梯度下降的梯度數(shù)據(jù)砌些。

同態(tài)加的原理是利用了冪函數(shù)的 $a^{x1} * a^{x2} = a^{x1+x1}$ 的特性呜投。對于Alice持有的數(shù)據(jù)m1的密文c1和Bob持有數(shù)據(jù)m2的密文c2,Bob使用如下公式計算同態(tài)加法運算：

$c = c1 * c2\ mod\ n^2$

Alice使用私鑰計算 $DEC(c) = m1 + m2$

正確性證明

為了證明同態(tài)加的正確性, 我們把加密的公式代入同態(tài)加運算：
$c = ((g^{m1}r^n\ mod\ n^2) * (g^{m2}r^n\ mod\ n^2)) mod\ n^2 = (g^{m1}r^ng^{m2}r^n) mod\ n^2 = (g^{m1\ +m2}{r^2}^n) mod\ n^2 = ENC(m1 + m2)$
解密c等價于：
$DEC(c) = DEC(ENC(m1 + m2)) = m1 + m2$

對于密文和明文相加的同態(tài)運算，我們當然可以先對明文加密存璃，之后再對兩個密文進行同態(tài)加運算的方式來計算仑荐。不過從上面的公式可以看出，擾動數(shù)據(jù) $r^n$ 中的r是一個任意值纵东。那么我們可以把計算密文c1和明文m2的和的計算轉換為：
$c1 + m2 = (g^{m1}*r^n\ mod\ n^2 * g^{m2}\ mod\ n^2) mod\ n^2 = g^{m1}+k*r^n mod\ n^2 = E(m1+m2)$

這樣少了一次計算 $r^n$ 的運算量粘招，提升了明文和密文相加運算的效率。

2.3.5 同態(tài)數(shù)乘

Paillier算法目前只支持明文和密文相乘的計算方式偎球，不支持密文和密文相乘洒扎。

同態(tài)數(shù)乘的原理是利用了冪函數(shù)的a^{x^k} = a^kx的特性。
Bob使用Alice對明文m1加密后的密文c1和明文k衰絮，計算
$c = c1^k\ mod\ n^2$
Alice使用私鑰計算 $DEC(c) = k*m1$

正確性證明
為了證明同態(tài)數(shù)乘的正確性, 我們把加密的公式代入同態(tài)數(shù)乘運算：
$c = c1^k\ mod\ n^2 = (g^{m1}*r^n\ mod\ n^2)^k\ mod\ n^2 = g^{k*m1}*r1^n\ mod\ n^2 = E(k*m1)$
解密c等價于：
$DEC(c) = DEC(ENC(k * m1)) = k * m1$

2.4 算法優(yōu)化

2.4.1 參數(shù)g優(yōu)化

在原始Paillier方案中袍冷，g的取值只需滿足 $g∈\mathbb{Z}_{n^2}^\ast$ 。Ivan和Mads在論文中給出了使用g = n + 1 的優(yōu)化方案[3]猫牡，并且證明了使用此方案后胡诗，可以和原始Paillier算法保持相同的安全性。
在使用g = n + 1后，實現(xiàn)密鑰生成和加密過程的性能提升煌恢。

密鑰生成：
把g = n + 1帶入μ的生成公式,得
$μ = {L(g^\lambda\ mod\ n^2)}^{-1}\ mod\ n = {L({(n\ +\ 1)}^\lambda\ mod\ n^2)}^{-1}\ mod\ n = {L((1\ +\ \lambda n)\ mod\ n^2)}^{-1}\ mod\ n = \lambda^{-1}\ mod\ n$
μ 生成可以直接取λ 對 n的模反元素骇陈。

加密：
把g = n+1，帶入加密公式瑰抵，得 $c = g^mr^n\ mod\ n^2 = {(n\ +\ 1)}^mr^n\ mod\ n^2 = (n * m + 1) * r^n\ mod\ n^2$

加密過程把計算g的m次冪的操作缩歪，變成了簡單的乘法操作：
c = (nm+1)rⁿ mod n²

2.4.2 高階冪運算優(yōu)化

在優(yōu)化了原始Paillier加密過程的 $g^m$ 冪運算后，加密操作中最耗性能的操作就是對 $r^n$ 高階冪函數(shù)的計算谍憔。2010年，Ivan Damg?ard, Mads Jurik 和 Jesper Buus Nielsen給出了優(yōu)化 $r^n$ 這個高階冪函數(shù)計算的方案[5]主籍，并證明了使用此方案后习贫，可以和原始Paillier算法保持相同的安全性。

密鑰生成：
要求p≡q≡3 (mod 4), 且gcd(p – 1, q – 1) = 2.
λ = (p - 1)(q - 1) / 2
選擇一個隨機數(shù)x千元，且 $x ∈Z_n^\ast, h = -x^2\ mod\ n$ 苫昌。
選擇一個自然數(shù)s，對于原版Paillier, 相當于為s設定了s = 1
$h_s = h^{n^s} mod\ n^{s\ +\ 1}$
優(yōu)化后幸海，新的公鑰為public-key=(n, h_s)

加密：
生成一個隨機數(shù)α祟身， $a ∈Z_{2^{\lceil k\ /\ 2\rceil}}$ , 其中k是密鑰長度
優(yōu)化后使用如下公式進行加密操作：
$c = (n\ \ast\ m\ +\ 1){h_s}^\alpha\ mod\ n^{s\ +\ 1}$
因為取值α << n, 使得加密計算過程中，計算 ${h_s}^\alpha$ 的性能物独，優(yōu)于計算 $r^n$ 的性能.

2.4.3 使用中國剩余定理

使用中國剩余定理袜硫，可以把諸如 $a^x\ mod\ n$ 形式的高階冪函數(shù)取模操作，分解為低階冪函數(shù)對n的因子取模的操作挡篓。

由于分解操作婉陷，需要使用到生成私鑰的關鍵數(shù)據(jù)p和q，所以使用中國剩余定理對高階冪函數(shù)取模操作的優(yōu)化官研，只能應用在使用私鑰的解密操作中秽澳。

解密：
使用中國剩余定理優(yōu)化解密算法的步驟如下：

定義分解因子p和q對應的函數(shù) $L_p(x) = \frac{x - 1}{p} , L_q(x) = \frac{x - 1}{q}$
計算 $h_p ≡ (p - 1) * q (mod\ p), h_q ≡ (q - 1) * p (mod\ q)$
計算 $m_p = L_p(c^{p\ -\ 1}\ mod\ p^2)\ h_p\ mod\ p,\ m_q = L_q(c^{q\ -\ 1}\ mod\ q^2)\ h_q\ mod\ q$
計算m = CRT(m_p, m_q) mod n, m 即為使用中國剩余定理優(yōu)化的解密后的明文

2.4.4 性能優(yōu)化對比

算法使用Python代碼實現(xiàn)，密鑰長度取2048bit, s參數(shù)取1戏羽，取模之前的冪運算均采用模冪方法優(yōu)化担神。其中后面的優(yōu)化均是在前面優(yōu)化的基礎上進行的優(yōu)化。

	原版	參數(shù)g優(yōu)化	冪運算優(yōu)化(s=1)	中國剩余定理(s =1)
密鑰生成	98.412	77.913	169.511	169.812
加密	20.043	9.107	4.704	4.704
解密	11.692	8.859	8.859	2.705

$表1\ Paillier性能優(yōu)化對比$
??

圖2 paillier性能優(yōu)化對比

從表1和圖2中可以看到始花，經過參數(shù)g優(yōu)化和冪運算優(yōu)化后妄讯，加密運算的效率較之原版方案提升了約3.26倍。經過使用中國剩余定理優(yōu)化后衙荐，解密運算的效率較之原版方案提升了約3.32倍捞挥。在密鑰生成上，使用了冪運算優(yōu)化后忧吟，密鑰生成的時間增加了約42%砌函。考慮到密鑰生成運算的次數(shù)，通常遠小于加解密運算的次數(shù)讹俊，相比之下密鑰生成的性能損失通晨殉粒可以忽略不計。

2.5 來自多方計算的安全問題

在上面Alice和Bob使用Paillier同態(tài)加密來進行分布式梯度值計算時仍劈，Alice持有私鑰厕倍，對Bob加密后的梯度數(shù)據(jù)，進行同態(tài)運算贩疙，并生成最終分布式梯度計算的梯度值讹弯。這里有一個問題，在這個場景下这溅，雖然Alice沒有獲得Bob的直接或加密后的梯度數(shù)據(jù)组民，但Alice知道最終的梯度值，這使得Alice可以根據(jù)差分結果悲靴，猜測出Bob本次計算的梯度數(shù)據(jù)臭胜，從而產生安全問題。

在多方安全計算中癞尚，由于同態(tài)計算的算法耸三，不一定能夠提供安全保證，使得我們必須應對計算過程中可能出現(xiàn)的安全問題浇揩。對于Alice和Bob的計算分布式梯度值的場景仪壮，可以根據(jù)當前的學習率引入合適的擾動數(shù)據(jù)來規(guī)避差分隱私問題，或者參與計算的多方至少是三方胳徽。

3 功能擴展

在原版Paillier中睛驳，明文m的定義域是[0, n)。在Alice和Bob的進行的分布式機器學習場景中膜廊，需要能夠對浮點和負數(shù)進行加密運算乏沸。在實際應用中，如果只能加密正整數(shù)爪瓜，那么Paillier的應用場景會受到較大的限制蹬跃。實際上，計算機的布爾電路只能對0和1的二進制數(shù)據(jù)進行計算铆铆，無論是浮點數(shù)還是負數(shù)蝶缀，甚至是整數(shù)的計算，都是通過特定的計算規(guī)則來完成的薄货，我們可以參照這些規(guī)則翁都，實現(xiàn)Paiiler算法對浮點數(shù)和負數(shù)的支持。

3.1 浮點數(shù)支持

IEEE 754標準中谅猾，單精度浮點表示采用1位符號柄慰，8位階碼和23位分數(shù)鳍悠。

對于浮點數(shù)，我們可以將所有參與計算的數(shù)值坐搔，編碼為更小的單位藏研，在計算完成后再解碼。比如浮點數(shù)3.14概行，可以預先乘以100蠢挡，即3.14 = 314 * {10}^{-2}。之后計算過程中凳忙，整數(shù)部分和指數(shù)部分分別運算业踏。

在計算機中，浮點數(shù)以符號位（Sign）涧卵，階碼（Exponent）和分數(shù)（Fraction）三部分聯(lián)合來標識堡称，底數(shù)(Base)固定為2。我們仍舊以3.14為例艺演， $3.14 = 0.785 * 2^2 = [11.0010001]_2$ 。實際使用中桐臊，為了表示更大的范圍胎撤，分數(shù)部分的取值范圍要求 1 <= fraction < 2, 這樣保證了分數(shù)部分的首位總是為1，這樣小數(shù)部分可以隱藏首位的1断凶。為了使階碼可以使用負數(shù)伤提，浮點標準規(guī)定了指數(shù)部分使用一個偏移值（Bias），這樣浮點數(shù)的值的計算方式為：
$x = {-1}^{sign} * (1 + Fraction) * 2^{(Exponent\ -\ Bias)}$

在擴充Paillier算法定義域到浮點數(shù)時认烁，浮點數(shù)各個部分的計算肿男，均需程序來實現(xiàn)。這里我們參照浮點數(shù)的表示法却嗡，且不使用隱藏位舶沛，假設給定Bias=8，那么3.14就可以編碼為（E = 2窗价，F(xiàn)=200(0.785 * 2⁸)）。我們再把整數(shù)2坪它，經過同樣的編碼帝牡，得到(E=2, F=128)

在Paillier計算中，由于階碼相同靶溜，3.14 + 2 = （E = 2, F = 328）懒震。最終執(zhí)行解碼惩阶，得到 $328 * 2^{-8} * 2^2 = 5.125$ 挎狸。計算結果存在較大的精度損失，實際應用中断楷，我們可以通過增大Bias的值锨匆，來提升計算結果的精度。

對于同態(tài)數(shù)乘來說冬筒，由于不需要階碼對齊恐锣，那么只需對F值做數(shù)乘，即可得到正確的結果舞痰。同樣對于3.14土榴，乘以3后得到（E = 2， F = 600）响牛，之后解碼玷禽，得到 $600 * 2^{-8} * 2^2 = 9.375$ 。同樣由于示例中Bias取值問題呀打，計算結果出現(xiàn)了較大的誤差矢赁。

3.2 負數(shù)支持

在計算機中，負數(shù)是以補碼的方式標識的贬丛。整數(shù)和負數(shù)相加撩银，是通過溢出來使得計算結果符合預期值，如果我們把負數(shù)的字節(jié)擴充豺憔，那么會得到一個原有字節(jié)空間的最大值和對應負數(shù)之和的正數(shù)额获，在此基礎上使用此正數(shù)進行四則運算，之后再縮容到原來的字節(jié)空間恭应，那么得到的仍舊是正確的結果抄邀。

類似的，為了使Paillier能夠支持負數(shù)的計算昼榛，我們可以給負數(shù)m_1增加一個周期值n, 來把負數(shù)m_1轉換為正整數(shù)撤摸。那么對于同態(tài)加運算來說准夷，計算結果c=ENC(m_1 + m_2 + n)。
此時同態(tài)加計算的結果為：

當 $m_1 + m_2 >= 0$ 時楔绞， $DEC(c) = m_1 + m_2$
當 $-n <= m_1 + m_2 < 0$ 時酒朵， $DEC(c) = m_1 + m_2 + n$
當 $m_1 + m_2 < -n$ 時结耀，計算結果不正確

同態(tài)數(shù)乘的計算結果為：

當 $k*m_1 >= 0$ , 時 $DEC(c) = k*m_1$
當 $-n <= k*m_1 < 0$ 時图甜， $DEC(c) = k*m_1 + n$
當 $k*m_1 < -n$ 時，計算結果不正確

為了統(tǒng)一以上出現(xiàn)的各種場景矿瘦，我們可以做如下限定：

操作數(shù)在參與同態(tài)計算前對n取模缚去，用來統(tǒng)一正數(shù)可以直接參與計算，負數(shù)則需要補n再進行計算的問題稠通。
設定操作數(shù)的最大值MAX_VALUE，比如32位整型的最大值飞主。并使得n的取值大于3 * MAX_VALUE碌识，這樣使得對于合法的 $m_1和m_2$ 筏餐，不存在 $m_1 + m_2 < -n$ 的場景穆律，且 $m_1 + m_2 < 0$ 時峦耘，計算結果總是大于MAX_VALUE。

至此赋秀，我們可以使用統(tǒng)一的規(guī)則绍弟，來處理負數(shù)參與同態(tài)運算時的各種場景樟遣。

4 主要公鑰加密算法對比

Paillier豹悬，RSA和ELGamal算法均為典型的基于公鑰的加密算法，我們從功能指標和性能指標兩個方向伤柄，來對比這些加密算法的區(qū)別和聯(lián)系适刀。

4.1 功能指標對比

	Paillier	RSA	ELGamal
安全基礎	復合剩余類問題	大數(shù)分解問題	離散對數(shù)問題
語義安全	是	否（可以使用諸如OAEP的隨機填充算法來達到語義安全的效果）	是
公鑰加密/私鑰解密	支持	支持	支持
私鑰簽名/公鑰驗簽	不支持（可以實現(xiàn)更為復雜的門限簽名）	支持	支持
算法復雜程度（非時間復雜度）	高	低	中
同態(tài)計算	同態(tài)加笔喉，同態(tài)數(shù)乘	同態(tài)乘	同態(tài)乘

$表2\ 功能指標對比$

4.2 性能指標對比

對4096-bit大小的明文進行加密：

表3 密文膨脹系數(shù)[5]

對1-bit大小的數(shù)據(jù)進行加密和解密運算，統(tǒng)計數(shù)據(jù)單位為ms待侵。

表4 加解密性能[5]

5 同態(tài)加密的應用

圖3 同態(tài)加密的應用

同態(tài)加密使得云計算和人工智能時代的數(shù)據(jù)怨酝，算法农猬，算力可以解耦斤葱，對于一家企業(yè)來說揍堕，無需完整具備以上三個條件也可以在云計算和人工智能時代獲取一席之地衩茸。

我們可以假設這樣一個場景楞慈，協(xié)和醫(yī)院擁有大量的高價值醫(yī)療行業(yè)數(shù)據(jù)，并想通過京東云服務的云計算和人工智能來進行數(shù)據(jù)分析聚霜。在同態(tài)加密之前蝎宇，能夠采取的方案要么時協(xié)和將隱私數(shù)據(jù)的明文提供給京東云計算來進行數(shù)據(jù)分析夫啊，使得隱私數(shù)據(jù)外泄；要么是京東為持有敏感數(shù)據(jù)的企業(yè)虱咧，采用傳統(tǒng)的On-Premise模式腕巡，放棄云計算帶來的各種便利绘沉。而同態(tài)加密择懂，使得協(xié)和可以以安全的方式向京東云服務提供隱私數(shù)據(jù)困曙，京東云計算也可以在不解密的情況下使用這些數(shù)據(jù)進行數(shù)據(jù)分析慷丽，從而解決了這個兩難問題要糊。依靠同態(tài)加密杨耙，使得基于數(shù)理統(tǒng)計相關的算法和數(shù)據(jù)可以獨立開來珊膜，既可以依托于云計算的算法和算力车柠，又完美地保護了客戶的隱私數(shù)據(jù)。

同態(tài)加密的應用不止限于簡單的數(shù)據(jù)分析塑陵，在以下很多場景下都有其用武之地：

隱私集合求交
在隱私集合求交中令花，其中一個參與方構建如下的多項式
d_i = r_i\prod_{x\in X}{(c_i-x)}
其中r_i為隨機數(shù)，c_i 是另一參與方提供的求交數(shù)據(jù)的同態(tài)加密之后的密文扮碧，x是己方持有的求交數(shù)據(jù)同態(tài)加密后的密文慎王。如果c_i 和x中任一數(shù)據(jù)相同北戏，那么得到的d_i嗜愈，在解密后的值為0，否則不為0剃毒。

聯(lián)邦學習
在聯(lián)邦學習過程中赘阀，聯(lián)邦學習的參與者之間使用同態(tài)加密傳遞學習過程中的中間信息基公，從而避免信息接收方推斷出其它參與聯(lián)邦學習的參與方的私密信息，保證了聯(lián)邦學習過程中的信息安全性酸休。

門限簽名
門限簽名是秘密共享和數(shù)字簽名技術的一種結合斑司。傳統(tǒng)的簽名技術，私鑰被保存在一個可信的中心節(jié)點中糙置。（t, n）門限簽名方案，把秘密分發(fā)給n個成員懊纳，組成一個簽名群體冤今。在這個群體中茂缚，單個成員不再具有簽名的權限龟糕，只有集齊了t個或更多誠實的成員，才能對數(shù)據(jù)進行數(shù)字簽名缓艳，這個的t即是門限值。門限簽名防止了單個中心節(jié)點導致的秘密泄露或職權濫用舶治，在證書頒發(fā)，多方身份識別声旺，資產托管佛致，電子投票等諸多領域具有應用價值。

聯(lián)合風控
在銀行或金融機構進行風險評估時惜浅，需要大量關于企業(yè)和個人的隱私信息。對于參與聯(lián)合風控的數(shù)據(jù)提供方來說伏嗜，不希望自身的隱私數(shù)據(jù)暴露給銀行或金融機構坛悉，而銀行和金融機構也不希望風控規(guī)則在三方環(huán)境下執(zhí)行。參與聯(lián)合風控的數(shù)據(jù)提供方军熏，通過對自身數(shù)據(jù)進行同態(tài)加密彤委，使得銀行或金融機構能夠正常進行風險評估艰额，同時又不泄露數(shù)據(jù)提供方的數(shù)據(jù)信息祖搓。

同態(tài)加密技術被譽為隱私計算技術“皇冠上的明珠”，這項技術使得我們在不需要信賴云服務提供商的前提下捌臊，使用云服務提供商的計算和存儲能力寇荧，從而解決了云計算中的隱私數(shù)據(jù)保護問題。同態(tài)加密技術的特點凡壤，使其在數(shù)字貨幣箕别，金融應用，醫(yī)療保健等領域有著非常廣泛的應用場景和實踐價值护蝶。同態(tài)加密技術為云計算和云存儲在應對隱私數(shù)據(jù)時，提供了一種可靠的解決方案涛漂。對同態(tài)加密技術的關注和研究攻泼，使得企業(yè)具有更多的理論和方案淆游，來應對和解決私密信息的計算和存儲問題，為數(shù)據(jù)的全面互聯(lián)互通传趾，提供了一種行之有效的解決方案蜕便。

配套代碼

sunxiaojun/privacy-preserving-computing (github.com)

參考文獻

[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.

最后編輯于：2022.10.09 18:46:07

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者

人面猴
序言：七十年代末展父，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌，老刑警劉巖瘾晃，帶你破解...
沈念sama閱讀 218,755評論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件偶洋，死亡現(xiàn)場離奇詭異，居然都是意外死亡，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,305評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人瓜饥，你說我怎么就攤上這事帐我】擦叮” “怎么了愧膀？”我有些...
開封第一講書人閱讀 165,138評論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長谣光。經常有香客問我檩淋，道長，這世上最難降的妖魔是什么萄金？我笑而不...
開封第一講書人閱讀 58,791評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任蟀悦，我火速辦了婚禮，結果婚禮上氧敢，老公的妹妹穿的比我還像新娘日戈。我一直安慰自己，他們只是感情好孙乖，可當我...
茶點故事閱讀 67,794評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布浙炼。她就那樣靜靜地躺著，像睡著了一般唯袄。火紅的嫁衣襯著肌膚如雪弯屈。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,631評論 1贊 305
城市分裂傳說
那天恋拷，我揣著相機與錄音资厉，去河邊找鬼。笑死蔬顾，一個胖子當著我的面吹牛宴偿，可吹牛的內容都是我干的湘捎。我是一名探鬼主播，決...
沈念sama閱讀 40,362評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼窄刘，長吁一口氣：“原來是場噩夢啊……” “哼消痛！你這毒婦竟也來了？” 一聲冷哼從身側響起都哭，我...
開封第一講書人閱讀 39,264評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤秩伞，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后欺矫，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體纱新，經...
沈念sama閱讀 45,724評論 1贊 315
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 37,900評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年穆趴，在試婚紗的時候發(fā)現(xiàn)自己被綠了脸爱。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,040評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡未妹，死狀恐怖簿废，靈堂內的尸體忽然破棺而出，到底是詐尸還是另有隱情络它，我是刑警寧澤族檬，帶...
沈念sama閱讀 35,742評論 5贊 346
?日本核電站爆炸內幕
正文年R本政府宣布，位于F島的核電站化戳，受9級特大地震影響单料，放射性物質發(fā)生泄漏。R本人自食惡果不足惜点楼，卻給世界環(huán)境...
茶點故事閱讀 41,364評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一扫尖、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧掠廓，春花似錦换怖、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,944評論 0贊 22
一樁弒父案沉颂，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至黄橘，卻和暖如春兆览，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背塞关。一陣腳步聲響...
開封第一講書人閱讀 33,060評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工抬探，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人。一個月前我還...
沈念sama閱讀 48,247評論 3贊 371
代替公主和親
正文我出身青樓小压，卻偏偏與公主長得像线梗，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子怠益，可洞房花燭夜當晚...
茶點故事閱讀 44,979評論 2贊 355

經典同態(tài)加密算法Paillier解讀 - 原理、實現(xiàn)和應用