? 多方安全計(jì)算的底層技術(shù)

以姚期智在1982年給出的百萬(wàn)富翁問(wèn)題和解決方案為引子，此后的學(xué)者不斷受到啟發(fā)，擴(kuò)展出了更多的基于密碼學(xué)算法的應(yīng)用協(xié)議和框架，滿足讓多方安全地完成任意計(jì)算任務(wù)。

自1986年姚期智提出第一個(gè)通用的多方安全計(jì)算框架（常被稱為Yao’s Garbled Circuit，姚氏混淆電路）以來(lái)，30多年間已經(jīng)有BMR、GMW、BGW、SPDZ等多種多方安全計(jì)算協(xié)議陸續(xù)被提出。至今，每年仍有大量的研究工作在改進(jìn)和優(yōu)化這些多方安全計(jì)算框架。

這些通用的多方安全計(jì)算框架都是從兩方、三方的簡(jiǎn)單場(chǎng)景中衍生而來(lái)的，基于的是幾個(gè)最關(guān)鍵的底層密碼學(xué)協(xié)議或框架，主要包含不經(jīng)意傳輸（Oblivious Transfer，簡(jiǎn)稱OT）、混淆電路（Garbled Circuit，簡(jiǎn)稱GC）、秘密分享（Secret Sharing，簡(jiǎn)稱SS）等。主流的兩方安全計(jì)算主要采用不經(jīng)意傳輸和混淆電路這兩種密碼學(xué)技術(shù)，而更通用的多方安全計(jì)算涉及不經(jīng)意傳輸、混淆電路、秘密分享等多種密碼學(xué)技術(shù)。接下來(lái)我們對(duì)這三個(gè)底層技術(shù)進(jìn)行介紹。

● 不經(jīng)意傳輸（OT）

不經(jīng)意傳輸也稱茫然傳輸，是一種基本的密碼學(xué)原語(yǔ)，可以在數(shù)據(jù)傳輸與交互過(guò)程中保護(hù)隱私。在OT協(xié)議中，數(shù)據(jù)發(fā)送方同時(shí)發(fā)送多個(gè)消息，而接收方僅獲取其中之一。發(fā)送方無(wú)法判斷接收方獲取了具體哪個(gè)消息，接收方也對(duì)其他消息的內(nèi)容一無(wú)所知。

最早的OT協(xié)議是在1981由Michael O.Rabin提出的，在Rabin的OT協(xié)議中，發(fā)送者Alice發(fā)送一條消息給接收者Bob，而Bob以1/2的概率接收到信息。在協(xié)議交互結(jié)束后，Alice并不知道Bob是否接收到了信息，而Bob能確信地知道自己是否收到了信息。顯而易見(jiàn)，這種模式并不具備落地的實(shí)用價(jià)值。

1985年，Shimon Even, Oded Goldreich和Abraham Lempel提出了更為實(shí)用的2選1OT協(xié)議。如圖2-1所示，在這種形式的不經(jīng)意傳輸模型中，Alice每次發(fā)兩條信息（m₀、m₁）給Bob, Bob提供一個(gè)輸入，并根據(jù)輸入獲得輸出信息。在協(xié)議結(jié)束后，Bob得到了自己想要的那條信息（m₀或者m₁），而Alice并不知道Bob最終得到的是哪條。值得注意的是，1988年，Claude Crépeau證明了Rabin的OT協(xié)議和2選1OT協(xié)議是等價(jià)的。

1986年，Brassard等人又將2選1OT協(xié)議擴(kuò)展為了N選1OT協(xié)議，其實(shí)現(xiàn)邏輯如圖2-2所示。

在多方安全計(jì)算應(yīng)用中，比如PSI、混淆電路等，一般需要執(zhí)行大量的OT協(xié)議來(lái)完成復(fù)雜的計(jì)算，效率問(wèn)題使得OT協(xié)議的實(shí)用價(jià)值并不高。1996年Beaver依據(jù)混合加密構(gòu)想提出了第一個(gè)OT擴(kuò)展協(xié)議，但這一協(xié)議需要計(jì)算復(fù)雜的偽隨機(jī)發(fā)生器，在實(shí)際中也不高效?；跀U(kuò)展的思想，Ishai等人在2003年提出將基礎(chǔ)的OT協(xié)議與隨機(jī)語(yǔ)言模型結(jié)合，通過(guò)少量基礎(chǔ)OT的計(jì)算代價(jià)和大量對(duì)稱加密操作來(lái)提高大量OT操作的效率，可以達(dá)到一分鐘執(zhí)行數(shù)百萬(wàn)次的OT協(xié)議，該協(xié)議可以同時(shí)滿足實(shí)用性和安全性需求，具有重要的意義，也得到了很廣泛的應(yīng)用。

● 混淆電路（GC）

混淆電路是一種將計(jì)算任務(wù)轉(zhuǎn)化為布爾電路并對(duì)真值表進(jìn)行加密打亂等混淆操作以保護(hù)原始輸入數(shù)據(jù)隱私的思路。利用計(jì)算機(jī)編程將目標(biāo)函數(shù)轉(zhuǎn)化為布爾電路后，對(duì)每一個(gè)門輸出的真值進(jìn)行加密，參與方之間在互相不掌握對(duì)方私有數(shù)據(jù)的情況下共同完成計(jì)算。最早的混淆電路是姚期智院士針對(duì)百萬(wàn)富翁問(wèn)題提出的解決方案，因此又稱為“姚氏混淆電路”。

GC協(xié)議的基礎(chǔ)是“電路”。根據(jù)計(jì)算理論，所有可計(jì)算的問(wèn)題都可以轉(zhuǎn)換為各個(gè)不同的電路，例如加法電路、比較電路、乘法電路等。因此，函數(shù)計(jì)算可以被規(guī)約為對(duì)電路的計(jì)算。

電路是由一個(gè)個(gè)門（gate）組成的，例如與門、非門、或門、與非門等。完成一個(gè)函數(shù)的計(jì)算，首先需要構(gòu)建一個(gè)由與門、或門、非門、與非門組成的布爾邏輯電路，每個(gè)門都包括輸入線和輸出線，布爾邏輯電路如圖2-3所示。

GC協(xié)議的關(guān)鍵是“混淆”，也就是對(duì)電路內(nèi)部所有的輸入和輸出都通過(guò)加密+打亂的方式進(jìn)行混淆，用加密的值的計(jì)算來(lái)代替明文的傳輸以達(dá)到計(jì)算雙方無(wú)法獲得對(duì)方的輸入值?；煜采w電路的所有環(huán)節(jié)，因此，以門為單位，每個(gè)門有一張對(duì)應(yīng)的真值表，如圖2-4所示。

為了計(jì)算門電路，Alice將輸入對(duì)應(yīng)的密鑰R_a,0或R_a,1發(fā)送給Bob；Bob和Alice執(zhí)行OT協(xié)議，Alice獲得Bob輸入對(duì)應(yīng)的密鑰R_b,0或R_b,1；Bob根據(jù)獲得的兩個(gè)密鑰對(duì)加密真值表的每一行嘗試解密，最終只有一行能解密成功，并提取相關(guān)的加密信息R_c,0或R_c,1；最后，Bob將計(jì)算結(jié)果返回Alice, Alice確定最終的計(jì)算結(jié)果。在以上過(guò)程中，Alice和Bob的交互仍然都是密文或隨機(jī)數(shù)。

由于混淆電路需要對(duì)每一位進(jìn)行電路門計(jì)算并且電路門數(shù)量巨大，導(dǎo)致計(jì)算效率較低。例如，計(jì)算AES加密算法大約需要30000個(gè)電路門，計(jì)算50個(gè)字符串大約需要250000個(gè)電路門。因此，研究者提出了一系列的電路優(yōu)化策略，還提出了新的混淆電路協(xié)議，包括由Goldreich等人提出基于秘密分享和OT協(xié)議的GMW編譯器，以及基于“Cut and Choose”[1]的適用于惡意模型的混淆電路等。

● 秘密分享（SS）

秘密分享也稱秘密分割或秘密共享，它給出了一種分而治之的秘密信息管理方案，原理是將秘密拆分成多個(gè)分片（share），每個(gè)分片交由不同的參與方管理。它源于經(jīng)典密碼理論，最早由Sharmir和Blakley在1979年分別基于拉格朗日插值多項(xiàng)式和線性幾何投影理論獨(dú)立提出。秘密分享一般用于兩方或多方計(jì)算中的算術(shù)計(jì)算場(chǎng)景。

秘密分享為存儲(chǔ)高敏感、高機(jī)密數(shù)據(jù)提供了良好的解決方案。對(duì)于敏感信息的存儲(chǔ)應(yīng)具備高機(jī)密性和高可靠性。如果采用單點(diǎn)存儲(chǔ)，則機(jī)密性提高的同時(shí)又難以抵抗內(nèi)部泄露帶來(lái)的風(fēng)險(xiǎn)，如果采用多備份存儲(chǔ)，則機(jī)密性又無(wú)法保障。

如圖2-5所示，秘密可以通過(guò)將超過(guò)一定門限數(shù)量的若干個(gè)分片重新組合進(jìn)行復(fù)原，但單一的分片無(wú)法獲取關(guān)于秘密的有效信息。因此，即使有參與者出現(xiàn)問(wèn)題，在一定數(shù)量范圍內(nèi)，秘密仍能完整恢復(fù)，從而有效地防止系統(tǒng)外敵人的攻擊和系統(tǒng)內(nèi)用戶的背叛。

同時(shí)，秘密分享還具有同態(tài)的特性。A和B兩個(gè)秘密被隨機(jī)分成多個(gè)碎片（X₁，X₂，…，X_n）和（Y₁，Y₂，…，Y_n），并分配到不同參與節(jié)點(diǎn)（S₁，S₂，…，S_n）中，每個(gè)拿到碎片節(jié)點(diǎn)的運(yùn)算結(jié)果再求和能夠重新構(gòu)造原始的秘密值。圖2-6給出了一個(gè)基于秘密分享的計(jì)算示例。這也是實(shí)現(xiàn)不交換原始數(shù)據(jù)，直接進(jìn)行計(jì)算的重要基礎(chǔ)。

目前，秘密分享的實(shí)現(xiàn)方案主要有以下幾個(gè)。

（1）（t，n）閾值密鑰分享方案。即將秘密分享給n個(gè)參與方，允許任意t個(gè)參與方將秘密數(shù)據(jù)解開(kāi)，但任何不多于t-1個(gè)參與方的小團(tuán)體都無(wú)法將秘密數(shù)據(jù)解開(kāi)。目的是利用n個(gè)共享中的至少t個(gè)共享之間的相互協(xié)作來(lái)控制某些重要任務(wù)，如導(dǎo)彈發(fā)射的控制、支票簽署等。

（2）多秘密分享方案。同時(shí)保護(hù)多個(gè)秘密，將不同的秘密和不同的授權(quán)子集聯(lián)系在一起。

（3）帶除名的秘密分享方案。n個(gè)用戶參與的秘密分享方案中如果有一個(gè)用戶不能信賴，則可將這個(gè)用戶除名，變成有n-1個(gè)用戶參與的秘密分享方案。