直方圖與餅形圖的保密生成協(xié)議*

葛 雪,王穎囡,竇家維

陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,西安 710119

1 引言

網(wǎng)絡(luò)的迅速發(fā)展為多個參與者利用各自的保密數(shù)據(jù)聯(lián)合進(jìn)行數(shù)據(jù)挖掘、知識發(fā)現(xiàn)、信息搜索以及尋求數(shù)據(jù)之間的各種統(tǒng)計規(guī)律、合作進(jìn)行科學(xué)研究等提供了巨大的機會,同時也給參與者的信息安全帶來了巨大的挑戰(zhàn).在互不信任的網(wǎng)絡(luò)環(huán)境中,參與者需要保護(hù)各自所擁有數(shù)據(jù)的隱私,在聯(lián)合計算過程中稍有不慎就可能導(dǎo)致數(shù)據(jù)的機密性喪失與隱私泄露.運用安全多方計算技術(shù),既能充分發(fā)揮機密數(shù)據(jù)的作用,又能保護(hù)數(shù)據(jù)的機密性與隱私,這使得安全多方計算越來越受到人們的關(guān)注.

1982年姚期智[1]提出了兩個參與者的安全計算問題,1988年Ben 和Goldwasser[2]引入了多個參與者的安全多方計算問題.安全多方計算是指兩個或更多參與者利用各自的保密數(shù)據(jù),聯(lián)合進(jìn)行的保密計算.計算結(jié)束后,沒有參與方能夠獲得多于規(guī)定輸出的信息.安全多方計算是網(wǎng)絡(luò)空間信息安全與隱私保護(hù)的關(guān)鍵技術(shù),它對于計算科學(xué)、密碼學(xué)和信息安全的理論與實踐都有重要的意義,是國際密碼學(xué)界近年來的研究熱點[3–5].Goldwasser[6]預(yù)言具有豐富理論基礎(chǔ)和廣泛應(yīng)用前景的安全多方計算將成為計算科學(xué)一個必不可少的工具.Cramer[7]也指出安全多方計算將成為計算科學(xué)一個威力強大的工具.

Yao、Goldwasser 以及Goldreich 等人[8–10]奠定了安全多方計算的理論基礎(chǔ).他們證明了所有安全多方計算問題都是可解的,并給出了解決方案.但是他們指出這些解決方案存在的共同問題是它們的效率都太低了,利用這些通用的解決方案去解決現(xiàn)實生活中各種各樣的問題是不切實際的.因此對具體問題應(yīng)該設(shè)計具體的解決方案.

在Goldwasser,Goldreich 和Cramer 關(guān)于安全多方計算研究與論述的激勵下,人們研究了各種各樣的安全多方計算問題,如保密的科學(xué)計算[1,11–17]、保密的計算幾何[18–20]、保密的統(tǒng)計分析[21,22]、保密的數(shù)據(jù)挖掘[23–25]、其他安全多方計算的應(yīng)用[26,27]等,但仍有許多問題需要研究.

其中,保密的統(tǒng)計分析是研究如何在合作環(huán)境下進(jìn)行統(tǒng)計分析,并確保每個參與者自身數(shù)據(jù)的安全性,這在自然科學(xué)、工程技術(shù)、社會科學(xué)的各個方面都有非常廣泛的應(yīng)用.本文主要研究了保密生成直方圖、餅形圖的問題,這是保密的統(tǒng)計分析中一個非常重要的問題.就目前我們所知,還沒有見到關(guān)于這個問題的解決方案.直方圖與餅形圖是一種統(tǒng)計報告圖,二者的優(yōu)點是可以直觀地看出數(shù)據(jù)整體的分布情況.與數(shù)據(jù)的排序相比,直方圖與餅形圖更加直觀,在數(shù)據(jù)較多時,對數(shù)據(jù)進(jìn)行一一進(jìn)行排序是不太現(xiàn)實的,會耗費過多的人力物力而收益甚微.在實際生活中,直方圖、餅形圖有非常多的應(yīng)用場景,比如:一個學(xué)校想要知道學(xué)生成績的分布情況,但是每個班的成績、每個同學(xué)的成績都屬于個人隱私,同學(xué)們不想對外公布,這時候就涉及到保密求直方圖、餅形圖的問題.另外,對于各地區(qū)隱私疾病直方圖、保密投票數(shù)據(jù)的直方圖與餅形圖等等在現(xiàn)實生活中都十分常見,因此研究直方圖與餅形圖的保密生成問題是十分必要的.

本文的主要貢獻(xiàn)如下:

(1)提供了一種新的編碼方法,能夠?qū)⑴c者的保密數(shù)據(jù)隱藏在數(shù)組中.

(2)利用該編碼方法結(jié)合Paillier 加法同態(tài)加密算法,設(shè)計了第一種保密生成直方圖的解決方案.該方案可以抵抗P1不參與時的合謀攻擊.

(3)利用該編碼方法結(jié)合橢圓曲線加法同態(tài)加密算法以及門限加密算法,設(shè)計了第二種保密生成直方圖的解決方案.第二種方案可以抵抗任意數(shù)量的合謀攻擊,并且效率也提高許多.

2 預(yù)備知識

2.1 安全性定義

半誠實模型:所謂半誠實參與者[10]是指那些在協(xié)議的執(zhí)行過程中按照協(xié)議要求忠實地履行協(xié)議的參與者,但他們可能會記錄下協(xié)議執(zhí)行過程中收集到的所有信息,在協(xié)議執(zhí)行后試圖根據(jù)記錄的信息推算出其他參與者的輸入.如果所有的參與者均為半誠實參與者,這樣的計算模型稱為半誠實模型.由于半誠實參與者不對協(xié)議實施主動攻擊,所以半誠實模型又稱為誠實但好奇(honest-but-curious)模型或被動模型.

設(shè)有n個參與者P1,···,Pn,分別具有保密數(shù)據(jù)x1,···,xn,記X=(x1,···,xn).他們利用協(xié)議Π保密地計算f(X)=(f1(X),···,fn(X)),其中fi(X)(i∈[n]={1,···,n})為參與者Pi得到的輸出結(jié)果.在協(xié)議執(zhí)行過程中,Pi得到的信息序列記為

其中,ri表示Pi在協(xié)議中產(chǎn)生的隨機數(shù),(j=1,···,t)表示Pi收到的第j個信息.對于部分參與者構(gòu)成的子集I={Pi1,···,Pis}?{P1,···,Pn},記

定義1(半誠實參與者的安全性[10])在參與者都是半誠實的情況下,如果存在概率多項式時間算法S,使得對于任意的I={Pi1,···,Pis}?{P1,···,Pn},均有下式成立:

其中表示計算上不可區(qū)分,則稱協(xié)議Π 保密地計算了n元函數(shù)f(X).

顯然,如果對于任意n?1 個參與者構(gòu)成的集合Γ,都存在滿足(1)式的S,則協(xié)議Π 能夠抵抗任意的合謀攻擊.

2.2 Paillier同態(tài)加密算法

同態(tài)加密的概念在文獻(xiàn)[28]中被首次提出,它可以保證在不影響明文數(shù)據(jù)機密性的情況下,直接操作密文來完成對明文的計算.簡單來說,對密文的計算等價于明文計算之后再加密.

Paillier 方案[29]的具體過程如下.

密鑰生成給定一個安全參數(shù)k,選擇兩個素數(shù)p,q,使得|p| =|q| =k,其中N=p×q,λ=lcm(p?1,q?1)是p?1 和q?1 的最小公倍數(shù).隨機選擇一個g∈,使得gcd(L(gλmodN2),N)=1,定義為L(x)=.算法的公鑰為(g,N),私鑰為λ.

加密隨機選擇一個隨機數(shù)r,r

解密計算

該算法是概率加密算法,具有加法同態(tài)性.假設(shè)密文為

那么

因此該算法滿足如下性質(zhì):

2.3 橢圓曲線同態(tài)加密算法

橢圓曲線密碼體制ECC(elliptic curve cryptography)是1985年由Miller 和Koblitz 共同提出的.其理論基礎(chǔ)是定義在有限域上的某一橢圓曲線上的整數(shù)點與無窮遠(yuǎn)點可構(gòu)成有限交換群.如果該群的階包含一個較大的素因子,則其上的離散對數(shù)問題是困難的.與RSA 算法相比,ECC 具有計算量小、密鑰短、對帶寬和處理器要求低等優(yōu)點.基于橢圓曲線實現(xiàn)ElGamal 密碼體制[30]描述如下.

在使用橢圓曲線密碼體制之前,必須設(shè)計把信息編碼到橢圓曲線上的點的編碼方法,具體如下[31].

(1)選擇一個具有n個點的橢圓曲線.

(2)選擇一個輔助基本參數(shù)k,比如設(shè)k=20(加密解密雙方達(dá)成一致).

(3)對于每一個m,Fori=1 tok?1,令x=mk+i,利用橢圓曲線方程求y.如果找到就停止,如果找不到就令i←i+1,繼續(xù)找,直到找到為止.實際上,可以找到一點(x,y),這個點就是消息m的編碼.

(4)解碼:點(x,y)解碼為的值向下取整).

密鑰生成選定一條橢圓曲線EC(a,b)與其上的一個基點G,在上任意選擇一個隨機數(shù)h,計算H=hG.(H,G)就是公鑰,h是私鑰.

加密消息編碼到EC(a,b)上一點M,并產(chǎn)生一個隨機整數(shù)r,計算密文

解密對密文1,C2,用私鑰h解密得到明文為

該算法是概率加密算法,具有加法同態(tài)性.假設(shè)密文

那么

因此該算法滿足如下性質(zhì):

2.4 門限解密

門限解密[32,33]是安全多方計算中對抗合謀攻擊的一個重要工具.在門限解密密碼體系中,n個參與者共同生成一個公鑰,每個人持有一部分解密密鑰.在加密過程中可以直接使用共同擁有的公鑰加密消息,但是需要多個參與者共同合作才能對密文進(jìn)行解密.如果解密一個消息至少需要t個人合作才能解密,少于t個人合作時將不能得到解密消息,這種密碼體制被稱為(t,n)門限密碼體制.

本文需要抵抗盡可能多的合謀攻擊,所以需要的是(n,n)門限密碼系統(tǒng)用于抵抗n?1 個參與者的合謀攻擊,這里可以利用橢圓曲線密碼系統(tǒng)構(gòu)造門限密碼系統(tǒng),具體構(gòu)造如下.

密鑰生成選定一條橢圓曲線EC(a,b)與其上的一個基點G,每個參與者Pi在上任意選擇一個私鑰hi,計算Hi=hiG,共同生成公鑰

加密消息編碼到EC(a,b)上一點M,并在上任意選擇一個隨機數(shù)r:1rn?1,計算密文C1,C2=m+rH,rG.

解密對密文C1,C2,通過下面解密過程得到明文:

3 直方圖保密生成協(xié)議

3.1 協(xié)議的基本原理

問題描述:假設(shè)現(xiàn)有n個參與者Pi(i=1,2,···,n),每一個Pi都有多個數(shù)據(jù)記為ei={ei1,ei2,···},他們希望合作計算這些數(shù)據(jù)的直方圖,同時不泄露其他任何私有信息(即參與方最后僅知道這些數(shù)據(jù)所生成的直方圖與餅形圖,并不知道其它參與者擁有的具體數(shù)據(jù)).

編碼方法:首先每一個參與者Pi共同商定將區(qū)間分割為m份,記為 {[y1,y2),[y2,y3),···,[ym,ym+1]} ={S1,S2,···,Sm},其中Si=[yi,yi+1)(i=1,2,···,m?1),Sm=[ym,ym+1],接著按照下面的方法構(gòu)造數(shù)組:

其中對于i∈{1,2,···,n},k∈{1,2,···,m},

以此方式,每個參與者的數(shù)據(jù)ei與數(shù)組Xi一一對應(yīng).對此得到的n個數(shù)組X1,X2,···,Xn求和,即將這些數(shù)組對應(yīng)元素相加,得到一個新的數(shù)組:

數(shù)組T即為所求對應(yīng)區(qū)間所含元素的個數(shù).根據(jù)區(qū)間{[y1,y2),[y2,y3),···,[ym,ym+1]} 以及數(shù)組T可繪制出相應(yīng)直方圖,對數(shù)組T稍加運算,計算出每個區(qū)間Si(i=1,2,···,n)所含元素個數(shù)占總數(shù)量的百分比,就可繪制出該數(shù)據(jù)的餅形圖.下面以某個年級學(xué)生的數(shù)學(xué)成績?yōu)槔?

例1若將學(xué)生成績分為[0,10),[10,20),···,[90,100]這10 個區(qū)間段,繪制表1.

表1 某個年級學(xué)生的數(shù)學(xué)成績Table 1 Math scores of a grade

按照上述編碼方式,

計算向量對應(yīng)分量之和即為

則可得出對應(yīng)的直方圖,再稍加運算,可得到餅形圖(如圖1).

圖1 某個年級學(xué)生數(shù)學(xué)成績直方圖與餅形圖Figure 1 Histogram and pie charts of math scores of a grade

以上的編碼方法就是本文計算直方圖與餅形圖的基本原理.直接這樣計算是無法保密的,而在密文的條件下進(jìn)行這樣的操作就可以實現(xiàn)保密運算.本文用Paillier 加密算法與橢圓曲線門限加密對數(shù)組中的0和1 進(jìn)行加密,使得任何參與者都無法分辨出數(shù)組中0 與1 的個數(shù)(由于求出直方圖便可求出相應(yīng)的餅形圖,為敘述簡潔,以下協(xié)議均僅求出直方圖).

3.2 基本的直方圖保密計算方案

首先,應(yīng)用具有加法同態(tài)性質(zhì)的Paillier 加密算法給出一種保密生成直方圖的基本方案,如協(xié)議1.

協(xié)議1直方圖的保密生成協(xié)議.

輸入Pi各自擁有的保密數(shù)據(jù)ei.

輸出該組數(shù)據(jù)的直方圖.

(1)P1應(yīng)用Paillier 公鑰系統(tǒng)生成私鑰sk 和公鑰pk,并公布公鑰pk.

(2)每個參與者Pi(i=1,2,···,n)以公式(2)將自己的數(shù)據(jù)轉(zhuǎn)化成數(shù)組Xi=(xi1,xi2,···,xim).

(3)每個參與者Pi(i=1,2,···,n)用公鑰pk 加密數(shù)組Xi得到E(Xi)=(E(xi1),E(xi2),···,E(xim)).

(4)參與者Pi(i=1,2,···,n)計算如下(此處的向量相乘為E(Xi)和E(Xi+1)中對應(yīng)分量相乘):

(5)參與者Pn將E(Xn)發(fā)送給P1,P1計算X=Dec(E(Xn)),繪制相應(yīng)的直方圖并公布.

3.3 方案分析

正確性分析在協(xié)議1 中,由于Paillier 加密算法的加法同態(tài)性(即對密文做乘法運算等于對相應(yīng)的明文做加法運算后再加密),可得出:

安全性分析由于只有P1有私鑰可以解密,所以協(xié)議可以抵抗沒有P1參加的任何合謀攻擊,但該協(xié)議不能抵抗有P1參與時的合謀攻擊.以下是關(guān)于協(xié)議1 安全性的具體分析.

定理1直方圖的保密生成協(xié)議在半誠實模型下是安全的.

證明:通過構(gòu)造滿足式(1)的模擬器S來證明本定理,此處選用可能參與合謀的最大合謀結(jié)構(gòu)進(jìn)行模擬.分為以下三種情況:

(1)P1不參與合謀,P2,···,Pn合謀能獲得P1的保密數(shù)據(jù)的信息.

因為只有P1才能夠解密密文,如果他不參與合謀,除了P2,···,Pn的數(shù)據(jù)和他們生成的密文之外,P2,···,Pn收到的關(guān)于e1的信息只有E(X1)=(E(x11),E(x12),···,E(x1m))=(c11,c12,···,c1m).由于加密算法是語義安全的,(ci1,ci2,···,cim)和m個隨機數(shù)是計算不可區(qū)分的.在此情況下,

給定輸入(I,(e1,···,en),fI(X)),S隨機選擇使得f(X′)=fI(,···,en)=(···,)=fI(X)=f(e1,···,en)=(t1,t2,···,tm)用···,en進(jìn)行模擬.首先按照協(xié)議要求構(gòu)造數(shù)組=(,,···,),加密得到

模擬器S 按照協(xié)議要求進(jìn)行加密運算.解密最終數(shù)組E(X′)得到

令S(I,(e1,···,en),fI(X))={I,e2,E(X2),···,en,E(Xn),fI(X′)},因為概率加密方案是語義安全的,所以E(X1)(),且fI(X1)c≡fI(),其他所有參數(shù)都是相等的,故

因此對于e1是安全的.

(2)P1不參與合謀,P2,···,Pn的n?2 個合謀想得到其中一個的保密數(shù)據(jù),因為這時P2,···,Pn的地位是平等的,能力是相同的,不失一般性假設(shè)P3,···,Pn合謀要獲得P2的保密數(shù)據(jù)的信息.這種情況與第一種情況相同,用類似的模擬可以證明對于e2是安全的.

(3)P1參與合謀.這種情況下的最大合謀結(jié)構(gòu)仍然是包含P1的n?1 個參與者合謀,要得到某一個Pi∈{P2,···,Pn} 的某個參與者的保密數(shù)據(jù)ei所在的區(qū)間范圍,無法知道ei的大小.

綜上所述,該協(xié)議對于半誠實參與者是安全的.

4 基于門限解密的直方圖保密生成協(xié)議

在本文協(xié)議1 中,參與者Pi將E(Xi)先發(fā)送給Pi+1,Pi+1計算E(Xi)×E(Xi+1),并將其發(fā)送給下一個參與者,以此類推,直到Pn將最后的每個參與者加密向量對應(yīng)分量的乘積E(Xn)發(fā)送給P1.P1將E(Xn)解密并公布,如果P1參與合謀攻擊,比如,參與者P1和P3合謀,會恢復(fù)出P2的數(shù)據(jù).所以需要借助門限橢圓曲線加密系統(tǒng)設(shè)計一個更安全、更高效的協(xié)議,以達(dá)到抵抗合謀攻擊的目的.基本原理與上述相同,不再贅述.

4.1 基本原理與協(xié)議

協(xié)議2基于門限密碼系統(tǒng)的直方圖的保密生成方案.

輸入Pi各自擁有的保密數(shù)據(jù)ei.

輸出該組數(shù)據(jù)的直方圖.

(1)n個參與者P1,···,Pn首先選定一條橢圓曲線EC(a,b),G為其上基點.每個參與者分別選擇一個私鑰hi,計算Hi=hiG,共同生成公鑰

將公鑰H公開,私鑰hi各自保留.

(2)每個參與者P1,···,Pn分別做如下運算:

(a)Pi將自己擁有的數(shù)據(jù)ei按公式(2)編碼方式轉(zhuǎn)化成數(shù)組Xi=(xi1,xi2,···,xim).

(b)參與者Pi將數(shù)組Xi編碼到EC(a,b)上作為橢圓曲線上的點Mi=(Mi1,Mi2,···,Mim).

(c)Pi在上任意選擇一個隨機數(shù)rij:1rijn?1,計算密文

并公布.

(3)參與者P1,···,Pn將加密后的數(shù)據(jù)E(Mi)依次相加(即對應(yīng)分量相加),并記

(4)參與者Pi計算hiC2j(j=1,2,···,m),并公布.P1,···,Pn將其依次相加將得到

(5)最后參與者Pi只需計算

并繪制相應(yīng)的直方圖即可.

4.2 方案分析

正確性分析在協(xié)議2 中,由于橢圓曲線密碼體制具有加法同態(tài)性質(zhì)(即對密文做加法運算等于對相應(yīng)的明文做加法運算后再加密),可得出:

所以協(xié)議2 是正確的,可以求出數(shù)組T,并繪制相應(yīng)的直方圖.

安全性分析協(xié)議的安全性是基于橢圓曲線加密體制的安全性.由于門限橢圓曲線的公鑰是由所有參與者共同產(chǎn)生的,即其中hi是參與者Pi所持有的私鑰碎片,如果想解密的話,就必須擁有全部參與者的私鑰碎片.所以整個解密的過程都必須要全部參與者參與,因而可以抵抗合謀攻擊.

在計算過程中,每個參與者Pi對外僅公布了加密信息E(Mi),在解密過程中對外也僅公布了加密信息hiC2j(j=1,2,···,m),由橢圓曲線密碼體制的安全性可知,在協(xié)議解密過程中如果Pi沒有參與,將無法解密得到Mj.因此在解密過程中,Pi的數(shù)據(jù)是完全保密的.我們給出下面的定理,僅給出證明思路,詳細(xì)的證明過程省略.

定理2在半誠實模型下,基于門限密碼系統(tǒng)的直方圖的保密生成協(xié)議2 是安全的.

證明:證明協(xié)議的安全性需要構(gòu)造滿足式(1)的模擬器S.根據(jù)語義安全的同態(tài)加密算法的性質(zhì),如果沒有私鑰,應(yīng)用概率公鑰系統(tǒng)加密的任何信息都是計算不可區(qū)分的,因此只要有一個參與者不合謀,對其他合謀者來說,他們實際執(zhí)行協(xié)議時獲得的view 和用滿足生成直方圖不變的任意一組輸入進(jìn)行模擬所得到的信息序列是計算不可區(qū)分的,所以只要在(1)式中令S(I,(xi1,···,xis)),fI(X))為模擬過程中的view,即可使(1)式滿足.

5 協(xié)議的效率分析

本部分對上述兩個保密生成直方圖的協(xié)議效率進(jìn)行分析比較.本文方案都是用同態(tài)加密算法解決直方圖問題,基本運算都是模乘運算.(忽略各協(xié)議中所需要的乘法運算)用Paillier 加密系統(tǒng)加密或者解密一次需要進(jìn)行兩次模指數(shù)運算.應(yīng)用橢圓曲線加密系統(tǒng)進(jìn)行的是模加運算,模加運算的次數(shù)與加密過程中所選隨機數(shù)r的二進(jìn)制位數(shù)有關(guān).

5.1 計算復(fù)雜性

在本文協(xié)議1 中,每個參與者都需要對編碼后的數(shù)組元素進(jìn)行加密,n個參與者需要進(jìn)行2mn次模指數(shù)運算,所以協(xié)議1 在加密過程中需要進(jìn)行2mn次模指數(shù)運算.最后P1對E(Xn)進(jìn)行解密,需要2m次模指數(shù)運算.所以協(xié)議1 共需要2m(n+1)次模指數(shù)運算,計算復(fù)雜性為2m(n+1).

在本文協(xié)議2 中,參與者都需要對編碼后的數(shù)組元素進(jìn)行加密,所以協(xié)議2 共加密2nm次.參與者利用自己的私鑰對密文聯(lián)合解密,共解密n次.加密和解密過程均需要進(jìn)行模加運算,所以協(xié)議2 的計算復(fù)雜性是O(nlogr)模加運算(r表示加密過程中的隨機數(shù)且0rp?1).

5.2 通信復(fù)雜性

衡量通信復(fù)雜度的指標(biāo)一般用協(xié)議交換信息的比特數(shù),或者用通信輪數(shù).在安全多方計算研究中通常用輪數(shù).

在協(xié)議1 中,每個參與者需要將加密后的密文發(fā)送給Pn,Pn將收到的密文做運算后發(fā)送給P1解密,在這個過程中需要n輪通信.最后P1解密,并且將解密結(jié)果告訴Pi,需要n?1 輪通信.所以協(xié)議1 共需要2n?1 輪通信,通信復(fù)雜性為O(n).

在協(xié)議2 中,所有參與者構(gòu)造公鑰需要n?1 輪通信,加密過程宣布Mi,需要1 輪通信,解密過程宣布需要1 次通信,所以協(xié)議2 共需要n+1 輪通信,通信復(fù)雜性為O(n).

表2 協(xié)議性能比較Table 2 Protocol performance comparison

5.3 實驗數(shù)據(jù)分析

本節(jié)我們通過模擬實驗來測試執(zhí)行協(xié)議1、協(xié)議2 所用的時間,通過協(xié)議執(zhí)行的時間來驗證方案的效率執(zhí)行情況.

實驗測試環(huán)境:Windows 10 64 位操作系統(tǒng),Intel(R)Core(TM)i5-6600 處理器CPU @3.30 GHz,8.00 GB 內(nèi)存,用java 語言在MyEclipse 上運行實現(xiàn).本文所做模擬實驗均在此環(huán)境下進(jìn)行.

實驗方法:本實驗中,我們的底層協(xié)議(Paillier 算法,橢圓曲線加密算法)是使用了現(xiàn)成的開源包.實驗設(shè)定m=10,參與者數(shù)分別為n=3,4,···,25.為使數(shù)據(jù)準(zhǔn)確,對n的每個設(shè)定值進(jìn)行1000 次模擬實驗測試,統(tǒng)計協(xié)議執(zhí)行時間的平均值(忽略協(xié)議中的預(yù)處理時間).圖2 描述了協(xié)議的執(zhí)行時間隨參與者個數(shù)增長的變化規(guī)律.

圖2 協(xié)議的執(zhí)行時間隨參與者個數(shù)增長的變化規(guī)律Figure 2 Execution time of agreement varies with growth of number of participants

由圖2 可知協(xié)議的執(zhí)行時間隨參與者個數(shù)增長而線性增加,并且很容易得出,基于橢圓門限解密的保密直方圖生成方案效率要高于基于Paillier 加密算法的保密直方圖生成方案.

6 結(jié)論

本文設(shè)計了一種新的編碼方法,以新的編碼方法與同態(tài)加密算法為基礎(chǔ),分別利用Paillier 加法同態(tài)加密算法、門限橢圓曲線加法同態(tài)加密算法構(gòu)造了保密生成直方圖問題的兩個安全多方計算協(xié)議.第一個協(xié)議在半誠實模型下是安全的,但不能有效地抵抗合謀攻擊.第二個協(xié)議可以抵抗多達(dá)n?1 個參與者的合謀攻擊.將協(xié)議加以推廣可以適用于更加普遍的情形,今后將在現(xiàn)有的研究基礎(chǔ)上進(jìn)一步研究抗惡意參與者(主動攻擊者)的直方圖問題.