基于秘密分享的高效隱私保護四方機器學習方案

閻允雪 馬 銘 蔣 瀚,2

1(山東大學軟件學院 濟南 250101) 2(山東省軟件工程重點實驗室(山東大學) 濟南 250101)

移動互聯網、云計算和大數據等技術的快速發展,催生了眾多新的服務模式和應用[1],這些服務和應用一方面為用戶提供精準化、個性化的服務,給人們的生活帶來了極大便利,另一方面又采集了大量用戶的相關信息,而所采集信息中往往含有大量隱私數據，包括個人身份信息(如電話號碼、身份證號等)、敏感信息(如金融財務、醫療健康等信息)，對這些信息的收集、共享、發布、分析與利用等操作會直接或間接地泄露用戶隱私[2],給用戶帶來極大的威脅和困擾.

隱私保護機器學習(privacy preserving machine learning, PPML)是一個蓬勃發展的研究領域,允許機器學習對用戶的私人數據進行計算,同時確保數據的隱私安全[3].安全多方計算(secure multi-party computation)協議允許多個參與者通過使用同態加密、秘密共享和不經意傳輸等密碼技術，以一種安全的方式完成數據的聚合與計算，因此成為應用在高效并行分布式機器學習中的關鍵.近年來，隨著數據的爆炸式增加,隱私保護機器學習中完成大量卷積、激活函數等非線性運算,這些計算的實現往往需要復雜的安全多方計算協議，并且需要根據具體的功能來選擇不同的安全多方計算技術.總之，基于安全多方計算的隱私保護機器學習方案目前處于初步發展時期，在安全模型、通信效率等還存在沒有解決的問題,距離真正應用還有一定的距離.

1 相關工作

PPML方法最早可追溯至2000年，Lindell等人[4]明確提出了允許兩方在不泄露自己隱私的前提下，通過協作對聯合數據集進行提取挖掘的方法.

傳統的安全多方計算協議為了實現惡意敵手模型下的安全性，需要使用茫然傳輸(oblivious transfer, OT)、認證秘密分享、零知識證明、承諾等工具,使得安全多方計算協議設計嚴重依賴這些基礎工具,效率較低.近年來,惡意敵手模型下基于Yao混亂電路的安全兩方計算協議,以及基于秘密分享的安全多方計算協議都提出了高效的實現方案[5].

現有的基于安全多方計算協議的隱私保護機器學習方案有SecureML,ABY,ABY3,Trident,Swift等.其中Mohassel等人[6]提出的SecureML安全機器學習框架,由2個不合謀的參與方利用秘密分享執行安全兩方計算協議.Demmler等人提出的ABY框架[7]利用Yao混亂電路來計算分段函數，該框架能夠完成3種不同分享方式之間的轉換，從而完成計算任務.ABY和SecureML兩個方案在設計乘法協議時都利用Beaver三元組技術，因此方案的通信成本和協議的效率都并不理想.方案ABY3[8]在半誠實環境和惡意環境下，能夠完成三方之間的算術共享、布爾共享和Yao共享，并且對SecureML[6]中的近似定點數乘法進行改進，使協議在三方參與環境下可以使用.但是ABY3方案均是專注于半誠實環境下的機器學習框架,在惡意環境下進行位提取,截斷的效率都會不同程度地降低[9-10].

Trident方案[11]提出了最多可以容忍一方腐敗的四方參與的隱私保護機器學習協議,在方案中對參與方要求比較高,通過引入一個額外的誠實參與方來提高協議在線階段的效率,并且協議在安全性方面僅僅滿足中止性,方案利用哈希值進行一致性檢測,當出現不一致時,協議就會中止.當惡意參與方提供錯誤的值時,將導致計算中止,并且協議不會有任何的輸出.雖然方案中都提出使用Abort的安全構建組件,但當出現爭議時，不能保證協議一定有輸出.只實現中止安全性的安全多方計算協議不能滿足安全外包計算的要求，因為用戶可能無法獲得輸出，導致用戶的參與度降低.

2021年,Koti等人提出的Swift方案[12]中通過引入聯合消息傳遞(joint message passing, JMP)原語,允許2個服務器將共有的消息發送給第3個服務器,當發現哈希值不一致時,沒有中止協議,而是能夠識別出誠實的服務器,將誠實方作為可信第三方(trust third party,TTP)服務器來完成計算.同時文中還將協議擴展到了第4個參與方,設計環境依舊是基于誠實大多數,在調用三方篩選協議進行哈希值一致性檢測出現爭議時，由于最多只有一個惡意方，因此惡意方只可能出現在3個服務器中，Swift方案將未參與篩選協議的第4個服務器作為TTP，參與方就會將消息發送給TTP,雖然方案能夠保證在有惡意參與方的情況下保證用戶一定可以獲得輸出結果，但對于作為TTP的參與方來說,就會掌握所有用戶的敏感數據信息,不符合安全多方計算協議的初衷.

本文提出了一個基于秘密分享的高效隱私保護四方機器學習方案,在至多存在一個惡意敵手模型中，當協議出現爭議時，能夠準確從4個參與方中確定出2個誠實參與方，執行安全兩方計算協議.本文設計的隱私保護機器學習方案主要貢獻包括2個方面：

2)通過對方案的效率分析和對比,本文的四方協議與僅提供半誠實/被動安全性的高效誠實多數三方協議的性能相似，這表明添加第四方是實現主動安全而不損害性能的有效方法.其中乘法協議只需要3個參與方在在線階段處于活躍狀態，提高了在線階段25%的通信.

2 預備知識

2.1 秘密分享

秘密分享是一個非常重要的基礎原語[13-15],是許多安全多方計算協議的重要構造模塊.如表1所示，4個參與方P={P0,P1,P2,P3}分享秘密v時的3種方式,這些分享都是在算數和布爾環上的.為了方便非交互通信,參與方利用Trident方案中的功能函數Fsetup為每個參與方建立預共享的隨機密鑰.參與方在分享秘密值v時，可以調用共享的密鑰設置函數Fsetup獲得滿足條件的相應參數.

[·]-sharing:v∈2由3個參與方P1,P2,P3共同分享.參與方P1擁有[v]1,參與方P2擁有[v]2,參與方P3擁有[v]3并且v=[v]1+[v]2+[v]3.

〈·〉-sharing:v∈2由3個參與方P1,P2,P3共同分享.如果參與方P1,P2,P3依次擁有的值為(v2,v3),(v1,v3),(v1,v2),并且v=v1+v2+v3.

〖·〗-sharing:v∈2由4個參與方P0,P1,P2,P3分享,如果存在λv,mv∈2并且滿足λv=λv,1+λv,2+λv,3,mv=v+λv,參與方P1,P2,P3都清楚地知道mv.

Table1 Secret Sharing Semantics

2.2 JMP原語

Swift方案中能夠實現輸出可達性的關鍵在于引入了JMP原語.JMP3PC協議在2021年由Koti等人提出.JMP原語允許2個服務器將公共消息中繼到第3個服務器，以便中繼成功或識別誠實服務器(或沖突對).如圖1所示為3方參與的JMP原語的理想功能圖.

如圖2所示,JMP3PC協議內容簡要來說,有3個服務器參與協議, 其中最多只有一個惡意服務器,通過JMP3PC協議可以確保輸入一致性,并且當發生爭議時,確保協議一定有輸出結果.其中Pi,Pj作為發送方,Pk作為接收方.Pi發送值v給Pk,Pj發送值H(v)給Pk,接收方Pk將接收到的值與哈希值進行比較,如果哈希值不一致,通過JMP3PC協議可以確認出一個參與方作為TTP繼續計算,并且不需要再次通信.

對于s∈{i,j,k},參與方Ps將bs=0作為檢測哈希值不一致的標志比特.協議分為發送階段和驗證階段.當檢測到哈希值不一致時,協議將不同的情況進行分類并選擇出TTP.如果Pi是沉默的,Pk沒有接收到發送的v,Pk廣播(accuse,Pi),那么Pk和Pi中必定有一個是惡意的參與方，這時選擇TTP=Pj.類似地，Pk廣播(accuse,Pj), 那么Pk和Pj中必定有一個是惡意的參與方，這時選擇TTP=Pi.如果當Pk收到不一致的消息對(v,H(v*))時,設定bk=1, 并將bk發送給Pi,Pj,由這兩方通過交換不一致標志比特相互進行交叉檢驗,若從Pk收到的或者從其他發送方接收到的比特為1,則這兩方將自己的不一致標志比特設定為1.當服務器的不一致標志比特為1時,服務器會廣播相應值的Hash結果.Pk的值來自它從Pi接收到的值.接下來按照具體協議來選出合適的服務器做TTP.

Swift方案將JMP協議擴展為4個參與方Pi,Pj,Pk,Pl，方案的模型依舊是至多只有一個惡意的參與方.但是當調用三方參與的JMP3PC協議時,一定可以確定3個參與方中存在一個參與方是惡意的,因此將未參與的JMP3PC協議的第4個參與方直接作為TTP,其他參與方將自己的消息發送給它,由作為TTP的參與方完成剩下的所有計算.接下來為了描述方案更加清晰，三方參與的JMP協議表示為JMP3PC, 四方參與的JMP協議表示為JMP4PC.

2.3 現實-理想范式

令π為一個協議,F為一個功能函數,令C為攻陷參與方集合,令Sim為一個仿真者算法.定義以下2個隨機變量的概率分布：1)Realπ(κ,C;x1,…,xn).在安全參數κ下執行協議,其中每個參與方Pi都將使用自己的私有輸入xi誠實地執行協議.令Vi為參與方Pi的最終視角,令yi為參與方Pi的最終輸出.因此可以將輸出表示為{Vi|i∈C},(y1,…,yn).2)IdealF,Sim(κ,C;x1,…,xn):計算(y1,…,yn)←F(x1,…,xn).輸出Sim(C,{(xi,yi)|i∈C}),(y1,…,yn).

如果現實世界中攻陷參與方所擁有的視角和理想世界中攻擊者所擁有的視角不可區分,那么協議在半誠實攻擊者的攻擊下是安全的[16-18].

給定協議π,如果對于任意一個現實世界中的攻擊者A,存在一個滿足corrupt(A)=corrupt(sim)的仿真者sim,使得對于誠實參與方的所有輸入{xi|i?corrupt(A)}概率分布Realπ,A(κ;{xi|i?corrupt(A)})和IdealF,Sim(κ;{xi|i?corrupt(Sim)})是在κ下不可區分的,則稱此協議在惡意攻擊者存在的條件下安全地實現了F.

3 新的基于秘密分享的四方安全多方計算協議

3.1 四方安全多方計算基礎協議

3.1.1 秘密分享協議

參與方通過調用秘密分享協議∏Sh(Pi,v)產生關于〖v〗的秘密分享,如圖3所示.秘密分享協議分為在線階段和離線階段.

當執行秘密分享協議∏Sh(P0,v)時,在離線階段：參與方P0持有值v,使用預先共享的密鑰來生成參數λv,j,并且λv=λv,1+λv,2+λv,3,參與方P0持有份額為(λv,1,λv,2,λv,3),參與方P1持有份額為(λv,2,λv,3),參與方P2持有份額為(λv,1,λv,3),參與方P3持有份額為(λv,1,λv,2).在在線階段:參與方P0計算mv,并發送給P1,P0,參與方P1通過調用JMP3PC協議發送給P2,P0,參與方P1通過調用JMP3PC協議發送給P3.因此各參與方擁有的份額為參與方P0持有份額為(λv,1,λv,2,λv,3,mv),參與方P1持有的份額為(λv,2,λv,3,mv),參與方P2持有的份額為(λv,1,λv,3,mv)，參與方P3持有的份額為(λv,1,λv,2,mv).

當執行秘密分享協議∏Sh(P1,v)時,在離線階段：參與方P1擁有值v,使用預先共享的密鑰來生成參數λ,參與方P0持有份額為(λv,1,λv,2,λv,3),參與方P1持有份額為(λv,1,λv,2,λv,3),參與方P2持有份額為(λv,1,λv,3),參與方P3持有份額為(λv,1,λv,2).在在線階段:參與方P1計算mv,并且發送給P2,P1,參與方P2通過調用JMP3PC協議發送給P3.因此各參與方擁有的份額為參與方P0持有份額為(λv,1,λv,2,λv,3),參與方P1持有份額為(λv,1,λv,2,λv,3,mv),參與方P2持有份額為(λv,1,λv,3,mv)，參與方P3持有份額為(λv,1,λv,2,mv).參與方P2,P3執行協議∏Sh(Pi,v)的過程和參與方P1類似,這里不再詳細展開了.

如圖4所示，執行協議∏ash(P0,v),參與方P0可以在離線階段計算值v的〈·〉-sharing.參與方P0擁有值v,參與方利用提前約定好的函數共同生成相關的參數.參與方P1擁有份額為(v2,v3)，參與方P2擁有份額為(v1,v3), 參與方P3擁有份額為(v1,v2).注意在文中第4節乘法截斷協議中完成r不同秘密分享方式的本地轉換中可以用到.

3.1.2 重構協議

如圖5所示,在重構協議∏Rec中,每個參與方可以從其他2個參與方中依次接收到自己缺失的份額和對應缺失份額的哈希值,參與方通過調用JMP3PC協議進行一致性輸入檢測,如果一致的話,那么該參與方可以根據自己持有的份額和收到的自己缺失的份額計算值v.如果收到的值不一致的話,則由JMP3PC協議選出的TTP和未參與JMP3PC協議的參與方進行安全兩方計算來重構值v.例如,P0,P2調用JMP3PC協議發送λv,1給P1.如果JMP3PC協議的執行結果是TTP=P0,則由P0和P3來計算值v.

3.1.3 乘法協議

首先簡單描述一下加法協議,對于輸入x,y,參與方可以利用秘密分享方案的線性屬性本地完成方案中的份額計算，即對于z=x+y來說，可以本地計算份額[z]=[x]+[y].接下來描述乘法協議,在協議執行過程中需要參與方進行交互，具體內容如圖6所示：

乘法協議執行分為2個階段：離線階段和在線階段.在離線階段,需要參與方本地計算γxy的分享.其中γxy=λxλy.通過調用JMP3PC協議來驗證其他參與方發送過來的份額的正確性.在計算過程中,通過調用∏zero協議[11]產生隨機數目的是隨機分配份額,以防止隱私泄露,注意這里的A+B+Γ=0.在在線階段,協議的目的主要是計算mz,其中mz=z+λz=xy+λz=(mx-λx)(my-λy)+λz=mxmy-λxmy-λyλx+λxλy+λz.

3.2 四方協議框架

本文方案的參與方是由4個服務器P={P0,P1,P2,P3}組成,通過同步網絡中私有和真實通道連接,最多容忍一個靜態惡意敵手.

本文設計的四方協議如圖7所示，當利用哈希值進行一致性檢測存在爭議時，通過調用JMP3PC三方協議一定可以找出一個TTP=Pi,由Pi和未參與JMP3PC協議的服務器進行下一步的計算.4個參與方P0,P1,P2,P3利用復制秘密共享,對秘密v進行分享,執行秘密分享協議∏Sh(P0,v)后,每個參與方持有的份額是：參與方P0持有份額為(λv,1,λv,2,λv,3),參與方P1持有份額為(λv,2,λv,3,mv),參與方P2持有份額為(λv,1,λv,3,mv),參與方P3持有份額為(λv,1,λv,2,mv).當執行重構協議，為了確保獲得一致性輸入，參與方會調用JMP3PC來發送份額，并進行一致性檢測，當檢測出不一致的情況時，假設調用JMP3PC協議的是P0,P1,P2三個參與方,并且輸出結果為TTP=P2時，那么由P2和P3來執行安全兩方計算協議，并將秘密值v重構出來.其他協議也是同樣的過程,這里不再一一展開描述.

4 機器學習隱私保護組成模塊

為了執行隱私保護機器學習,我們需要有效地實例化3個組件,其中主要包括共享截斷、安全比較、非線性激活函數.

4.1 共享截斷

協議在ABY3,Trident協議的基礎上進行了改進.ABY3方案是在評估乘法門之后對份額進行截斷,以較高的概率保留基礎值；Trident方案通過不使用任何的布爾電路,從而將離線階段的復雜性降到了常數.本文在2個協議的基礎上,在滿足誠實大多數的條件下,結合JMP3PC協議,保證在線階段參與方可以接受到相應的份額,最后一定可以得到正確的輸出結果.

協議的具體內容如圖8所示.首先協議執行離線階段，在執行協議∏mult(x,y,z)的離線階段后,參與方本地計算r并進行截斷后獲得rt.參與方執行協議∏ash(P0,rt),獲得〈rt〉，并通過驗證H(m1+m2)≠H(c)等式是否成立來判斷份額是否正確.協議執行在線階段,與乘法協議在線階段類似,z的截斷值可以由〖z〗t〗=〖(z〗-r)t〗+rt獲得.

4.2 安全比較

參與方檢測x

4.3 激活函數

在隱私保護機器學習中最常用的2個激活函數為rectified linear Unit(ReLU)和Sigmoid(sig).

1)ReLU

2)Sigmoid

5 安全分析

5.1 正確性

(rd,1+rd,2+rd,3)+c=(r)-(2drt+rd)+

c=0+c=c.

5.2 協議安全證明

本文提供的安全性是基于理想世界或現實世界模擬來展開的描述[19-20].現實世界中參與方至多有一個是惡意服務器,我們用A來表示現實世界的敵手,用S來表示理想世界的敵手.證明來自于敵手的模擬視圖和現實視圖是不可區分的.

協議的證明過程簡要來說,從輸入共享階段開始,S將誠實方的輸入設置為0.模擬器可以從共享協議中提取A的輸入.S可以獲得整個協議的所有輸入,因此S可以計算電路的所有中間值和輸出.參與方P0,P1,P2,P3中至多有一個惡意參與方.除了圖11所示協議的安全性證明,其他基本協議的證明也很容易推導出來,這里就不全部展開描述了.

5.3 隱私保護魯棒性

本文提出隱私保護魯棒性的4PC隱私保護機器學習方案,是針對JMP四方協議的擴展,可以更好地保護誠實方的隱私.在協議的執行過程中,正在參與JMP協議的3個服務器,當接收方接收到的哈希值不一致時,可以確認出惡意方在哪一對服務器中,同時確認出一定是誠實方的參與方作為TTP，由TTP和未參與JMP協議的第4個服務器進行下一步的計算.因此,該協議可以在惡意參與方破壞的情況下仍然保持正確的輸出,同時誠實方不能恢復私有輸入.在協議執行的過程中,我們可以準確地判斷協議的問題出現在哪一步,能夠更好地對服務器的性能進行綜合評估，并且當協議中確認TTP后會及時廣播.

在通過JMP3PC協議確認TTP后，TTP與未參與協議的參與方執行安全兩方計算協議.方案能夠更好地保護用戶隱私,不會將全部的信息以明文的形式由一個參與方保存,同時鎖定了可能的惡意方,并且惡意方在整個過程中不會得到額外的消息.協議的調用過程中不會泄露正在計算的私有信息,但仍然允許計算完成.誠實方不存儲非協議的消息,在惡意方存在的情況下,能夠保持計算的正確性.隱私保護魯棒性協議的安全性和實用性具有非常重要的意義.

6 方案效率分析

6.1 通信開銷

如何降低協議的通信量和輪數復雜度一直都是設計一個更加高效的隱私保護機器學習方案的關鍵.接下來主要包括本文涉及到的基本協議具體效率分析,如表2所示,將本文方案的離線階段和在線階段的交互輪數以及通信量與ABY3方案進行了詳細的對比.通過對比可以發現，本文提出的改進之后的四方隱私保護方案降低了通信量.

Table 2 Communication Overhead of Protocol

從2個方面將本文提出的方案進行分析,包括線性計算協議和非線性計算協議.1)關于秘密分享的加法協議和常數的乘法是可以本地完成份額的計算,因此其線性屬性可以以非交互方式來執行協議.2)秘密分享協議∏Sh在離線階段通過使用Fsetup生成共享密鑰.在在線階段,當Pi=P0時,協議∏ash計算并發送值mv給其他參與方,并且調用JMP協議,確認收到了正確的mv，因此需要2輪交互和通信量是2.協議∏ash可以完整地在離線階段執行.P0計算v3發送給P1.P0,P1調用JMP協議發送給P2.因此需要一輪交互和通信量是2位.對于發送給其他參與方也是類似的情況.3)重構協議∏Rec在在線階段每一個參與方接收自己的缺失的份額并進行驗證,因此需要的一輪交互和通信量為4位.4)乘法協議的執行分為2個階段,在離線階段,P1,P2,P3需要與其他參與方交互獲得γxy的份額,同理，離線階段,P1,P2,P3需要獲得的份額，因此需要的一輪交互和通信量是3位.

機器學習的組成模塊中進行非線性計算時，常用到截斷協議、安全比較協議、激活函數等.本文涉及到的基本協議包括：1)協議∏MultTr在離線階段,需要調用∏ash協議來產生關于γt的分享,通過判斷哈希值是否相等來驗證分享是否正確，因此需要2輪交互和6位的通信量.2)協議∏ReLU在離線階段需要3輪交互和8+2位的通信量，在在線階段需要4輪交互和8+2位的通信量.3)協議∏Sigmoid在離線階段需要3輪交互和15+7位的通信量，在在線階段需要5輪交互和16+7位的通信量.

6.2 方案對比

結合安全多方計算工具來實現隱私保護機器學習,不同的安全多方計算協議可以適用于不同的場景,因此出現了許多使用不同安全多方計算原語組合構建機器學習隱私的保護方案.如表3所示:

Table 3 Comparison of Privacy Preserving Machine Learning Schemes Based on Multi-party Computation

為了更好地理解本文提出方案的實現功能和應用范圍，本文提供了多方參與的隱私保護機器學習相關方案在參與方個數、模型及方案的主要特征進行了對比.通過方案對比可以得出：1)ABY和SecureML只滿足半誠實環境下的安全多方計算協議；2)Trident方案需要額外引入一個誠實的參與方；3)Swift方案雖然通過篩選協議選出了一個TTP，但是不論是三方還是四方的安全多方計算協議都是其他參與方把所有信息發給TTP繼續計算，不符合安全多方計算協議設計的初衷；4)本文提出的四方隱私保護機器學習方案能夠在協議發生爭議時,篩選出2個誠實參與方繼續執行協議，保證用戶可以得到輸出結果,不用擔心因為惡意敵手的行為而拒絕服務.確定出的2個誠實參與方能夠高效地完成安全兩方計算協議.

7 總結與展望

近年來,隱私保護機器學習方案在實用性和模型準確性等方面取得了很大的進步,但是仍然有許多問題需要解決.基于安全多方計算的隱私保護機器學習中的模型設計和通信開銷一直是研究的重點.本文提出了一個完整的四方參與的隱私保護機器學習方案,遵循誠實大多數的原則,不需要單獨引入額外的誠實方,同時能夠保證在有惡意參與方的情況下,協議依然能夠正確計算保證輸出.

下一步的工作主要由3個方面展開：1)關于方案參與方的數量問題,如何將協議的參與方個數擴展到N,并且協議實現的環境不再只是針對至多一個惡意參與方.2)如何在提升安全屬性的前提下,將性能開銷進一步優化.3)針對不同的應用需求和不同的應用架構,如何更好地保護模型參數信息、降低隱私泄露的風險,都是未來我們需要關注和解決的問題.

作者貢獻聲明：閻允雪提出了方案的具體思路和實驗方案并撰寫論文;馬銘負責完成實驗的對比分析并撰寫論文;蔣瀚提出指導意見并修改論文.