2.3 基于安全多方計(jì)算的安全機(jī)制

安全多方計(jì)算（MPC）是密碼學(xué)的一個(gè)子領(lǐng)域，目的是多個(gè)參與方協(xié)同地從每一方的隱私輸入中計(jì)算某個(gè)函數(shù)的結(jié)果，而不用將這些輸入數(shù)據(jù)展示給其他方。基于MPC，對于任何函數(shù)功能需求，我們都可以在不泄露除輸出以外的信息的前提下計(jì)算它。MPC最初針對的是一個(gè)安全兩方計(jì)算問題（即著名的“百萬富翁問題”）而被正式提出的。

定義2-12 百萬富翁問題 ^[289] 兩個(gè)百萬富翁都想比較到底誰更富有，但是又都不想讓別人知道自己有多少錢。如何在沒有可信的第三方的情況下解決這個(gè)問題？

該問題在1982年由姚期智教授提出^[289，290]，在1987年由Goldreich等人推廣至多方場景^[109]，如圖2-4所示。

當(dāng)前主要有三種常用的隱私計(jì)算框架，可以用來實(shí)現(xiàn)安全多方計(jì)算^[284，25]，它們分別是：秘密共享（Secret Sharing，SS）^[253，234]，不經(jīng)意傳輸（Oblivious Transfer，OT）^[110，154]，混淆電路（Garbled Circuit，GC）^[45，136]。

2.3.1 秘密共享

秘密共享（Secret Sharing或者Secret Splitting，中文又稱為密鑰共享）^[44，253]，最早由著名密碼學(xué)家Shamir和Blakley于1979年分別提出。秘密共享是現(xiàn)代密碼學(xué)領(lǐng)域的一個(gè)重要分支，是信息安全和數(shù)據(jù)保密的重要技術(shù)手段，也是安全多方計(jì)算和聯(lián)邦學(xué)習(xí)等領(lǐng)域的一個(gè)基礎(chǔ)應(yīng)用技術(shù)^[23]。

直觀來說，秘密共享就是指將要共享的秘密在一個(gè)用戶群體里進(jìn)行合理分配，以達(dá)到由所有成員共同掌管秘密的目的。秘密共享通過將原始秘密值A分割為隨機(jī)多份，比如分割為n份，記為A₁，A₂，· · ·，A_n，并將這些份（或稱共享內(nèi)容）分發(fā)給n個(gè)不同的參與方，從而隱藏秘密值的一種概念。第i個(gè)參與方只擁有部分的秘密值A_i。當(dāng)且僅當(dāng)足夠數(shù)量（比如至少t個(gè)）的秘密值組合在一起時(shí)，才能夠重新構(gòu)造被共享的秘密，而任意的t-1個(gè)秘密值都不能重構(gòu)原始數(shù)據(jù)。

定義2-13 （t，n） 門限秘密共享方案^[250，253] 對于數(shù)據(jù)集合A，有n個(gè)用戶集合（1，2，· · ·，n），一個(gè)（t，n）門限秘密共享方案包括分享（Share）和重構(gòu)（Reconstruct）兩個(gè)環(huán)節(jié)。

? 分享：分享是指借助一個(gè)算法M將原始數(shù)據(jù)m∈M拆分為n個(gè)部分（s₁，· · ·，s_n），并將它們分別下發(fā)給n個(gè)用戶。

? 重構(gòu)：重構(gòu)是指借助一個(gè)算法F從n個(gè)用戶中任意選取t個(gè)用戶的秘密值，構(gòu)成一個(gè)t元組，將這個(gè)t元組作為函數(shù)F的輸入，能還原原始數(shù)據(jù)m∈M。更一般地，對于任意的m ∈ M，對于任意的t個(gè)用戶集合（i₁，i₂，· · ·，i_t）?（1，2，· · ·，n），滿足：

這里的t也被稱為門限值。

當(dāng)前的秘密共享方案研究，就在于如何高效地構(gòu)造（t，n）門限秘密共享方案。這些方案包括算術(shù)秘密共享（Arithmetic Secret Sharing）^[77]、Shamir秘密共享（Shamir’s Secret Sharing）^[253]和二進(jìn)制秘密共享（Binary Secret Sharing）^[274]等多種方式。

? t=1：這是最簡單的形式，事實(shí)上，我們只需要將原始數(shù)據(jù)m∈M分發(fā)到n個(gè)用戶即可。

? t=n：有多種方式可以實(shí)現(xiàn)（n，n）門限，較為常用的一種方案是，將原始數(shù)據(jù)m∈M編碼為一個(gè)二進(jìn)制表示s，對于前n-1個(gè)用戶，任意生成和s長度相等的二進(jìn)制表示s_i，s_i就是第i個(gè)用戶的秘密值，對于第n個(gè)用戶，我們將其秘密值設(shè)置為

? t=k：這種方案的實(shí)現(xiàn)形式有很多，典型的實(shí)現(xiàn)包括Shamir的基于拉格朗日插值法的實(shí)現(xiàn)^[253]。Blakley的門限方案則是利用多維空間點(diǎn)的性質(zhì)建立的^[254]。有興趣的讀者可以查閱相關(guān)資料，這里不再詳述具體實(shí)現(xiàn)過程。

在秘密共享系統(tǒng)中，攻擊者必須同時(shí)獲得一定數(shù)量的秘密碎片才能獲得密鑰，這種共享系統(tǒng)提高了系統(tǒng)的安全性。另外，當(dāng)某些秘密碎片丟失或被毀時(shí)，利用其他的秘密份額仍然能夠獲得秘密，從而提高系統(tǒng)的可靠性。秘密共享的上述特征，使它在實(shí)際中得到了廣泛的應(yīng)用，包括通信密鑰的管理、數(shù)據(jù)安全管理、銀行網(wǎng)絡(luò)管理、導(dǎo)彈控制發(fā)射、圖像加密等^[23]。

此外，秘密共享沒有中心節(jié)點(diǎn)的概念，因此有助于聯(lián)邦學(xué)習(xí)的去中心化實(shí)現(xiàn)。文獻(xiàn)[51]提出了基于秘密共享的安全聚合機(jī)制，用于保護(hù)橫向聯(lián)邦學(xué)習(xí)系統(tǒng)里的梯度和模型參數(shù)信息。

2.3.2 不經(jīng)意傳輸

不經(jīng)意傳輸（Oblivious Transfer，OT）是由Rabin在1981年提出的一種兩方計(jì)算協(xié)議^[233]，被廣泛應(yīng)用于安全多方計(jì)算（MPC）等領(lǐng)域。

在不經(jīng)意傳輸中，發(fā)送方擁有一個(gè)“消息-索引”對（M₁，1），···，（M_N，N）。在每次傳輸時(shí)，接收方選擇一個(gè)滿足1≤i≤N的索引i，并接收M_i。接收方不能得知關(guān)于數(shù)據(jù)庫的任何其他信息，發(fā)送方也不能了解關(guān)于接收方i的選擇的任何信息。

接下來，我們給出“n個(gè)中取1”不經(jīng)意傳輸?shù)亩x。

定義2-14 “n個(gè)中取1”不經(jīng)意傳輸^[269] 設(shè)A方有一個(gè)輸入表（x₁，· · ·，x_n）作為輸入，B方有i∈1，···，n作為輸入。“n個(gè)中取1”不經(jīng)意傳輸是一種安全多方計(jì)算協(xié)議，其中，A不能學(xué)習(xí)到關(guān)于i的信息，B只能學(xué)習(xí)到x_i。

當(dāng)n=2時(shí)，我們得到了“2個(gè)中取1個(gè)”不經(jīng)意傳輸（1-out-of-2不經(jīng)意傳輸），“2個(gè)中取1個(gè)”不經(jīng)意傳輸對兩方安全計(jì)算是普適的^[140]。換言之，給定一個(gè)“2個(gè)中取1個(gè)”不經(jīng)意傳輸，我們可以執(zhí)行任何的安全兩方計(jì)算操作。

研究者已發(fā)表了許多不經(jīng)意傳輸?shù)臉?gòu)造方法，例如Bellare-Micali構(gòu)造^[46]、Naor-Pinka構(gòu)造^[215]、Hazay-Lindell構(gòu)造^[179]。

在實(shí)際應(yīng)用中，不經(jīng)意傳輸?shù)囊环N實(shí)施方式是基于RSA公鑰加密技術(shù)^[244，21]。舉例來說，“2個(gè)中取1個(gè)”不經(jīng)意傳輸?shù)囊粋€(gè)簡單的實(shí)施流程如下^[21]。

? 發(fā)送方生成兩對不同的公鑰和私鑰對，并公開這兩個(gè)公鑰，記這兩個(gè)公鑰分別為公鑰pk₁和公鑰pk₂。假設(shè)接收方希望收到消息m₁，但不希望發(fā)送方知道他想要收到的是消息m₁。接收方生成一個(gè)隨機(jī)數(shù)k，再用公鑰pk₁對k進(jìn)行加密，并傳給發(fā)送方。

? 發(fā)送方用他的兩個(gè)私鑰對這個(gè)加密后的k進(jìn)行解密，用私鑰sk₁解密得到k₁，用私鑰sk₂解密得到k₂。只有k₁是等于k的，k₂是一個(gè)無意義的數(shù)。不過，因?yàn)榘l(fā)送方不知道接收方加密k時(shí)用的是哪個(gè)公鑰，所以他并不知道解密出來的k₁和k₂中哪一個(gè)值才是真的k的值。

? 發(fā)送方把m₁和k₁進(jìn)行異或，把m₂和k₂進(jìn)行異或，并把兩個(gè)異或結(jié)果都發(fā)送傳給接收方。

? 接收方使用k與收到的消息進(jìn)行異或。接收方只能算出m₁，而無法推測出m₂。這是因?yàn)榻邮辗讲恢浪借€sk₂，從而推不出k₂的值，而且發(fā)送方也不知道接收方能算出哪一個(gè)消息。

? 接收方可以進(jìn)一步通過校驗(yàn)信息（checksum，例如CRC校驗(yàn)碼）來確定m₁是正確收到的消息。

2.3.3 混淆電路

混淆電路（Garbled Circuit，GC）是姚期智教授提出的安全多方計(jì)算概念^[22，289]。GC的思想是通過布爾電路的觀點(diǎn)構(gòu)造安全函數(shù)計(jì)算，使得參與方可以針對某個(gè)數(shù)值來計(jì)算答案，而不需要知道它們在計(jì)算式中輸入的具體數(shù)字。因?yàn)镚C的多方的共同計(jì)算是通過電路的方式實(shí)現(xiàn)的，所以這里的關(guān)鍵詞是“電路”。實(shí)際上，所有可計(jì)算問題都可以轉(zhuǎn)化為各個(gè)不同的電路，例如加法電路、比較電路、乘法電路等。而電路是由一個(gè)個(gè)門（gate）組成的，例如與門、非門、或門、與非門等。

混淆電路可以看成一種基于不經(jīng)意傳輸?shù)膬煞桨踩?jì)算協(xié)議，它能夠在不依賴第三方的前提下，允許兩個(gè)互不信任方在各自私有輸入上對任何函數(shù)進(jìn)行求值。由于與、或、非門組成的邏輯電路可以執(zhí)行任何計(jì)算，所以GC使用電路表示待計(jì)算函數(shù)。

GC的中心思想是將計(jì)算電路分解為產(chǎn)生階段和求值階段。兩個(gè)參與方各自負(fù)責(zé)一個(gè)階段，而在每一階段中電路都被加密處理，所以任何一方都不能從其他方獲取信息，但仍然可以根據(jù)電路獲取結(jié)果。GC由一個(gè)不經(jīng)意傳輸協(xié)議和一個(gè)分組密碼組成。電路的復(fù)雜度至少是隨輸入內(nèi)容大小的增大而線性增長的。

在GC發(fā)表后，GMW（Goldreich，Micali and Wigderson）三位學(xué)者將GC擴(kuò)展使用于多方，用以抵抗惡意的攻擊者^[110]。有關(guān)GC的更多信息，讀者可以參考文獻(xiàn)[283]。