基于Cut-and-Choose技術(shù)的安全多方計算

趙 川 徐 俊

1(濟南大學(xué)信息科學(xué)與工程學(xué)院 濟南 250022)2(山東省網(wǎng)絡(luò)環(huán)境智能計算技術(shù)重點實驗室(濟南大學(xué)) 濟南 250022)3(山東省軟件工程重點實驗室(山東大學(xué)) 濟南 250101)

隨著物聯(lián)網(wǎng)以及互聯(lián)網(wǎng)信息技術(shù)的不斷發(fā)展，數(shù)據(jù)正呈現(xiàn)急速增長的趨勢，動輒達到數(shù)百TB甚至數(shù)十至數(shù)百PB，標(biāo)志著大數(shù)據(jù)時代的來臨.同時，這一趨勢也推動了機器學(xué)習(xí)和人工智能研究的浪潮.人臉識別、疫情監(jiān)測、智慧醫(yī)療等應(yīng)用逐漸改變?nèi)祟惖纳a(chǎn)、生活方式.然而，在這些應(yīng)用背后，個人隱私數(shù)據(jù)被各類企業(yè)收集事件屢見不鮮，引起國內(nèi)外的廣泛關(guān)注.如何在確保用戶隱私和數(shù)據(jù)安全的情況下完成某項計算任務(wù)，是一項亟待解決的重要問題.

在密碼學(xué)研究中，安全多方計算(secure multi-party computation, MPC)是一種非常重要的密碼學(xué)原語，由Yao[1]在1982年首次提出.MPC能夠使各參與方聯(lián)合計算任意的功能函數(shù)(functionality)，而不暴露他們各自的私有輸入和輸出.具體地說，在MPC場景中，n個參與方Pi(i=1,2,…,n)希望對他們的私有數(shù)據(jù)xi聯(lián)合計算一個目標(biāo)函數(shù)F(x1,x2,…,xn)=(y1,y2,…,yn).在計算完成后，所有的參與方Pi應(yīng)獲得自己的相應(yīng)輸出yi，而不能獲取到其他任何信息.一個安全的MPC協(xié)議，能夠保證多個互不信任的參與方即使在面對某些參與方不誠實的行為時，也能確保誠實方輸出的正確性以及輸入的隱私性.目前，MPC已經(jīng)被應(yīng)用于統(tǒng)計數(shù)據(jù)分析[2]、郵件過濾[3]、云計算服務(wù)[4]和隱私保護機器學(xué)習(xí)[5]等領(lǐng)域.

1986年，Yao[6]提出了一個安全兩方計算協(xié)議，將要計算的目標(biāo)任務(wù)表示成布爾電路，并進一步構(gòu)造出混淆電路，允許雙方能夠基于各自的輸入對電路進行計算，同時不會向?qū)Ψ叫孤度魏嗡接行畔?然而，該協(xié)議只能抵抗半誠實敵手的攻擊，不能保證協(xié)議運行結(jié)果的正確性，也不能保證公平性(即一方可能在另一方獲得輸出之前掌握了自己的輸出，并提前終止協(xié)議).惡意敵手可以采取任何策略破壞協(xié)議從而獲得其期望的結(jié)果.為了抵抗這種攻擊，一種經(jīng)典的方法是采用零知識證明[7-8]來驗證協(xié)議中每一步執(zhí)行的正確性，從而確保參與方嚴(yán)格按照協(xié)議規(guī)定執(zhí)行.但是這種情況下，協(xié)議的效率十分低效.盡管文獻[9-10]提出了較為高效的解決辦法，然而并不適用于大規(guī)模的計算任務(wù).

一種更高效的方法是采用Cut-and-Choose技術(shù)來檢查混淆電路[11-14].在構(gòu)造電路時，電路構(gòu)造方Alice并不是生成1個混淆電路發(fā)送給計算方Bob，而是構(gòu)造s個混淆電路并發(fā)送給Bob.然后Bob對這些電路進行劃分，隨機選擇打開一部分電路作為檢查電路，并利用Alice發(fā)送的隨機種子(用于生成混淆電路)檢查這些打開的電路是否正確構(gòu)造.如果所有這些電路都是正確的，那么Bob將計算剩余的電路，獲得最終輸出.這種方法能夠迫使Alice正確生成混淆電路，否則Bob將以一定的概率知道Alice進行了欺騙，并終止協(xié)議.

在早期的工作當(dāng)中，這種Cut-and-Choose技術(shù)主要用于抵抗惡意敵手實現(xiàn)兩方的安全計算.此后，該技術(shù)也被用于實現(xiàn)隱蔽安全協(xié)議，但并沒有引起太多的關(guān)注.近年來，隨著研究者對于隱蔽敵手的持續(xù)研究，該方法或者基于該方法的思想也被廣泛應(yīng)用于實現(xiàn)公開可驗證的隱蔽安全協(xié)議，涌現(xiàn)出了一些代表性的工作.本文將就這種方法介紹其主要的研究進展以及最新的研究成果.值得指出的是，本文的總結(jié)基于前人工作的基礎(chǔ).特別地，文獻[15]對基于Cut-and-Choose技術(shù)的惡意兩方安全計算協(xié)議進行了詳細(xì)的總結(jié)和對比，文獻[16]在其工作中對Cut-and-Choose技術(shù)的研究進展也作了簡要介紹.與上述2篇文獻相比，本文所涵蓋的研究工作更廣、更新，重點對近幾年熱門的公開可驗證隱蔽模型相關(guān)工作進行了較為詳細(xì)的分析和總結(jié).

1 基礎(chǔ)知識

在介紹基于Cut-and-Choose技術(shù)的安全計算協(xié)議之前，我們首先介紹相關(guān)的基礎(chǔ)知識，包括安全模型的定義、茫然傳輸(oblivious transfer, OT)、混淆電路(garbled circuits, GC)、Cut-and-Choose.

1.1 安全模型

考慮到敵手的存在，MPC的設(shè)計目標(biāo)是，對于給定的目標(biāo)函數(shù)，一組互不信任的參與方只能獲得關(guān)于各自輸入數(shù)據(jù)的目標(biāo)函數(shù)的正確輸出，而不能掌握其他任何信息.一般地，根據(jù)敵手的行為，可以將MPC的安全模型分為4種:

1) 半誠實安全.在該安全模型中，被敵手腐化的參與方誠實地遵守協(xié)議規(guī)定，與誠實參與方共同完成某項計算任務(wù).但同時敵手可以根據(jù)其控制的參與方所收到的來自誠實參與方的消息，試圖通過觀察協(xié)議運行中所獲得的視圖來推斷出一些關(guān)于誠實參與方私有輸入的信息.通常，將這種敵手稱為半誠實敵手或者被動敵手，即此類敵手不會采取任何破壞協(xié)議的行為.盡管這是一種比較弱的安全概念，但在許多現(xiàn)實應(yīng)用場景中考慮此類安全模型仍是合理的.

2) 惡意安全.與半誠實敵手相反，在協(xié)議執(zhí)行過程中，惡意敵手(也稱為主動敵手)是十分活躍的，可以控制被腐化的參與方任意地偏離協(xié)議描述(如發(fā)送虛假消息、故意終止協(xié)議等)，從而破壞協(xié)議的安全性.這種能夠抵抗惡意敵手的安全模型提供了強大的安全保障，確保任何攻擊不會成功.

3) 隱蔽安全.盡管在許多現(xiàn)實場景中，半誠實安全模型是合理的，但是這種安全保障還是太弱.一般來說，如果敵手通過作弊獲得的收益遠(yuǎn)大于實際獲得的，那么它更愿意冒被抓的風(fēng)險而選擇作弊.而對于惡意安全模型，盡管具有很強的安全保證，但是效率太低.為了解決這些問題，隱蔽安全的概念被提出.隱蔽安全能保證如果敵手在執(zhí)行協(xié)議時有任何作弊行為，誠實參與方能夠以一定的概率發(fā)現(xiàn)敵手作弊.并且當(dāng)這個概率足夠大時，對那些企圖作弊而又害怕被抓的參與方具有一定的威懾作用，從而能夠在一定程度上阻止作弊行為的發(fā)生.

4) 公開可驗證的隱蔽安全.在隱蔽安全模型中，參與方可以任意偏離協(xié)議描述，但會以一定的概率被抓住.這種安全保證比半誠實模型更強.同時，隱蔽安全模型下所設(shè)計的協(xié)議比惡意安全協(xié)議更易于實現(xiàn)，也更高效.然而，隱蔽安全模型仍然有些弱，因為其只對本次協(xié)議執(zhí)行中的敵手具有威懾力.當(dāng)誠實參與方發(fā)現(xiàn)敵手的作弊行為后，可以立刻終止協(xié)議來避免損失.但是敵手可以繼續(xù)選擇與其他參與方(如另外一家企業(yè))合作，并試圖作弊且有可能作弊成功.因此，Asharov等人[17]提出了具有公開可驗證的隱蔽(publicly verifiable covert, PVC)安全模型.在PVC模型中，當(dāng)作弊行為被發(fā)現(xiàn)時，誠實的參與方可以在不泄露私有信息的情況下，公開一份證書用來證實敵手的作弊行為.任何第三方可以檢查該證書的有效性.若有效，則會嚴(yán)重影響敵手的聲譽，使其失去進一步與其他參與方合作計算的可能.這種公開可驗證性極大地增強了隱蔽安全模型的安全性.

1.2 茫然傳輸

茫然傳輸(OT)是安全多方計算中的一個基本原語，涉及2個參與方，對安全協(xié)議的研究具有重要的作用.本節(jié)我們介紹標(biāo)準(zhǔn)的1-out-of-2 OT.發(fā)送方Alice擁有2個私有字符串x0，x1；接收方Bob通過自己的選擇比特b∈{0,1}，選擇2個字符串中的1個.在傳輸完成以后，Bob將獲得xb，而不會知道另一個字符串x1-b.同時Alice不會收到任何輸出，并且無法知道Bob獲得了哪一個字符串.該過程的形象描述如圖1所示：

Fig. 1 Illustration of OT圖1 OT示意圖

更正式地說，1-out-of-2 OT可以寫成如下理想功能函數(shù)FOT，如圖2所示：

功能函數(shù)OT該功能函數(shù)在發(fā)送方Alice和接收方Bob之間運行.輸入: ① Alice輸入x0,x1∈{0,1}κ,κ表示字符串的長度; ② Bob輸入一個選擇比特b∈{0,1}.輸出: ① Bob輸出xb; ② Alice不會獲得任何輸出.

1.3 混淆電路

1986年Yao[6]基于混淆電路和OT構(gòu)造了一個通用的安全兩方計算協(xié)議，稱為Yao協(xié)議.盡管該協(xié)議通信復(fù)雜度較高，但是其通信輪數(shù)是常數(shù)，與電路的深度無關(guān).目前許多MPC協(xié)議都是基于姚氏混淆電路構(gòu)造的.

考慮到任意多項式時間內(nèi)可計算的功能函數(shù)都可以表示成一個布爾電路，在Yao協(xié)議[6]中，首先將目標(biāo)函數(shù)F表示成布爾電路C.然后由電路構(gòu)造方Alice對電路的每一個門進行混淆，即將該門對應(yīng)的真值表(有4種可能的結(jié)果)進行加密并打亂順序(稱之為混淆表)，并逐層組合，實現(xiàn)對整個電路C的混淆.最后讓計算方Bob逐層計算每個混淆電路門，完成混淆電路C的計算，從而獲得函數(shù)F的輸出.

具體地說，對于電路C中的每條導(dǎo)線w，讓Alice生成2個密鑰k0，k1(又稱為標(biāo)簽)，分別對應(yīng)w上2個可能的值0和1.在執(zhí)行過程中，根據(jù)Alice和Bob的輸入，每條導(dǎo)線將與具體的明文值和相應(yīng)的密鑰有關(guān).計算方Bob只知道密鑰，而不會知道相應(yīng)的明文值.例如，對于電路中的一個“AND”門G，如圖3所示，有2條輸入線wx，wy以及1條輸出線wz.wx，wy上的輸入分別為u,v(u,v∈{0,1})，wz上的輸出為t∈{0,1}.

Fig. 3 AND gate圖3 AND門

Table 1 Garbled AND Gate表1 混淆AND門

通過對每一個電路門進行表1所示的混淆操作，并逐層組合(前一個門的輸出是后一個門的輸入)，Alice最終能夠獲得電路C的混淆版本GC.Alice將混淆電路以及自己輸入所對應(yīng)的密鑰值發(fā)送給Bob.隨后，Alice和Bob運行OT協(xié)議，茫然地將Bob的輸入所對應(yīng)的密鑰傳輸給Bob.有了每條電路輸入線上的密鑰值，Bob就可以對混淆電路進行逐層解密，最后獲得電路輸出線上的密鑰，并通過查找表將獲得的密鑰映射到真實的輸出值.

1.4 Cut-and-Choose技術(shù)

Yao協(xié)議[6]是使用最廣泛的MPC協(xié)議之一.但是該協(xié)議只能實現(xiàn)半誠實安全，不能抵抗惡意敵手的攻擊.例如，Alice為了獲取Bob的信息，可以選擇發(fā)送錯誤的混淆電路給Bob.經(jīng)典的解決方案是采用GMW編譯器[7]的方式，利用零知識證明迫使?jié)撛诘膼阂鈪⑴c方誠實執(zhí)行協(xié)議.Alice需要使用零知識證明以證明構(gòu)造的混淆電路的正確性[7,18].但一般而言，零知識證明需要用到大量的公鑰操作，非常低效.另一種實現(xiàn)惡意安全的方法是采用“MPC-in-the-head”技術(shù)[19-21]，參與方通過模擬一個虛擬的誠實方大多數(shù)的多方協(xié)議來保證安全性[21-22].由此設(shè)計出來的協(xié)議具有漸進的復(fù)雜度，但協(xié)議整體的效率依賴于被模擬的安全多方協(xié)議和模擬該多方協(xié)議的半誠實協(xié)議，并且目前還沒有任何實例給出這種方法在實際應(yīng)用中具體的時間復(fù)雜度[14].Lindell等人[23]提出將SPDZ協(xié)議[24]作為外部協(xié)議生成混淆電路，但沒有給出實例化的方案.Nielsen等人[25]通過為各參與方持有的秘密信息份額添加信息論安全的MAC以實現(xiàn)認(rèn)證通過的AND門和OT協(xié)議，從而防止不誠實的參與方進行作弊，由此設(shè)計出通信復(fù)雜度與電路深度成正比的TinyOT協(xié)議.

為了能夠有效抵御惡意敵手的攻擊，同時提高協(xié)議的效率，基于Cut-and-Choose技術(shù)被提出[8].該技術(shù)主要用于安全兩方協(xié)議，確保其中一方此前收到的來自另一方的消息是遵循協(xié)議規(guī)范正確構(gòu)造的.早期工作中這種方法也被廣泛與交互式證明[26]、零知識協(xié)議[26-28]、證據(jù)不可區(qū)分以及證據(jù)隱藏協(xié)議[29]進行結(jié)合.其主要思想是，一方在協(xié)議執(zhí)行過程中對發(fā)送的消息生成多個副本，另一方通過隨機選擇其中一部分進行檢查保證消息的正確性.一旦檢查通過，剩余的消息將參與協(xié)議的后續(xù)階段.這種思想最早可以追溯到文獻[30]，用于盲簽名的實現(xiàn).該技術(shù)應(yīng)用于混淆電路的具體過程為：

1) Alice首先選取s個隨機種子，利用這些種子生成s份獨立的混淆電路GC，每一個電路用于表示相同的目標(biāo)函數(shù)F，其中s稱為電路復(fù)制因子.然后Alice將所有的電路和與其輸入線相關(guān)的密鑰發(fā)送給Bob.

2) Bob隨機選取一部分電路I?{1,2,…,s}，作為檢查電路.對于每一個電路j∈I，Bob要求獲取Alice的隨機種子seedj，從而得到電路中每條線上的2個密鑰(分別對應(yīng)數(shù)值0和1)，用于打開電路GCj進行檢查，驗證GCj是否構(gòu)造正確，即GCj是否是電路C的正確混淆版本.

① 如果所有的電路構(gòu)造正確，Bob按照Yao協(xié)議[6]獨立地計算I以外的剩余電路(稱為計算電路).

② 如果至少有一個電路是錯誤的，那么Bob知道Alice是不誠實的.考慮到讓Bob直接終止協(xié)議可能會帶來安全性問題，不同的方案中規(guī)定Bob此時會有不同的處理，我們將在后續(xù)章節(jié)進行詳細(xì)介紹.

Cut-and-Choose技術(shù)能夠有效抵御惡意的Alice構(gòu)造錯誤的電路，即Alice作弊會以很高的概率被Bob檢測到，但該方法同時也引入了2個重要的安全性問題——輸入一致性問題以及選擇失敗攻擊問題.參與方可以在不同的混淆電路中提供不同的輸入，獲取不同的輸出，從而推斷出與對方輸入數(shù)據(jù)相關(guān)的信息.此外該方法并不能確保所有未被打開的電路是正確的，因為每一個電路都是以1/2的概率被檢查.Bob可能從計算電路中獲得多個不一致的輸出，這種情況下它將知道Alice在作弊.如果Bob選擇終止協(xié)議，可能會泄露信息，因為Alice可以事先猜測Bob在OT協(xié)議時的輸入故意使用錯誤的密鑰(選擇失敗攻擊).例如，在OT協(xié)議執(zhí)行中，Alice使用正確的密鑰值作為Bob輸入第1位為0所對應(yīng)的消息，而使用一個與混淆電路中真實使用的密鑰不同的隨機數(shù)作為Bob輸入為1所對應(yīng)的消息.之后Alice通過觀察發(fā)現(xiàn)如果Bob沒有終止協(xié)議，則說明Bob的第1位輸入為0；若其終止了協(xié)議，則說明Bob的輸入為1.

為了解決這個問題，一般將計算電路的大多數(shù)輸出值作為最終的計算結(jié)果.此時，如果所有的檢查電路都是正確的并且大多數(shù)計算電路是錯誤的，那么認(rèn)為Alice作弊成功.在基于Cut-and-Choose技術(shù)設(shè)計MPC協(xié)議時，如果Alice成功作弊的概率可以忽略(即達到統(tǒng)計安全級別2-40)，我們就認(rèn)為該協(xié)議是安全的，通常達到統(tǒng)計安全級別與s的選取、被檢查的電路個數(shù)以及每個電路被檢查的概率與策略有關(guān).

與使用零知識證明(低效的非對稱操作)實現(xiàn)惡意安全相比，Cut-and-Choose技術(shù)可以有效提高協(xié)議的效率.同時，從協(xié)議整體運行時間以及目標(biāo)函數(shù)表示成布爾電路等情況出發(fā)，在混淆電路上進行Cut-and-Choose技術(shù)依然是抵御惡意敵手的最有效方式.值得注意的是，近年來，Wang等人[31]提出了一種新型高效的構(gòu)造惡意安全協(xié)議的方法Authenticated-GC，只需要構(gòu)造一個經(jīng)過認(rèn)證的混淆電路，就可以完成對目標(biāo)任務(wù)的計算，并且具有常數(shù)輪復(fù)雜度.之后在2018年，他們又提出了優(yōu)化方案[32]，進一步提高了通信效率.

鑒于Cut-and-Choose技術(shù)在惡意敵手場景中具有良好的表現(xiàn)，因此，早期大部分的工作將該方法應(yīng)用于惡意兩方安全計算，但是完全的惡意安全模型難以實現(xiàn)、效率低.此后，相繼有相關(guān)工作在隱蔽模型下使用Cut-and-Choose技術(shù)，但是沒有引起太多關(guān)注.而隨著近年來研究者對隱蔽敵手的深入研究，許多結(jié)合Cut-and-Choose技術(shù)實現(xiàn)PVC模型的優(yōu)秀工作不斷涌現(xiàn).下面，我們將從Cut-and-Choose技術(shù)分別應(yīng)用于惡意模型、隱蔽模型以及PVC模型3個不同的場景對相關(guān)領(lǐng)域的研究工作進行介紹.

2 基于Cut-and-Choose技術(shù)的惡意安全協(xié)議

在利用Cut-and-Choose技術(shù)抵御惡意敵手時，一個主要的挑戰(zhàn)是如何最大程度將電路復(fù)制因子s降低，從而用更少的混淆電路來達到概率為2-40的統(tǒng)計安全級別.如1.4節(jié)所述，一種經(jīng)典的做法是讓計算方Bob計算多個電路，并取電路計算結(jié)果中占大多數(shù)的輸出值作為最終輸出.后來又涌現(xiàn)了許多工作對這一做法作出改進，設(shè)計了多種不同的安全協(xié)議.我們把這些相關(guān)的工作分為4類：

1) MajorityCut.根據(jù)所選擇的計算電路，讓Bob將所有計算電路輸出值中的大多數(shù)結(jié)果作為最終的輸出，使得Alice只能夠以可忽略的概率成功作弊，從而保證協(xié)議輸出的正確性.

2) SingleCut.在所有未打開的計算電路中，即使只有一個計算電路是正確的，也能夠保證Bob可以獲得正確的協(xié)議輸出.

3) BatchedCut.這種方法將Cut-and-Choose技術(shù)應(yīng)用于多個安全計算實例中，即參與雙方通過不同的輸入安全地計算目標(biāo)函數(shù)F多次，在每次安全計算中，要求電路構(gòu)造方Alice構(gòu)造多個混淆電路以應(yīng)用Cut-and-Choose技術(shù)，保證電路正確的同時又能夠獲得良好的分?jǐn)傂?

4) Gate-LevelCut.與將Cut-and-Choose技術(shù)應(yīng)用到整個電路不同，這種方法在電路的門上進行Cut-and-Choose技術(shù).Alice生成許多個混淆門并發(fā)送給Bob，然后Bob要求Alice打開一部分混淆門進行檢查；檢查通過后，Bob由剩余未打開的混淆門構(gòu)造出要計算的目標(biāo)電路.

下面我們詳細(xì)介紹4種方法相關(guān)的研究成果.

2.1 MajorityCut

為了避免低效的零知識證明操作，同時又能夠抵抗惡意敵手的攻擊，Pinkas[8]將Cut-and-Choose技術(shù)引入到基于混淆電路的安全兩方計算中，并通過盲簽名[33]和定時承諾[34]來保證協(xié)議的公平性.在該方案中，要計算的目標(biāo)函數(shù)F(x,y)=(FAlice(x,y),FBob(x,y))，F(xiàn)Alice(x,y)表示Alice的輸出，Bob的輸出為FBob(x,y).Alice首先為目標(biāo)函數(shù)構(gòu)造一部分混淆電路，并連同承諾過的輸入線上的密鑰一起發(fā)送給Bob.為防止Alice惡意構(gòu)造錯誤的電路，Bob隨機選擇一半電路，要求Alice打開對應(yīng)這些電路的每一條輸入線的2個密鑰(對應(yīng)0和1)的承諾以及對隨機數(shù)k的承諾(k用于決定混淆表中輸出結(jié)果的位置).根據(jù)這些信息，Bob可以驗證這些打開的電路能否正確地計算目標(biāo)函數(shù)，若這些電路中有任何一個是錯誤的，則Bob終止協(xié)議.一旦驗證通過，Bob可以對剩余的電路進行計算，將計算電路中占大多數(shù)的輸出結(jié)果返回給Alice.同時為了防止Bob發(fā)送錯誤的輸出結(jié)果給Alice(反之亦然)，導(dǎo)致協(xié)議的不公平性，文獻[8]要求雙方基于另一方的密鑰對各自獲得的輸出結(jié)果進行承諾，并采用盲簽名驗證所承諾的內(nèi)容的正確性來解決這一問題.與基于零知識證明的工作相比，由于混淆電路的檢查和計算都是高效的對稱加密，因此利用Cut-and-Choose技術(shù)可以有效地提升協(xié)議的效率[15].

2006年Kiraz等人[35]指出，盡管文獻[8]可以保證協(xié)議輸出的公平性，但仍然是不安全的，在OT協(xié)議執(zhí)行過程中容易遭受選擇失敗攻擊(如1.4節(jié)所述).而為了抵抗這種攻擊，他們提出采用committed OT技術(shù)，保證任何試圖使用錯誤信息代替OT協(xié)議正確輸入的行為都將會被Alice發(fā)現(xiàn)而終止協(xié)議.然而，與標(biāo)準(zhǔn)OT相比，committed OT的效率比較低.

同年，文獻[36]基于Pedersen承諾提出了2種不同的解決方案以克服Fairplay協(xié)議[37]存在的缺陷，即一方作弊而不被發(fā)現(xiàn)，例如Alice可以通過改變1-out-2-of OT協(xié)議的2個輸入密鑰的順序進行攻擊.但是該工作要求只有Bob可以獲得輸出，并且Alice依然可以在OT協(xié)議中故意構(gòu)造錯誤的輸入來獲取Bob的隱私信息.此外，由于采用大量的承諾操作來保證Alice對于不同的電路使用相同的輸入，這項工作的通信代價過高，需要傳輸承諾的數(shù)量為O(n2s+|C|s)，n是電路C的輸入長度，|C|是電路的大小.后來在2007年歐密會上，Woodruff[38]對此進行了改進，將通信開銷降至O(|C|s).

同年，Lindell等人[11]指出將Cut-and-Choose技術(shù)和Yao協(xié)議[6]簡單地結(jié)合并不一定能得到一個惡意安全的協(xié)議.于是，在他們的工作中，合理地結(jié)合兩者實現(xiàn)了高效的惡意兩方安全計算協(xié)議，與半誠實的Yao協(xié)議[6]幾乎具有相同的計算開銷，并基于理想/現(xiàn)實模擬范例給出了完整的安全證明.他們將Cut-and-Choose技術(shù)應(yīng)用于整個電路以及輸入(用于保證Alice輸入的一致性)，并選擇打開一半的電路進行檢查，如圖4所示.在這種情況下，惡意的Alice成功欺騙Bob接受一個錯誤輸出的概率為2-s/17.因此他們的協(xié)議至少需要構(gòu)造680個混淆電路實現(xiàn)概率為2-40的統(tǒng)計安全.另一方面，由于需要發(fā)送O(sn2)個承諾，n是Bob的輸入長度，這項工作的通信開銷過高.

Fig. 4 Overview of reference [11] protocol圖4 文獻[11]協(xié)議的簡要描述

Cut-and-Choose技術(shù)功能函數(shù)ccot該功能函數(shù)在發(fā)送方Alice和接收方Bob之間運行.輸入: ① Alice輸入一個向量x={(x0i,x1i)}si=1; ② Bob輸入σ1,σ2,…,σs以及大小為s∕2的集合P,P?{1,2,…,s}.輸出: ① 對每個j∈P,Bob獲得(x0j,x1j); ② 對每個j?P,Bob獲得xσjj; ③ Alice不會獲得任何與σ1,σ2,…,σs以及集合P有關(guān)的信息.

簡單地說，對于所有的檢查電路中Bob的每條輸入線，Bob可以得到密鑰對中的全部2個密鑰；而在計算電路中，Bob只獲得與其選擇比特σ相對應(yīng)的密鑰.利用該原語，文中將抵抗選擇失敗攻擊與電路檢查這2部分進行了融合，在有效檢測敵手是否作弊的同時降低了協(xié)議通信復(fù)雜度.進一步，他們的工作放棄對電路的承諾，通過適當(dāng)增加指數(shù)運算(需要O(sn)次模冪操作)，減少了通信代價，并結(jié)合高效的零知識證明以驗證Diffie-Hellman元組，將輸出錯誤的概率降到了2-0.311s，與文獻[11]相比，該方案只需要構(gòu)造128個混淆電路就可以保證協(xié)議輸出的正確性.但與文獻[11,39]中抵抗選擇失敗攻擊的方法相比，Cut-and-Choose OT效率并不具有優(yōu)勢.

文獻[13]則通過檢查60%的電路進一步地將這個概率減小到了2-0.32s.同時，該項工作還指出，假設(shè)計算電路和檢查電路開銷相同，為了獲得2-ρ的統(tǒng)計安全(ρ是統(tǒng)計安全參數(shù))，至少需要ρ≈3s個電路.這意味著，對于2-40的錯誤概率，仍然需要構(gòu)造125個電路.如果電路的規(guī)模巨大，協(xié)議依舊會比較低效.

2017年趙川等人[40]指出文獻[14]基于Cut-and-Choose OT設(shè)計的安全兩方計算協(xié)議由于密鑰的傳輸被分割成幾個階段，導(dǎo)致參與方之間的交互依然復(fù)雜，不易理解和應(yīng)用.因此，他們提出了雙向Cut-and-Choose OT，要求Alice增加2個輸入字符串，以賦予Alice主動選擇權(quán)，而不是僅僅輸入密鑰對等待Bob進行選擇.Alice可以通過1個比特決定Bob接收其輸入的2個密鑰中的哪一個，同時Bob依然能夠根據(jù)其指示比特j決定獲得1個密鑰還是2個密鑰.這種雙向性使得所有的密鑰可以在同一階段全部傳輸完成，顯著地降低了Alice和Bob之間的交互輪數(shù).為了與文獻[14]中的單向OT協(xié)議進行更加直觀的比較，考慮上述雙向OT協(xié)議批處理的版本，通過功能函數(shù)Fccbot進行表述，如圖6所示：

Cut-and-Choose Bilateral OT功能函數(shù)ccbot該功能函數(shù)在發(fā)送方Alice和接收方Bob之間運行.輸入: ① Alice輸入向量x={(x0i,x1i),(y0i,y1i),bi,τi}si=1,bi是置換比特,bi∈{0,1},τi是選擇比特,τi∈{0,1}; ② Bob輸入σ1,σ2,…,σs以及集合P,P?{1,2,…,s}.輸出: ① 對每個j∈P且j=1,Bob獲得{(xbij,x1-bij),1-bi,(y0i,y1i)}; ② 對每個j?P,Bob獲得(xτjj,yσjj,τj⊕bj),τj⊕bj指示xτjj的位置; ③ Alice不會獲得任何與σ1,σ2,…,σs以及集合P有關(guān)的信息.

2.2 SingleCut

在MajorityCut方法中，總是選取一定數(shù)量的電路進行檢查(如s/2)，根據(jù)檢查電路和計算電路的劃分，以及接受計算電路輸出的大多數(shù)結(jié)果，能夠?qū)阂獾腁lice成功作弊的概率降到2-ks，k∈(0,1].然而，與此同時，該方法要求Alice必須向Bob證明在所有的計算電路中其提供了相同的輸入，由此帶來了額外的開銷.

在2013年美密會上，Lindell[41]對文獻[14]提出的Cut-and-Choose OT進行了改進，允許Bob以1/2的概率獨立地檢查任意數(shù)量的電路而不是選取一半的電路打開檢查.他的這項工作在僅構(gòu)造s個混淆電路的情況下，就能保證敵手成功作弊的概率為2-ρ，打破了文獻[13]指出的至少需要3s個電路的限制.即對于2-40的錯誤概率，該工作只需要構(gòu)造40個電路.其背后思想是：當(dāng)且僅當(dāng)所有打開的電路都是正確的且所有的計算電路都是錯誤的時候，Alice才可以作弊成功.

具體而言，他將整個協(xié)議的構(gòu)造分為2個階段進行.在第1階段，電路構(gòu)造方Alice首先生成s個混淆電路，每個電路以1/2的概率被獨立地選擇作為檢查電路或計算電路.令x1,x2分別是Alice和Bob的輸入，對于所有的計算電路，如果Bob計算得到同樣的輸出F(x1,x2)，那么Bob將F(x1,x2)存儲在本地；否則，根據(jù)事先約定，Alice為所有電路中的輸出線分配相同的輸出密鑰，因此Bob可以在本地存儲一個“proof”，用于證明2個計算電路的不同輸出——同一輸出線上對應(yīng)2個不同的輸出密鑰.

在第2階段，參與雙方安全地計算一個“懲罰函數(shù)”.如果Bob接收到的輸入不一致，則其將“proof”作為輸入，通過“懲罰函數(shù)”，Bob將獲得Alice的真實輸入，從而在本地再次計算電路獲得輸出.否則，Bob將F(x1,x2)以及一個隨機數(shù)作為輸入，在這種情況下，Bob不會從懲罰函數(shù)的計算中收到任何有用信息.注意這里之所以讓Bob即便在沒有獲得“proof”的情況下依然需要和Alice運行“懲罰函數(shù)”，是因為如果2種情況下Bob的行為有區(qū)別，則Alice完全可以得知Bob是否在不同的計算電路中獲得了不同的輸出，而這樣是會泄露Bob的輸入信息的.

同年，另一項工作[42]基于文獻[43]中兩方對稱構(gòu)造混淆電路的思想，提出使用對稱Cut-and-Choose技術(shù)來抵抗惡意敵手的攻擊.在這項工作中，要求每一方構(gòu)造s個混淆電路，由另一方檢查部分混淆電路的正確性，一旦檢查通過，雙方計算各自的剩余電路，然后根據(jù)計算結(jié)果，決定電路的最終輸出值.進一步地說，對于混淆電路中某一條輸出線，如果一方在其生成的至少一個計算電路的輸出線上獲得輸出v，并且另一方的計算電路中也存在這種情況，那么該參與方在這條輸出線上的最終輸出就是v.這種情況下，由于一方是誠實的，其構(gòu)造的所有電路都是正確的，此時只要另一參與方提供的計算電路中至少有一個是正確的，就能保證目標(biāo)電路的正確性.當(dāng)檢查s/2個電路時，該工作確保敵手僅能以2-s+O(log s)的概率成功作弊.然而，由于每一方都需要構(gòu)造混淆電路，在協(xié)議中被發(fā)送的電路數(shù)量是以往工作的2倍.

此外文獻[44-45]分別采用不同的方法，同樣保證了只需要s個電路，就能將輸出錯誤的概率降到2-s.這些工作均確保不誠實的Alice只有在所有的計算電路不正確的情況下，才能破壞協(xié)議的安全性.

2.3 BatchedCut

Cut-and-Choose技術(shù)引入的開銷主要與構(gòu)造以及發(fā)送的混淆電路數(shù)量有關(guān).通過2.2節(jié)的方法，盡管只需要構(gòu)造s個混淆電路就能將敵手成功作弊的最大概率限制為2-s，但如果要計算的電路規(guī)模巨大，發(fā)送s個混淆電路，仍然會帶來不小的開銷.并且在實際應(yīng)用中，往往需要雙方共同參與某項計算任務(wù)多次，而每次只是輸入不同.此時，如果每次仍然繼續(xù)構(gòu)造s個混淆電路以保證計算的正確性，不僅需要生成大量的電路，并且是不高效的.因此，BatchedCut方法被提出.其基本思想是首先由Alice生成一些電路，經(jīng)Bob選擇打開其中一部分進行檢查后，Bob將剩余的電路隨機組合分成若干組.每組中的電路用于執(zhí)行一次協(xié)議，這樣在若干次執(zhí)行(具有不同的輸入)以后，由于全部的電路可以分?jǐn)偟矫看螆?zhí)行當(dāng)中(每次計算需要構(gòu)造的混淆電路數(shù)量將小于s)，因此，這種方法可以有效地分?jǐn)侰ut-and-Choose技術(shù)帶來的開銷.

Huang等人[47]結(jié)合“LEGO” Cut-and-Choose[48]和Fast Cut-and-Choose[41]，采用不同的方法運行安全協(xié)議多次來保證電路的正確性，每次執(zhí)行只分?jǐn)傒^低的開銷.具體來說，他們將整個過程分為2個階段.在第1階段，將“LEGO” Cut-and-Choose技術(shù)應(yīng)用在電路級別(而不是電路門級別)，即Alice構(gòu)造許多個混淆電路并發(fā)送給Bob，然后Bob要求Alice隨機打開一部分電路進行檢查.如果沒有檢查到錯誤的電路，就執(zhí)行第2階段.Bob將未打開的電路分到多個桶中，對每一個桶執(zhí)行Fast Cut-and-Choose技術(shù)[41].他們的方法保證了即使每個桶中只有一個電路是正確的，協(xié)議的安全性也不會被破壞.

2015年文獻[49]提出了一種新的方法來保證Alice在所有的混淆電路中使用相同的輸入，只需要對每個電路而不是每個輸入比特[39,50]執(zhí)行O(s)次對稱加密操作，并且在離線/在線場景中，由于需要構(gòu)造的混淆電路的數(shù)量小，這種方法產(chǎn)生的開銷也比較低.此外，這項工作還采用了文獻[39]中抵抗選擇失敗攻擊的方法，對文獻[46]中基于離線/在線范例的協(xié)議進行了優(yōu)化和實現(xiàn)，進一步減小了在線階段的通信開銷.

2.4 Gate-LevelCut

至此，我們給出了基于Cut-and-Choose技術(shù)的惡意安全兩方計算的經(jīng)典工作.表2展示了主要的惡意安全兩方計算協(xié)議的各項對比.

Table 2 Comparison of Secure Two-Party Computation Protocols Against Malicious Adversary表2 惡意兩方安全計算協(xié)議對比

3 基于Cut-and-Choose技術(shù)的隱蔽安全協(xié)議

3.1 相關(guān)背景

在針對半誠實敵手的模型中，安全計算可以非常高效地執(zhí)行，但是協(xié)議的安全性卻不令人滿意.半誠實模型能夠保證的是，如果所有的參與方都遵守協(xié)議規(guī)范，那么就可以實現(xiàn)安全性.而針對惡意敵手的安全協(xié)議能夠提供非常強大的安全保障.但是這樣強大的安全保證是有代價的，一般而言，惡意安全協(xié)議比半誠實安全協(xié)議要慢幾個數(shù)量級[25].

為了權(quán)衡效率和安全性，Aumann等人[54]在理想/現(xiàn)實模擬范例下，根據(jù)敵手的能力，給出了2種針對隱蔽敵手的安全性定義，即可以保證：如果敵手試圖作弊以破壞協(xié)議的某些安全屬性(正確性、隱私性、輸入獨立性等)，那么誠實的參與方能夠以一定的概率ε(ε稱為威懾因子)檢測到敵手的欺騙行為.對于敵手的這種欺騙能力，粗略地說，即如果敵手在理想模型下，除了獲得正常的輸出以外，還知道一些有關(guān)誠實方輸入的信息，那么它就成功地進行了欺騙.

事實上，賦予敵手這種欺騙能力的思想早在文獻[37,55-57]中已經(jīng)提及，但是他們的工作并沒有作出形式化的說明和定義.其中Malkhi等人[37]提出的方案和目前抵御隱蔽敵手的工作思想上基本一致.由Alice向Bob發(fā)送s個混淆電路，然后Bob隨機選取1個電路作為計算電路，驗證剩余s-1個電路是否確實可以表示目標(biāo)函數(shù).這種方法允許Alice發(fā)送錯誤的電路而不會被發(fā)現(xiàn)的概率最大為1/s.而文獻[56]只考慮誠實方占大多數(shù)的情況，并且對于安全的定義沒有遵循模擬范例.但Aumann等人[54]引入的隱蔽敵手的概念加強了他們的工作，而且能夠量化所有可能的敵手(而不是以某種特定策略執(zhí)行協(xié)議的敵手)[58].

無論惡意敵手或者隱蔽敵手，Cut-and-Choose技術(shù)都是一種高效的編譯技術(shù)，針對這2種敵手的工作也有些相像，但同時又有所不同.在應(yīng)用Cut-and-Choose技術(shù)抵抗惡意敵手攻擊時，要求誠實的參與方確保另一方作弊的概率要足夠?。欢鎸﹄[蔽敵手，要求誠實的一方在敵手試圖欺騙時，能夠以較大的概率檢測到這一作弊行為，在起到對敵手有一定威懾作用的同時，不顯著影響協(xié)議的效率，使得隱蔽安全協(xié)議比惡意安全協(xié)議更高效.下面我們將對隱蔽敵手模型的相關(guān)成果進行簡要介紹.

3.2 研究工作

在TCC 2007會議上，Aumann等人[54]基于Cut-and-Choose技術(shù)對Yao協(xié)議[6]進行了修改，要求發(fā)送s份混淆電路，然后打開s-1份電路，以檢查電路構(gòu)造是否正確.同時為了避免選擇失敗攻擊，將計算方Bob的每個輸入位擴展為m位的異或，最終實現(xiàn)了具有威懾因子ε=(1-s-1)(1-2-m+1)的隱蔽安全兩方協(xié)議.這種對安全模型的放松使得協(xié)議設(shè)計者能夠構(gòu)造高效的協(xié)議，并且與半誠實協(xié)議的效率只有很小的差距.

在文獻[54]工作的基礎(chǔ)上，文獻[58]基于BMR協(xié)議[59]設(shè)計出非誠實方占多數(shù)的具有隱蔽安全的多方協(xié)議，并且敵手只能以1/s的概率欺騙成功.然而該工作要求大量的承諾操作，通信代價過高.對于電路規(guī)模為|C|的布爾電路，需要傳輸?shù)谋忍財?shù)量為O(n3sρ|C|)，ρ是統(tǒng)計安全參數(shù).

之后Damg?rd等人[60]提出采用編譯器的方法將半誠實安全的協(xié)議轉(zhuǎn)換成隱蔽安全的協(xié)議，不同于文獻[58]，他們的方案要求誠實方占大多數(shù).盡管他們并沒有直接利用Cut-and-Choose技術(shù)結(jié)合混淆電路來檢測敵手的作弊行為，但是思想是一致的.具體來說，他們利用Shamir秘密共享技術(shù)為半誠實安全協(xié)議準(zhǔn)備2組輸入，一組是真實的輸入，一組是錯誤的輸入，這些輸入都是以份額的形式存在.各個參與方并不知道自己所擁有的份額是否是錯誤的.然后，在2組輸入上分別運行半誠實安全協(xié)議，直到各方持有輸出份額.通過揭示哪些輸入份額是錯誤的，參與方在包含該輸入份額的執(zhí)行中，使用與該執(zhí)行相關(guān)的所有信息來檢查是否存在作弊行為.如果沒有，接受包含真實輸入執(zhí)行的輸出.最終他們的協(xié)議能夠以1/4的概率抵抗隱蔽敵手的攻擊.但是由于為半誠實安全協(xié)議提供了2組輸入，如果沒有檢測到欺騙的話，他們協(xié)議的成本基本上是原來協(xié)議的2倍.

在2013年美密會上，Lindell[41]基于Cut-and-Choose OT實現(xiàn)了惡意安全的同時，對惡意安全協(xié)議進行了修改，能夠以ε=1-2-s+1的概率抵抗隱蔽敵手的攻擊.即如果檢查電路中至少有一個是錯誤的，那么Bob將聲明Alice被敵手腐化進行了作弊，而不是終止協(xié)議.而對于所有的檢查電路都構(gòu)造正確但存在2個電路輸出不一致的情況，Bob只需要在第2階段獲得Alice的輸入x1，本地計算獲得正確的F(x1,x2).

4 基于Cut-and-Choose技術(shù)的PVC安全協(xié)議

4.1 相關(guān)背景

隱蔽安全模型的提出具有一定的實際意義，在某些情況下，敵手被發(fā)現(xiàn)作弊所造成的聲譽損失大于不被發(fā)現(xiàn)所帶來的收益.因此，它能勸阻那些關(guān)心自己聲譽、不想冒險被發(fā)現(xiàn)作弊的隱蔽敵手.因而隱蔽安全比半誠實安全提供了更強的安全保障，同時與惡意安全相比，它也能實現(xiàn)更高的協(xié)議效率[14,39,58].

但是，隱蔽安全模型的安全性從某種意義上來說還是不夠強.具體說來，如果電路構(gòu)造方Alice試圖作弊，協(xié)議能夠保證她被計算方Bob以一定的概率抓住，因此Bob就會知道Alice是不誠實的，但Bob并不能說服第三方Alice存在作弊行為，因為他并不掌握任何Alice作弊的證據(jù).為了解決該問題，Asharov等人[17]提出了一個更強的安全模型——公開可驗證的隱蔽(PVC)安全模型.它能確保在檢測到敵手欺騙的情況下，誠實的一方通過blame算法計算出一個公開可驗證的證書，任何第三方可以利用judge算法，將該證書作為輸入，驗證證書的有效性，從而檢查被指控方是否確實進行了欺騙.

4.2 具體的PVC協(xié)議設(shè)計

為了給出PVC模型下的一個安全協(xié)議構(gòu)造，Asharov等人[17]對文獻[54]的工作進行了修改，要求雙方對交換的信息進行簽名，并用所提出的新原語——signed-OT(簽名OT)代替標(biāo)準(zhǔn)OT，實現(xiàn)了具有公開可驗證的隱蔽安全兩方計算協(xié)議.該協(xié)議幾乎與不具有公開可驗證性的文獻[54]具有同等的效率.

具體來說，在該協(xié)議中，首先由Alice生成s個混淆電路，并對這些電路進行承諾后發(fā)送給Bob；經(jīng)過signed-OT協(xié)議，Bob可以獲得在每個電路中對應(yīng)其輸入的所有被簽名的密鑰.如圖7所示，Alice輸入(x0,x1)和一個簽名密鑰sk，Bob輸入一個隨機比特b，協(xié)議執(zhí)行結(jié)束后，Bob將獲得簽名消息——(xb,Signsk(b,xb)).這保證了如果Bob探測到了任何Alice的欺騙行為，由于它在一組不一致的消息上擁有Alice的簽名，這便可以作為Alice欺騙的證據(jù).通過一個1-out-of-ssigned-OT運行Cut-and-Choose技術(shù)，Bob能夠獲得要打開的s-1個檢查電路的信息以及對這些信息的簽名，從而檢查這些電路是否構(gòu)造正確.同時，由于Alice并不知道Bob對于檢查電路的選擇(由signed-OT保證)，Alice無法因被檢測到其作弊而提前終止協(xié)議.如果沒有檢測到欺騙，Bob向Alice揭示其選擇的計算電路標(biāo)識.相應(yīng)地，Alice發(fā)送對應(yīng)該標(biāo)識的混淆電路和其輸入密鑰，Bob根據(jù)這些密鑰可以對該電路進行計算獲得輸出.

signed-OT功能函數(shù)sigot該功能函數(shù)在發(fā)送方Alice和接收方Bob之間運行.輸入: ① Alice輸入(x0,x1,sk),sk是簽名私鑰; ② Bob輸入(vk,b),vk是驗證簽名的公鑰.輸出: ① 計算σ=(xb,Signsk(b,xb)),若Verifyvk((b,xb),σ)=1,Bob獲得σ;否則,終止協(xié)議; ② Alice不會獲得任何輸出.

Fig. 8 Overview of reference [62] protocol圖8 文獻[62]協(xié)議的簡要描述

signed-OT需要大量的公鑰操作，代價昂貴.并且在Asharov等人[17]的方案中，為了避免Alice進行選擇失敗攻擊，采用XOR-tree技術(shù)將計算方的每個輸入比特擴展為m位異或的方式(增加了輸入的長度，需要額外的signed-OT)，這對效率有很大的影響，因為每個輸入比特都需要執(zhí)行一次OT協(xié)議.當(dāng)每個輸入比特被分成m個份額時，每個輸入比特將需要m次OT協(xié)議.此外，這種方式對威懾因子ε的大小也會產(chǎn)生影響.

在2015年亞密會上，Kolesnikov等人[61]基于文獻[12]的工作提出使用signed-OT擴展代替signed-OT的思想來減少公鑰操作，從而實現(xiàn)了協(xié)議效率的改進，但這并不適用于小規(guī)模電路.而且，該方案依然采用XOR-tree技術(shù)來避免選擇失敗攻擊，為了實現(xiàn)較大的威懾因子，不得不引入額外的開銷.

Hong等人[62]在2019年歐密會上，采用標(biāo)準(zhǔn)OT，提出了一個新的公開可驗證的隱蔽安全協(xié)議，簡單且開銷低，避免了昂貴的signed-OT，同時放棄了XOR-tree技術(shù)，降低了計算復(fù)雜度，并實現(xiàn)了常數(shù)大小的驗證證書.

在他們的方法當(dāng)中，Alice隨機選擇s個隨機種子，用于生成s個混淆電路.這些種子不僅決定了混淆電路和承諾的生成，而且用于OT協(xié)議中來傳輸Bob的輸入密鑰.這意味著Bob通過標(biāo)準(zhǔn)OT茫然地獲得一個種子后，Alice的執(zhí)行對Bob來說就是確定性的.此后雙方執(zhí)行一個具有惡意安全的OT協(xié)議s次，允許Bob獲得s-1次執(zhí)行中Alice使用的隨機種子和計算電路的標(biāo)識.

同時，Alice需要對所有的混淆電路以及OT協(xié)議的執(zhí)行副本進行簽名，然后發(fā)送給Bob.根據(jù)這些隨機種子，Bob可以模擬OT協(xié)議執(zhí)行和混淆電路的生成，如果模擬的結(jié)果與之前收到的結(jié)果不一致，Bob將輸出證書(該證書包含有Alice簽名的OT協(xié)議執(zhí)行副本、GC協(xié)議執(zhí)行副本以及隨機種子)作為Alice欺騙行為的證據(jù).如圖8所示，我們給出整個協(xié)議的大致描述.

與文獻[17,61]的工作相比，標(biāo)準(zhǔn)OT比signed-OT更簡單，而且signed-OT在通信和計算方面都比標(biāo)準(zhǔn)OT有更高的成本.此外，文獻[62]的工作實現(xiàn)了證書大小與電路規(guī)模和參與方的輸入長度無關(guān).為了防止Alice發(fā)送錯誤的輸入密鑰，文獻[61]中要求Alice對這些密鑰進行承諾，但該工作避免了這一要求.我們在表3中給出了文獻[17,61-62]的通信復(fù)雜度對比.

宏觀上看，文獻[62]的工作采用更為簡單的標(biāo)準(zhǔn)OT，降低了計算開銷，常數(shù)大小的證書減小了通信成本.但是在檢查協(xié)議執(zhí)行中Alice是否有欺騙行為發(fā)生時，要求Bob本地再次模擬執(zhí)行s-1次OT協(xié)議，將模擬的結(jié)果與實際得到的輸出進行比較，計算方開銷較高，并且在驗證證書的合法性時，也需要Bob完全模擬一次OT協(xié)議的執(zhí)行.

Table 3 Comparison of Communication Complexity of Different PVC Protocols表3 不同PVC協(xié)議的通信復(fù)雜度對比

在CCS 2019會議上，Zhu等人[63]將敵手的收益/損失考慮在內(nèi)，提出一個新的安全概念——Financial Security.同時他們指出，現(xiàn)有的PVC協(xié)議關(guān)注的重點不是judge算法的復(fù)雜性，而是使用一個整體的算法來執(zhí)行大量計算.對此，他們將公開可驗證的隱蔽安全計算與一個高效的、去中心化的judge算法(由以太坊智能合約實現(xiàn))相結(jié)合，實現(xiàn)了具有Financial Security的兩方計算協(xié)議.

在他們的方案中，通過調(diào)用s-1次Sender Non-Repudiable OT(發(fā)送方不可否認(rèn)OT，和signed-OT具有同樣的功能)，Bob能夠獲得用于生成所選擇的s-1個檢查電路的隨機種子，實現(xiàn)了威懾因子ε=1-s-1.與傳統(tǒng)的安全兩方計算定義相比，新的安全概念將各參與方的收益/損失進行了量化，減少了復(fù)雜密碼學(xué)操作的數(shù)量.與文獻[62]的工作不同的是，電路計算方Bob的“負(fù)擔(dān)”較輕，不需要完全模擬一次OT協(xié)議的執(zhí)行，并且judge算法不要求敵手的參與，也不需要知道計算所用的秘密輸入，可以實現(xiàn)完全去中心化.

如表4所示，我們給出了文獻[17,61-63]中4項工作使用不同的OT協(xié)議所引入的帶寬開銷.

Table 4 Comparison of Communication Complexity of Different OT Protocols表4 不同OT協(xié)議的通信復(fù)雜度對比

4.3 采用編譯器實現(xiàn)PVC協(xié)議

為了實現(xiàn)某種安全模型下的協(xié)議構(gòu)造，一種方法是直接構(gòu)造滿足該安全模型的具體安全協(xié)議，另一種方法是使用編譯器，將安全性較弱的協(xié)議轉(zhuǎn)換為安全性較強的協(xié)議.與具體協(xié)議相比，編譯器的主要優(yōu)勢在于，即使未來有新的高效方法可以實現(xiàn)半誠實安全協(xié)議，但只要該協(xié)議滿足編譯器的轉(zhuǎn)換要求，它也能通過編譯器被轉(zhuǎn)換成具有更強安全保證的協(xié)議，而不再需要繼續(xù)基于這種方法嘗試構(gòu)造出更強安全保障的協(xié)議.

2020年美密會，Damg?rd等人[64]構(gòu)造了2個編譯器將半誠實安全協(xié)議轉(zhuǎn)換成公開可驗證的隱蔽安全協(xié)議.該工作采用離線/在線結(jié)構(gòu)，將協(xié)議分成預(yù)處理階段(Πoff)和在線階段(Πon).離線階段與私有輸入無關(guān)，用于生成相關(guān)隨機性，例如混淆電路、乘法三元組等.而在線階段利用這些相關(guān)隨機性和參與方的私有輸入來計算目標(biāo)函數(shù).他們通過第1個編譯器實現(xiàn)了一個具有公開可驗證的隱蔽安全預(yù)處理協(xié)議，然后結(jié)合第2個編譯器，將帶私有輸入的協(xié)議由半誠實安全性編譯成公開可驗證的隱蔽安全性.同時，在該項工作中，離線/在線的設(shè)置能夠有效地應(yīng)對Cut-and-Choose技術(shù)所面臨的挑戰(zhàn)：在適當(dāng)?shù)臅r機打開電路進行檢查.因為如果過早地打開電路，則在協(xié)議的后續(xù)階段可能會發(fā)生欺騙；而如果未能及時打開電路，那么可能會泄露誠實參與方的輸入信息.

具體地說，他們的工作延續(xù)了Cut-and-Choose技術(shù)的思想，在設(shè)計第2個編譯器時，采用“MPC-in-the-head”/“watchlist”技術(shù).Alice和Bob分別有m個虛擬方，將自己的私有輸入分享給各自的m個虛擬方.所有的這些虛擬方聯(lián)合執(zhí)行半誠實安全協(xié)議Π.在協(xié)議執(zhí)行期間，Alice和Bob代表他們模擬的虛擬方發(fā)送消息.如果任何一個真實的參與方(Alice或Bob)存在欺騙行為，那么必然會在至少一個虛擬參與方中產(chǎn)生該作弊行為.通過讓Alice和Bob各自檢查彼此的部分虛擬方，來檢查協(xié)議執(zhí)行過程中是否存在欺騙.假設(shè)Alice得到了Bob的q個虛擬方的輸入和隨機種子，Alice就可以重構(gòu)出這些虛擬方本應(yīng)該發(fā)送的消息.由于Bob不知道檢查了哪些虛擬方，任何欺騙行為都將以q/m的概率被發(fā)現(xiàn).

Table 5 Comparison of Deterrence Factor ε in Pre-processing Protocols表5 預(yù)處理協(xié)議中威懾因子ε的比較

對此，在Faust等人[65]的工作中，引入了一種新的機制——time-lock加密[66],將time-lock加密結(jié)合可驗證延遲函數(shù)[67]來實現(xiàn)公開可驗證.time-lock加密背后的思想很簡單，可以理解為將秘密放在拼圖(puzzle)中，只有在一段固定的時間以后，成功完成拼圖，才能獲得秘密.具體而言，在執(zhí)行半誠實安全協(xié)議時，他們的方案要求利用time-lock加密對所有參與方的隨機字符串r(用于選擇打開部分半誠實協(xié)議實例)、隨機性u(生成puzzle)以及隨機種子進行加密.即使被腐化的參與方惡意終止，通過完成拼圖，誠實的參與方也能獲得隨機種子而不需要與敵手進行交互.然后，誠實的參與方基于這些種子模擬所有的參與方并運行除第r次以外的s-1次半誠實協(xié)議，來檢查是否有欺騙行為發(fā)生.

盡管采用time-lock加密引入了額外的開銷，但是另一方面由于其獨立于半誠實協(xié)議的復(fù)雜度，因此可以分?jǐn)傇撻_銷.與文獻[64]相比，time-lock加密能夠確保總有一次半誠實協(xié)議執(zhí)行沒有被檢查，這提高了威懾因子的大小.

Scholl等人[68]指出文獻[58]的工作并不滿足標(biāo)準(zhǔn)安全的定義，無法實現(xiàn)可識別欺騙(一種安全性質(zhì))，即不能夠允許所有誠實的參與方統(tǒng)一意見，一致認(rèn)同不誠實的參與方存在欺騙行為.因此，他們首先提出第1個編譯器，將半誠實安全的預(yù)處理協(xié)議轉(zhuǎn)換成具有可識別欺騙和可識別終止性質(zhì)的隱蔽安全協(xié)議.為了獲得公開可驗證性，同時防止敵手通過偽造證書陷害誠實的參與方，他們引入了一個新的概念——公開可驗證作弊(public verifiable cheating)，能夠正確地標(biāo)識被敵手腐化的參與方，即使該參與方?jīng)]有做出試圖獲取秘密信息的行為，但在協(xié)議執(zhí)行過程中提前終止協(xié)議.同時，為防止在檢查協(xié)議執(zhí)行時敵手事先知道誠實參與方掌握了對其不利的信息而提前終止協(xié)議，要求所有的參與方本地生成time-lock puzzles，迫使被腐化的參與方在無法獲知是否欺騙成功的情況下對要打開的協(xié)議執(zhí)行進行承諾.而文獻[65]則需要利用一個惡意安全的MPC協(xié)議來生成puzzles，這引入了額外的開銷，且敵手可以從預(yù)處理協(xié)議獲得輸出后進行欺騙.

最后，Scholl等人[68]將所提出的編譯器應(yīng)用于BMR協(xié)議[59]、SPDZ協(xié)議[24,69]進行實例化，得到了可以抵御任意數(shù)量的惡意參與方攻擊的公開可驗證的隱蔽安全協(xié)議.

表6給出了對基于Cut-and-Choose技術(shù)/思想的各PVC協(xié)議的總結(jié)對比.圖9給出了基于Cut-and-Choose技術(shù)的安全多方計算協(xié)議的主要發(fā)展脈絡(luò)圖.

Table 6 Comparison of Protocols in PVC Model表6 PVC安全模型下的協(xié)議對比

Fig. 9 Development of MPC protocols based on Cut-and-Choose technology圖9 基于Cut-and-Choose技術(shù)的安全多方計算協(xié)議發(fā)展脈絡(luò)圖

5 結(jié)束語

本文介紹了密碼學(xué)協(xié)議設(shè)計中一個非常重要的Cut-and-Choose技術(shù)，并對基于這種方法實現(xiàn)惡意安全、隱蔽安全、公開可驗證隱蔽安全協(xié)議的發(fā)展作了簡要介紹.相對于零知識證明、承諾等密碼學(xué)工具，Cut-and-Choose技術(shù)是一種高效的抵抗惡意敵手的解決方法.因此，在早期的研究工作中，被廣泛應(yīng)用于惡意安全模型中，并逐漸發(fā)展和完善，產(chǎn)生了許多優(yōu)秀的工作.

隱蔽安全的概念是為了折中半誠實安全和惡意安全而提出的，具有現(xiàn)實意義.在隱蔽安全模型中，被敵手腐化的參與方可以任意地違背協(xié)議的規(guī)范，但是卻能夠被誠實的參與方以一定的概率發(fā)現(xiàn).這種安全性能夠提供比半誠實安全更強的安全保障，同時也能達到比惡意安全更好的效率.但這種安全性對敵手的影響是有限的.它只能保證當(dāng)敵手作弊被發(fā)現(xiàn)時，誠實的參與方可以終止協(xié)議并放棄與其合作.但是，誠實的參與方不能公開地(可能會泄露其私有輸入)說服第三方敵手在協(xié)議過程中進行了作弊，這導(dǎo)致敵手依然可以選擇在下次計算任務(wù)中違背協(xié)議.

對此Asharov等人[17]提出了公開可驗證的隱蔽安全，具有更強的安全性，可以保證發(fā)現(xiàn)敵手作弊的同時，輸出一個證書而不會泄露自己的秘密信息，任何第三方依據(jù)該證書可以驗證敵手的不誠實行為而放棄與它合作.但他們的工作關(guān)注的是可行性，依賴于昂貴的signed-OT，與當(dāng)時最新的半誠實協(xié)議相比，沒有競爭力.后來Kolesnikov等人[61]作出了各種效率的改進，但是依然需要巨大的開銷.

自2019年Hong等人[62]的工作采用更簡單的標(biāo)準(zhǔn)OT顯著提高了公開可驗證協(xié)議的效率，引起了更多研究者的關(guān)注.然而此時，對于公開可驗證的隱蔽安全模型的工作依然針對的是兩方場景.此后，相繼有3項最新的工作被提出來實現(xiàn)多方場景下的公開可驗證隱蔽安全協(xié)議.與此前工作不同，這3項工作放棄構(gòu)造具體協(xié)議，采用編譯器的方式將安全性較弱的半誠實協(xié)議轉(zhuǎn)換為公開可驗證的隱蔽安全協(xié)議，同時由于離線/在線結(jié)構(gòu)的使用，他們的協(xié)議具有較低的開銷并且只有常數(shù)輪通信.通過編譯器，可以自動地將半誠實安全的協(xié)議轉(zhuǎn)換成安全性更強的協(xié)議.即使未來有新的更加高效的方法或技術(shù)來實現(xiàn)半誠實安全協(xié)議，但只要該協(xié)議滿足編譯器的轉(zhuǎn)換要求，它也能通過編譯器被轉(zhuǎn)換成具有更強安全保證的協(xié)議，而不再需要基于這種方法嘗試構(gòu)造出更強安全保障的協(xié)議.因此，我們相信，對于以后設(shè)計公開可驗證的隱蔽安全協(xié)議，利用編譯器的方式更容易為研究者所接受.

此外，目前基于Cut-and-Choose技術(shù)抵抗惡意敵手的工作，已經(jīng)趨于成熟.通過放松安全模型，這些工作很容易過渡到實現(xiàn)隱蔽安全.而與隱蔽安全相比，這種額外的“公開可驗證性”體現(xiàn)在要求電路構(gòu)造方對混淆電路生成協(xié)議副本、OT協(xié)議副本以及使用的隨機種子進行簽名，實現(xiàn)認(rèn)證性與不可抵賴性.我們認(rèn)為可以結(jié)合區(qū)塊鏈等其他具有認(rèn)證功能的技術(shù)與隱蔽安全的研究工作相結(jié)合，實現(xiàn)具有公開可驗證性質(zhì)的隱蔽安全協(xié)議.相信在不久的將來，會有更多關(guān)于公開可驗證的安全多方計算工作被提出，并能夠用于解決實際問題.