張恩,朱君哲,范海菊,李功麗

1.河南師范大學(xué) 計算機(jī)與信息工程學(xué)院,新鄉(xiāng) 453007

2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實驗室,新鄉(xiāng) 453007

1 引言

安全求和協(xié)議作為安全多方計算的一種實例,在分布式環(huán)境下的隱私保護(hù)、電子選舉、社會網(wǎng)絡(luò)分析中有著廣泛應(yīng)用.安全求和協(xié)議是指有n個參與者,其中Pi輸入為si,i=1,···,n,經(jīng)過運(yùn)算,最后每個參與者得到s=si.當(dāng)協(xié)議結(jié)束時,如果參與者僅知道自己的輸入和輸出,那么稱協(xié)議是安全的.目前已經(jīng)有一系列文獻(xiàn)[1-9]對安全求和協(xié)議進(jìn)行了研究.文獻(xiàn)[1–3]均采用的方法是,假設(shè)s=∑的范圍在[0,···,l]中,P1從[0,···,l]中隨機(jī)選擇一個數(shù)R,將(R+s1)modn發(fā)送給P2,因為R是隨機(jī)選擇的,所以(R+s1)modn是均勻分布的.P2不會了解s1的值,然后P2加上自己的值發(fā)給P3,依此類推,即Pi收到S=R+sj,i=2,···,n,Pn將最后的結(jié)果發(fā)給P1,P1減去R得到最終的求和值,然后告訴其他人,在這個過程中,沒有參與者能夠了解自己輸入和輸出之外的信息.但是該方案不能抵抗合謀,因為Pi-1和Pi+1能夠通過比較他們發(fā)送和接收的值算出Pi的輸入si.Shepard等[4]提出一種分割圈安全求和算法(CPSS),在他們的算法中,有C個不同的漢密爾頓圈,P1首先將s1和R相加,然后分成C個不同的隨機(jī)數(shù)沿著不同的漢密爾頓圈發(fā)送.最終P1收到不同漢密爾頓圈發(fā)來的值后,將隨機(jī)數(shù)消去得到結(jié)果.Mehnaz等[5]提出了一種基于誠實模型的安全求和協(xié)議,并且應(yīng)用到了機(jī)器學(xué)習(xí)中.Liu等[6]提出了一種基于雙粒子Bell態(tài)的量子安全多方求和協(xié)議.Jung等[7]提出了一種沒有安全通信信道或沒有可信密鑰分發(fā)者的安全求和協(xié)議,該協(xié)議可抵抗K個敵手的攻擊后將字符串模式匹配問題轉(zhuǎn)化成集合成員判定問題,Ashouri-Talouki等[8]提出了無需安全信道的3個安全求和協(xié)議.

但是,以上所有的方案都有一個共同的缺陷,當(dāng)參與方第一個了解求和的值之后,其沒有動機(jī)將結(jié)果發(fā)給其他人,即協(xié)議的公平性無法保證.雖然有一系列協(xié)議[9-13]對安全計算中的公平性進(jìn)行了研究,但都限于兩方參與者.田有亮等[14]提出一種通用可組合安全的公平多方計算協(xié)議.文獻(xiàn)[15–17]分別對理性安全多方計算進(jìn)行了研究.Zhang等[15]提出基于聲譽(yù)系統(tǒng)的服務(wù)器輔助的隱私集合交集協(xié)議,該協(xié)議允許參與各方使用不同的對稱密鑰,最終所有的用戶都可公平的得到計算結(jié)果，但該協(xié)議只適用于隱私集合比較.Kargupta等[16]基于博弈論提出一種理性安全求和協(xié)議,誠實者通過將計算量加大等措施,對發(fā)出合謀邀請的參與者懲罰,使其在協(xié)議執(zhí)行時沒有合謀的動機(jī),但在他們的協(xié)議中,參與者可以在協(xié)議執(zhí)行之后合謀攻擊,從而獲得誠實者的隱私輸入.王伊蕾等[17]介紹了理性安全多方計算的發(fā)展?fàn)顩r及典型成果,并提出一些需要進(jìn)一步研究的問題.

針對以上問題,本文結(jié)合密碼學(xué)與博弈論,構(gòu)建了一種基于電路計算的理性安全多方求和協(xié)議.電路計算是設(shè)計安全多方計算協(xié)議的關(guān)鍵,在密碼學(xué)中起到了舉足輕重的作用.本文主要工作如下:(1)結(jié)合密碼算法和博弈論對參與者的策略和效用進(jìn)行了分析和設(shè)計,構(gòu)建了電路計算的概率效用模型;(2)參與者遵守協(xié)議的收益比背離協(xié)議的收益大,所以參與者有動機(jī)遵守電路計算的每一步;(3)不需要擁有大多數(shù)誠實參與者這個強(qiáng)條件,該協(xié)議也能夠保證每個成員在點對點通信網(wǎng)絡(luò)環(huán)境下公平地獲得求和結(jié)果并且能夠抵抗至多n-2個成員的合謀攻擊.

2 定義與模型

2.1 基礎(chǔ)定義

定義1安全多方求和.在交互概率圖靈機(jī)集合(M1,···,Mn)中,每一個圖靈機(jī)有公開輸入帶、私有輸入帶、私有隨機(jī)帶、隱私輸出帶和公開輸出帶,令1k為安全參數(shù),xi為Pi的輸入,Di為xi選擇的域,令f:D1×D2×···×Dn→S,是一個單輸出的多方求和函數(shù).

定義2安全計算.令sum是一個求和功能,π是可以計算sum的多方求和協(xié)議,=(x1,···,xn),輔助輸入為z,如果對每個概率多項式算法A(代表真實模型下的敵手策略),存在一個概率多項式算法B(代表理想模型下的敵手策略)滿足

其中REALπ,A(z)()表示協(xié)議π在真實模型下的聯(lián)合執(zhí)行,IDEALf,B(z)()表示f在理性模型下的聯(lián)合執(zhí)行.則稱協(xié)議π安全計算sum.

定義3多方輸入承諾功能[18].

其中,r在{0,1}|x|2上均勻分布.

定義4多方擴(kuò)展投幣[18].對任意多項式l:N→N和多項式時間可計算功能g,多方擴(kuò)展投幣的定義為:

其中,r在{0,1}l(n)上均勻分布.

定義5多方認(rèn)證計算[18].令f:{0,1}?×{0,1}?→{0,1}?,h:{0,1}?→{0,1}?是多項式時間可計算的.h-認(rèn)證f-計算的m-方功能定義為:

如果βi=h(α)則否則

定義6納什均衡.在博弈中,策略組合a=(a1,···,an)∈A是一個納什均衡,如果任一博弈方i的策略都是對其余博弈方策略的最佳對策,也就是說博弈保持

因為納什均衡具有一致預(yù)測的特性,每個博弈方都可以預(yù)測某個結(jié)果,也可以預(yù)測對手會預(yù)測它,還可以預(yù)測對手會預(yù)測自己會預(yù)測它······,通過預(yù)測來了解每個博弈方的策略及博弈的結(jié)果.

2.2 電路計算模型

電路計算在密碼學(xué)中有著非常重要的作用,是安全多方計算協(xié)議的關(guān)鍵環(huán)節(jié),一個算法電路是一個有向非循環(huán)圖,每個邏輯門相當(dāng)于一個節(jié)點,其有輸入和輸出邊,稱作邏輯門的輸入線和輸出線,首先每個參與者將自己擁有的電路的輸入線分成n個子份額,通過電路計算,每個參與者得到每個電路輸出線的子份額,然后每個參與者將子份額發(fā)給其他參與者,這樣可以得到電路計算結(jié)果.而邏輯門是一種電子裝置,它有一個或者兩個輸入,只有一個輸出.常用的有與門、非門、或門和異或門等,利用與門、或門、非門三種基本的邏輯門電路可組成復(fù)雜的復(fù)合門電路,且任何邏輯電路都可以由與門和異或門組合實現(xiàn).

例如:圖1為半加器結(jié)構(gòu)圖.為了完成兩個一位二進(jìn)制數(shù)相加,在不考慮相鄰低位的進(jìn)位的情況下,完成兩個一位二進(jìn)制數(shù)相加稱為半加,半加功能電路圖的實現(xiàn)稱為半加器.半加器由一個與門和一個異或門組成.顯然,與門具有進(jìn)位功能,異或門具有半加器求和的功能.輸出邏輯表達(dá)式為式(6).

以安全多方電路求和為例,假設(shè)有m個參與者,Pi(i=1,···,m)的隱私輸入串為xi=0,1}n,協(xié)議在結(jié)束后,如果每個參與者都了解f(x1,···,xm)=∑,且沒有人了解其他參與者的輸入,那么認(rèn)為此協(xié)議是安全的.下面首先構(gòu)造加法電路,不能簡單使用前面介紹的半加器,因為這時不僅要考慮兩個本位數(shù)相加,還要考慮將低位向本位的進(jìn)位一起相加的運(yùn)算,而實現(xiàn)全加功能的電路叫全加器.為了描述方便,以兩方為例,如果用Ai,Bi表示第i位的兩個加數(shù),用Ci-1表示相鄰低位的進(jìn)位,Ci表示往相鄰高位的進(jìn)位,Si表示本位相加和,那么構(gòu)造的一位加法器如圖2所示.

圖2 1位全加器Figure 2 One bit full adder

輸出邏輯表達(dá)式為:

多位的加法器可以采用將一位加法器串行或者并行的方法實現(xiàn),這里不再贅述.

假設(shè)每個參與者擁有邏輯求和電路每條輸入線值的子份額,等計算完成時,參與者擁有這個求和電路每一根輸出線值的子份額,此外不產(chǎn)生任何其他的附加信息.具體如下:首先每個參與者分割自己的輸入,將輸入值的每一位產(chǎn)生m個子份額.也就是說Pi(i=1,···,m)方產(chǎn)生(),其中然后Pi將子份額發(fā)給相應(yīng)的參與者,例如第一方將發(fā)給第二方,將發(fā)給第m方.經(jīng)過電路計算后,Pi分別擁有電路輸出線zi=0,1}n每一位的子份額.這樣計算完成后,每一方只知道自己的輸入和輸出結(jié)果,其余的信息都不了解.傳統(tǒng)的電路計算可以保證參與者輸入的隱私性,但是卻很難保證計算的公平性.針對這個問題,本文結(jié)合博弈論和密碼算法,構(gòu)建了理性電路計算模型,在所設(shè)計的模型中,理性的參與者沒有合謀的動機(jī),參與者根據(jù)自身效用得失,選擇誠實地遵守協(xié)議,最終每個參與者能夠公平地得到計算結(jié)果.

2.3 理性電路計算模型

在理性電路計算模型下,參與者不會像半誠實攻擊者那樣嚴(yán)格遵守協(xié)議規(guī)則,也不像惡意攻擊者那樣任意偏離協(xié)議,而是每個參與者都是理性的,所有策略都是為了使自身利益最優(yōu)化,理性的參與者根據(jù)收益的大小,可能會在協(xié)議開始時就拒絕參與協(xié)議,也可能替代他們的本地輸入,在得到計算結(jié)果后,也可能早期中斷協(xié)議.或者合謀偏離協(xié)議.但是,如果誠實地遵守協(xié)議是參與者最優(yōu)策略的話，那么參與者將沒有偏離協(xié)議的動機(jī),為了使參與者具有合作的動機(jī),本節(jié)構(gòu)建的電路概率效用模型如下.

我們用ai表示參與者Pi的策略,a=(a1,···,an)表示所有參與者的策略組合,a-i表示除Pi外其他人的策略,()=(a1,···,ai-1+1,···,an)表示參與者Pi的策略改為,r為參與者行動組合最后出現(xiàn)的結(jié)果,info(r)是一個多元組(s1,···,sn),其中如果si=1,表示Pi獲得計算輸出,否則表示沒有獲得,我們讓infoi(r)=si表示用num(r),表示了解計算結(jié)果的人數(shù),那么有如下效益假設(shè):

(1)如果info(r)=info(r′),那么ui(r)=ui(r′);

(2)如果info(r)＞info(r′),那么ui(r)＞ui(r′);

(3)如果info(r)=info(r′)且num(r)＜num(r′),那么ui(r)＞ui(r′).

即在安全多方計算中,理性的參與者首先想了解計算結(jié)果,然后希望越少的人了解計算結(jié)果越好.這保證了只要參與協(xié)議的收益足夠大,那么理性的參與者就有參與協(xié)議的動機(jī).用U+,U,U-,U--表示參與者在以下幾種情況下的收益:(a)當(dāng)r表示Pi了解秘密信息,而其他參與者不了解秘密信息時,那么ui(r)=U+;(b)當(dāng)r表示Pi了解秘密信息,而至少有一個其他參與者也了解秘密信息時,那么ui(r)=U;(c)當(dāng)r表示Pi不了解秘密信息,其他參與者也不了解秘密信息時,那么ui(r)=U-;(d)當(dāng)r表示Pi不了解秘密信息,而至少有一個其他參與者了解秘密信息時,ui(r)=U--.他們間的關(guān)系是U+＞U＞U-＞U--.

本文所設(shè)計的模型采用了多輪博弈,并且不讓參與者知道博弈何時結(jié)束.為了及時的發(fā)現(xiàn)參與者欺騙,在每一輪中利用可驗證的方法對參與者的行為和策略進(jìn)行檢驗.將秘密s∈Zq放在某一輪中,用k表示,其余的為無意義的測試輪.當(dāng)協(xié)議在第r輪時,如果其他參與者采用指定的策略σ-i(即誠實的發(fā)送子秘密的份額),而參與者Pi采用策略進(jìn)行欺騙,用cheat表示這個基本事件.當(dāng)r＜k,用early表示,此刻,Pi只能通過猜測秘密進(jìn)行欺騙;當(dāng)r=k,用exact表示,即Pi正好在第k輪偏離協(xié)議;當(dāng)r＞k,用late表示,即參與者在k輪之后進(jìn)行欺騙;correct表示Pi輸出了正確的秘密值;Pr[·]表示事件發(fā)生的概率.那么參與者Pi在第r輪欺詐的期望收益為:

且

(因為s∈Zq),及可得:

由此可知如果滿足式(11)

則協(xié)議能夠保證博弈達(dá)到均衡狀態(tài),使得參與者不會背離協(xié)議,從而正確的執(zhí)行協(xié)議.

3 Beaver構(gòu)造的有偏向投幣協(xié)議

在Beaver構(gòu)造的有偏向的投幣協(xié)議[19]中,設(shè)d是明確公平性約束的參數(shù),令R(x1,···,xn)=x1⊕···⊕xn.如果對于任意xi是均勻隨機(jī)比特,那么R也是均勻隨機(jī)的比特.對于?功能來說,如果x1+···+x2kd≥kd+1,那么?(x1,···,x2kd)=1,否則?=0.如果?的輸入是均勻隨機(jī)的,那么輸出則是以概率偏向0.協(xié)議偽代碼如算法1.

代碼中EVALUATE功能表示安全多方計算功能,詳細(xì)內(nèi)容請參考文獻(xiàn)[19].協(xié)議的思想是產(chǎn)生一系列偏向0的投幣,然后將投幣值和計算值異或,誠實者能夠及時發(fā)現(xiàn)惡意者中斷協(xié)議或者有欺騙的行為并且此時所有參與者獲得的信息量基本相等(最多差一個采樣點).但是Beaver的協(xié)議僅適用于布爾類型的函數(shù)值,為了能將其擴(kuò)展到多方求和協(xié)議,本文結(jié)合博弈論的思想改進(jìn)了Beaver設(shè)計的協(xié)議,根據(jù)參與者的收益函數(shù),生成一個隨機(jī)字符串,利用隨機(jī)字符串隱藏多方求和的值,然后參與者按位揭示隨機(jī)串,最終恢復(fù)求和的值.

4 基于電路計算的理性安全多方求和協(xié)議

在我們的協(xié)議中,除保證參與者有執(zhí)行協(xié)議的動機(jī)之外,還有以下要求:(1)保證每個理性的參與者的輸入需要獨立于其他參與者的輸入;(2)在每個階段,保證合謀集團(tuán)都能發(fā)送正確的信息;具體步驟如下.

Algorithm 1:有偏向的投幣協(xié)議for l=1,···,k3d do for m=1,···,2kd do Each player i chooses a random bit bim.Run EVALUATE-R(b1m,···,bnm),and let cm be the output.end Enddo Run EVALUATE-?(c1,···,c2kd)to obtain a secret,biased coin,ej.Run EVALUATE-exor on V and ej to obtain the masked result rj.Each player i broadcasts his piece of rj.Each player i interpolates rj if n-t pieces have been broadcast,otherwise he outputs cheating.end Enddo Output:Majority(r1,···,rk3d)

(1)根據(jù)所求功能,首先設(shè)計相應(yīng)的邏輯電路,假設(shè)有m個參與者,Pi(i=1,···,m)的輸入串為希望電路輸出得到為了描述方便,本文首先設(shè)計了有兩個參與者的兩方安全求和電路,每個參與者輸入為2位的電路,如圖3,其中表示xi的最低位,y0表示電路求和值f(x1,···,xm)的最低位.其次設(shè)計了4個參與者的四方安全求和電路,每個參與者的輸入為2位的求和電路,如圖4.對于n人多位的電路可以類推設(shè)計.

圖3 兩方安全求和電路Figure 3 Two-party secure sum circuit

(2)利用傳統(tǒng)的多方計算協(xié)議產(chǎn)生一個隨機(jī)二進(jìn)制串R(可以將R視為一個向量),|R|取決于參與者的效益且滿足具體過程如下:每個參與者隨機(jī)選擇一比特σi,令功能Coin-gen(σ1,···,σn)=σ1⊕···⊕σn,運(yùn)行傳統(tǒng)的GMW多方電路計算[18]產(chǎn)生一系列投幣(承諾但隱藏的)br=Coin-gen(σ1,···,σn),令br(1,···,|R|)為第r個比特.這樣,每個參與者擁有R串中每一位比特的子份額.

(3)利用傳統(tǒng)的GMW多方電路計算[18]輸出f(x1,···,xn)+R的子份額,此時,如果每個參與者將子份額發(fā)給其他參與者,不會對公平性造成影響,因為有隨機(jī)數(shù)R對f(x1,···,xn)進(jìn)行了隨機(jī)隱藏,這樣,每個參與者獲得f(x1,···,xn)+R的值.

(4)然后循環(huán)|R|輪來取得R中的每一位,獲得的具體步驟如下:在r(1,···,|R|)輪,利用Beaver等[19]投幣協(xié)議來揭示R中的每一位br.具體如下:循環(huán)k3d次,每次運(yùn)行EVALUATE?(c1,···,c2kd),獲得概率偏向0的投幣ej,運(yùn)行多方電路計算,每個參與者獲得ej⊕br的子份額,然后每個參與者依次發(fā)送子份額,循環(huán)k3d之后,參與者可以獲得k3d個采樣點,根據(jù)0和1數(shù)量的多數(shù)原則可確定br的值,通過|R|輪循環(huán)后,所有參與者都能獲得R.最后,和前面獲得的f(x1,···,xn)+R相減,即每個參與者可公平地得到求和值.

(5)為了保證參與者能誠實的執(zhí)行協(xié)議,利用GMW編譯器,對以上每一步驟進(jìn)行編譯.

圖4 四方安全求和電路Figure 4 Four-party secure sum circuit

5 協(xié)議分析

定理1在基于電路計算的安全多方求和過程中,參與者在獲得最后求和結(jié)果時,不會泄露自身的隱私輸入.

證明:在一個邏輯電路計算中,假設(shè)有m個參與者,Pi(i=1,···,m)的輸入串為{0,1}n,每個參與者分割每一位輸入,對于每個數(shù)字i=1,···,m,j=1,···,n和k/i,Pi隨機(jī)選擇一位發(fā)送Pi,使其為第(i-1)n+j根電路輸入線值的子份額,而Pi的子份額為由于任何邏輯電路都可以由與門和一個異或門組合實現(xiàn),而與門代表乘法門、異或門代表加法門,所以只需考慮這兩種門的計算即可.因為不經(jīng)意傳輸協(xié)議在多方安全計算中占有至關(guān)重要的作用,下面考慮加法門和乘法門的計算.

在邏輯電路中加法門的計算,每個參與者將zi=ai+bi作為邏輯加法門輸出線值的子份額,這些子份額滿足: 可以看到這正是理想的值,所以加法門平凡地滿足要求.

在邏輯電路中乘法門的計算,如果仍采用上面的方法來計算乘法門,計算結(jié)果則不符合要求,下面看一下通過乘法門進(jìn)行計算后所得結(jié)果:

從式(13)看出,Pi知道ai,bi,而可以由Pi和Pj執(zhí)行安全兩方電路計算獲得,計算過程如下:

Pi隨機(jī)選擇一位比特ci,并將ci作為與門輸出線值的子份額即另外Pi準(zhǔn)備四個值Pi和Pj執(zhí)行不經(jīng)意傳輸協(xié)議.

調(diào)用不經(jīng)意傳輸協(xié)議后,Pj得到與門輸出值的子份額,即

下面分四種情況討論:

(1)當(dāng)(aj,bj)=(0,0)時,令=ci+(ai+0)·(bi+0),即=,這時滿足式(14):

(2)當(dāng)(aj,bj)=(0,1)時,令即=,這時滿足式(15):

(3)當(dāng)(aj,bj)=(1,1)時,令即=,這時滿足式(16):

(4)當(dāng)(aj,bj)=(1,0)時,令即=,這時滿足式(17):

我們可以看到經(jīng)過與門的計算P1得到得到,滿足式(18):

下面Pi將作為乘法門輸出線的子份額,可知乘法門滿足式(19):

將加法門和乘法門組合后,就形成了一個邏輯求和電路,通過對邏輯電路中的每一個邏輯門運(yùn)算,Pi會獲得電路輸出線的子份額si.最終,Pi將自己的電路輸出線的子份額si發(fā)給其他人,這樣每個人都能夠得到電路計算結(jié)果

定理2方案在滿足式(21)的條件下,參與者沒有合謀偏離協(xié)議的動機(jī),協(xié)議能保證公平性.

證明:在方案中,每一個合謀集團(tuán)C?[n],|C|≤m-1中的合謀者不能通過合謀獲得R,如果合謀者通過猜測R,猜對的概率為合謀者Pi獲得效益為.猜錯的概率為1-,合謀者Pi獲得效益為合謀者Pi的期望收益為

而當(dāng)

即

也就是當(dāng)

時,參與者沒有偏離協(xié)議動機(jī),當(dāng)參與者執(zhí)行協(xié)議第四步,在取得R中的最后一位時,如果合謀者提前中斷協(xié)議,將會使得所有參與者有的概率獲得R,這里有兩種情況:一種是合謀者在誠實者前面發(fā)送子份額,另一種是合謀者在誠實者之后發(fā)送子份額.在第一種情況中,當(dāng)合謀者中斷協(xié)議時,合謀者和后發(fā)送子份額的誠實者了解的信息采樣點相同.在第二種情況中,當(dāng)合謀者中斷協(xié)議時,合謀者比先發(fā)送子份額的誠實者多了解一個信息采樣點(信息量幾乎相等).所以合謀者沒有偏離協(xié)議的動機(jī),最終每個參與者都能公平的得到計算結(jié)果.

6 小結(jié)

本文結(jié)合密碼學(xué)與博弈論,對安全多方求和過程中,參與者遵守和背離協(xié)議的策略、效益進(jìn)行了分析與設(shè)計,構(gòu)建了一種安全多方求和電路的概率效用模型.我們所設(shè)計的理性安全多方求和協(xié)議消除了成員欺詐的動機(jī)并且不需要擁有大多數(shù)誠實參與者這個強(qiáng)條件,解決了參與者在多方求和計算過程中合謀問題,能夠保證每個成員在標(biāo)準(zhǔn)點對點通信網(wǎng)絡(luò)下公平地獲得求和結(jié)果.