云環(huán)境下多方保密計算最大值、最小值及其統(tǒng)計學應用*

李占利,陳立朝,陳振華,劉婭茹

西安科技大學 計算機科學與技術(shù)學院,西安 710054

1 引言

在信息化、網(wǎng)絡化的時代,隱私保護變得日益重要,越來越多的合作計算需要在保護隱私的基礎之上進行,把這種計算模式可歸結(jié)到安全多方計算的范疇中,這是由華裔科學家、圖靈獎獲得者姚期智[1]教授率先提出的,需要參與合作計算的每一方利用自己的隱私數(shù)據(jù)合作計算出一個共同的函數(shù),要求任何一方都得不到其他參與者的隱私數(shù)據(jù),也不能利用中間計算結(jié)果推導出他人的保密數(shù)據(jù).安全多方計算具有廣泛的實際應用,如:保密質(zhì)量評估[2]、保密的數(shù)據(jù)挖掘[3–6]、保密的計算幾何[7–10]、保密的統(tǒng)計分析[11]、保密科學計算[12]、安全云外包計算[8,13–15]等.在保密的科學計算中,已經(jīng)研究了百萬富翁問題[16–18]、安全集合操作[19–26]、保密排序[27–29]、保密計算最值[30]等問題.

保密求最值(最大值、最小值)在保密科學計算中是非常重要的問題,在統(tǒng)計學中也有重要的應用.保密求最值是指:多個參與者想要知道他們當中數(shù)據(jù)的最值(包括最小值和最大值),但是任何一方都不愿意讓其他人獲知自己的隱私數(shù)據(jù).該問題具有很多應用場景,并且也有重要的應用價值.

場景一:有多個國家想知道他們當中導彈數(shù)量的最大值、最小值,但是任何一個國家必然不會直接將自己國家導彈的數(shù)量公布于眾,要解決這個問題,其數(shù)學模型就是多方保密計算最值.

場景二:要統(tǒng)計某一群體當中擁有的最多財富與最少財富,從而獲知該群體的貧富差異,但是群體中每個人用的財富多少是隱私,一般不會輕易告訴他人,因此,該問題也要歸結(jié)為多方保密求最值問題.

上述場景一屬于保密軍事問題,場景二屬于保密的民生統(tǒng)計問題,實際中更多類似的場景都可歸結(jié)為此類問題,但目前關(guān)于此類問題的研究不是很多,效率不是很理想,影響實際應用.此外,由于已有的關(guān)于保密求最值是通過參與者之間進行交互完成的傳統(tǒng)模式方案,用戶(參與者)的計算成本較高,不利于實際執(zhí)行.本文首次將保密求最值問題放在了云計算平臺下實現(xiàn)的,也是首次給出了可抗量子攻擊的多方保密求最值的解決方案.

1.1 相關(guān)工作

早在1982年,Yao[1]率先提出安全多方計算,并給出了安全多方計算的通用方案—姚氏混淆電路,由于計算復雜度是輸入數(shù)據(jù)規(guī)模的指數(shù)級別,顯然不切合實際.隨后,Goldreich 等人[31,32]也給出了安全多方計算的通用解決方案,然而從方案的計算效率方面考慮,他們指出該方案針對具體的安全多方計算問題是不實際的,但是,Goldreich 等人引入了安全多方計算的安全性定義和證明的模擬范例,并證明了在半誠實參與者條件下一般的安全多方計算問題是可解,也證明了存在部分惡意參與者的情況下的安全多方計算問題同樣也是可解的,認為研究具體安全多方計算問題是有必要的,這不僅激勵了研究者的研究興趣,還為后續(xù)針對具體問題的研究打開了理論局面.Goldreich 等人推動了安全多方計算研究的發(fā)展.

對于安全多方計算最大值、最小值問題,到目前為止已有的研究方案不多,2017年竇家維等人[30]首次給出了安全多方計算最小值的解決方案,方案是基于編碼、ElGamal 同態(tài)加密算法,并結(jié)合秘密共享以及門限密碼體制設計的,緊接著,以多方保密計算最小值協(xié)議為基礎,經(jīng)過改造可以多方保密計算最大值.在該方案中,協(xié)議1 不可抵抗含擁有私鑰參與方的合謀攻擊;協(xié)議2 是基于編碼、ElGamal 同態(tài)加密和秘密分割等方法設計的,由于采用了密文分割技術(shù),并要通過不經(jīng)意傳輸進行實現(xiàn),協(xié)議的通信復雜度和計算復雜度驟增;竇等人緊接著巧妙采用ElGamal 門限密碼體制設計了協(xié)議3,較協(xié)議1 和協(xié)議2 其安全性提高了,但是由于所有的協(xié)議都是通過參與者之間進行交互完成計算的,而且協(xié)議是多個參與者交互完成,計算能力僅僅依靠參與者自身,而在解決復雜問題時參與者自身計算能力往往是有限的,同時效率也較低.云計算具有強大的計算能力和存儲能力,正好可以用來解決參與者計算能力有限、效率低等問題,從而盡可能為參與者降低計算成本.

竇等人的方案雖然是首次解決了最小值以及最大值問題,然而該方案中的所有協(xié)議都是基于離散對數(shù)數(shù)學難題的加密技術(shù),一旦量子計算機得到應用,那么基于數(shù)論假設的離散對數(shù)等數(shù)學難題將在多項式時間內(nèi)是可解的,從而基于數(shù)論難題假設的同態(tài)加密算法構(gòu)造的協(xié)議將會是不安全的.1996年,Hoffstein 等人[33]提出NTRU(number theory research unit)算法,是一種基于多項式環(huán)的公鑰密碼體制,其安全性基本是與求解最壞情況格上困難問題等同的,因此被認為可以抵抗量子攻擊,該公鑰密碼體制具有公私鑰生成高效、易于并行計算等特點[34–36].

針對上述問題,本文采用0-1 編碼,將保密數(shù)據(jù)隱藏于對應編碼的數(shù)組中,接著采用多密鑰NTRU 全同態(tài)加密算法,將最大值、最小值問題架構(gòu)在云計算平臺上進行解決,設計相應的安全多方計算協(xié)議.然后,將協(xié)議簡單地應用于統(tǒng)計學中,解決了多方保密計算極差的問題,協(xié)議簡潔高效且安全.

1.2 本文貢獻

本文是首次將多方保密計算最值問題架構(gòu)在云計算平臺下進行解決,具體的貢獻如下:

(1)將保密數(shù)據(jù)通過0-1 編碼,從而把數(shù)據(jù)隱藏在所編碼的0-1 數(shù)組中,再結(jié)合多密鑰NTRU 全同態(tài)加密算法,提出了一種解決保密計算最大值、最小值的問題的新方案,并證明了方案的安全性,然后應用新方案設計了多方保密計算極差的協(xié)議.

(2)首次提出將多方保密求最大值、最小值問題架構(gòu)在云計算平臺下的解決方案,由于采用云外包技術(shù),為用戶節(jié)省了很大的計算成本,因而效率較高.

(3)本文在云計算平臺下設計的協(xié)議,由于采用多密鑰NTRU 加密算法,不僅完全抵抗任意數(shù)量的合謀攻擊,而且還可以抵抗量子攻擊.

2 預備知識

2.1 安全多方計算的安全性定義

(1)理想模型

所謂理想模型,就是存在一個可相信第三方(trusted third party,TTP),他不會欺騙任何參與方,也不會向任何一個參與方透漏其他參與方的任何信息.假設現(xiàn)在有N(N2)個參與方P1,P2,···,PN,借助TTP 完成一項計算,只需要N個參與方將自己的保密數(shù)據(jù)x1,x2,···,xN告訴TTP,TTP 計算f(x1,x2,···,xN),只將計算結(jié)果分別告訴參與方.由于N個參與方僅僅知道f(x1,x2,···,xN),而不知道其他任何額外的消息,因此這樣的一個安全多方計算協(xié)議是最安全的(稱為理想?yún)f(xié)議),實際中任何保密計算協(xié)議的安全性都不會超過理想?yún)f(xié)議的安全性.

由于實際的安全多方計算是沒有TTP 的,因此在現(xiàn)實中設計的安全多方計算協(xié)議如果泄露的信息不比在理想模型下多,那么就被認為是安全的.

(2)半誠實參與者

安全多方計算協(xié)議的執(zhí)行環(huán)境有兩種,即半誠實參與者模型和惡意參與者模型[31,32],半誠實參與者是指在執(zhí)行協(xié)議過程中,會忠實地嚴格遵守協(xié)議本身的步驟,但是這些參與者也會保留協(xié)議執(zhí)行過程中的各種計算結(jié)果,企圖通過這些中間結(jié)果推導出其他參與方的輸入數(shù)據(jù)信息.

本文涉及的參與者和云服務器都是半誠實的,因此本文設計的協(xié)議都是在半誠實模型下執(zhí)行的,而對于惡意模型下的協(xié)議,可使用Goldreich 等人[31,32]提出的通用轉(zhuǎn)化方法直接由半誠實協(xié)議轉(zhuǎn)化得出,要研究惡意模型下的協(xié)議,往往是先研究半誠實模型下的協(xié)議,再研究惡意敵手如何攻擊這種協(xié)議,找到避免惡意攻擊的方法,將其添加到協(xié)議中,從而就形成惡意模型下的協(xié)議,因此研究半誠實模型下的協(xié)議有著重要意義.所以我們在本文中只給出半誠實模型下的協(xié)議,同時也給出在半誠實模型下對應的安全性模擬范例.

(3)云計算環(huán)境下多方計算的安全性定義

鑒于本文的協(xié)議都是在云計算平臺下設計的,計算過程有不全可信第三方(云服務器)的參與,且參與方數(shù)量多于2,和傳統(tǒng)模式的安全兩方計算的安全性定義有所不同,因此我們在這里給出在云計算平臺下的安全性定義.

設N個參與方P1,P2,···,PN分別擁有保密數(shù)據(jù)x1,x2,···,xN,Cloud Sever(CS)是云服務器,f(x1,x2,···,xN)為概率多項式函數(shù),π是計算f的協(xié)議.這N+1 方須在不泄露xi(i∈[N])的情況下,合作計算f(x1,x2,···,xN)=(f1(x1,x2,···,xN),···,fN(x1,x2,···,xN)).目的是為使每一位參與方Pi(i∈[N])分別得到fi(x1,x2,···,xN,在整個過程中,不論合謀與否都要必須確保任何一方都無法獲取其他方的保密輸入數(shù)據(jù)xi.

將每一位參與方Pi(i∈[N])在執(zhí)行協(xié)議π的時候得到的視圖記為viewi(x1,x2,···,xN),CS 的視圖記為view0(x1,x2,···,xN).在這個系統(tǒng)中存在兩類合謀,一類是參與方Pi(i∈[N])中若干方合謀,但至多僅有N?1 方合謀;另一類是CS 與部分參與者Pi合謀,最壞情況下,CS 至多和任意N?1個參與者合謀想要獲得剩下一方的保密數(shù)據(jù).將第一類合謀情況下的視圖記為viewI(x1,x2,···,xN)(其中,I?[N],且2|I|N?1).Pi將第二類合謀情況下的視圖記為viewI′(x1,x2,···,xN)(其中,CS∈I′?[N]∪{CS},且2|I′|N).Pi發(fā)送給CS 的數(shù)據(jù)分別為E(xi),CS 的計算結(jié)果為E(x1,x2,···,xN)(即CS 獲得的輸出).

定義1在云計算環(huán)境下,我們說協(xié)議π保密計算了f(x1,x2,···,xN),如果存在多項式時間的算法(模擬器)Si、S0、SI、SI′使得表1 中所有式子同時成立.

表1 云計算環(huán)境下多方計算的安全性Table 1 Security definition of multiparty computation in cloud environment

2.2 多密鑰NTRU 全同態(tài)加密[37]

文獻[38]中提出了同態(tài)加密的概念,同態(tài)加密是指直接通過在密文上進行計算以達到明文某種運算的目的.同態(tài)加密經(jīng)歷了半同態(tài)到全同態(tài)的發(fā)展,半同態(tài)是指在密文上僅能進行某一種操作(即加法或者乘法),以達到明文的運算的目的,而全同態(tài)可進行兩種運算操作(加法和乘法),本文的協(xié)議利用了全同態(tài)加密,下面給出NTRU 全同態(tài)加密方案.

(1)多密鑰NTRU 全同態(tài)加密方案

KeyGen.:給定安全參數(shù)κ,產(chǎn)生(pki,ski,ek)(i∈[t]),其中pki和ski分別是每個用戶的公、私鑰,ek 是公開的求值密鑰.公、私鑰的具體構(gòu)造如下:

給定安全參數(shù)κ,B有界的誤差分布χ=χ(κ)和n次多項式?(x)=?κ(x)，且χ=χ(κ)是在多項式環(huán)R=Z[x]/?(x)上的分布,給出一個有界的多項式f′,g∈χ,并且設f=2f′+1,顯然有f≡1(mod2)成立,令h=2gf′為公鑰,f為私鑰(如果在環(huán)R中f的逆不存在,須重新取f′).

Enc.:給定公鑰pki和消息mi,產(chǎn)生密文ci=(pki,mi)(i∈[t]).

任取有界多項式si,ei∈χ,mi∈M={0,1}(明文消息mi編碼成多項式,其系數(shù)為0 或1).輸出密文ci=hiei+2ei+mi.

Dec.:給定t個用戶的私鑰ski和一個密文c??,布爾電路C,其中c??為多密鑰全同態(tài)操作所得密文,輸出相應的明文Dec(sk1,sk2,···,skt,c??)=C(m1,m2,···,mt).

計算u=c??f1·f2·ft∈R,以及u(mod2),輸出明文C(m1,m2,···,mt).這里要求u的系數(shù)在集合中.關(guān)于多密鑰NTRU 全同態(tài)加密方案各個算法的構(gòu)造以及安全性分析和全同態(tài)性詳見文獻[37]中3.2 節(jié)、3.3 節(jié)和3.4 節(jié)以及文獻[39].

Eval.:對于布爾電路C,輸出t個密文的同態(tài)運算操作結(jié)果為:

上述Eval.是一個全同態(tài)操作,計算t個密文的和或積,這個同態(tài)運算可以看成兩個新密文和的和或者積.其中看成是由t個密文中的一部分同態(tài)運算的結(jié)果,是剩下的一部分密文同態(tài)運算的結(jié)果,同時這兩個新密文分別對應一套公鑰,記為K1和K2.

(a)加法同態(tài):直接計算cadd=c??=+;

(b)乘法同態(tài):分為兩種情況,如果K1K2=?,則cmult==×否則,設K1K2={pki1,···,pkir},則用如下方法計算cmult.

對于全部τ∈{0,1,···,logq},取sτ,eτ∈χ,計算γτ=hsτ+2eτ+2τf,令ek=(γ0,···,γlogq)∈對于j∈[r](r為K1和K2交集的勢),定義的二進制表示,以及ekij=(γij,0,···,γij,logq),令迭代到最后有

總之,上述t個密文是由|K1K2| 個公鑰產(chǎn)生的,cadd和cmult的解密密鑰為K1K2對應的私鑰:這里fKi(i=1,2)表示Ki中所有公鑰對應的私鑰乘積.這與解密算法Dec.是一致的,即當有λ個公鑰產(chǎn)生的密文進行同態(tài)運算時,解密的私鑰為f1f2···fλ,與同一個公鑰下對應不同的密文參與同態(tài)的次數(shù)無關(guān).這里

(2)多密鑰NTRU 全同態(tài)加密算法的解密

為了清楚給出多個密文同態(tài)操作后的解密,我們給出N=2 時的解密過程.設c1和c2是兩組完全不同的公鑰h1和h2產(chǎn)生的密文:c1=h1s1+2e1+m1,c2=h2s1+2e2+m2,對應的私鑰分別為f1和f2,則用共同解密密鑰f1f2解密cadd=c1+c2和cmult=c1c2可簡化如下.

(a)加法同態(tài)的解密運算:

(b)乘法同態(tài)的解密運算:

對于N3 的情形,即多個密文的全同態(tài)操作后的解密運算和N=2 是類似的.

3 問題的描述與轉(zhuǎn)化

3.1 問題描述

設有N個參與方P1,P2,···,PN,分別持有一個保密數(shù)據(jù)x1,x2,···,xN,他們想計算這N個參與方的最大值、最小值,但每一位參與方都不想泄漏自己的私有數(shù)據(jù)信息.

3.2 問題轉(zhuǎn)化

在本文中,我們先讓每一位參與者Pi將自己的私有數(shù)據(jù)xi按照本文給出的0-1 編碼方法編碼一個0-1 數(shù)組,然后結(jié)合多密鑰NTRU 同態(tài)加密算法解決了本文提出的最值問題.

0-1 編碼:設x1,x2,···,xN∈{v1,v2,···,vm} =U,這里U是一個全序集,即滿足v1

這樣,Pi的保密數(shù)據(jù)xi與編碼的數(shù)組Xi=(αi1,···,αim)是對應的,對N個數(shù)組X1,X2,···,XN作乘積,即將數(shù)組對應的元素相乘,得到新的數(shù)組Y=(y1,y2,···,ym),其中再將數(shù)組Y的所有元素相加,得到即:

由Xi的構(gòu)造式(1)以及計算k的表達式(2),易證明有下面命題成立.

命題1如果對于每一個xi(i∈[m]),按照式(1)構(gòu)造數(shù)組Xi,并以式(2)計算k,則

min{x1,x2,···,xN}=vk

為了更清楚地呈現(xiàn)命題1,我們給出一個實例.

例1設全序集U={1,3,5,7,9,11},P1,P2,P3分別擁有x1=3,x2=7,x3=9,遵循命題1 計算這三個數(shù)的最小值,具體見表2.

表2 命題1 的實例Table 2 Example of Proposition 1

根據(jù)命題1 可計算若干個數(shù)據(jù)中的最小值,若直接按照命題1 進行計算,顯然所有數(shù)據(jù)的隱私性沒有得到保護,因此,需要利用同態(tài)加密算法將每個數(shù)組進行加密,再保密計算k.這里對數(shù)組加密指的是對數(shù)組中每一個元素加密.

3.3 具體協(xié)議

協(xié)議1 云計算環(huán)境下多方保密計算最小值Input:P1,P2,···,PN 各自所持的秘密數(shù)據(jù)x1,x2,···,xN ∈{v1,v2···,vm} =U,其中v1

分析:(1)不合謀的情形,由于使用多密鑰同態(tài)加密算法,每個參與者各用自己產(chǎn)生的公鑰加密自己的私有數(shù)據(jù),無法獲得別人的私鑰,因此,任何人得不到其他參與者的秘密數(shù)據(jù).

(2)合謀的情形,本文方案中的合謀分為兩類,參與者之間的合謀和參與者與CS 的合謀.先討論前者的合謀,不失一般性,假設有N?1 個參與方P1,P2,···,PN?1合謀想要知道PN的秘密數(shù)據(jù)E(XN)=(E(αN1),···,E(αNm)),方案整個過程中,任何人無法獲得別人的私鑰,因此直接從加密PN的數(shù)組中無法獲得XN=(αN1,···,αNm),從而得不到xN;如果通過協(xié)議1 中步驟3–5 聯(lián)合解密得到N方的最小值vk=min{x1,x2···,xN} 小于N?1 方合謀的最小值vk′=min{x1,x2···,xN?1},即k

本文將上述協(xié)議1 所給的全序集合編碼方法稍作修改,就可以改造出多方保密計算最大值的協(xié)議,P1,P2,···,PN各自所持的秘密數(shù)據(jù)x1,x2,···,xN∈{v1,v2···,vm} =U,其中v1>v2>··· >vm,即要求全序集中元素從大到小排列,編碼修改如下:

為了更加直觀地呈現(xiàn)出解決多方計算最大值問題的轉(zhuǎn)化過程,也呈現(xiàn)出與協(xié)議1 的緊密關(guān)系,給出實例2 如表3 所示.

例2設全序集U={11,9,7,5,3,1},P1,P2,P3分別擁有x1=3,x2=7,x3=9,遵照式(3)的編碼,然后計算這三個數(shù)的最大值,具體見表3.

表3 最大值問題轉(zhuǎn)化實例Table 3 Transformation example of maximum problem

由于最大值問題與最小值問題的轉(zhuǎn)化過程是對稱的,因此,將問題架構(gòu)在云計算平臺下,結(jié)合多密鑰NTRU 全同態(tài)加密算法構(gòu)造相應協(xié)議如下.

協(xié)議2 云計算環(huán)境下多方保密計算最大值Input:P1,P2,···,PN 各自所持的秘密數(shù)據(jù)x1,x2,···,xN ∈{v1,v2···,vm} =U,其中v1 >v2 >··· >vm.Output:vk =max{x1,x2···,xN}1 每個參與方Pi(i ∈[N])通過式(3)將自己的保密數(shù)據(jù)xi 編碼成數(shù)組Xi.2 每個參與者Pi 執(zhí)行多密鑰NTRU 加密算法中密鑰生成系統(tǒng),產(chǎn)生公鑰pki =hi 和私鑰ski =fi.各自使用自己產(chǎn)生的公鑰加密已編碼的數(shù)組,得到:E(Xi)=(E(αi1),···,E(αim)).3 每個參與者Pi 將自己自加密的數(shù)組發(fā)送給CS,利用多密鑰NTRU 全同態(tài)計算E(k)=∑m j=1∏N i=1 E(αij),并將E(k)發(fā)送給任意一個參與者,不妨設為P1.4 P1 收到CS 發(fā)來的E(k),計算u1 =E(k)f1,P1 將u1 發(fā)送給P2.5 P2 收到u1,計算u2 =u1f2 =E(k)f1f2,直到PN 計算k =un =uN?1fN =E(k)f1f2···fN,此時vk =max{x1,x2···,xN}.6 PN 將最大值vk =max{x1,x2···,xN} 告訴其他參與方.

由于協(xié)議2 是在協(xié)議1 的基礎上構(gòu)建起來的,僅改變了協(xié)議1 中全序集元素的排列順序和相應的編碼方式,兩個協(xié)議是完全對稱的,根據(jù)協(xié)議1 后面的分析,所以協(xié)議2 的正確性是自明的.

3.4 安全性分析

定理1在半誠實模型下,協(xié)議1 是安全的.

證明:由于本文協(xié)議1 是架構(gòu)在云計算平臺的,因此要證明定理1,需要構(gòu)造模擬器Si、S0、SI、SI′使得表1 中所有式子都成立.為了節(jié)省篇幅,在這里給出不合謀情形中模擬器Si的構(gòu)造過程,以及合謀情形中模擬器的構(gòu)造過程,模擬器S0、SI的構(gòu)造過程省略.

(1)構(gòu)造模擬器Si.

在此協(xié)議中,fi(x1,x2,···,xN)=fj(x1,x2,···,xN)=vk或vk,其中ij.假設等號成立,構(gòu)造模擬器Si.Si接受xi,fi(x1,···,xi,···,xN)作為輸入,按如下方式進行:

(a)Si隨機取N?1 個數(shù)使得:fi(x1,···,xi,···,xN).并按照3.2 節(jié)編碼方法(1)對進行0-1 編碼,不失一般性,編碼如下:

(c)Si得到這些之后,計算

(d)按照協(xié)議1 的解密過程解密E(k?),得k?,從而得到最小值vk?.

于是有:

同理,用類似的方法可構(gòu)造模擬器S0使得:

(2)構(gòu)造模擬器SI′.

不失一般性,設N?1 個參與方P1,P2,···,PN?1與CS 合謀,想要得到PN的保密數(shù)據(jù)xN,此協(xié)議中,fi(x1,x2,···,xN)=fj(x1,x2,···,xN)=vk或vk,其中ij.假設等號成立,構(gòu)造模擬器SI′(I′={P1,P2,···,PN?1,CS}).P1,P2,···,PN?1的輸入和輸出為 {(x1}[N?1]和{fi(x1,x2,···,xN)}[N?1],CS 將得到{E((xi)}[N]作為輸入,輸出為將{(x1}I′,{E((Xi)}[N],{fi(x1,x2,···,xN)}I′作為輸入,按如下方式進行:

(a)模擬器SI′隨機取一個數(shù),使得1]).并按照3.2 節(jié)編碼方法(1)對x1,x2,···,xN?1,進行0-1 編碼,不失一般性,編碼如下:

(b)用(X1,···,XN?1,)進行模擬,按照協(xié)議1,將數(shù)組(X1,···,XN?1,)進行加密,得到(E(X1),···,E(XN?1),E()).

(c)SI′得到這些之后,計算

(d)按照協(xié)議的解密過程,解密E(k′),得到k′,從而得到vk′.

可得SI′({xi}I′,{fi(x1,x2,···,xN)}I′,E(x1,x2,···,xN))={{xi}[N?1],{E(xi)}[N],E(k′),k′,vk′},viewI′(x1,x2,···,xN)={{xi}[N?1],{E(xi)}[N],E(k),k,vk}.

由于vk′=fi(x1,x2,···,xN?1,)=fi(x1,x2,···,xN?1,xN)(i∈[N?1]),則vk=vk′,從而k=k′,E(k)(k′).所以:

SI′({xi}I′,{fi(x1,x2,···,xN)}I′,E(x1,x2,···,xN))viewI′(x1,x2,···,xN)

由上述證明過程可知,即使 CS 和P1,P2,···,PN?1合謀,也得不到PN的隱私數(shù)據(jù),因為viewI′(x1,x2,···,xN)只是由P1,P2,···,PN?1和CS 的輸入{xi}[N?1],{E(xi)}[N],E(k′),以及自身獲得的輸出{fi(x1,x2,···,xN)}[N?1],E(k)得到的,不含PN的任何消息.

同理,CS 不參與合謀,僅P1,P2,···,PN中若干方合謀,用構(gòu)造SI′類似的方法可以構(gòu)造模擬器SI使得:

SI({xi}I,{fi(x1,x2,···,xN)}I)c=viewI(x1,x2,···,xN)

協(xié)議2 與協(xié)議1 在轉(zhuǎn)化方法以及協(xié)議設計上是完全對稱的,采用類似證明定理1 的方法和過程即可證明協(xié)議2 是安全的,因此下面定理是成立的,本文省略其證明過程.

定理2在半誠實模型下,協(xié)議2 是安全的.

3.5 效率分析

(1)理論分析

由于文獻[30]中的協(xié)議是首次多方保密解決最值問題的方案,與本文的協(xié)議1 和協(xié)議2 有相似之處,都是采用編碼的轉(zhuǎn)化方式,同時都是結(jié)合同態(tài)加密算法設計的.因此本文將協(xié)議1 和協(xié)議2 與竇等人的協(xié)議進行比較.文獻[30]方案中基本運算是模乘運算,本文的基本運算是模乘與模加運算,而模加運算相對于模乘的運算成本是可忽略的.為了便于比較,不考慮各個方案中準備階段以及隨機數(shù)選取的計算開銷,因此我們以模乘次數(shù)作為衡量計算開銷的標準.文獻[30]中方案采用ElGamal 加密體制,模數(shù)為大素數(shù)p,模乘運算記為Mp;本文方案模取φ(x)=xn+1、q和2,模乘運算記為Mφ,p,2,且假設編碼的長度都統(tǒng)一為m,N表示參與方的數(shù)量,m表示全集的勢.

計算開銷:設參與者P1,P2,···,PN所持有保密數(shù)據(jù)分別為x1,x2,···,xN∈U,|U| =m.本文協(xié)議1(由于協(xié)議2 與協(xié)議1 完全對稱,這里僅分析協(xié)議1)中每一方Pi(i∈[N])需要m+1 次模乘運算,因此本文協(xié)議1 共需要N(m+1)Mφ,p,2次模乘運算;文獻[30]中協(xié)議1 參與者Pi(i∈[N])最多需要m次加密和2m次模乘運算以及需要y次解密,而ElGamal 加密算法每次加密需要2 logp次模乘運算,每次解密需要logp次模乘運算[16],因此文獻[30]中協(xié)議1 共需(2Nm+y)logp+2Nm(Mp)次模乘運算;文獻[30]中協(xié)議3 協(xié)商構(gòu)造公鑰過程中需要mlogp次模乘數(shù)運算,參與者Pi(i∈[N])最多需要m次加密,需要2Nmlogp次模乘運算,解密過程中需要(Nm+y)logp次模乘運算,則文獻[30]中協(xié)議3共需要(3Nm+m+y)logp(Mp)次模乘運算.由于文獻[30]中的協(xié)議2 在其協(xié)議1 的基礎之上下采用密文分割和不經(jīng)意傳輸技術(shù),效率低于其協(xié)議1 的效率,因此不對其協(xié)議2 進行效率分析.

通信開銷:衡量通信復雜度的指標有兩種,協(xié)議交換信息量的比特數(shù)和通信輪數(shù),在安全多方計算研究中,通常是采用通信輪數(shù)來進行衡量.本文協(xié)議1 加密后將密文發(fā)送給CS 需要N次通信,解密過程中需要N次通信,將解密結(jié)果告訴其他參與方需要N?1 次通信,因此本文協(xié)議1 共需要3N?1 次通信.在文獻[30]的協(xié)議1 中Pi(i∈[N?1])將加密后密文發(fā)送給PN需要N?1 次通信,PN解密后將結(jié)果告訴其他參與方也需要N?1 次通信,因此整個過程需要2(N?1)輪通信;在文獻[30]的協(xié)議3 中協(xié)商構(gòu)造公鑰和機密過程中各需要N?1 次通信,解密過程需要y(N?1)次通信,因此文獻[30]的協(xié)議3 共需要(y+2)(N?1)次通信,這里y表示最小值.

性能:以協(xié)議是否適合云計算平臺、能否抗量子攻擊、抗合謀情況作為衡量性能的指標,其中× 表示不具有此性能,?表示具有此性能,≮表示部分具有此性能.

綜合以上分析,本文協(xié)議與文獻[30]中協(xié)議1 和協(xié)議3 效率比較如表4 所示,性能比較如表5 所示.

表4 協(xié)議效率比較Table 4 Efficiency comparison among protocols

表5 協(xié)議性能比較Table 5 Performance comparison among protocols

根據(jù)表4,本文協(xié)議1 計算開銷最低,盡管通信開銷高于文獻[30]協(xié)議1,但是通過表5 看出文獻[30]協(xié)議1 只能部分抗合謀,而且既不適合云計算平臺,也不能抗量子攻擊.通過表4 和表5,與文獻[30]協(xié)議3 相比,除了可以完全抵抗合謀外,本文協(xié)議1 適合云計算平臺,可抗量子攻擊,顯然更優(yōu).

(2)仿真實驗

由表4 可以看出,文獻[30]中的協(xié)議1 比協(xié)議3 的效率高.因此,本文將文獻[30]中的協(xié)議1 與本文協(xié)議1 所采用的加密算法通過Java 編程語言實現(xiàn),比較耗時情況.本次實驗過程中,采用的計算機配置如下:操作系統(tǒng)為Windows 7 旗艦版,CPU 為AMD A6-3240M 1.5 GHz,內(nèi)存為4.00 GB.

文獻[30]中的協(xié)議采用ElGamal 加密算法,模為p,模乘運算記為Mp;本文協(xié)議采用NTRU 加密算法,模取φ(x)=xn+1、q和2,模乘運算記為Mφ,q,2,實驗過程中，取ElGamal 加密算法中參數(shù)p與NTRU 加密算法使用的域參數(shù)n(即φ(x)=xn+1 中的n)的位數(shù)相同,并且本實驗將NTRU 加密算法中模q固定為1024 bits.這里將p和n都分別取128 bits、256 bits、380 bits、512 bits,在這4 組參數(shù)下,分別計算一個模乘運算Mp和Mφ,q,2的平均耗時,每組參數(shù)下,每個模乘運算取7 個實驗結(jié)果,求每個模乘的平均耗時,得到表6,其中表6的第一列表示n(p)的位數(shù)(bit),第2–3 列分別表示在不同模數(shù)下一個模乘運算Mp和Mφ,q,2的平均耗時(ms).

根據(jù)表6,進一步計算出表4 中計算開銷所需要的logp(Mp)和Mφ,q,2的結(jié)果,并畫出logp(Mp)和Mφ,q,2隨模數(shù)變化趨勢圖,如圖1 所示.橫軸為不同的模數(shù)(bit),縱軸表示ElGamal 和NTRU 兩種加密體制在不同模數(shù)下分別對應logp(Mp)和Mφ,q,2平均耗時(ms).其中ElGamal 中為logp(Mp),NTRU中為Mφ,q,2.

通過圖1 可以看出,ElGamal 加密算法中的logp(Mp)的平均耗時比NTRU 加密算法中的Mφ,q,2的平均耗時多,即logp(Mp)>Mφ,q,2,且隨著模數(shù)線性增加.由理論分析所得表4 中的數(shù)據(jù),得到本文協(xié)議1 的耗時低于文獻[30]中協(xié)議1 的耗時,因此本文協(xié)議1 的效率高于文獻[30]中兩個協(xié)議.

表6 不同模數(shù)下的一個模乘的平均耗時Table 6 Average consuming-time of modular multiplication under different modulus

圖1 log p(Mp)(ElGamal)與Mφ,q,2(NTRU)的平均耗時對比Figure 1 Comparison of average consuming-time between log p(Mp)(ElGamal)and Mφ,q,2(NTRU)

4 最大值、最小協(xié)議在統(tǒng)計學上的簡單應用—多方保密計算極差

4.1 問題描述

極差是一個簡單而又常見的統(tǒng)計量,表示一組數(shù)據(jù)中最大值與最小值的差.而多方保密計算極差是指多個參與方P1,P2,···,PN分別持有一個數(shù)據(jù)x1,x2,···,xN,他們想要保密計算出所有數(shù)據(jù)的極差,但是不想讓任何人知道自己所持數(shù)據(jù)的任何信息.具有重要應用價值和前景,如:要統(tǒng)計某一群體當中貧富差距,從而獲知該群體的貧富差異,但是群體中每個人用的財富多少是隱私,一般不會輕易告訴他人,因而,此問題的數(shù)學模型就規(guī)約為多方保密計算極差.

4.2 問題的轉(zhuǎn)化

如果分別直接調(diào)用一次協(xié)議1 和協(xié)議2,就會分別計算出最大值與最小值,這樣不符合解決問題的需求.本文以協(xié)議1 為基礎,構(gòu)造多方保密計算極差協(xié)議.不妨設x1,x2,···,xN∈{1,2,···,m},這里x1,x2,···,xN<

利用與3.2 節(jié)類似的轉(zhuǎn)化方法計算

按照式(4)的編碼方法和式(5)轉(zhuǎn)化方法,容易得到下面命題2.

命題2如果對于每一個xi(i∈[N]),按照式(4)構(gòu)造數(shù)組Xi={βi1,βi2,···,βim},并以表達式(5)計算l,則max{x1,x2,···,xN}=m?l.

因此x1,x2,···,xN的極差為range=m?l ?k=m?(l+k),從而問題轉(zhuǎn)化為保密計算l+k.為了更加直觀,我們給出實例3.

例3設全序集U={1,2,3,4,5,6},P1,P2,P3分別擁有x1=2,x2=3,x3=5,根據(jù)上述轉(zhuǎn)化方案計算這三個數(shù)的極差,具體見表7.

表7 極差問題的轉(zhuǎn)化實例Table 7 Transformation example of range problem

由于統(tǒng)計問題在實際應用中樣本可能比較龐大,因此多方保密計算極差問題仍然架構(gòu)在云計算平臺上進行解決,下面給出具體協(xié)議.

4.3 具體協(xié)議

協(xié)議3 云計算下多方保密計算極差Input: P1,P2,···,PN 各自所持的秘密數(shù)據(jù)x1,x2,···,xN ∈{1,2,···,m},這里x1,x2,···,xN

協(xié)議3 整個過程中每位參與者需要2m次加密和m次解密,總共需要3Nm次模乘運算,需要進行3N?1 輪通信.由于協(xié)議3 在協(xié)議1 的基礎之上進行改造的,而且使用的加密算法具有語義安全性,因此利用證明定理1 的類似方法即可證明下面的推論,這里不再具體進行證明.

推論在半誠實下,多方計算極差問題的協(xié)議3 是安全的.

5 總結(jié)與展望

保密科學計算中多方保密計算最值(最大值、最小值)問題是重要的安全多方計算問題,其解決方案具有重要理論價值和重要應用前景.然而,目前已存在的方案不多,而且方案效率不理想,不利于實際應用.因此,本文采用0-1 編碼的方法,結(jié)合多密鑰全同態(tài)加密算法,將最值問題架構(gòu)在云計算平臺之上進行解決,構(gòu)造相應協(xié)議,并利用模擬范例的方法證明了協(xié)議的安全性.同已有的解決方案比較,本文方案不僅取得了較高的效率,還適合云計算平臺,同時,本文方案采用了NTRU 加密算法,由于其安全性是與求解最壞情況格上困難問題是等同的,因此被認為可以抵抗量子攻擊,所以本文協(xié)議也可以抵抗量子攻擊,最后,將協(xié)議1 應用在統(tǒng)計學領域中,解決了多方保密計算極差問題.

本文方案都是在半誠實模型下構(gòu)造的,只能防止半誠實敵手攻擊,而實際應用中會遇到惡意敵手,盡管存在從半誠實協(xié)議到惡意模型協(xié)議的通用轉(zhuǎn)化方法,然而針對多方保密計算最值問題,如何設計惡意模型下相應協(xié)議,具體問題需要尋找各種可能的惡意攻擊方法,進而構(gòu)造惡意模型下相應的協(xié)議,這將是未來研究的工作之一.