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

1(信息安全國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院信息工程研究所) 北京 100195) 2(中國科學(xué)院大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 北京 100049) 3(華控清交信息科技(北京)有限公司 北京 100084) 4(中國科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 合肥 230026)

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

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

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

不經(jīng)意傳輸(oblivious transfer, OT)由Rabin于1981年提出[4]，消息發(fā)送方擁有多個消息，接收方獲得其中某個值，發(fā)送方不知道接收方的選擇信息.其衍生技術(shù)相關(guān)不經(jīng)意傳輸(correlated oblivious transfer, COT)可以生成具有關(guān)系的隨機(jī)數(shù).OT,COT是重要的密碼學(xué)組件，能夠?yàn)镚C傳輸導(dǎo)線標(biāo)簽、為SS生成相關(guān)隨機(jī)數(shù)，只使用OT技術(shù)也能實(shí)現(xiàn)MPC協(xié)議.在OT的性能優(yōu)化歷程中，OT擴(kuò)展(OT Extension)技術(shù)引入對稱加密來降低計(jì)算開銷，靜默OT擴(kuò)展(silent OT Extension)技術(shù)在本地?cái)U(kuò)展隨機(jī)數(shù)種子來降低通信開銷.

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

以上4類MPC技術(shù)在計(jì)算性能、通信效率和存儲開銷等方面都具有各自的優(yōu)勢和劣勢，單一的MPC技術(shù)往往不能滿足實(shí)際應(yīng)用中計(jì)算復(fù)雜函數(shù)的需求，需要將多種MPC技術(shù)相結(jié)合才能獲得性能均衡的實(shí)現(xiàn)方案.

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

PPML方案涉及多種類型的運(yùn)算，考慮到參與方的數(shù)據(jù)規(guī)模不同、計(jì)算和網(wǎng)絡(luò)能力不同、安全模型不同，可以在具體場景下組合多種MPC技術(shù)來實(shí)現(xiàn)PPML方案.

1 安全模型及目標(biāo)

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

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

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

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

2 MPC技術(shù)發(fā)展

2.1 混淆電路

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

Fig. 1 Technological development of 2-party garbled circuit圖1 兩方參與的混淆電路技術(shù)發(fā)展脈絡(luò)

2.1.1 半誠實(shí)安全兩方混淆電路的性能優(yōu)化

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

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

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

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

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

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

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

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

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

2.1.2 惡意安全兩方混淆電路的性能優(yōu)化

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

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

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

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

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

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

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

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

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

2) 可鑒別的混淆電路

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

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

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

2.1.3 多方參與的混淆電路

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

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

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

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

2) 三方混淆電路

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

2.2 不經(jīng)意傳輸

不經(jīng)意傳輸(OT)是密碼學(xué)的基本協(xié)議原語之一，由Rabin于1981年提出.OT技術(shù)主要包括OT，OT擴(kuò)展以及相關(guān)不經(jīng)意傳輸(COT).OT在MPC場景中有廣泛的應(yīng)用：OT自身可實(shí)現(xiàn)多項(xiàng)式計(jì)算[44-45]和比較大小[46]；OT作為重要的MPC安全組件可與其他MPC技術(shù)結(jié)合應(yīng)用，例如OT在混淆電路中承擔(dān)著傳輸標(biāo)簽的任務(wù)；COT能夠?yàn)槊孛芊窒矸桨干上嚓P(guān)隨機(jī)數(shù)[47]、消息鑒別碼等.

Fig. 3 The technic of oblivious transfer圖3 OT技術(shù)原理

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

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

1) OT擴(kuò)展

Beaver[53]于1996年首次提出OT擴(kuò)展，使用κ(κ為計(jì)算安全參數(shù))個基礎(chǔ)OT(base OT)可以生成κ的多項(xiàng)式個OT，但是該方案需要使用GC計(jì)算復(fù)雜的偽隨機(jī)數(shù)發(fā)生器導(dǎo)致效率很低.

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

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

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

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

2) 相關(guān)不經(jīng)意傳輸

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

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

以上COT方案中，BCG+19a和Ferret基于VOLE實(shí)現(xiàn)了OT擴(kuò)展，而SGRR19沒有實(shí)現(xiàn)OT擴(kuò)展.

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

Table 1 Comparison of OT Extension Schemes表1 OT擴(kuò)展技術(shù)性能對比

2.3 秘密分享

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

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

2.3.1 SS-MPC計(jì)算線性運(yùn)算

SS-MPC根據(jù)系統(tǒng)中敵手控制的參與方數(shù)量，可分為誠實(shí)方占多數(shù)的SS-MPC和不誠實(shí)方占多數(shù)的SS-MPC.

1) 誠實(shí)方占多數(shù)

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

近年來由于機(jī)器學(xué)習(xí)等應(yīng)用場景的需要，涌現(xiàn)出基于SS-MPC實(shí)現(xiàn)的PPML方案，包括ABY3和SecureNN等.這些方案的底層協(xié)議是加法、乘法和比較等基本算子的SS-MPC協(xié)議，高層協(xié)議實(shí)現(xiàn)了機(jī)器學(xué)習(xí)模塊的隱私保護(hù)，本節(jié)主要關(guān)注這些方案的底層協(xié)議.由于加法運(yùn)算在本地對份額相加即可，乘法運(yùn)算的流程相對復(fù)雜，因此主要對乘法運(yùn)算進(jìn)行分析.

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

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

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

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

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

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

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

2) 不誠實(shí)方占多數(shù)

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

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值，滿足關(guān)系M1=K2+Δ2x1，M2=K1+Δ1x2.鑒別P1的份額x1時，P1向P2提供(x1,M1)，P2使用(K2,Δ2)驗(yàn)證等式M1=K2+Δ2x1是否成立，若等式成立則鑒別通過，鑒別P2的份額同理.BDOZ可以擴(kuò)展到n個參與方的場景，但是每個參與方都需要對其他n-1個參與方的MAC密鑰分別生成一個MAC，存儲開銷和參與方的數(shù)量成線性關(guān)系.

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

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

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

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

2.3.2 SS-MPC計(jì)算非線性運(yùn)算

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

SecureNN實(shí)現(xiàn)的比較運(yùn)算可以比較秘密值和常數(shù)值的大小，參與方擁有p上秘密值x的比特份額和明文比特串r，秘密值和常數(shù)值長度均為l位.從低位到高位依次為第1,2,…,l個比特計(jì)算比較運(yùn)算時，對x和r的第i位從高位到低位依次計(jì)算由于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方案的安全模型和性能進(jìn)行了對比.我們對乘法、比較(或最高有效位)運(yùn)算的通信量和交互輪數(shù)2個方面進(jìn)行比較，其中l(wèi)為秘密比特串長度，p為有限域的大小.通過對比發(fā)現(xiàn)，ASTRA是半誠實(shí)安全模型下性能最好的方案，TRIDENT和BLAZE在惡意安全模型下實(shí)現(xiàn)的乘法運(yùn)算具有較好的性能，但是在計(jì)算最高有效位時TRIDENT的性能更好.SecureNN的乘法性能為矩陣乘法運(yùn)算的性能，其他方案是單個數(shù)據(jù)乘法運(yùn)算的性能.

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

2.4 同態(tài)加密

同態(tài)加密支持對多個數(shù)據(jù)的密文進(jìn)行運(yùn)算，解密得到的結(jié)果與數(shù)據(jù)明文運(yùn)算結(jié)果一致.即明文與密文的運(yùn)算滿足同態(tài)性質(zhì)：

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

其中,+和⊕分別是明文和密文空間上的運(yùn)算.

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

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

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

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

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

全同態(tài)加密可用于機(jī)器學(xué)習(xí)中的隱私保護(hù)并保持非交互性，比如PEGASUS[101]可以使用2種同態(tài)技術(shù)實(shí)現(xiàn)機(jī)器學(xué)習(xí)中的線性和非線性運(yùn)算.文獻(xiàn)[100]中數(shù)據(jù)擁有方和模型擁有方分別使用自己的公鑰加密數(shù)據(jù)，并將其發(fā)送給服務(wù)器，服務(wù)器能夠?qū)?種密鑰加密的密文進(jìn)行運(yùn)算.

3 MPC基礎(chǔ)技術(shù)的比較

本節(jié)對混淆電路、秘密分享和同態(tài)加密3類MPC基礎(chǔ)技術(shù)的計(jì)算方數(shù)量、計(jì)算量、通信量和交互輪數(shù)進(jìn)行分析對比，如表3所示：

Table 3 Comparison of MPC Fundamental Schemes表3 不同MPC基礎(chǔ)技術(shù)對比

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

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

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

在實(shí)際應(yīng)用中，計(jì)算函數(shù)一般是線性運(yùn)算和非線性運(yùn)算的組合，由于GC,SS和HE適用于不同場景，將多種MPC技術(shù)結(jié)合的混合技術(shù)能夠獲得更好的性能.表4中對現(xiàn)有MPC的實(shí)現(xiàn)進(jìn)行總結(jié).

Table 4 The Implementations of MPC Schemes表4 MPC方案方現(xiàn)

4 隱私保護(hù)機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)廣泛應(yīng)用于計(jì)算機(jī)視覺、語音識別和自然語言處理等領(lǐng)域.圖4為機(jī)器學(xué)習(xí)層次結(jié)構(gòu)圖，第1層為機(jī)器學(xué)習(xí)典型算法，第2層為機(jī)器學(xué)習(xí)組成模塊，第3層為機(jī)器學(xué)習(xí)基本算子.

Fig. 4 The hierarchy of machine learning圖4 機(jī)器學(xué)習(xí)層次結(jié)構(gòu)圖

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

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

將激活函數(shù)轉(zhuǎn)換為加法、乘法和比較等基本算子組合函數(shù)的方法，可以更好地使用MPC來進(jìn)行運(yùn)算.

神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練最常用的優(yōu)化算法是梯度下降優(yōu)化(gradient descent optimization)算法，包括正向傳播和反向傳播2個過程：正向傳播是輸入信息通過輸入層經(jīng)隱藏層逐層處理并傳向輸出層，然后對輸出值計(jì)算損失函數(shù)；反向傳播是依據(jù)微積分中的鏈?zhǔn)椒▌t沿著輸出層到輸入層計(jì)算中間變量和參數(shù)的梯度，并更新參數(shù)；訓(xùn)練模型需要重復(fù)正向傳播和反向傳播多次直到模型收斂.神經(jīng)網(wǎng)絡(luò)推理的運(yùn)算是一次正向傳播的過程.在機(jī)器學(xué)習(xí)的計(jì)算過程中，用戶數(shù)據(jù)和模型參數(shù)是浮點(diǎn)數(shù)的形式，而MPC只能對整數(shù)類型的數(shù)據(jù)做運(yùn)算，因此在使用MPC完成PPML時，要將浮點(diǎn)數(shù)轉(zhuǎn)換為固定點(diǎn)數(shù)(固定精度的整數(shù))，并且在計(jì)算乘法后要計(jì)算截?cái)噙\(yùn)算.

機(jī)器學(xué)習(xí)分為3種明文架構(gòu)，在客戶端-服務(wù)器架構(gòu)中，客戶端向服務(wù)器發(fā)送明文數(shù)據(jù)，服務(wù)器計(jì)算推理結(jié)果并返回給客戶端.在外包計(jì)算架構(gòu)中，數(shù)據(jù)擁有方(模型擁有方)將其數(shù)據(jù)(模型)發(fā)送給一組外包服務(wù)器，服務(wù)器得到運(yùn)算結(jié)果后將其返回給數(shù)據(jù)擁有方.在聯(lián)邦學(xué)習(xí)架構(gòu)中，客戶端在本地使用私有數(shù)據(jù)訓(xùn)練得到局部模型并將其上傳到中央服務(wù)器，服務(wù)器聚合得到更新的模型.

針對明文的機(jī)器學(xué)習(xí)架構(gòu)無法保證用戶私有數(shù)據(jù)和服務(wù)商模型參數(shù)的隱私性，在明文架構(gòu)中引入MPC技術(shù)能夠?qū)崿F(xiàn)隱私保護(hù),得到3種基于MPC的PPML架構(gòu)，分別為安全客戶端-服務(wù)器架構(gòu)(secure client server, S-CS)、安全外包計(jì)算(secure outsourced computation, S-OC)、安全聯(lián)邦學(xué)習(xí)(secure federated learning, S-FL),如圖5所示:

Fig. 5 The construction of PPLM based MPC圖5 基于MPC的PPML架構(gòu)圖

基于S-CS架構(gòu)的PPML方案用于做神經(jīng)網(wǎng)絡(luò)推理，允許客戶端在不向服務(wù)器透露其私有數(shù)據(jù)的情況下獲得神經(jīng)網(wǎng)絡(luò)推理結(jié)果，同時保護(hù)服務(wù)器模型參數(shù)的隱私.該架構(gòu)有時需要客戶端和服務(wù)器協(xié)同計(jì)算，由于服務(wù)器擁有更強(qiáng)的算力，在設(shè)計(jì)算法時傾向于為服務(wù)器分配相對復(fù)雜的運(yùn)算.與明文CS架構(gòu)相比，S-CS架構(gòu)中客戶端通常需要參與運(yùn)算.

基于S-OC架構(gòu)的PPML方案支持神經(jīng)網(wǎng)絡(luò)的訓(xùn)練和推理.數(shù)據(jù)擁有方對私有數(shù)據(jù)計(jì)算份額后發(fā)送給一組不會合謀的服務(wù)器.在神經(jīng)網(wǎng)絡(luò)推理時，模型參數(shù)擁有方以秘密分享的方式將其機(jī)器學(xué)習(xí)模型托管到一組服務(wù)器上，客戶端將私有數(shù)據(jù)秘密分享給這組服務(wù)器，每個服務(wù)器對私有數(shù)據(jù)份額、模型參數(shù)份額進(jìn)行模型推理的協(xié)同計(jì)算，每個服務(wù)器將得到的推理結(jié)果份額返回給客戶端，客戶端對其進(jìn)行秘密恢復(fù)后可得到完整的推理結(jié)果.在神經(jīng)網(wǎng)絡(luò)訓(xùn)練時，多個數(shù)據(jù)擁有方以秘密分享的方式將數(shù)據(jù)集托管到一組服務(wù)器上，服務(wù)器在聯(lián)合數(shù)據(jù)集上訓(xùn)練機(jī)器學(xué)習(xí)模型.與明文OC架構(gòu)不同，S-OC架構(gòu)的計(jì)算服務(wù)器彼此之間不能合謀.

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

4.1 基于S-CS架構(gòu)的PPML

從MPC技術(shù)、性能和準(zhǔn)確率3個方面對基于S-CS架構(gòu)的PPML進(jìn)行總結(jié)，如表5所示.表5中的方案都實(shí)現(xiàn)了多個基準(zhǔn)工作的評估，本節(jié)選取部分評估實(shí)驗(yàn)來對比性能.其中Delphi和CrypTFlow2使用深度神經(jīng)網(wǎng)絡(luò)ResNet-32對CIFAR-100數(shù)據(jù)集進(jìn)行推理，其余方案只在淺層神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了對MNIST數(shù)據(jù)集的推理.

Table 5 The PPML Schemes based on S-CS Architecture表5 基于S-CS架構(gòu)的PPML方案

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

1) S-CS架構(gòu)的線性層實(shí)現(xiàn).主要使用AHE和SS技術(shù)，標(biāo)量乘法可以轉(zhuǎn)換為AHE運(yùn)算.MiniONN,GAZELLE和Delphi都使用AHE實(shí)現(xiàn)了線性層.GAZELLE與MiniONN相比，減少了同態(tài)運(yùn)算次數(shù)、客戶端和服務(wù)器的交互次數(shù)，并且設(shè)計(jì)了適用于機(jī)器學(xué)習(xí)的同態(tài)線性代數(shù)核.Delphi與GAZELLE相比，將在線階段繁重的同態(tài)運(yùn)算前移到預(yù)處理運(yùn)算，降低了在線階段的計(jì)算開銷.Chameleon和CrypTFlow2分別使用SS，COT來實(shí)現(xiàn)線性層的運(yùn)算.此外，DeepSecure和XONN都是應(yīng)用于模型參數(shù)為二進(jìn)制數(shù)的網(wǎng)絡(luò)，因此使用GC來實(shí)現(xiàn)線性運(yùn)算.

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

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

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

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

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

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

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

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

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

4.2 基于S-OC架構(gòu)的PPML

從參與方數(shù)量、機(jī)器學(xué)習(xí)功能、安全模型和MPC技術(shù)等方面對現(xiàn)有基于S-OC架構(gòu)的PPML方案進(jìn)行總結(jié)，如表6所示：

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

1) S-OC架構(gòu)的MPC技術(shù).基于S-OC架構(gòu)的方案主要使用秘密分享技術(shù)，通常需要2～4個計(jì)算方協(xié)同計(jì)算.ABY3等方案通過設(shè)置冗余的加性秘密份額實(shí)現(xiàn)了門限的效果，可以容忍一個參與方的單點(diǎn)失效，增強(qiáng)了系統(tǒng)的容錯能力，其中ABY3實(shí)現(xiàn)了中止安全性，ASTRA等實(shí)現(xiàn)了安全性更強(qiáng)的公平性.

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

3) S-OC架構(gòu)支持的機(jī)器學(xué)習(xí)功能.表6中所有方案都能支持神經(jīng)網(wǎng)絡(luò)推理，除ASTRA和CrypTFlow以外其他方案都能支持神經(jīng)網(wǎng)絡(luò)訓(xùn)練.

4) S-OC架構(gòu)與S-CS架構(gòu)的對比.S-CS架構(gòu)中應(yīng)用了多種MPC技術(shù)，包括AHE,OT,GC,SS等.而在S-OC架構(gòu)中主要使用單一的SS技術(shù)，因?yàn)闄C(jī)器學(xué)習(xí)在訓(xùn)練模型時需要迭代計(jì)算多次，SS是計(jì)算開銷最小的MPC技術(shù)，能夠有效降低模型訓(xùn)練時間.現(xiàn)有的HE和OT方案無法有效支持S-OC架構(gòu)下的安全多方計(jì)算.

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

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

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

ASTRA對ABY3線性計(jì)算的改進(jìn)是將一部分在線階段的運(yùn)算前移到預(yù)處理階段，對非線性運(yùn)算的改進(jìn)是使用秘密分享代替并行前綴加法器，獲得了恒定輪數(shù)的效果.ASTRA只實(shí)現(xiàn)了線性回歸、邏輯回歸等模型的安全推理，而未實(shí)現(xiàn)模型訓(xùn)練.BLAZE與ASTRA相比的改進(jìn)是提供對神經(jīng)網(wǎng)絡(luò)模型的支持，并且增加模型訓(xùn)練的功能.TRIDENT在ABY3的基礎(chǔ)上,將線性層的截?cái)嘤?jì)算和乘法計(jì)算合并來避免額外的通信開銷，并且優(yōu)化了ASTRA的最高有效位計(jì)算方法.

SecureNN僅使用秘密分享技術(shù)構(gòu)造了神經(jīng)網(wǎng)絡(luò)中的線性層和非線性層，四方設(shè)置比三方設(shè)置獲得更好的性能，其對MNIIST數(shù)據(jù)集進(jìn)行模型訓(xùn)練和推理，獲得93.4%～99.15%的準(zhǔn)確率，比明文模型訓(xùn)練開銷增加17～33倍.

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

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

4.3 基于S-FL架構(gòu)的PPML

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

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

目前已有一些基于MPC實(shí)現(xiàn)的聯(lián)邦學(xué)習(xí)框架投入使用.FATE項(xiàng)目最初使用加法同態(tài)加密技術(shù)來構(gòu)建聯(lián)邦學(xué)習(xí)底層安全計(jì)算協(xié)議，在之后的版本上增加了SPDZ秘密分享協(xié)議，提供更多樣化的MPC協(xié)議支持.此外，2019年發(fā)布的PySyft是用于隱私保護(hù)深度學(xué)習(xí)的開源庫，將SPDZ等MPC技術(shù)和差分隱私集成到聯(lián)邦學(xué)習(xí)框架并向用戶提供應(yīng)用程序接口.

5 總結(jié)與展望

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

PPML是當(dāng)前最受關(guān)注的MPC應(yīng)用領(lǐng)域，近年來在可用性和準(zhǔn)確性等方面取得了很大的進(jìn)步，但是仍然有許多問題需要解決，未來工作可圍繞以下3個方面展開.

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

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

3) 降低模型隱私泄露風(fēng)險.現(xiàn)有的部分S-CS架構(gòu)下的方案會向客戶端泄露過濾器的大小、卷積的步長以及神經(jīng)網(wǎng)絡(luò)隱藏層的種類等模型信息.未來仍需進(jìn)一步探索對模型參數(shù)信息更有效的保護(hù)方案.