安全多方計算及其在機器學習中的應用

郭娟娟 王瓊霄 許 新 王天雨 林璟鏘

1(信息安全國家重點實驗室(中國科學院信息工程研究所) 北京 100195) 2(中國科學院大學網絡空間安全學院 北京 100049) 3(華控清交信息科技(北京)有限公司 北京 100084) 4(中國科學技術大學網絡空間安全學院 合肥 230026)

安全多方計算(secure multiparty computation, MPC)起源于姚期智在1982年提出的百萬富翁問題.在MPC中，參與方將各自的秘密數據輸入到一個約定函數進行協同計算，即使在一方甚至多方被攻擊的情況下，MPC仍能保證參與方的原始秘密數據不被泄露，并且保證函數計算結果的正確性.自MPC理論創立以來，已經衍生出多個技術分支，包括混淆電路、秘密分享、同態加密和不經意傳輸等.

混淆電路(garbled circuit, GC)是姚期智于1986年提出的安全兩方計算協議[1]，參與方在不知曉他人數據的前提下，使用私有數據共同計算一個用邏輯電路表示的函數.大多數混淆電路方案支持2個參與方計算，其性能優化集中于優化單個電路門的密文數量、傳輸的電路數量等.近年來多參與方計算的混淆電路方案相繼提出.混淆電路的優點是能在恒定輪數內完成計算，只涉及開銷較小的對稱加密運算；缺點是通信量和電路大小呈線性關系，因此不適合計算復雜運算，只適用于比較大小等簡單的邏輯運算.

秘密分享(secret sharing, SS)由Shamir[2]和Blakley[3]于1979年分別提出，數據擁有方計算秘密數據的份額并將其分發給計算方，計算方對不同秘密的份額計算，得到計算結果的份額.由于秘密拆分方式不同，秘密分享分為基于多項式插值的秘密分享和加性秘密分享(additive secret sharing).加性算術秘密分享能夠計算線性運算、加性布爾秘密分享能夠計算比較大小等非線性運算.加性秘密分享只需要進行簡單的運算，計算開銷小，在MPC中得到了廣泛的應用.秘密分享的缺點是交互輪數和電路深度有關.

不經意傳輸(oblivious transfer, OT)由Rabin于1981年提出[4]，消息發送方擁有多個消息，接收方獲得其中某個值，發送方不知道接收方的選擇信息.其衍生技術相關不經意傳輸(correlated oblivious transfer, COT)可以生成具有關系的隨機數.OT,COT是重要的密碼學組件，能夠為GC傳輸導線標簽、為SS生成相關隨機數，只使用OT技術也能實現MPC協議.在OT的性能優化歷程中，OT擴展(OT Extension)技術引入對稱加密來降低計算開銷，靜默OT擴展(silent OT Extension)技術在本地擴展隨機數種子來降低通信開銷.

同態加密(homomorphic encryption, HE)的概念由Rivest等人[5]于1978年提出，可以在無需解密的情況下直接對加密數據執行計算.在發展過程中先后有部分同態加密方案與淺同態加密方案提出，直到2009年Gentry[6]構造出首個全同態加密方案.同態加密的優點是能以最小的通信成本設計輪數較優的MPC協議，缺點是乘法同態運算會帶來較大的計算和存儲開銷，目前加法同態在實際中應用較多.

以上4類MPC技術在計算性能、通信效率和存儲開銷等方面都具有各自的優勢和劣勢，單一的MPC技術往往不能滿足實際應用中計算復雜函數的需求，需要將多種MPC技術相結合才能獲得性能均衡的實現方案.

目前MPC技術最典型的應用場景是隱私保護機器學習(privacy-preserving machine learning, PPML).MPC在模型訓練和推理中可以保護用戶數據和模型參數的隱私.近年來，Microsoft,Amazon和Google等公司提供“機器學習即服務”(machine learning as a service, MLaaS)，即公司提供訓練好的模型來對用戶數據計算推斷結果.模型數據是公司的重要資產，一旦泄露會帶來重大的經濟損失，同時用戶也不愿意泄露私有數據，MPC能夠在保護雙方隱私的前提下完成模型推理.此外，在隱私保護法律法規GDPR,EFF和HIPPA等的約束下，不同機構間無法交換明文數據，MPC能夠在保證數據集隱私的前提下來完成模型的訓練.

PPML方案涉及多種類型的運算，考慮到參與方的數據規模不同、計算和網絡能力不同、安全模型不同，可以在具體場景下組合多種MPC技術來實現PPML方案.

1 安全模型及目標

根據系統對敵手的容忍程度，MPC的安全模型可以分為半誠實安全模型(semi-honest model)和惡意安全模型(malicious model).

半誠實安全模型：敵手會按照協議規定進行運算，但試圖通過協議中得到的信息挖掘其他參與方的隱私數據，該模型保證用戶隱私信息不被敵手獲得.

惡意安全模型：敵手不會遵守約定執行協議，會以錯誤的協議執行結果推斷信息，惡意攻擊行為也可以是任意的不可推理的.該模型中用戶隱私數據不會被敵手獲得，且不會因為敵手的惡意行為導致協議錯誤運行.在惡意安全模型中，要確保準確檢測到敵手惡意行為會帶來很大開銷，因此提出了安全性和開銷更均衡的隱蔽安全(covert)模型，能夠在一定概率下檢測到敵手惡意行為.公開可驗證(public verifiable covert, PVC)方案在滿足隱蔽安全條件的基礎上，參與方生成公開可驗證的欺騙證據，該模型適用于惡意行為被發現會遭受懲罰的現實場景.Covert模型和PVC模型通常只適用于GC和OT兩種MPC技術.

MPC的安全目標包括參與方數據隱私性和計算結果正確性等.進一步，對于參與方獲得的計算輸出結果，MPC協議能夠達到的安全屬性由強到弱依次為：保證結果輸出(guaranteed output delivery, GOD)、公平性(fairness, FN)、一致中止(unanimious abort, UA)和選擇中止(selective abort, SA).假設敵手可以控制t個參與方，誠實方占多數(honest majority)時門限值滿足t

2 MPC技術發展

2.1 混淆電路

混淆電路(GC)技術最初關注兩方參與的技術方案，技術發展分別從性能提升和安全性提升2方面展開，安全性主要體現在半誠實安全與惡意安全的區別，在具有同等安全的情況下，提升方案性能是解決GC實用性的重要研究方向.此外，隨著MPC實際應用需求的增加，近年多方參與的GC方案研究也逐漸增多.本節將對兩方參與的半誠實安全方案、兩方參與的惡意安全方案及多方參與的方案分別進行介紹.圖1展示了兩方參與的GC技術發展脈絡圖.

Fig. 1 Technological development of 2-party garbled circuit圖1 兩方參與的混淆電路技術發展脈絡

2.1.1 半誠實安全兩方混淆電路的性能優化

混淆電路是姚期智于1986年提出的一種電路加密技術，參與方混淆器(Garbler)和評估器(Evaluator)對各自的隱私輸入計算目標函數，首先需要將目標函數轉換成布爾電路的形式，布爾電路由多個二輸入單輸出的電路門級聯而成.GC的構造是從單個電路門開始，先加密一個門再延伸到加密整個電路.GC工作流程如圖2所示，以AND門為例，設電路門導線的索引為a,b和c，混淆器擁有導線a的輸入值va,評估器擁有導線b的輸入值vb.首先，在GC生成階段，混淆器為所有導線選取隨機數作為標簽Lw,vw，下標w為導線索引，vw為導線取值，取值為0或1.按照真值表順序依次使用輸入標簽加密輸出標簽得到4個密文，打亂密文排列順序得到混淆表.然后，雙方交互傳輸信息：混淆器向評估器發送混淆表、混淆器的輸入標簽La,va；評估器通過和混淆器執行OT獲得自己的輸入標簽Lb,vb.最后，在GC評估階段，評估器使用輸入標簽解密混淆表密文獲得輸出標簽，當電路門是輸出門時，評估器使用輸出標簽解密輸出門密文得到明文輸出.對于每個電路門，混淆器生成6個隨機數、使用兩重對稱加密生成4個密文，評估器依次對4個密文解密直到解密成功為止.在整個過程中，GC的通信量取決于交互階段雙方傳輸的信息，包括混淆表、混淆器標簽和OT傳輸評估器標簽，主要的通信開銷是混淆表.GC的計算開銷來源于混淆器生成混淆表密文、評估器解密混淆表密文時的計算.

Fig. 2 The diagram of garbled circuit圖2 混淆電路工作流程

混淆電路提出至今，通信開銷一直是其性能瓶頸，半誠實安全模型下的很多方案都致力于通過減少單個門的密文數量來降低通信開銷.

Beaver等人[7]于1990年提出的BMR方案構造了point-and-permute(p&p)方法，混淆器為輸入導線w選取掩碼比特λw，對導線真實值vw和掩碼比特計算異或得到排列比特pw,vw，即pw,vw=vw⊕λw.混淆器在生成混淆表時，按照2個輸入導線的排列比特對密文進行排列，并將排列比特和標簽一起發給評估器.評估器解密時無需依次嘗試4個密文，只需解密排列比特位置的密文即可獲得輸出標簽，并且由于掩碼比特是隨機的，評估器不能根據排列比特推測出混淆器的真實輸入，混淆電路的隱私性也得到了保證.

Naor等人[8]于1999年提出了GRR(garbled row reduction, GRR)，將單個電路門的密文數量從4個減少到3個.混淆器生成混淆表時，令混淆表中的第一個密文為0.若評估器要解密第一個密文，則對密文0解密獲得輸出導線標簽.2009年Pinkas等人[10]提出的GRR2，進一步將密文數量降為2個，然而該方案使用多項式插值的方法實現，需要計算模冪運算，導致計算效率低.

Kolesnikov等人[9]于2008年提出了Free-XOR，其計算XOR門的通信開銷為0個密文，是目前計算XOR門的最優方案.混淆器選取全局隨機數R，在生成GC時令每根導線2個標簽取值相差固定值R，即Lw,1=Lw,0⊕R.評估器計算XOR門時將兩方的輸入標簽異或得到輸出標簽，無需計算和傳輸混淆表，但是計算AND門時仍需要混淆表，因此Free-XOR適用于XOR門較多的運算.Kolesnikov等人[11]于2014年提出了FleXOR，計算AND門的方法與GRR2兼容，只需要2個密文，計算XOR門需要0～2個密文.

Zahur等人[12]于2015年提出的半門(Half gates)是目前計算AND門的最優方案，該方案與Free-XOR兼容，計算AND,XOR門的通信開銷分別為2,0個密文.Half gates將AND門轉換為2個半門的異或，即c=a∧b=a∧(r⊕r⊕b)=(a∧r)⊕(a∧(r⊕b)).混淆器半門計算a∧r，評估器半門計算a∧(r⊕b)，其中，混淆器擁有導線a的輸入值va，評估器擁有導線b的輸入值vb，令r=λb(λb為混淆器已知的掩碼比特).在GC生成階段，混淆器為混淆器半門生成2個密文H(La,0)⊕LGC,0,H(La,1)⊕LGC,0⊕λbR，對2個密文進行p&p和GRR處理后，混淆器半門的密文減少為1個；混淆器為評估器半門生成2個密文H(Lb,λb)⊕LEC,0,H(Lb,λb⊕1)⊕LEC,0⊕La,0，對2個密文做GRR處理后評估器半門的密文減少為1個，該半門無需做p&p處理，因為將評估器輸入看作vb⊕λb，那么評估器擁有的vb則為排列比特.評估器獲得混淆表和2個半門的輸入標簽La,va,Lb,vb⊕λb后，分別解密2個密文獲得混淆器半門、評估器半門的輸出標簽LGC,LEC，將2個輸出標簽異或得到AND門的輸出標簽.

Ball等人[13]于2016年提出Garbled gadgets可用于混淆算術電路和布爾電路.算術電路的實現是將Free-XOR從模2擴展到模m，此時每個導線w具有m個標簽且相鄰標簽之間相差全局值R，該方案實現了無通信開銷的模m的加法和常數乘法.

混淆電路的性能優化不僅包括對通信性能的優化，也有一些方案對于計算性能進行優化.早期GC通過對輸入標簽計算哈希、將哈希結果與輸出標簽異或來生成混淆表密文.英特爾內核的專用AES-NI指令用硬件加速了AES運算，激勵Bellare等人[30]于2013年提出使用固定密鑰AES實現的GC方案，比使用哈希算法實現的GC方案快50倍.此后大多數GC,OT方案都使用固定密鑰AES實現，然而2020年Guo等人[31]發現很多GC方案在實現時因錯誤使用固定密鑰AES而易受攻擊，為此提出了安全使用固定密鑰AES的方法并給出安全證明.

2.1.2 惡意安全兩方混淆電路的性能優化

半誠實安全模型往往不能滿足現實生活中的需求，惡意混淆器會做出發送錯誤的電路給評估器或通過錯誤地執行協議來推測評估器的輸入等惡意行為.為此，一些抵御惡意敵手的混淆電路方案被提出，包括基于Cut-and-choose的混淆電路、可鑒別的混淆電路(Authenticated-GC)等.基于Cut-and-choose的混淆電路的性能優化目標是在滿足特定安全條件時最小化傳輸電路的數量，通常只支持兩方計算.Authenticated-GC將秘密分享技術應用于混淆電路中，并為秘密份額添加消息鑒別碼，均衡了通信開銷和交互輪數.

1) 基于Cut-and-choose的混淆電路

使用零知識證明技術來保證參與方正確執行協議會帶來巨大開銷.為了降低開銷，Pinkas[14]于2003年首次將Cut-and-choose技術引入到GC中，Lindell等人[15]于2007年提出了第一個具有完整安全性證明的基于Cut-and-choose的惡意安全GC.在基于Cut-and-choose的GC中，混淆器生成σ(σ為復制因子)個GC并發送給評估器，評估器隨機選擇c個電路作為檢測電路，剩余電路作為評估電路，惡意敵手攻擊成功的概率為2-ρ(ρ為統計安全參數).評估器要求混淆器提供生成檢測電路的隨機數，來驗證檢測電路是否實現約定函數，檢測通過后，按正常混淆電路的流程對評估電路進行計算以確定最終計算結果.

在基于Cut-and-choose的GC方案中，需要解決的問題是輸入一致性問題(input consistency)和選擇失敗攻擊(selective failure attack)問題.輸入一致問題指的是惡意混淆器向評估器提供的σ個混淆電路的輸入不一致，影響最終計算結果.選擇失敗攻擊指的是惡意混淆器將電路門混淆表的其中一個密文篡改為錯誤的密文，如果這個密文剛好是評估器需要解密的密文，評估器在解密時檢測到錯誤會退出，此時混淆器便會知道評估器的排列比特，進一步使用自己擁有的評估器的掩碼比特計算出評估器的真實輸入.

對于輸入一致性問題，早期的工作[15]使用承諾方案來解決，通信開銷較高.Shelat等人[16]于2011年提出一致性檢測方法，通過傳輸少量參數代替零知識證明來降低通信開銷.Lindell[20]于2016年提出輸入恢復(input recovery)技術，當混淆器輸入不一致導致評估器得到不同輸出結果時，可以懲罰混淆器提供真實輸入.Wang等人[21]于2017年提出在輸出導線中編碼陷門的方法，使得評估器在獲得多個輸出時可以恢復出混淆器的輸入.此外，還有一些方案[17,32-33]也給出了解決輸入一致性問題的辦法.

對于選擇失敗攻擊問題，文獻[15]中評估器將真實輸入與多個隨機比特的異或值作為OT輸入，使得評估器退出時與真實輸入無關，混淆器無法通過選擇失敗攻擊推測評估器輸入.Shelat等人[34]通過構造探測矩陣降低了使用OT的數量，然而導致異或運算次數為評估器輸入大小的平方，Wang等人[21]通過將評估器的輸入分為多個塊并構造更小的探測矩陣來減少計算開銷.

基于Cut-and-choose的GC性能提升問題也受到廣泛關注.Yan等人[18]于2014年提出了批處理(Batched)Cut-and-choose，兩方對同一函數f(不同輸入數據)進行N次安全計算時，批處理Cut-and-choose方案中的混淆器生成Nρ+c個電路，評估器隨機選擇c個電路作為檢測電路，將剩余的電路隨機分配到N個bucket中，每個bucket中包含計算一次f所需的電路，減少了每次計算的攤銷成本.Lindell等人進一步對該技術進行了改進和實現[19,35].先前單一Cut-and-choose的復制因子為O(ρ)，而批處理Cut-and-choose的復制因子為2+O(ρ/logN)，可見其極大地降低了開銷.

由于將Cut-and-choose應用于整個電路開銷很大，于是Nielsen等人[22]2009年首次提出應用于電路門的Cut-and-choose方案LEGO，該方案中混淆器構造大量NAND門，雙方對這些電路門執行批處理Cut-and-choose，評估器隨機選擇部分電路打開檢測正確性，將剩余門隨機分配給bucket并集成到混淆電路中.評估器在評估電路時，取出bucket中大多數輸出作為該門的輸出.LEGO使用了Pederson同態承諾，導致效率較低，Frederiksen等人[23]于2013年提出的MiniLEGO采用基于OT的異或同態承諾協議，Frederiksen等人[24]于2015年提出的TinyLEGO通過優化bucket的構造來提高通信效率.Kolesnikov等人[25]于2017年提出的DUPLO可以對任意電路組件進行Cut-and-choose，電路組件的大小范圍可以是單個電路門到整個電路.Zhu等人[26]于2017年提出的JIMU通過使用異或同態哈希來代替先前的異或同態承諾.

公開可驗證(PVC)安全最早于2012年提出，阿里巴巴[36]于2019年首次實現了公開可驗證的混淆電路，該方案使用Cut-and-choose的方法來實現，混淆器發送多個電路給評估器，評估器選擇一個電路用于評估，剩余電路用于檢測.每個參與方的所有行為都自動帶有類似簽名的機制以供其他參與方存證，當發現惡意行為時將其簽名公開，令惡意參與方承受名譽損失，以此來威懾理性的參與方正確執行協議.

2) 可鑒別的混淆電路

先前的方案均存在一定局限性：對整個電路實施Cut-and-choose的通信、計算開銷大；對電路門實施Cut-and-choose的運行時間長；惡意安全秘密分享協議的交互輪數多等.針對現有協議的不足，Wang等人[27]于2017年提出恒定輪數的可鑒別混淆電路Authenticated-GC.為了解決選擇失敗攻擊問題，該方案引入預處理程序將導線掩碼比特拆分為2個份額，將其分別分發給混淆器和評估器，然而掩碼比特拆分后導致混淆器無法獨立地生成混淆表，需要混淆器和評估器這2個參與方分布式地生成混淆表.由于混淆器可能構造錯誤的混淆表份額影響最終計算結果，該方案引入BDOZ型MAC[37]使得雙方可鑒別對方混淆表份額的正確性.

Authenticated-GC方案中混淆器和評估器協同生成混淆電路，預處理程序包括“與計算函數無關的預處理”和“與計算函數有關的預處理”.“與計算函數無關的預處理”為混淆器和評估器生成全局密鑰、輸入導線掩碼比特的份額及對應的MAC，混淆器和評估器可以在本地計算出XOR門的輸出導線掩碼比特及MAC.然而計算AND門時，需要“與計算函數有關的預處理”生成AND三元組，即預處理程序根據從混淆器和評估器收到的輸入導線掩碼比特計算輸出導線的掩碼比特，并返回給混淆器和評估器，然后兩方使用各自的份額生成混淆表份額.在數據輸入階段雙方對彼此的掩碼比特鑒別通過后再執行OT傳輸標簽，在電路評估階段評估器逐層使用輸入導線標簽計算輸出導線標簽及鑒別信息，在電路輸出階段評估器鑒別輸出導線MAC正確后使用標簽解密GC獲得結果.

Katz等人[28]于2018年提出安全兩方計算場景下Authenticated-GC的優化方案，通過設計與半門方案兼容的可鑒別混淆電路、避免每次混淆都發送MAC以及優化AND門的三元組來提高計算和通信效率.

2.1.3 多方參與的混淆電路

1) 基于BMR的多方混淆電路

為了能夠讓多個參與方協同地生成混淆電路，Beaver等人[7]于1990年提出BMR協議，將姚氏混淆電路擴展到多方場景，各參與方為每條導線生成加密值，對所有參與方生成的同一導線的加密值計算異或，得到該導線最終的加密值.

原始BMR方案只能抵御半誠實行為敵手，但與其他安全計算技術(SPDZ,SHE和OT)合用可以抵御惡意行為敵手.最初BMR使用零知識證明技術來證明生成導線加密值時正確使用了偽隨機函數(pseudo random function, PRF)，計算開銷較大.SPDZ-BMR[38],SHE-BMR[39]和OT-BMR[40]對PRF的證明和檢查有所不同：SPDZ-BMR在評估電路時使用SPDZ型MAC來檢查PRF值和密鑰；SHE-BMR使用SHE來驗證PRF值的正確性；OT-BMR使用COT來對PRF值進行一致性檢查.SPDZ-BMR,SHE-BMR和OT-BMR中每個門的通信開銷依次為O(n4κ),O(n3κ),O(n2B2κ)，其中B=O(1+ρ/log|C|).可見2017年提出的OT-BMR為這幾個方案中性能最優的方案.

2017年Wang等人[41]將可鑒別混淆電路方案與BMR技術結合，設計了多方混淆電路方案，通信開銷為O(n2Bκ).Yang等人[29]于2020年進一步提出優化方案，針對文獻[27]中“與計算函數有關的預處理”進行改進，優化了AND三元組生成方式，并首次提出將半門方案應用于多方場景，其中三方計算“與計算函數有關的預處理”的通信效率提高了35%.

2) 三方混淆電路

實際應用中也存在少數參與方計算混淆電路的場景，例如只有3個參與方.安全三方計算通過秘密分享實現的方案較多，混淆電路也有少量專門支持3個參與方的方案，通常包含2個混淆器以及1個評估器，評估器通過2個混淆器生成的電路一致性來判斷是否有惡意行為.CKM+14[42]將Cut-and-choose應用于三方混淆電路，評估器P3的輸入通過XOR拆分為多個份額，混淆器P1,P2基于BMR協作生成GC，評估器P3分別和P1,P2通過Cut-and-choose的方式驗證雙方生成GC的正確性.MRZ15[43]需要2個混淆器協商一致的隨機數來生成混淆電路，能夠容忍一個惡意混淆器，評估器采用秘密分享拆分其輸入并從2個混淆器得到輸入份額的標簽，進一步恢復出真實輸入的標簽，該方案僅使用對稱加密而無需使用OT，從而提高了計算效率.MRZ15之后被應用于混合計算框架ABY3，可以與三方秘密分享技術進行轉換.

2.2 不經意傳輸

不經意傳輸(OT)是密碼學的基本協議原語之一，由Rabin于1981年提出.OT技術主要包括OT，OT擴展以及相關不經意傳輸(COT).OT在MPC場景中有廣泛的應用：OT自身可實現多項式計算[44-45]和比較大小[46]；OT作為重要的MPC安全組件可與其他MPC技術結合應用，例如OT在混淆電路中承擔著傳輸標簽的任務；COT能夠為秘密分享方案生成相關隨機數[47]、消息鑒別碼等.

Fig. 3 The technic of oblivious transfer圖3 OT技術原理

Even等人[48]于1982年提出1-out-of-2 OT的概念，如圖3(a)所示.發送方Alice輸入2個消息m0,m1，接收方Bob輸入選擇比特b，OT向Bob輸出mb，協議執行過程中Alice不能獲知選擇比特b且Bob不能獲知m1-b.OT可以由基于不同安全假設的公鑰加密算法來實現，包括基于DDH實現的NP01[49]、基于LWE實現的BD18[50]和MR19[51]等.

然而使用非對稱密碼算法生成大量的OT會帶來很大的計算開銷，并且Impagliazzo等人[52]于1989年證明無法在不使用公鑰密碼的情況下實現OT.為了降低計算開銷，研究者們提出了OT擴展技術，使用混合加密方式來生成OT，即先使用少量的公鑰算法生成對稱密鑰，再進一步使用對稱加密來完成消息的不經意傳輸.

1) OT擴展

Beaver[53]于1996年首次提出OT擴展，使用κ(κ為計算安全參數)個基礎OT(base OT)可以生成κ的多項式個OT，但是該方案需要使用GC計算復雜的偽隨機數發生器導致效率很低.

在基礎OT階段，Bob復制κ份選擇向量r得到m×κ維矩陣R，然后選取m×κ維隨機矩陣T并計算T′=T⊕R.Alice和Bob互換原本的發送方和接收方身份提供輸入：Bob作為發送方輸入矩陣T,T′，Alice作為接收方輸入長度為κ位的隨機比特串s.基礎OT執行結束后Alice獲得輸出矩陣Q，該矩陣第i列(1≤i≤κ)滿足Qi=(si·r)⊕Ti，第j行(1≤j≤m)滿足Qj=(rj·s)⊕Tj.

惡意接收方Bob可以在基礎OT階段使用不同的選擇向量來同時獲得發送方Alice的2個消息，因此需要對接收方的輸入進行一致性檢測來發現惡意行為.IKNP03在半誠實協議的基礎上，引入了Cut-and-choose技術來在OT擴展階段檢測Bob輸入的一致性，這種檢測方式帶來了很大的開銷.

研究者們提出了一系列半誠實模型下OT擴展的性能優化方案.Asharov等人[55]于2013年提出的方案ALSZ13分別設計了相關不經意傳輸(COT)擴展和隨機不經意傳輸(Random OT, ROT)擴展.COT中發送方擁有的輸入消息是相關的，例如Free-XOR的標簽傳輸；ROT中發送方擁有的消息不相關的.Kolesnikov等人[56]于2013年提出的方案KK13適用于傳輸短秘密值，該應用場景包括GMW的AND運算等.KK13改變了IKNP03中選擇向量r的重復編碼方式，Bob對r采用隨機編碼后可在OT擴展階段獲得1-out-of-nOT.當傳輸的短消息長度為1位時KK13比IKNP03的通信效率提高O(logκ)倍.由于KK13方案里n取值上限為256，Kolesnikov等人[57]提出方案KKRT16對其進行改進，Bob通過使用PRF對r編碼，實現了1-out-of-∞ OT擴展.Boyle等人[58]于2019年提出的方案BCG+19b基于偽隨機關系隨機數生成器(pseudorandom correlation generator, PCG)實現了靜默OT擴展，使用PCG實現靜默預處理時，參與方之間只需要少量通信來生成隨機數種子，然后在本地對短隨機數種子進行擴展來生成具有關系的長隨機數.BCG+19b中生成一個OT平均只需要0～3位的通信開銷，極大地降低了OT擴展的通信量，但是其輪數復雜度高，適用于通信帶寬資源受限的場景.

此外，還有一些方案用來提高惡意安全模型下OT擴展的效率.由于基于Cut-and-choose實現的一致性檢測方案[59-60]性能太差，Nielsen等人[61]于2012年提出另一種一致性檢測的方法NNOB12，使用哈希函數在基礎OT階段對Bob的選擇向量r進行一致性檢測，實現該方案需要2.7κ個基礎OT.ALSZ15[62]在NNOB12的基礎上進行改進，將基礎OT數量減少為κ+ρ.KOS15[63]在IKNP03半誠實安全方案的基礎上改進協議，在OT擴展階段對接收方輸入向量進行一致性檢測.在KOS15中，Alice和Bob協商一個行數索引集C，接收方Bob計算T*=⊕j∈CTj和R*=⊕j∈CRj并發送給發送方Alice，然后Alice計算T*⊕(R*·s)并檢查Q*=T*⊕(R*·s)是否成立，若不成立則退出協議.KOS15僅需κ個基礎OT，與IKNP03半誠實安全方案相比并未引入額外的開銷.3個方案NNOB12,ALSZ15和KOS15都實現了惡意安全的1-out-of-2的OT擴展，OOS16[64]方案在KK13的基礎上加入與KOS15類似的一致性檢測獲得惡意安全的1-out-of-nOT擴展(n≤276)，該協議只需要κ個基礎OT，運行時間比KK13增長約20%.

2) 相關不經意傳輸

相關不經意傳輸(COT)最早在ALSZ13中提出，其功能是生成相關的隨機數.COT的流程如圖3(c)所示，發送方的輸入為r,r⊕Δ，接收方的輸入索引為b，COT向接收方輸出r⊕Δb.向量不經意線性評估(vector oblivious linear-function evaluation, VOLE)是COT的廣義定義，接收方可以獲得發送方所持有信息的線性組合.

KOS15提出可以使用COT來實現OT擴展中的基礎OT協議.Boyle等人[65]于2018年提出的方案BCGI18基于LPN假設構造了半誠實安全的VOLE，通過PCG在本地生成關系向量.Boyle等人[66]于2019年提出的BCG+19a生成分布式密鑰時使用可穿孔的偽隨機函數(puncturable pseudorandom function, PPRF)代替BCGI18中的分布式點函數(distributed point function, DPF)，并且通過安全設置PPRF密鑰將協議的安全性提升為惡意安全性，該方案的通信開銷比IKNP03減少1 000倍，計算效率只提高了6倍.Schoppmann等人[67]的并行工作SGRR19基于primal-LPN實現了半誠實安全的VOLE協議，通信效率只比IKNP03提高20倍，計算效率高于BCG+19a.Ferret20[68]基于SGRR19改進了VOLE方案，實現的半誠實安全方案將通信開銷減少15倍.在半誠實方案的基礎上引入一致性檢測實現惡意安全性，平均每個COT的運行時間比半誠實安全方案慢1～3 ns.

以上COT方案中，BCG+19a和Ferret基于VOLE實現了OT擴展，而SGRR19沒有實現OT擴展.

表1對OT擴展方案從安全模型、輪數、通信量和運行時間等方面進行對比.其中，κ取值為128，N為比特向量位數，通信量、運行時間為生成1個OT時的平均通信量、平均運行時間.通過對比得出BCG+19a為目前通信效率最好的方案，Ferret20為目前計算效率最好的方案.

Table 1 Comparison of OT Extension Schemes表1 OT擴展技術性能對比

2.3 秘密分享

傳統的秘密分享方案中，秘密分發者將秘密拆分為份額并分發給參與方，只有足夠數量的秘密份額組合在一起才能夠恢復出秘密信息.基于秘密分享的安全多方計算(secret sharing-secure multiparty computation, SS-MPC)指的是參與方對不同秘密數據的份額進行運算，得到計算結果的份額，足夠數量的結果份額組合在一起能夠恢復出計算結果.本節圍繞SS-MPC來展開介紹，而不關注SS技術本身.

SS-MPC根據秘密的生成方式可以分為基于多項式插值的秘密分享和加性秘密分享.基于多項式插值的SS-MPC容易實現任意門限，但是需要模冪運算，導致其計算效率低.加性秘密分享根據秘密數據形式可以分為算術秘密分享和布爾秘密分享，在計算線性運算時通常需要使用算術秘密分享，在計算非線性運算時通常需要使用布爾秘密分享.加性秘密分享的優勢是計算效率高，其門限方案的實現需要參與方持有冗余份額.目前SS-MPC在實際中應用最廣泛，能夠高效地實現線性運算和非線性運算.

2.3.1 SS-MPC計算線性運算

SS-MPC根據系統中敵手控制的參與方數量，可分為誠實方占多數的SS-MPC和不誠實方占多數的SS-MPC.

1) 誠實方占多數

SS-MPC在早期有一些經典方案.GMW方案[69]于1987年被提出，能夠支持多個參與方進行布爾運算，秘密數據以異或的形式拆分，計算XOR運算可在本地完成，計算AND運算需要參與方兩兩之間執行1-out-of-4 OT，導致交互輪數較多.BGW方案[70]于1988年被提出，是基于Shamir秘密分享實現的SS-MPC方案，但其計算乘法要用到隨機化和降階處理，導致開銷較大.Beaver三元組[71](Beaver triples)于1991年被提出，是SS-MPC中最常用的乘法組件.該方案在預處理階段選取隨機數a,b和c，滿足c=ab，并為其生成加性份額ai,bi和ci(1≤i≤n).在線階段，參與方Pi擁有秘密數據x,y的加性份額xi,yi，Pi在本地計算xi-ai,yi-bi并廣播；收到其他參與方廣播的份額后Pi將份額相加得到x-a,y-b，然后對已有數據計算得到積的份額zi=(x-a)bi+(y-b)ai+ci.秘密恢復階段，每個參與方提供zi，對zi求和再與(x-a)(y-b)相加便能恢復出xy.

近年來由于機器學習等應用場景的需要，涌現出基于SS-MPC實現的PPML方案，包括ABY3和SecureNN等.這些方案的底層協議是加法、乘法和比較等基本算子的SS-MPC協議，高層協議實現了機器學習模塊的隱私保護，本節主要關注這些方案的底層協議.由于加法運算在本地對份額相加即可，乘法運算的流程相對復雜，因此主要對乘法運算進行分析.

SS-MPC最初提出時交互輪數多、通信量也較大，大多數SS-MPC方案都是對這2個指標進行優化.優化方法主要包括引入相關隨機數、將計算前移到預處理階段以及增加計算方的數量等.為了解決計算方的單點失效問題，一些方案構造了門限秘密分享來提高系統容錯能力.

2008年提出的Sharemind[72]設計了半誠實安全的三方SS-MPC方案.秘密分享的過程為：數據擁有方對數據x,y計算加性份額xi,yi(i=1,2,3)并分發給計算方Pi.計算乘法的過程為：Pi在本地計算xiyi，3個計算方交互計算得到交叉項xiyj(i,j=1,2,3).例如計算交叉項x1y2，P3選取隨機數a1,a2并分別分發給P1,P2，然后計算w3=a1a2作為自己的份額；P1和P2分別計算x1+a1,y2+a2并發送給對方，然后P1,P2通過計算分別得到份額w1=-a1(y2+a2),w2=y2(x1+a1).至此，每個Pi分別得到交叉項x1y2的份額wi，滿足w1+w2+w3=x1y2，其他交叉項的計算同理.最終Pi將自己的本地份額與交叉項份額相加得到xy的份額.

為了降低Sharemind的輪數和通信量，2016年Araki等人提出的方案AFL+16[73]引入相關隨機數，并通過設置冗余秘密份額構造了半誠實安全的2-out-of-3 SS-MPC方案.該方案設計了算術、布爾2種秘密分享方案，以算術秘密分享為例，秘密分享的過程為：數據擁有方選取3個和為0的l位長隨機串a1,a2,a3，滿足a1+a2+a3=0，然后計算秘密數據x的加性份額xi=ai-1-x(i=1,2,3)，令i=1時i-1=3，同理可計算秘密數據y的加性份額.數據擁有方向計算方Pi分發份額(ai,xi),(bi,yi).計算乘法的過程為：Pi選取隨機數αi，計算ri=(xiyi-aibi+αi)/3并將ri發給Pi+1，其中α1+α2+α3=0；收到其他參與方的信息后，Pi計算積的份額(ci,zi)：ci=-ri-1-ri,zi=-2ri-1-ri.秘密恢復時任意2個計算方可以恢復出xy.

2018年提出的ABY3[74]受到AFL+16設置冗余份額的啟發，基于此設計了新的2-out-of-3 SS-MPC方案，進一步通過份額校驗實現了惡意安全方案.秘密分享的過程為：數據擁有方計算長度為l位的秘密數據x,y的加性份額xi,yi(i=1,2,3)，并向3個計算方Pi分發份額(xi,xi+1),(yi,yi+1).計算乘法的過程為：Pi在本地計算得到積的份額zi=xiyi+xiyi+1+xi+1yi+αi并將其發給Pi-1，其中α1+α2+α3=0.在秘密恢復階段，任意2個計算方可以恢復出xy.ABY3通過使用Beaver三元組來完成份額校驗，實現的惡意安全方案最多能夠容忍一個惡意參與方.

為了降低ABY3在線階段的通信量和交互輪數，2019年提出的ASTRA[75]將一個計算方的運算前移到預處理階段進行.秘密分享的過程為：在離線階段數據擁有方P0同時也是計算方，分別與計算方P1,P2使用PRF生成2個隨機數rx,1,rx,2，在線階段P0計算秘密數據x的份額mx=x+rx并發送給P1,P2，其中rx=rx,1+rx,2,P1,P2分別設置x的份額為(mx,rx,1),(mx,rx,2)，秘密y的份額同理可得.計算乘法的過程為：離線階段P0和P1生成隨機數rz,1,rxy,1，P0和P2生成隨機數rz,2,rxy,2，滿足rxy,1+rxy,2=rxry.在線階段的計算過程中，2個計算方Pi(i=1,2)分別計算mz,i=(i-1)×mxmy-mxry,i-myrx,i+rz,i+rxy,i，雙方交換份額相加得到mz=xy+rz,1+rz,2，設置份額為(mz,rz,i).在秘密恢復階段，任意2個計算方可以恢復出xy=mz-rz,1-rz,2.ASTRA的惡意安全方案在半誠實安全方案的基礎上加入一致性檢測，在輸入和輸出階段通過對比份額的哈希值來檢查份額一致性，在計算階段使用Beaver三元組驗證正確性.

2020年提出的BLAZE[76]對ASTRA中一致性檢測的預處理過程進行改進，將其通信量減少1/7.同年，TRIDENT[77]用另一種思路來提升ASTRA的性能，設計了四方秘密分享方案，在線階段需要3個參與方兩兩之間會生成積的份額及其哈希值，并發給另一方檢驗一致性.

SecureNN[78]是2019年提出的半誠實安全三方及四方SS-MPC方案.數據擁有方生成m×n維秘密矩陣x,n×v維秘密矩陣y的加性份額xi,yi(i=1,2)，并分發給計算方P1,P2，矩陣元素是長度為l位的比特串.三方秘密分享方案中計算乘法時采用Beaver三元組的思想，P0作為輔助節點來生成Beaver三元組以及其他隨機數，P1和P2是計算節點.四方秘密分享方案中P1,P2是計算節點，P3,P4是輔助計算節點.計算乘法運算時首先P1,P2分別在本地計算x1y1,x2y2；然后，P1分別把x1,y1發給P3,P4，P2分別把y2,x2發給P3,P4；收到份額后，P3,P4分別計算交叉項x1y2,x2y1并發送給P1,P2.在秘密恢復階段，將P1和P2擁有的份額相加即可恢復出矩陣xy.

2) 不誠實方占多數

在惡意安全的SS-MPC方案中，可以通過向秘密份額添加消息鑒別碼，來檢測計算過程中計算方是否存在篡改行為.這類方案主要包括BDOZ和SPDZ等，能夠用于不誠實方占多數的場景，達到了中止安全性，即發現參與方惡意行為時中止協議.

Bendlin等人[35]于2011年提出了BDOZ消息鑒別碼，在2個參與方的場景下，P1,P2分別擁有全局密鑰Δ1,Δ2，以及秘密x的加性份額x1,x2.秘密x的BDOZ份額用[x]來表示，P1擁有[x]1=(x1,M1,K1)，P2擁有[x]2=(x2,M2,K2).其中K1,K2是MAC密鑰，M1,M2是MAC值，滿足關系M1=K2+Δ2x1，M2=K1+Δ1x2.鑒別P1的份額x1時，P1向P2提供(x1,M1)，P2使用(K2,Δ2)驗證等式M1=K2+Δ2x1是否成立，若等式成立則鑒別通過，鑒別P2的份額同理.BDOZ可以擴展到n個參與方的場景，但是每個參與方都需要對其他n-1個參與方的MAC密鑰分別生成一個MAC，存儲開銷和參與方的數量成線性關系.

為了解決BDOZ中的存儲開銷問題，Damg?rd等人[79]于2012年提出另一種消息鑒別碼SPDZ，每個參與方只存儲恒定數量的MAC.SPDZ型MAC表示為M(x)=α×x，其中α為MAC全局密鑰、x為秘密數據.在SPDZ方案中，每個參與方Pi(1≤i≤n)持有密鑰α的加性秘密份額αi,x的加性秘密份額xi和MAC值M(x)的加性秘密份額M(x)i.驗證MAC時需要先恢復出x,α和M(x)再檢查等式M(x)=α×x是否成立.SPDZ型MAC滿足加法、常數乘法的同態性，計算乘法時需Beaver三元組協助來驗證份額.具體實現時，SPDZ在預處理階段使用FHE生成Beaver三元組和MAC，并使用零知識證明保證FHE密文的正確性.

Damg?rd等人于2013年提出SPDZ的改進方案[80]，該方案在驗證MAC時無需恢復MAC密鑰，因此可以繼續對還未驗證的秘密數據進行計算.驗證MAC時各參與方首先廣播xi，收到廣播的份額后計算得到x，然后各參與方分別計算Mi-xαi，對n個參與方的Mi-xαi求和，若求和的結果為0則驗證通過.

Keller等人[47]于2016年提出MASCOT，保持SPDZ的在線階段不變，在預處理階段使用COT生成Beaver三元組.Keller等人[81]于2018年提出方案KPD2018，使用BGV的加法同態代替原始方案中的FHE來生成Beaver三元組，獲得了比MASCOT更好的性能.

Cramer等人[82]于2018年提出了有限環上的方案SPDZ2K，環上的計算更接近于CPU計算單元的實際計算情況，有限環上的安全計算具備很高的實際意義，該方案的效率和有限域上的方案基本一致.

2.3.2 SS-MPC計算非線性運算

SS-MPC實現的非線性運算包括比較運算和最高有效位(most significant bit,MSB)運算.

SecureNN實現的比較運算可以比較秘密值和常數值的大小，參與方擁有p上秘密值x的比特份額和明文比特串r，秘密值和常數值長度均為l位.從低位到高位依次為第1,2,…,l個比特計算比較運算時，對x和r的第i位從高位到低位依次計算由于r[i]-x[i]+1≥0，所以只要存在ci=0則說明同時滿足和r[i]-x[i]=-1，即x和r的第i+1位至l位都相等且第i位x[i]>r[i]，由此可得x>r；若不存在ci=0則x

表2對SS-MPC方案的安全模型和性能進行了對比.我們對乘法、比較(或最高有效位)運算的通信量和交互輪數2個方面進行比較，其中l為秘密比特串長度，p為有限域的大小.通過對比發現，ASTRA是半誠實安全模型下性能最好的方案，TRIDENT和BLAZE在惡意安全模型下實現的乘法運算具有較好的性能，但是在計算最高有效位時TRIDENT的性能更好.SecureNN的乘法性能為矩陣乘法運算的性能，其他方案是單個數據乘法運算的性能.

Table 2 Comparison of SS-MPC Schemes表2 SS-MPC安全模型和性能比較

2.4 同態加密

同態加密支持對多個數據的密文進行運算，解密得到的結果與數據明文運算結果一致.即明文與密文的運算滿足同態性質：

Dec(Enc(x+y))=Dec(Enc(x)⊕Enc(y)),

其中,+和⊕分別是明文和密文空間上的運算.

早在1978年Rivest等人就提出了隱私同態(privacy homomorphism)的概念，但這個概念一直被認為是一個開放性的問題，直到2009年Gentry提出首個全同態加密方案，證明了在加密數據上計算任何函數的可行性.

同態加密可以劃分為部分同態加密(partial homomorphic encryption, PHE)、淺同態加密(somewhat homomorphic encryption, SHE)和全同態加密(fully homomorphic encryption, FHE).部分同態加密僅支持單一類型的密文同態運算，主要包括加法同態(additive homomorphic encryption, AHE)和乘法同態(multiplicative homomorphic encryption, MHE)，代表方案分別為Paillier[83]和ElGamal[84].淺同態加密支持低次多項式運算.全同態加密的構造均遵循Gentry的思想藍圖，利用自舉(bootstrapping)技術將淺同態加密方案轉換為全同態加密方案，即通過同態地執行解密電路以更新密文、約減噪音，從而支持進一步的同態運算.目前主流的FHE方案大多基于格上的困難問題(主要是LWE,RLWE)構造，代表方案包括BGV[85],BFV[86-87],GSW[88],CGGI[89],CKKS[90]等.

基于(R)LWE構造的同態方案中，密鑰切換(key switching)技術和模切換(modulus switching)技術分別用于解決同態乘法運算導致的密文維數和噪音量級增長問題.為了降低自舉導致的性能開銷，BGV方案利用密鑰切換和模切換技術實現了一種不需要自舉就能構造的層次全同態加密(leveled fully homomorphic encryption, leveled FHE)方案.層次全同態加密根據方案預期計算的電路深度設置參數，能夠計算任意多項式深度的電路，已經可以滿足多數應用場景下的計算需求.BFV方案中提出了一種新的張量技術，構造了一個標量不變的leveled FHE方案.GSW方案是基于近似特征向量法建立的簡單全同態加密方案，消除了密鑰切換過程，使得同態加法和乘法在很大程度上就是矩陣的加法和乘法.CGGI方案通過在環面上構造RGSW和RLWE的外部積，對加密比特進行門自舉，在運行時間和可用性上具有優勢.CKKS方案構造類似于BGV方案，支持定點數的近似運算.

根據明文空間的不同，同態加密方案可以進一步分為逐字同態加密(word-wise HE)和逐比特同態加密(bit-wise HE)兩類.逐字運算的HE方案例如BGV,BFV和CKKS等，優點是支持打包技術，可以將多個明文打包為單個密文并以單指令多數據方式對明文進行操作，提高了運算效率；早期的逐字運算方案只支持加法及乘法等多項式計算，難以有效支持除法、根號等非多項式運算，2020年Cheon等人[91]提出通過復合多項式近似符號函數使用CKKS來實現同態比較.逐比特運算的HE方案包括TFHE,FHEW[92]等，優點是可以支持非多項式運算，但是由于不能使用打包技術導致性能顯著低于逐字運算方案.阿里巴巴于2020年提出的全同態加密技術PEGASUS有效橋接逐字運算方案CKKS和逐比特運算方案FHEW兩類全同態加密技術，使用CKKS密文有效計算線性函數，轉換為FHEW密文形式后可通過查表來計算非線性運算.

單密鑰同態方案只能對同一個密鑰加密的密文進行運算，而多密鑰全同態加密(Multikey-FHE, MKHE)支持對不同密鑰加密的密文進行同態運算，但需要參與方聯合解密密文.2012年首個NTRU型的MKHE方案提出[93]，此后MKHE技術迅速發展，相繼提出GSW型的MKHE[94-97]、BGV型的MKHE[98-99]和TFHE型的MKHE[100].MKHE方案的構造和實現上仍需進一步的優化，主要關注多跳功能(允許運算過程中有新的參與方加入)的實現、密鑰(參與方)數量上限、密文增長、密鑰切換優化等多個方面.

全同態加密可用于機器學習中的隱私保護并保持非交互性，比如PEGASUS[101]可以使用2種同態技術實現機器學習中的線性和非線性運算.文獻[100]中數據擁有方和模型擁有方分別使用自己的公鑰加密數據，并將其發送給服務器，服務器能夠對2種密鑰加密的密文進行運算.

3 MPC基礎技術的比較

本節對混淆電路、秘密分享和同態加密3類MPC基礎技術的計算方數量、計算量、通信量和交互輪數進行分析對比，如表3所示：

Table 3 Comparison of MPC Fundamental Schemes表3 不同MPC基礎技術對比

GC-MPC由于實現了底層的基本邏輯運算符，因此具有通用性，可面向不同的應用邏輯.GC-MPC一般有2個計算方，若是基于BMR實現的協議則可以支持多個計算方.混淆電路的計算開銷主要是對稱加密或哈希函數的計算，計算開銷較小；混淆電路交互輪數是恒定的2輪，通信量與電路門的數量成正比.GC-MPC在計算簡單邏輯運算時具有優勢，如比較運算和加法運算，但是在計算復雜運算時會產生龐大的電路從而導致通信量很大、性能降低.目前沒有出現針對大數據量復雜計算的GC-MPC處理平臺，GC-MPC只在一些小數據量、簡單計算場景中有具體應用，比如拍賣、薪水公平性調研等.

SS-MPC的計算方數量一般大于2，SS-MPC計算方的運算都是簡單的加法和乘法運算，不涉及模冪運算，因此計算開銷小.SS-MPC的輪數和電路深度成線性關系，導致計算方端到端通信會有較長時延.近年來隨著算法優化和網絡帶寬不斷提升，SS-MPC的性能優勢不斷凸顯，逐漸成為目前應用最廣的MPC技術.SS-MPC不僅能高效計算加法和乘法等線性運算，還能夠計算比較大小、最高有效位和除法等非線性運算.目前SS-MPC的實際應用有Sharemind MPC等通用計算平臺，以及CrypTFlow等PPML開源實現.

HE-MPC通常支持兩方運算，多密鑰HE支持多方運算.HE-MPC的輪數恒定、通信量比前2種MPC技術小.但是HE-MPC的計算開銷很大，其中同態加法和標量乘法(明文和同態密文相乘)計算開銷相對較小，然而同態乘法無論是自舉，還是leveled FHE都需要對密文進行降維和降噪從而產生大量計算開銷.此外，一些HE方案密鑰和密文空間復雜度高，需要較大的存儲開銷.對于一些具有深度較大的布爾或算術電路，同態加密計算效率難以被實際應用接受.

在實際應用中，計算函數一般是線性運算和非線性運算的組合，由于GC,SS和HE適用于不同場景，將多種MPC技術結合的混合技術能夠獲得更好的性能.表4中對現有MPC的實現進行總結.

Table 4 The Implementations of MPC Schemes表4 MPC方案方現

4 隱私保護機器學習

機器學習廣泛應用于計算機視覺、語音識別和自然語言處理等領域.圖4為機器學習層次結構圖，第1層為機器學習典型算法，第2層為機器學習組成模塊，第3層為機器學習基本算子.

Fig. 4 The hierarchy of machine learning圖4 機器學習層次結構圖

機器學習算法主要包括神經網絡(neural networks, NN)、線性回歸(linear regression)和邏輯回歸(logistic regression)等.神經網絡是機器學習應用最廣泛的算法，由輸入層、隱藏層和輸出層構成，其中隱藏層包括卷積層(convolutional layer, CONV)、全連接層(fully connected layers, FC)和池化層(pooling layer).卷積層的運算是過濾器矩陣和數據特征向量的內積運算；全連接層的運算是先計算神經元向量與權重矩陣的內積再與偏移向量相加；池化層是計算過濾器窗口內元素的最大值或平均值，分別稱為最大池化層和平均池化層.神經網絡隱藏層和輸出層都要使用激活函數(activation function)為神經元引入非線性因素，使得神經網絡可以逼近任何非線性函數，隱藏層常用的激活函數有ReLU,Sigmoid和tanh.線性回歸和邏輯回歸算法相對簡單，都可以看作是單層神經網絡，其中邏輯回歸使用了Sigmoid激活函數.

從機器學習底層的基本算子來看，卷積層、全連接層和平均池化層可以使用加法和乘法2種線性運算實現.最大池化層可以使用比較大小或最高有效位等非線性運算來實現.激活函數在PPML方案中通常被轉換為線性運算和非線性運算的組合，例如將ReLU表示為ReLU(x)=max(0,x)=(MSB(x)⊕1)×x，文獻[111]中提出可以使用多項式來近似激活函數Sigmoid(x)=1/(1+e-x)：

將激活函數轉換為加法、乘法和比較等基本算子組合函數的方法，可以更好地使用MPC來進行運算.

神經網絡模型訓練最常用的優化算法是梯度下降優化(gradient descent optimization)算法，包括正向傳播和反向傳播2個過程：正向傳播是輸入信息通過輸入層經隱藏層逐層處理并傳向輸出層，然后對輸出值計算損失函數；反向傳播是依據微積分中的鏈式法則沿著輸出層到輸入層計算中間變量和參數的梯度，并更新參數；訓練模型需要重復正向傳播和反向傳播多次直到模型收斂.神經網絡推理的運算是一次正向傳播的過程.在機器學習的計算過程中，用戶數據和模型參數是浮點數的形式，而MPC只能對整數類型的數據做運算，因此在使用MPC完成PPML時，要將浮點數轉換為固定點數(固定精度的整數)，并且在計算乘法后要計算截斷運算.

機器學習分為3種明文架構，在客戶端-服務器架構中，客戶端向服務器發送明文數據，服務器計算推理結果并返回給客戶端.在外包計算架構中，數據擁有方(模型擁有方)將其數據(模型)發送給一組外包服務器，服務器得到運算結果后將其返回給數據擁有方.在聯邦學習架構中，客戶端在本地使用私有數據訓練得到局部模型并將其上傳到中央服務器，服務器聚合得到更新的模型.

針對明文的機器學習架構無法保證用戶私有數據和服務商模型參數的隱私性，在明文架構中引入MPC技術能夠實現隱私保護,得到3種基于MPC的PPML架構，分別為安全客戶端-服務器架構(secure client server, S-CS)、安全外包計算(secure outsourced computation, S-OC)、安全聯邦學習(secure federated learning, S-FL),如圖5所示:

Fig. 5 The construction of PPLM based MPC圖5 基于MPC的PPML架構圖

基于S-CS架構的PPML方案用于做神經網絡推理，允許客戶端在不向服務器透露其私有數據的情況下獲得神經網絡推理結果，同時保護服務器模型參數的隱私.該架構有時需要客戶端和服務器協同計算，由于服務器擁有更強的算力，在設計算法時傾向于為服務器分配相對復雜的運算.與明文CS架構相比，S-CS架構中客戶端通常需要參與運算.

基于S-OC架構的PPML方案支持神經網絡的訓練和推理.數據擁有方對私有數據計算份額后發送給一組不會合謀的服務器.在神經網絡推理時，模型參數擁有方以秘密分享的方式將其機器學習模型托管到一組服務器上，客戶端將私有數據秘密分享給這組服務器，每個服務器對私有數據份額、模型參數份額進行模型推理的協同計算，每個服務器將得到的推理結果份額返回給客戶端，客戶端對其進行秘密恢復后可得到完整的推理結果.在神經網絡訓練時，多個數據擁有方以秘密分享的方式將數據集托管到一組服務器上，服務器在聯合數據集上訓練機器學習模型.與明文OC架構不同，S-OC架構的計算服務器彼此之間不能合謀.

基于S-FL架構的PPML方案可以防止中央服務器執行模型逆向攻擊(model inversion attack)來推測出用戶的私有訓練集，與明文FL架構不同，S-FL架構客戶端在本地得到局部模型參數后，需要對其加密后再上傳至中央服務器.

4.1 基于S-CS架構的PPML

從MPC技術、性能和準確率3個方面對基于S-CS架構的PPML進行總結，如表5所示.表5中的方案都實現了多個基準工作的評估，本節選取部分評估實驗來對比性能.其中Delphi和CrypTFlow2使用深度神經網絡ResNet-32對CIFAR-100數據集進行推理，其余方案只在淺層神經網絡實現了對MNIST數據集的推理.

Table 5 The PPML Schemes based on S-CS Architecture表5 基于S-CS架構的PPML方案

從實現S-CS的MPC技術來看，CryptoNets,DeepSecure分別是基于單一技術HE和GC設計的方案，分別產生了較大的計算開銷和通信開銷.之后的PPML方案考慮線性層和非線性層的不同計算特性，組合多種MPC技術實現安全運算，對此類方案分析為：

1) S-CS架構的線性層實現.主要使用AHE和SS技術，標量乘法可以轉換為AHE運算.MiniONN,GAZELLE和Delphi都使用AHE實現了線性層.GAZELLE與MiniONN相比，減少了同態運算次數、客戶端和服務器的交互次數，并且設計了適用于機器學習的同態線性代數核.Delphi與GAZELLE相比，將在線階段繁重的同態運算前移到預處理運算，降低了在線階段的計算開銷.Chameleon和CrypTFlow2分別使用SS，COT來實現線性層的運算.此外，DeepSecure和XONN都是應用于模型參數為二進制數的網絡，因此使用GC來實現線性運算.

2) S-CS架構的非線性層實現.主要使用SS,GC和OT技術，使用SS來執行非線性層的運算.通常先對非線性運算進行多項式近似，然后再使用SS來執行運算，近似運算會導致準確率降低.使用GC來執行非線性層的運算雖然可以提高準確率，但是會增加通信開銷，例如GAZELLE.CrypTFlow2使用OT來執行非線性運算，能夠同時保證準確率和通信效率，獲得了優于GC約7倍的通信效率.此外，也有一些方案為了同時獲得可觀的準確率和通信效率，分別使用GC和SS各完成一部分非線性運算，例如MiniONN,Chameleon和Delphi.

3) S-CS架構的MPC技術演進分析.通用神經網絡(不包括BNN)線性層的實現只包含HE和SS技術，最早使用leveled FHE的方法來實現，其巨大的計算開銷嚴重影響了方案的可用性.此后提出的AHE實現的優化包括算法層面的優化，即構造適用于S-CS場景的同態線性代數核；以及協議層面的優化，即將繁重的HE運算前移到預處理階段，同時結合SS來完成線性運算，降低在線階段的計算開銷.通用神經網絡非線性層技術是影響整個方案性能開銷、準確率的關鍵，GC和SS分別只能滿足高準確率和高性能，而無法同時達到最優效果.2020年提出的CrypTFlow2使用OT計算非線性運算，在保證準確率的前提下極大地提高了計算、通信效率.

CryptoNets[112]是Microsoft提出的第一個使用同態加密實現隱私保護機器學習的方案，該方案的缺點是使用LHE友好的激活函數(例如平方函數)代替常用的ReLU和Sigmoid，影響了結果準確性，并且在犧牲準確性的前提下，計算成本依然非常大.CryptoNets每小時可完成59 000次推理.

MiniONN[113]的線性層結合加性秘密分享和同態加密2種技術實現，客戶端將私有數據拆分為2份并將其中一份發給服務器，服務器計算模型參數的同態密文并發給客戶端，客戶端對該密文和自己的數據份額計算乘法并將結果發給服務器，服務器結合這些信息可以計算出線性層的輸出.對于非線性層，使用GC來計算激活函數ReLU，使用SS來計算激活函數Sigmoid和Tanh的多項式近似函數.

Chameleon[114]的線性層使用秘密分享方案Beaver三元組來計算，引入可信第三方在離線階段生成相關隨機數.非線性層使用GMW或GC計算，由于GMW的輪數和電路深度有關，因此當電路深度較深時使用GC計算非線性層，其余情況使用GMW計算非線性層.Chameleon的運行時間比MiniONN快4.2倍.

GAZELLE方案[115]設計了同態線性代數核來優化同態運算，并使用優化的AHE方案計算線性層，使用GC來計算ReLU所需的比較運算，并通過加性秘密分享技術在LHE和GC之間有效切換.計算線性層時，客戶端計算輸入數據x的密文Enc(x)并發送給服務器，服務器對Enc(x)和自己擁有的模型明文參數計算標量乘法得到線性層輸出的密文Enc(y).由于密文Enc(y)不能直接作為GC的輸入，并且如果將Enc(y)發給客戶端解密可能會泄露模型參數.使用秘密分享可以解決這個問題：服務器選取隨機數作為份額-ys，并計算Enc(y)+Enc(ys)=Enc(y+ys)發送給客戶端，客戶端解密獲得份額yc=y+ys，將yc和-ys作為GC的輸入便能計算非線性函數.GAZELLE方案在線階段的運行時間比Chameleon快20倍.

Delphi[116]將GAZELLE線性層繁重的同態加密運算前移到預處理階段，客戶端私有數據為x，服務器擁有模型參數M.在線性層的預處理階段，客戶端選取隨機數r，對其計算同態密文Enc(r)并發給服務器；服務器選取隨機數s作為線性層份額并計 算Enc(Mr-s)并發給客戶端；客戶端解密得到Mr-s并將其作為線性層份額.在線性層的在線階段，客戶端計算x-r并發送給服務器，服務器設置線性層份額為M(x-r)+s，可見雙方的份額之和等于線性計算結果Mx.對非線性層的改進是使用多項式近似激活函數并用Beaver三元組來計算，這種方法在減小開銷的同時也會導致準確率降低，考慮到效率和準確率的折中，在保證準確率滿足閾值的前提下最大化近似計算激活函數的數量，并分別使用GC和SS計算2部分激活函數.Delphi獲得的準確率與明文模型準確率相差不到0.04%，運行時間比GAZELLE快22倍、通信效率提升9倍.

先前工作在實現ReLU時存在通信開銷大或準確率低等問題，CrypTFlow2使用OT實現的比較大小運算避免了先前方案的弊端.參與方P0,P1在比較長度為l位的私有數據x和y時，可以將其拆分為高位、低位比特串的拼接x=x1‖x0,y=y1‖y0，使用式1{x

DeepSecure[117]和XONN適用于二進制神經網絡的安全推理.DeepSecure對GC組件進行優化并引入了降低開銷的預處理技術，運行時間優于CryptoNets，但同時也帶來了更大的通信開銷.XONN[118]將神經網絡中線性層的運算轉換為向量點乘運算，神經網絡第一層客戶端輸入數據是整數、神經網絡權重是二進制，使用OT計算整數和二進制數的向量點乘；神經網絡中間層運算數據都是二進制值0和1，使用同或(XNOR)和加法來計算二進制點乘運算，由于可用XOR代替XNOR運算，且GC已經實現Free-XOR，因此整個方案的開銷較小，性能優于GAZELLE方案7倍.

4.2 基于S-OC架構的PPML

從參與方數量、機器學習功能、安全模型和MPC技術等方面對現有基于S-OC架構的PPML方案進行總結，如表6所示：

Table 6 The PPLM Schemes Based on S-OC Architecture表6 基于S-OC架構的PPML方案

1) S-OC架構的MPC技術.基于S-OC架構的方案主要使用秘密分享技術，通常需要2～4個計算方協同計算.ABY3等方案通過設置冗余的加性秘密份額實現了門限的效果，可以容忍一個參與方的單點失效，增強了系統的容錯能力，其中ABY3實現了中止安全性，ASTRA等實現了安全性更強的公平性.

2) S-OC架構的安全模型.部分方案只設計了單一安全模型下的方案，例如半誠實安全模型下的SecureML、惡意安全模型下的BLAZE，還有一些方案分別構造了半誠實和惡意2種安全模型下的方案，例如ASTRA等.

3) S-OC架構支持的機器學習功能.表6中所有方案都能支持神經網絡推理，除ASTRA和CrypTFlow以外其他方案都能支持神經網絡訓練.

4) S-OC架構與S-CS架構的對比.S-CS架構中應用了多種MPC技術，包括AHE,OT,GC,SS等.而在S-OC架構中主要使用單一的SS技術，因為機器學習在訓練模型時需要迭代計算多次，SS是計算開銷最小的MPC技術，能夠有效降低模型訓練時間.現有的HE和OT方案無法有效支持S-OC架構下的安全多方計算.

SecureML是半誠實安全模型下的兩方計算方案.整個訓練過程分為離線和在線2個階段，離線階段利用HE或者OT生成Beaver三元組；在線階段計算線性層運算時使用秘密分享技術，計算激活函數時使用平方函數做近似并通過GC來計算，然而近似運算導致精度降低，只獲得了93.4%的準確率.

與SecureML結構類似，QUOTIENT[119]也是半誠實安全模型下的兩方計算方案.該方案將模型參數表示為三元值{-1,0,1}、私有數據表示為整數形式，因此計算方需要對算術份額和布爾份額進行運算，使用COT來完成乘法運算，使用GC來完成非線性運算.QUOTIENT的模型推理采用S-CS架構，而其他S-OC方案的模型推理依然是外包給計算方來完成.QUOTIENT對ResNet32模型進行訓練，準確率與明文模型相比只降低了0.1%～2.17%，與SecureML相比運行效率提高了13倍.

ABY3是首個三方計算場景下的混合協議，由算術秘密分享、布爾秘密分享和姚氏電路3種MPC技術構成.三方的設置無法使用傳統的兩方混淆電路方案，只能使用專門為三方設計的混淆電路.該方案還設計了不同MPC技術的高效切換協議.ABY3使用MNIST數據集訓練得到的模型準確性為93%～99%，神經網絡、線性回歸的訓練時間比SecureML快80～55 000倍.

ASTRA對ABY3線性計算的改進是將一部分在線階段的運算前移到預處理階段，對非線性運算的改進是使用秘密分享代替并行前綴加法器，獲得了恒定輪數的效果.ASTRA只實現了線性回歸、邏輯回歸等模型的安全推理，而未實現模型訓練.BLAZE與ASTRA相比的改進是提供對神經網絡模型的支持，并且增加模型訓練的功能.TRIDENT在ABY3的基礎上,將線性層的截斷計算和乘法計算合并來避免額外的通信開銷，并且優化了ASTRA的最高有效位計算方法.

SecureNN僅使用秘密分享技術構造了神經網絡中的線性層和非線性層，四方設置比三方設置獲得更好的性能，其對MNIIST數據集進行模型訓練和推理，獲得93.4%～99.15%的準確率，比明文模型訓練開銷增加17～33倍.

SecureNN等方案在實現時都需要手動在MPC友好的低級語言或開發庫上實現PPML模型，這種方式對ML開發者不夠友好.CrypTFlow[120]編譯器能夠自動將TensorFlow的推理代碼轉換為多種MPC協議，在實現編譯器后端MPC協議時對SecureNN三方計算方案的通信效率進行改進，更便于開發者使用.SecureNN將矩陣x和y的卷積計算轉換為更大的矩陣x′和y′的乘法，然后使用Beaver三元組來計算x′和y′的積來獲得卷積結果，其中變形矩陣x′有冗余參數會增大通信開銷.CrypTFlow的改進是先使用Beaver三元組計算原始矩陣x和y的積，得到中間結果的份額后，參與方在本地對矩陣進行轉換，避免交互過程中傳輸冗余的信息.CrypTFlow對SecureNN非線性層的改進是消除輔助節點向2個計算方發送份額的過程，將ReLU和最大池化層的通信開銷降低了1/4.最后，CrypTFlow使用SGX技術將MPC協議從半誠實安全轉換為惡意安全.CrypTFlow目前只實現了神經網絡推理，準確性與明文推理相近，半誠實安全方案和惡意安全方案的運行時間分別為30 s和2 min.

此外，國內提出的方案PrivPy[121]由語言前端和計算引擎后端組成，前端提供編程接口和代碼優化，后端執行基于秘密分享的隱私保護計算.PrivPy支持3種后端：PrivPy設計的2-out-of-4秘密分享協議后端、SPDZ和ABY3.PrivPy設計的后端需要采用二次秘密分享技術，前2個參與方獲得私有數據份額后，再計算新的份額發送給后2個計算方，通過冗余份額的設置，在秘密恢復階段只要有2個參與方即可恢復出計算結果.PrivPy實現的模型訓練和推理的性能均優于ABY3.

4.3 基于S-FL架構的PPML

聯邦學習(FL)是為了解決數據孤島問題而提出的機器學習算法，由一個中央服務器和多個客戶端組成.客戶端在本地使用私有數據訓練模型，將模型梯度發送至中央服務器.服務器整合多個客戶端的模型梯度得到全局模型.FL架構僅需要傳輸模型梯度，客戶端的私有數據自始至終沒有離開本地，即便如此，研究表明中央服務器可以通過對模型逆向攻擊來推測出客戶端數據.

為了保護用戶數據隱私，Shokri等人[122]于2015年提出的方案在模型準確性和隱私保護之間進行折中，提出將模型梯度的1%～10%上傳到云服務器的方法.Aono等人[123]于2017年證明攻擊者從部分梯度中也能推測出有用信息，并使用密碼學來解決隱私泄露的問題：客戶端在本地使用加法同態算法對局部模型梯度加密并將密文上傳至中央服務器，服務器對各參與方的密文計算同態加法并將結果返回給客戶端，客戶端解密后得到更新的模型梯度.谷歌[124]于2017年提出了基于秘密分享實現的聯邦學習安全聚合方案，參與方使用秘密分享計算掩碼向量，使用掩碼向量對局部梯度計算異或加密并上傳至服務器.服務器先對收到的數據求和，然后使用秘密恢復技術計算出掩碼向量，并將其從求和值中消去，得到全局模型.該方案利用Shamir的門限特性，只要用戶數量滿足門限就消去掩碼，解決了實際應用中可能存在的用戶中途退出問題.谷歌將該方案應用于GBoard輸入法中來進行單詞預測.

目前已有一些基于MPC實現的聯邦學習框架投入使用.FATE項目最初使用加法同態加密技術來構建聯邦學習底層安全計算協議，在之后的版本上增加了SPDZ秘密分享協議，提供更多樣化的MPC協議支持.此外，2019年發布的PySyft是用于隱私保護深度學習的開源庫，將SPDZ等MPC技術和差分隱私集成到聯邦學習框架并向用戶提供應用程序接口.

5 總結與展望

安全多方計算提出的前20年一直停留在理論層面的研究，沒有應用于實際生活中的方案和系統.2000年以來，各種MPC基礎技術在實踐中都有了相應的系統實現，例如Fairplay,Sharemind MPC和SEAL等.在大數據應用的推動下，MPC基礎理論的迭代更新和工程實踐的廣泛應用體現了其學術和實用價值，MPC在未來的發展中有巨大的潛力和廣闊的發展前景.

PPML是當前最受關注的MPC應用領域，近年來在可用性和準確性等方面取得了很大的進步，但是仍然有許多問題需要解決，未來工作可圍繞以下3個方面展開.

1) 進一步提升準確率與系統性能.MPC實現的PPML方案開銷依然遠大于明文模型的運算，準確率與明文模型相比還是會有一定的損失.PPML方案非線性層的實現方式會為準確率帶來很大的影響，相對而言GC精度較高但性能開銷大，SS性能較好但無法達到GC的精度，現有PPML方案都在效率和準確率之間進行折中.最新提出的使用OT實現非線性運算的方案同時獲得了性能和準確率的保證，僅適用于兩方參與的場景.因此MPC基礎技術的優化將對PPML技術的性能優化起到重要作用.此外，在PPML使用混合技術方案中降低不同技術的轉換開銷也將進一步提升PPML技術的可用性.

2) 提升系統安全性.現有的很多方案都只滿足半誠實安全模型，未來需要進一步加強對惡意敵手的防御.另一方面，早期的惡意安全方案實現了中止安全性，2019年之后的方案都達到了更強的安全屬性-公平性，提升系統的安全屬性也是今后研究的一個重要方向，未來要實現的安全目標是能夠保證結果輸出(GOD)，并且在性能開銷也需要控制在可接受范圍內.

3) 降低模型隱私泄露風險.現有的部分S-CS架構下的方案會向客戶端泄露過濾器的大小、卷積的步長以及神經網絡隱藏層的種類等模型信息.未來仍需進一步探索對模型參數信息更有效的保護方案.