熊 維 王海洋 唐祎飛 劉 偉

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

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

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

本文關(guān)注的是理想多方計(jì)算情況下目標(biāo)函數(shù)本身對(duì)參與者輸入提供的保護(hù)程度,只有能夠衡量各個(gè)參與者在這種情況下隱私泄露的程度,才能真正評(píng)估各個(gè)參與者在實(shí)際進(jìn)行安全多方計(jì)算應(yīng)用過程中的隱私泄露情況.因此,隱私度量的研究對(duì)安全多方計(jì)算的應(yīng)用和部署具有理論意義和實(shí)踐價(jià)值.

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

1 相關(guān)工作

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

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

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

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

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

2 理想多方計(jì)算隱私度量方法

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

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

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

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

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

2.1 平均熵

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

函數(shù)輸出的平均熵H(f(P2,y2))體現(xiàn)所有輸入對(duì)P2輸出的分布影響.

2.2 特定熵

2.3 信息收益

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

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

3 安全多方計(jì)算的隱私保護(hù)強(qiáng)度

3.1 理想隱私損耗

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

3.2 實(shí)際隱私損耗

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

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

安全多方計(jì)算函數(shù)f′(x1,x2)由m個(gè)中間函數(shù)f1(),f2(),…,fm()復(fù)合而成,每次中間函數(shù)運(yùn)行結(jié)束后,各方均會(huì)獲得相應(yīng)的輸出(y(1,1),y(1,2)),(y(2,1),y(2,2)),…,(y(m,1),y(m,2)),其中y(i,1)為第i個(gè)中間函數(shù)的參與者P1的輸出,y(i,2)為第i個(gè)中間函數(shù)的參與者P2的輸出;并且各方會(huì)根據(jù)前一個(gè)中間函數(shù)的輸出重新構(gòu)造對(duì)下一步中間函數(shù)的輸入(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)個(gè)中間函數(shù)的參與者P1的輸入,x(i,2)為第i個(gè)中間函數(shù)的參與者P2的輸入.概括來講,中間輸入和輸出等價(jià)于實(shí)際安全多方計(jì)算過程中各方通過交互所獲得的數(shù)據(jù)并執(zhí)行下一次運(yùn)算的過程.參與者P1在整個(gè)安全運(yùn)算過程輸入數(shù)據(jù)視圖變化為x1=x(1,1)→x(2,1)→…→x(m,1),輸出數(shù)據(jù)的視圖變化為y(1,1)→y(2,1)→…→y(m,1)=y1;參與者P2的輸入數(shù)據(jù)視圖變化為x2=x(1,2)→x(2,2)→…→x(m,2),輸出數(shù)據(jù)的視圖變化為y(1,2)→y(2,2)→…→y(m,2)=y2.

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

實(shí)際隱私損耗的意義為尋找安全方案執(zhí)行過程中對(duì)隱私泄露最大的步驟,由于整個(gè)隱私保護(hù)方案f′(x1,x2)與目標(biāo)函數(shù)等價(jià),因此實(shí)際隱私損耗至少等于目標(biāo)函數(shù)的理想隱私損耗.

3.3 隱私保護(hù)強(qiáng)度

對(duì)一個(gè)目標(biāo)函數(shù)f(x1,x2)=(y1,y2)和具體實(shí)現(xiàn)該目標(biāo)函數(shù)的安全計(jì)算方案f′(x1,x2)=fm(…f3(f2(f1(x1,x2),…),…),…)=(y1,y2),定義該安全計(jì)算方案在參與者P2輸入x2=β和輸出y2=γ時(shí)的隱私保護(hù)強(qiáng)度為目標(biāo)函數(shù)的理想隱私損耗與安全計(jì)算方案的實(shí)際隱私損耗之間的比值,即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)).

隱私保護(hù)強(qiáng)度體現(xiàn)安全多方計(jì)算方案對(duì)目標(biāo)函數(shù)在計(jì)算過程中所造成的額外隱私泄露情況,相對(duì)于在理想運(yùn)行環(huán)境下目標(biāo)函數(shù)自身特性對(duì)輸入數(shù)據(jù)隱私的保護(hù),一個(gè)安全的隱私計(jì)算方案其安全強(qiáng)度越高(越接近1)越接近理想的運(yùn)行條件,其計(jì)算過程所造成的額外隱私泄露越少.

4 安全多方計(jì)算的隱私保護(hù)成本

隱私保護(hù)成本是實(shí)現(xiàn)目標(biāo)函數(shù)的安全計(jì)算函數(shù)比理想運(yùn)行情況下(存在可信中心的情況)計(jì)算目標(biāo)函數(shù)需要付出的額外通信和計(jì)算開銷,表示為獲得隱私保護(hù)所需要付出的代價(jià).

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

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

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

因?yàn)檫_(dá)到理想情況下的隱私保護(hù)強(qiáng)度會(huì)引發(fā)通信花費(fèi)大、計(jì)算消耗多等問題,所以實(shí)際隱私損耗和計(jì)算成本都不是越小越好.在實(shí)際應(yīng)用中,需要綜合考慮隱私保護(hù)成本和隱私度量情況評(píng)估安全多方計(jì)算方案的實(shí)現(xiàn),達(dá)到方案實(shí)用性與隱私性之間的平衡.

5 結(jié) 語

隨著學(xué)術(shù)界、工業(yè)界對(duì)安全多方計(jì)算越來越重視,實(shí)際應(yīng)用的落地需求越來越強(qiáng)烈.此時(shí),度量目標(biāo)函數(shù)本身、安全多方計(jì)算方案組合及工程優(yōu)化過程中的隱私損耗的重要性日益突出.本文試圖針對(duì)隱私計(jì)算領(lǐng)域提供參與者衡量方案安全性的框架,以此為基礎(chǔ)對(duì)安全多方計(jì)算的實(shí)際應(yīng)用可行性進(jìn)行了量化評(píng)估.