安全多方計算應用的隱私度量方法

熊 維 王海洋 唐祎飛 劉 偉

1(神州融安數字科技(北京)有限公司 北京 100086) 2(北京國際大數據交易有限公司 北京 100020) 3(大數據協同安全技術國家工程研究中心 北京 100071)

傳統的計算模型如單機狀態的圖靈機模型,其計算的輸入、輸出和運算程序都由一方獨自占有.多方計算是指由多個參與者提供數據或計算資源并進行聯合計算的情況,其相對于單方計算會引發諸如公平性、數據隱私、計算成本等問題.常見的概念例如安全多方計算、外包計算、分布式計算、多方提供數據的中心式計算等均屬于多方計算的范疇.其中,安全多方計算(secure multi-party computation, MPC)的基本思想是Yao等人[1]于20世紀80年代提出的,它是指在無可信第三方的情況下,多個參與者可以安全地計算一個約定函數的系統.安全地計算指在函數計算過程中每個參與者不能獲得其他參與者的輸入和輸出信息.

影響安全多方計算方案隱私信息泄露的因素眾多,設計一個既安全又高效的安全多方計算的實現方案很具有挑戰性,這促使人們尋求方案可用性和隱私性之間的平衡.目前,安全多方計算研究多集中在如何防止計算過程中隱私信息的泄露,也就是說如何防止1個參與者通過計算過程獲得其他參與者輸入或輸出的信息.然而,1個參與者通過其合法的函數輸入和輸出推導出其他參與者輸入信息或者輸出信息的可能性卻沒有進行充分研究.

本文關注的是理想多方計算情況下目標函數本身對參與者輸入提供的保護程度,只有能夠衡量各個參與者在這種情況下隱私泄露的程度,才能真正評估各個參與者在實際進行安全多方計算應用過程中的隱私泄露情況.因此,隱私度量的研究對安全多方計算的應用和部署具有理論意義和實踐價值.

基于Shannon[2]提出的信息熵理論,本文首先研究并提出理想多方計算模型下目標函數對各方數據隱私保護的度量方法,進而提出實際情況下的安全多方計算的隱私保護強度的概念,最后提出隱私保護成本的計算方法.本文主要貢獻如下:1)針對理想多方計算模型,從攻擊者的角度定義平均熵和特定熵的概念,提出計算信息收益的方法,從而描述在攻擊者的視角下其他參與者特定的輸入對攻擊者輸出分布的影響程度;2)通過計算目標函數的理想隱私損耗和實際安全多方計算應用中的實際隱私損耗,衡量安全多方計算具體方案的隱私保護強度;3)為達到實際安全多方計算方案實用性與隱私性之間的平衡,需要對計算過程中的成本進行量化,本文提出計算目標函數需要付出的額外通信和計算開銷來衡量隱私保護成本.

1 相關工作

目前,隱私度量的研究主要集中于特定的隱私計算領域如位置服務、社交網絡和數據挖掘等.王彩梅等人[3]提出基于信息熵度量匿名通信系統的隱私度量方法.其他方案主要是為特定協議[4-6]量身定做的簡單概率模型的隱私度量方法.另外一些方案[7-9]則是使用形式化的方法提供更高層次的抽象和更嚴格的匿名分析.

彭長根等人[10]于2016年提出基于Shannon信息論的幾種隱私保護信息熵模型.隱私保護基本信息熵模型是將發送方擁有的信息集稱為隱私信源,將接收方獲取的信息集稱為隱私信宿,隱私的泄露渠道假設為通信信道.該方案主要研究在隱私保護機制不泄露隱私信息的前提下攻擊者通過隱私通信信道獲取隱私信息的隱私度量方法.

上述研究主要針對匿名性和位置隱私保護等信息發布場景的隱私保護度量,這些應用場景只對隱私信源信息進行一次隱私保護處理,且隱私保護處理過程固定.然而,在安全多方計算或者隱私計算[11-12]的應用場景下,各參與者之間進行多次交互所聯合實現的任務可以是任意的目標函數.因此,上述模型未充分考慮信源與信宿之間具有多次交互或者計算函數為任意函數的復雜情況.

衡量安全多方計算目標函數對特定參與者的輸入信息的隱私保護能力的另一個角度是密碼分析.密碼分析技術是測試函數安全強度的最有力工具.可將目標函數的隱私度量看作一種密碼分析.對于MPC的計算函數z=f(x,y),x由參與者P0輸入,y由參與者P1輸入,計算結果z由參與者P0獲取.計算函數可轉換為布爾函數的正規型表示,輸入和輸出以比特形式表述,可將函數f(x,y)視為加密函數,輸入x視為明文消息,輸入y視為密鑰,輸出z視為密文.由多個明文和密文對以及加密函數f()分析密鑰信息的過程是典型的“選擇明文攻擊”.

目前,安全多方計算主要包括使用姚氏混淆電路[1]、秘密分享技術[13]、同態密碼技術[14]等進行安全計算一個目標函數的方案.這些方案的設計更關注目標函數計算過程的安全性,卻忽略了目標函數的輸入及輸出本身所帶來的隱私信息泄露.Lindell[15]指出確保目標函數不泄露輸入信息是隱私計算得以應用的隱含前提條件.

2 理想多方計算隱私度量方法

對函數f(x1,x2,…,xn)=(y1,y2,…,yn),具有n個參與者P1,P2,…,Pn進行聯合計算,P1持有輸入x1,P2持有輸入x2,…,Pn持有輸入xn,所有輸入的定義域是公開的,除此之外,每個參與者無法獲得與其他參與者的輸入相關的任何信息;所有參與者都無法獲得關于函數計算過程中的任何信息(如由一個可信的中心收集各個參與者的輸入,再執行運算,最后將相應的計算結果發送給相應的參與者,可信中心不會與任何參與者共謀);函數計算結束后,每個參與者獲得既定的計算結果,P1獲得輸出y1,P2獲得輸出y2,…,Pn獲得輸出yn,每個參與者無法獲得關于其他參與者輸出的任何信息.

上述情況是多方計算的理想情況,各方均不會從計算過程中獲取任何其他的信息,可信中心也不會向任何一方泄露更多信息,在這種情況下,1個參與者想要攻擊其他參與者只能通過其自身的輸入和輸出以及目標函數的性質完成.

對上述函數f(x1,x2,…,xn)=(y1,y2,…,yn),為適應計算設備的運算環境,假設函數的輸入和輸出均為離散的情況,設參與者輸入的定義域分別為s1,s2,…,sn,x1∈s1,x2∈s2,…,xn∈sn, |s1|,|s2|,…,|sn|分別表示定義域中可能的輸入值的個數;設參與者輸出的值域分別為v1,v2,…,vn,y1∈v1,y2∈v2,…,yn∈vn,|v1|,|v2|,…,|vn|分別表示輸出值域中可能的輸出值的個數.

為簡化模型的復雜程度,以下僅考慮兩方計算的情況.多方計算函數可以簡化成兩方計算函數,對于多方計算函數f(x1,x2,…,xn)=(y1,y2,…,yn),可假定在最惡劣的情況下,其中n-1方參與者共謀以窺探其中1個參與者的輸入和輸出情況,那么共謀的n-1方參與者會獲得彼此之間的輸入和輸出信息,此時模型則等價于上述兩方計算模型,共謀的n-1方作為一個參與者,被攻擊的一方作為另一個參與者.

對于只有兩方參與的目標函數f(x1,x2)=(y1,y2),定義計算信息收益的概念,揭示在參與者P2的視角下參與者P1的特定輸入x1對參與者P2的輸出y2分布的影響程度.

2.1 平均熵

設目標函數f(x1,x2)=(y1,y2)的2個參與者分別為P1和P2,在理想的多方計算條件下(計算過程不泄露任何信息),參與者P2(攻擊者)試圖只通過其輸入x2和輸出y2分析參與者P1的輸入x1或者輸出y1.

函數輸出的平均熵H(f(P2,y2))體現所有輸入對P2輸出的分布影響.

2.2 特定熵

2.3 信息收益

差值越大或者比值越大表明該特定輸入對參與者P2的輸出分布影響越大,參與者P2越容易從其自身的輸出推斷出參與者P1的值.

該定義可以理解為參與者P1有一個特定的數據x1=α與參與者P2共同計算函數f(x1,x2),參與者P2通過不斷試探的方法,也就是遍歷其輸入x2獲得額外的輸出信息,以此推斷參與者P1的輸入情況.當參與者P2發現其輸出熵嚴重偏離函數的平均情況(差值越大/比值越大)即可判定參與者P1的輸入值.

3 安全多方計算的隱私保護強度

3.1 理想隱私損耗

目標函數f(x1,x2)=(y1,y2)的2個參與者分別為P1和P2,在理想的多方計算條件下(計算過程不泄露任何信息),定義“隱私損耗”的概念,揭示參與者P2通過其輸入x2和輸出y2推斷出參與者P1輸入x1的可能性.

3.2 實際隱私損耗

在理想的多方計算場景下,各參與者僅知道各自的輸入和輸出,而不知道其他的任何信息,但在實際的安全多方計算實現方案中,如基于同態密碼的委托計算、基于秘密分享的安全多方計算等方案中,各方在沒有可信第三方的情況下使用基于密碼或者信息論的安全措施進行數據的交換,計算結束后各方可以獲得與理想情況下的相同的輸出,但除此之外各方都會獲得大量的中間交互信息.

實際的安全多方計算方案可以模型化為原目標函數經過一系列的等價變換最終獲取與理想情況下的目標函數相同結果的過程.所謂等價變換指2種不同的運算過程對相同的輸入都得到相同的輸出結果.設在理想計算環境下,目標函數f(x1,x2)=(y1,y2) 的2個參與者分別為P1和P2,輸入分別為x1和x2,相應的輸出分別為y1和y2.設目標函數f(x1,x2)=(y1,y2)安全等價變換為f′(x1,x2)=fm(…f3(f2(f1(x1,x2),…),…),…)=(y1,y2),對相同的輸入(x1,x2),安全多方計算函數f′(x1,x2)和理想情況下的目標函數f(x1,x2)輸出相同的結果(y1,y2).

安全多方計算函數f′(x1,x2)由m個中間函數f1(),f2(),…,fm()復合而成,每次中間函數運行結束后,各方均會獲得相應的輸出(y(1,1),y(1,2)),(y(2,1),y(2,2)),…,(y(m,1),y(m,2)),其中y(i,1)為第i個中間函數的參與者P1的輸出,y(i,2)為第i個中間函數的參與者P2的輸出;并且各方會根據前一個中間函數的輸出重新構造對下一步中間函數的輸入(x(1,1)=x1,x(1,2)=x2),(x(2,1),x(2,2)),…,(x(m,1),x(m,2)),其中x(i,1)為第i(1≤i≤m)個中間函數的參與者P1的輸入,x(i,2)為第i個中間函數的參與者P2的輸入.概括來講,中間輸入和輸出等價于實際安全多方計算過程中各方通過交互所獲得的數據并執行下一次運算的過程.參與者P1在整個安全運算過程輸入數據視圖變化為x1=x(1,1)→x(2,1)→…→x(m,1),輸出數據的視圖變化為y(1,1)→y(2,1)→…→y(m,1)=y1;參與者P2的輸入數據視圖變化為x2=x(1,2)→x(2,2)→…→x(m,2),輸出數據的視圖變化為y(1,2)→y(2,2)→…→y(m,2)=y2.

參與者P2固定輸入x2=β和輸出y2=γ時,第i個中間函數fi(…f3(f2(f1(x1,x2),…),…),…),1≤i≤m的隱私損耗為Li=L(x1,x2=β,y(i,2),fi(…f3(f2(f1(x1,x2),…),…),…)),定義其中最大的隱私損耗為安全計算方案f′(x1,x2)=fm(…f3(f2(f1(x1,x2),…),…),…)=(y1,y2)在參與者P2輸入x2=β和輸出y2=γ時參與者P1的輸入x1的實際隱私損耗為L(x1,x2=β,y2=γ,f′(x1,x2))=max{Li|1≤i≤m}.

實際隱私損耗的意義為尋找安全方案執行過程中對隱私泄露最大的步驟,由于整個隱私保護方案f′(x1,x2)與目標函數等價,因此實際隱私損耗至少等于目標函數的理想隱私損耗.

3.3 隱私保護強度

對一個目標函數f(x1,x2)=(y1,y2)和具體實現該目標函數的安全計算方案f′(x1,x2)=fm(…f3(f2(f1(x1,x2),…),…),…)=(y1,y2),定義該安全計算方案在參與者P2輸入x2=β和輸出y2=γ時的隱私保護強度為目標函數的理想隱私損耗與安全計算方案的實際隱私損耗之間的比值,即L(x1,x2=β,y2=γ,f(x1,x2))-L(x1,x2=β,y2=γ,f′(x1,x2))或者L(x1,x2=β,y2=γ,f(x1,x2))/L(x1,x2=β,y2=γ,f′(x1,x2)).

隱私保護強度體現安全多方計算方案對目標函數在計算過程中所造成的額外隱私泄露情況,相對于在理想運行環境下目標函數自身特性對輸入數據隱私的保護,一個安全的隱私計算方案其安全強度越高(越接近1)越接近理想的運行條件,其計算過程所造成的額外隱私泄露越少.

4 安全多方計算的隱私保護成本

隱私保護成本是實現目標函數的安全計算函數比理想運行情況下(存在可信中心的情況)計算目標函數需要付出的額外通信和計算開銷,表示為獲得隱私保護所需要付出的代價.

對于中心化的多方計算目標函數f(x1,x2,…,xn)=(y1,y2,…,yn),其通信開銷至多為2n次,即各方將輸入發往可信中心并各自接收可信中心發來的輸出.其計算開銷即為可信中心在本地執行函數f(x1,x2,…,xn)的所需時間函數T(f(x1,x2,…,xn)).

對實現目標函數f(x1,x2,…,xn)=(y1,y2,…,yn)的安全計算方案f′(x1,x2,…,xn)=fm(…f3(f2(f1(x1,x2,…,xn),…),…),…)=(y1,y2,…,yn),其通信開銷至多為2mn2次數據傳輸,也就是各方在每次執行中間函數的過程中都需要相互之間發送和接收數據.其計算時間開銷為T(f′(x1,x2,…,xn))=n·{T(f1(x1,x2,…,xn))+T(f2(…))+…+T(fm(…))},n方參與者均需要在本地執行相關計算.

隱私保護成本如下:額外的通信開銷為2mn2-2n次數據傳輸,額外的計算開銷為T(f′(x1,x2,…,xn))-T(f(x1,x2,…,xn)).

因為達到理想情況下的隱私保護強度會引發通信花費大、計算消耗多等問題,所以實際隱私損耗和計算成本都不是越小越好.在實際應用中,需要綜合考慮隱私保護成本和隱私度量情況評估安全多方計算方案的實現,達到方案實用性與隱私性之間的平衡.

5 結 語

隨著學術界、工業界對安全多方計算越來越重視,實際應用的落地需求越來越強烈.此時,度量目標函數本身、安全多方計算方案組合及工程優化過程中的隱私損耗的重要性日益突出.本文試圖針對隱私計算領域提供參與者衡量方案安全性的框架,以此為基礎對安全多方計算的實際應用可行性進行了量化評估.