趙 川 徐 俊

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

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

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

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

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

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

1 基礎知識

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

1.1 安全模型

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

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

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

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

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

1.2 茫然傳輸

茫然傳輸(OT)是安全多方計算中的一個基本原語，涉及2個參與方，對安全協議的研究具有重要的作用.本節(jié)我們介紹標準的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可以寫成如下理想功能函數FOT，如圖2所示：

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

1.3 混淆電路

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

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

具體地說，對于電路C中的每條導線w，讓Alice生成2個密鑰k0，k1(又稱為標簽)，分別對應w上2個可能的值0和1.在執(zhí)行過程中，根據Alice和Bob的輸入，每條導線將與具體的明文值和相應的密鑰有關.計算方Bob只知道密鑰，而不會知道相應的明文值.例如，對于電路中的一個“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將混淆電路以及自己輸入所對應的密鑰值發(fā)送給Bob.隨后，Alice和Bob運行OT協議，茫然地將Bob的輸入所對應的密鑰傳輸給Bob.有了每條電路輸入線上的密鑰值，Bob就可以對混淆電路進行逐層解密，最后獲得電路輸出線上的密鑰，并通過查找表將獲得的密鑰映射到真實的輸出值.

1.4 Cut-and-Choose技術

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

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

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

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

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

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

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

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

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

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

2 基于Cut-and-Choose技術的惡意安全協議

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

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

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

3) BatchedCut.這種方法將Cut-and-Choose技術應用于多個安全計算實例中，即參與雙方通過不同的輸入安全地計算目標函數F多次，在每次安全計算中，要求電路構造方Alice構造多個混淆電路以應用Cut-and-Choose技術，保證電路正確的同時又能夠獲得良好的分攤效率.

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

下面我們詳細介紹4種方法相關的研究成果.

2.1 MajorityCut

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

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

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

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

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

Cut-and-Choose技術功能函數ccot該功能函數在發(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有關的信息.

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

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

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

Cut-and-Choose Bilateral OT功能函數ccbot該功能函數在發(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有關的信息.

2.2 SingleCut

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

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

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

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

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

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

2.3 BatchedCut

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

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

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

2.4 Gate-LevelCut

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

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

3 基于Cut-and-Choose技術的隱蔽安全協議

3.1 相關背景

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

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

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

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

3.2 研究工作

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

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

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

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

4 基于Cut-and-Choose技術的PVC安全協議

4.1 相關背景

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

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

4.2 具體的PVC協議設計

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

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

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

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

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

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

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

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

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

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

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

Table 3 Comparison of Communication Complexity of Different PVC Protocols表3 不同PVC協議的通信復雜度對比

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

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

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

Table 4 Comparison of Communication Complexity of Different OT Protocols表4 不同OT協議的通信復雜度對比

4.3 采用編譯器實現PVC協議

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

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

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

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

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

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

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

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

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

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

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

5 結束語

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

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

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

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

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