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

西安科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,西安 710054

1 引言

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

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

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

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

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

1.1 相關(guān)工作

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

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

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

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

1.2 本文貢獻(xiàn)

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

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

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

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

2 預(yù)備知識(shí)

2.1 安全多方計(jì)算的安全性定義

(1)理想模型

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

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

(2)半誠(chéng)實(shí)參與者

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

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

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

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

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

將每一位參與方Pi(i∈[N])在執(zhí)行協(xié)議π的時(shí)候得到的視圖記為viewi(x1,x2,···,xN),CS 的視圖記為view0(x1,x2,···,xN).在這個(gè)系統(tǒng)中存在兩類合謀,一類是參與方Pi(i∈[N])中若干方合謀,但至多僅有N?1 方合謀;另一類是CS 與部分參與者Pi合謀,最壞情況下,CS 至多和任意N?1個(gè)參與者合謀想要獲得剩下一方的保密數(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 的計(jì)算結(jié)果為E(x1,x2,···,xN)(即CS 獲得的輸出).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 問題描述

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

3.2 問題轉(zhuǎn)化

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

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

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

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

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

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

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

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

表2 命題1 的實(shí)例Table 2 Example of Proposition 1

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

3.3 具體協(xié)議

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

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

(2)合謀的情形,本文方案中的合謀分為兩類,參與者之間的合謀和參與者與CS 的合謀.先討論前者的合謀,不失一般性,假設(shè)有N?1 個(gè)參與方P1,P2,···,PN?1合謀想要知道PN的秘密數(shù)據(jù)E(XN)=(E(αN1),···,E(αNm)),方案整個(gè)過程中,任何人無法獲得別人的私鑰,因此直接從加密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 所給的全序集合編碼方法稍作修改,就可以改造出多方保密計(jì)算最大值的協(xié)議,P1,P2,···,PN各自所持的秘密數(shù)據(jù)x1,x2,···,xN∈{v1,v2···,vm} =U,其中v1>v2>··· >vm,即要求全序集中元素從大到小排列,編碼修改如下:

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

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

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

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

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

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

3.4 安全性分析

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

證明:由于本文協(xié)議1 是架構(gòu)在云計(jì)算平臺(tái)的,因此要證明定理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.假設(shè)等號(hào)成立,構(gòu)造模擬器Si.Si接受xi,fi(x1,···,xi,···,xN)作為輸入,按如下方式進(jìn)行:

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

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

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

于是有:

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

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

不失一般性,設(shè)N?1 個(gè)參與方P1,P2,···,PN?1與CS 合謀,想要得到PN的保密數(shù)據(jù)xN,此協(xié)議中,fi(x1,x2,···,xN)=fj(x1,x2,···,xN)=vk或vk,其中ij.假設(shè)等號(hào)成立,構(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′作為輸入,按如下方式進(jìn)行:

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

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

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

(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ù),因?yàn)関iewI′(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é)議設(shè)計(jì)上是完全對(duì)稱的,采用類似證明定理1 的方法和過程即可證明協(xié)議2 是安全的,因此下面定理是成立的,本文省略其證明過程.

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

3.5 效率分析

(1)理論分析

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

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

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

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

綜合以上分析,本文協(xié)議與文獻(xiàn)[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 計(jì)算開銷最低,盡管通信開銷高于文獻(xiàn)[30]協(xié)議1,但是通過表5 看出文獻(xiàn)[30]協(xié)議1 只能部分抗合謀,而且既不適合云計(jì)算平臺(tái),也不能抗量子攻擊.通過表4 和表5,與文獻(xiàn)[30]協(xié)議3 相比,除了可以完全抵抗合謀外,本文協(xié)議1 適合云計(jì)算平臺(tái),可抗量子攻擊,顯然更優(yōu).

(2)仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

4.1 問題描述

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

4.2 問題的轉(zhuǎn)化

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

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

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

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

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

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

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

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

4.3 具體協(xié)議

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

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

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

5 總結(jié)與展望

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

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