第四節 安全多方計算技術

一 安全多方計算的定義

安全多方計算技術（Security Multi-Party Computation, SMC）起源于1982年世界著名計算機學家姚期智（Andrew Chi-Chih Yao）的百萬富翁問題：

“兩個百萬富翁想比較一下誰更富有，但是他們不想讓對方、更不想讓第三方知道自己確切的錢數。”

由此可以得出安全多方計算技術是解決兩方或多方參與且互不信任的前提下保護隱私的協同計算問題，安全多方計算技術要確保參與方信息的獨立性和計算的正確性，同時又可以保護各參與方的信息不泄露給其他參與方或第三方。[60]

安全多方計算技術要解決的問題可以描述如下：一組參與方希望共同計算某個約定的函數，每個參與方提供函數的一個輸入，要求參與方提供的輸入對其他參與方保密（出于安全考慮）。[61]如果存在安全可信第三方，則安全多方技術所要解決的問題可以輕易地得到解決：只需各個參與方將各自的輸入交給安全可信第三方，由安全可信第三方計算后得到函數值，再將函數值發布給各參與方。但現實中很難找到這樣的安全可信第三方，從而安全多方計算技術的研究應運而生。安全多方計算在電子投票、電子選舉、電子拍賣、秘密共享、門限簽名等場景中有著重要的作用。

根據參與方在安全多方計算中的行為，將參與方劃分為以下三種類型：

（一）惡意參與方

在安全多方計算執行過程中，惡意參與方參與計算的目的就是獲取其他參與方的輸入、輸出及中間結果。惡意參與方可能將自己的輸入、輸出或中間結果泄露給攻擊方，同時可能不按照計算的要求完成計算的每個步驟，甚至篡改數據或執行步驟。

（二）半誠信參與方

在安全多方計算執行過程中，半誠信參與方完全按照計算的要求完成計算的每個步驟，嚴格保密自己的輸入、輸出及中間結果。半誠信參與方可能通過收集其他參與方的中間結果試圖推導其原始輸入數據、輸出數據，也有可能將自己的輸入、輸出或中間結果泄露給攻擊方。

（三）誠信參與方

在安全多方計算執行過程中，誠信參與方完全按照計算的要求完成計算的每個步驟，不篡改數據也不會修改計算步驟，同時嚴格保密自己的輸入、輸出及中間結果。但誠信參與方可能通過收集其他參與方的中間結果試圖推導其原始輸入數據、輸出數據。誠信參與方與半誠信參與方的根本區別在于誠信參與方不會被攻擊方腐敗。[62]

根據攻擊方在安全多方計算中腐敗的參與方的不同，安全多方計算中將攻擊方劃分為以下三種類型：

（一）主動攻擊方

主動攻擊方是安全多方計算中的惡意參與方。主動攻擊方可以腐敗安全多方計算中的其他參與方后獲取被腐敗方的輸入、輸出及中間結果，甚至可以讓腐敗方篡改輸入、輸出及中間結果，篡改計算步驟，直至計算終止。

（二）被動攻擊方

被動攻擊方是安全多方計算中的半誠信參與方。被動攻擊方可以腐敗安全多方計算中的其他參與方后獲取被腐敗方的輸入、輸出及中間結果。被動攻擊方不能篡改輸入、輸出及中間結果，不能篡改計算步驟，不能阻止計算。這也是被動攻擊方與主動攻擊方的區別。

（三）易變攻擊方

易變攻擊方是混亂的，在安全多方計算的不同周期，可能是不同的攻擊方，有時候是被動攻擊方，有時候是主動攻擊方。

根據參與方的不同，安全多方計算模型有以下兩種：

（一）半誠信模型

所有參與方均為半誠信參與方或誠信參與方，則此模型為半誠信模型。

定義2.2：設n元函數f:（{0,1}?）n→（{0,1}?）n，其中fi（x1, x2, …, xn）表示f（x1, x2, …, xn）中的第i個元素。令f1（x1, x2, …, xn）表示子序列fi1（x1, x2, …, xn）, …, fit（x1, x2, …, xn），其中I = {i1, i2, …, in}?[m]def= {1,2, …, n}。設∏是表示計算f的n方協議，在用輸入=（x1, x2, …, xn）執行協議過程中，第i 個參與方 Pi的觀察表示為 VIEWi∏（）。令，其中I = {i1, i2, …, it}。

（二）惡意模型

有惡意參與方的模型即為惡意模型。

安全多方計算模型以保護誠信參與方，不保護半誠信參與方，取締惡意參與方為目的。

安全多方計算具有如下三個特性：

（一）安全性

任何參與方只能得到安全多方計算后的中間結果或輸出，不能得到其他參與方的輸入數據、中間結果。

（二）公平性

若惡意參與方不能在其他誠信參與方或半誠信參與方獲得中間結果或輸出之前獲得其他誠信參與方或半誠信參與方的中間結果或輸出，則稱為完全公平。若惡意參與方攻擊其他半誠信參與方后，在其他半誠信參與方之前獲得中間結果或輸出，則稱為部分公平。

（三）正確性

安全多方計算模型的參與方輸入數據后經過計算等得到正確的中間結果和輸出。

1982年，世界著名計算機學家姚期智提出了基于兩方的安全計算協議。1987年，在密碼學理論的支持下，O. Goldreich, A. Wigderson和S. Micali等人提出了基于多方的安全計算協議，其中協議是可以計算的任意函數。當存在被動攻擊方時，給出并證明了存在n-Secure協議；當存在主動攻擊方時，給出并證明了存在（n-1）-Secure協議。1998年，在信息學理論的支持下，D. Chaum, I. Damgard和C. Crepeau等人研究了基于安全模型的安全多方計算，并證明了當存在被動攻擊方時，存在（n-1）-Secure協議；當存在主動攻擊方時，存在（-1）-secure協議。1990年，S. Goldwasser和L. Levin等人提出了當大部分參與方（超過參與方的50%）都被腐敗時的安全多方計算協議。隨后O. Goldreich, N. Linial和S. Goldwasser等人對于不安全的通訊信道、擁有無限計算能力的攻擊者模型下的安全多方計算協議進行了研究。R. Ostrovsky和M. Yung在安全信道模型下對移動攻擊者（Mobile Adversaries）進行了研究。

二 安全和模型（Secure Sum）

文獻 [15] 提出垂直分布數據中基于SMC技術的k-Means方法，文獻 [16] 提出在垂直分布和水平分布數據中基于SMC技術的k-Means方法。在水平分布數據中利用SMC求平均值協議可以在不泄露隱私的情況下完成聚類挖掘，在垂直數據中使用SMC中的Secure SUM技術和Secure-Means技術在不泄露隱私的情況下完成聚類挖掘。安全和模型主要應用于分布式數據挖掘系統，算法如下：

輸入：s個參與方，分別屬于s個站點，每個參與方輸入數據Vi（s≥3）

輸出：

算法：

設的范圍是[0,n]；

設S1是主站點，產生隨機數R，且R∈ [0, n]；

主站點S1計算R+V1mod n后發送給站點S2；

……

從站點 Sl接收 V = R +Vjmod n，計算 R +Vjmod n =（Vj+V）mod n后發送給站點；

……

站點Ss重復步驟4后，發送給Sl；

Sl-R后得到結果輸出。

三 安全積模型（Secure Multiplication）

通過計算各站點子項集的向量標量積確定頻繁項集，引入隨機向量，使用代數方法計算確定頻繁項集。如果x1, x2, …, xm屬于X站點，y1, y2, …, yn屬于Y站點，則要構造向量和…，通過計算和的向量積以確定 {x1, x2, …, xm, y1, y2, …, yn} 是否是頻繁的，實現基于關聯規則的安全積模型。

在垂直分布式數據中，基于SMC方法，文獻 [63] 提出了在半信任第三方服務器上，采用標量積協議的保持隱私的ID3算法。文獻 [64]提出使用同態加密的方法計算屬性的信息增益，通過比較信息增益生成決策樹。文獻 [65] 基于標量積和xln（x）協議的隱私保持C4.5算法，實現基于分類的安全積模型。

輸入：站點A有=（x1, x2, …, xn），站點B有=（y1, y2,…, yn）

輸出：站點A、B均獲得

算法：

（1）A、B站點共同產生隨機矩陣C

（2）站點A

1．產生維向量R

2. X′ = C×R, X″=X+X′

3. X″發送到站點B

（3）站點B

1. S′ =xi″×yi

2. Y′=×Y

3. S′和Y′發送到站點A

（4）站點A

1. S″ =Y′×Ri

2. S=S′-S″

3. S發送到站點B

四 安全交集模型（Secure Intersection）

文獻 [18] 提出在水平分布式數據實現隱私保護數據挖掘要分別計算各站點的置信度（Confidence）和支持度（Support）。首先使用可交換加密算法，計算全局候選集；其次計算候選集全局支持度；最后基于SMC中的Secure SUM技術和Secure-Union技術實現累加后判斷其是否屬于頻繁項集。這種與加密技術結合的方法，實現了信息共享的最小化，在挖掘的同時增加的開銷任務較小，實現基于關聯規則的安全交集模型。

輸入：s個參與方，各參與方數據Vi（i∈ [1, s]），各參與方生成公鑰（Ei, Di）

輸出：V1∩V2∩…∩Vs

算法：

M=Vi
for s-1 steps do
  M′ = newarray[ M ], j=0
  for each X ∈M do
    M′[j ++]= encrypt（X, Ei）
  end for
  隨機變換M′順序，發送到Simod k
end for
M′ = newarray[ M ], j=0
for each X ∈ M do
  M′[j ++]= encrypt（X, Ei）
end for
隨機變換M′順序，發送到Si mod 2
輸出M

五 安全并集模型（Secure Union）

文獻[60—66]給出了基于Pohlig -Hellman加密的安全并集模型算法，Pohlig-Hellman加密理論主要有以下兩個定理支持：

定理2-1 EKi1（…EKin（M）…）= EKj1（…EKjn（M）…）

定理2-2 ?M1∈M, ?M2∈M，且M1≠M2，對給定的k, ε＜，則有Pr（EKi1（…EKin（M1）…）= EKj1（…EKjn（M2）…））＜ ε

輸入：s個參與方，各參與方數據Vi（i∈ [1, s]），各參與方生成符合定理2.1的密鑰（Ei, Di）

輸出：V = V1∪V2∪…∪Vs

算法：

令V=Ф

各站點加密各自數據Ei（Di）

for i=1 to s

V = V∪Ei（Di）

end for

消除V中的重復項

各站點解密Di（V）

輸出V