鞏林明 , 李順東 , 竇家維 , 王道順

1(西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710048)

2(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710119)

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

4(清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系,北京 100084)

近年來(lái),隨著基于位置的服務(wù)在移動(dòng)智能設(shè)備上的廣泛應(yīng)用,保密探測(cè)問(wèn)題已經(jīng)成為移動(dòng)、社交網(wǎng)絡(luò)中保護(hù)隱私的一個(gè)研究熱點(diǎn).保密近感探測(cè),是保密探測(cè)問(wèn)題的一個(gè)重要分支.保密近感探測(cè)問(wèn)題研究的是移動(dòng)網(wǎng)絡(luò)中任意兩個(gè)用戶如何協(xié)同計(jì)算出他們的實(shí)時(shí)位置是否彼此臨近而不泄漏各方的具體位置.時(shí)至今日,保密近感探測(cè)問(wèn)題已取得了一些可喜的成果[1-21],但這些成果中除了Mu 等人[1]取得的以外,其他協(xié)議[2-21]都是采用格柵分解技術(shù)(如果參與方在相同的格柵內(nèi),即同在一個(gè)預(yù)先設(shè)定大小的圓形區(qū)域內(nèi),則認(rèn)為參與各方毗鄰)實(shí)現(xiàn)保密近感探測(cè)的.然而,這種方法不滿足移動(dòng)或社交網(wǎng)絡(luò)用戶的個(gè)性化需求,如:Alice 正在頤和園度周末,她想知道她的業(yè)余劃船搭檔Bob 是否也在頤和園內(nèi),是否可以和Bob 一起參加公園里正在舉辦的雙人劃船比賽.采用格柵分解技術(shù)的近感探測(cè)只能探測(cè)到Bob 是否處在以Alice 為中心、預(yù)先設(shè)定半徑值的圓域內(nèi).2016 年,Mu 等人[1]綜合運(yùn)用安全多方計(jì)算、Paillier[22]和ElGamal[23]同態(tài)加密方案設(shè)計(jì)了一個(gè)保密探測(cè)區(qū)域?yàn)槿我馔苟噙呅蔚膮f(xié)議.該協(xié)議滿足了用戶個(gè)性化的需求(用戶不再預(yù)先設(shè)定保密探測(cè)區(qū)域閾值的大小,保密探測(cè)區(qū)域可以是任意的多邊形),非常方便用戶表示保密探測(cè)區(qū)域.

但文獻(xiàn)[1]的協(xié)議仍然存在以下兩個(gè)方面的不足.

(1)文獻(xiàn)[1]的協(xié)議除了用Paillier 加密系統(tǒng)保密計(jì)算符號(hào)外,還需要調(diào)用K(凸多邊形的頂點(diǎn)數(shù))次高計(jì)算復(fù)雜度的、由ElGamal 加密方案實(shí)現(xiàn)的保密比較大小運(yùn)算.

(2)文獻(xiàn)[1]的協(xié)議并未徹底解決保密近感探測(cè)問(wèn)題,只適用于解決用戶參與計(jì)算區(qū)域的臨近兩點(diǎn)坐標(biāo)分量差大于0 的情形,當(dāng)用戶參與計(jì)算區(qū)域的臨近兩點(diǎn)坐標(biāo)分量差值小于0 時(shí),該協(xié)議會(huì)輸出錯(cuò)誤的結(jié)果.原因是文獻(xiàn)[1]的協(xié)議用Paillier 加密方案直接加密負(fù)數(shù),并在加密負(fù)數(shù)的結(jié)果上實(shí)施同態(tài)運(yùn)算.

事實(shí)上,Paillier 加密方案不能直接用于加密負(fù)數(shù),加密負(fù)數(shù)以及在加密的負(fù)數(shù)上進(jìn)行同態(tài)操作需要做額外的比特密文同態(tài)運(yùn)算.關(guān)于Paillier 加密方案不能直接用于加密負(fù)數(shù),并在加密負(fù)數(shù)的結(jié)果上實(shí)施同態(tài)運(yùn)算方面的具體闡述如下.

命題1.Paillier 加密方案不能直接用于加密負(fù)數(shù).

設(shè)a∈Zn,,-a表示負(fù)數(shù),并假定Paillier 加密方案能夠直接加密一個(gè)負(fù)數(shù),則由其加密算法的正確性可知:由加密運(yùn)算生成的密文Enc(-a),經(jīng)過(guò)解密運(yùn)算Dec(Enc(-a)),一定能正確恢復(fù)出消息-a.

事實(shí)上,由解密運(yùn)算:

得到消息-a的概率很小,因?yàn)橐扔?a,則需1≡(1+λkan)modn2成立.即n|λka因?yàn)間cd(λ,n)=1,所以n|λka則必有n|ka.而為安全起見(jiàn),系統(tǒng)參數(shù)k是不會(huì)取κp或者κq的,所以只有當(dāng)a≡0 modn,解密算法才能正確恢復(fù)出消息-a.因此,Paillier 加密算法能夠加密負(fù)數(shù)的假設(shè)不成立.

同理,已知a∈Zn在Paillier 加密體制下的密文ca=garnmodn2a∈Zn無(wú)法直接通過(guò)同態(tài)計(jì)算得到c-ab=g-ab(r′)nmodn2a∈Zn,其中,b∈Zn.□

用Paillier 通過(guò)特殊處理可以實(shí)現(xiàn)對(duì)一個(gè)負(fù)數(shù)的加密,但難以實(shí)現(xiàn)對(duì)若干個(gè)正、負(fù)數(shù)對(duì)應(yīng)密文實(shí)施若干次同態(tài)運(yùn)算.目前所采用的特殊處理方法大致可以分為3 類.

(1)明文的符號(hào)由明文所處的區(qū)間隱式地確定,用這種方法能夠加密明文的范圍是.通常是將整型區(qū)間[0,n]劃分成兩個(gè)等長(zhǎng)的區(qū)間,并事先規(guī)定哪個(gè)區(qū)間內(nèi)的數(shù)代表負(fù)數(shù).例如,可以事先規(guī)定處在內(nèi)表示負(fù)數(shù),如果解密結(jié)果,則解密方需要在解密的基礎(chǔ)上執(zhí)行額外計(jì)算:m′=m-n.

(2)用加密加法逆元的方法實(shí)現(xiàn)對(duì)[-n,0]內(nèi)整數(shù)的加密:用-a表示負(fù)數(shù),則在Zn群上可將-a視為a的逆元n-a,進(jìn)而可以通過(guò)加密運(yùn)算生成的密文Enc(n-a),經(jīng)過(guò)解密運(yùn)算Dec(Enc(n-a)),一定能夠正確恢復(fù)出消息n-a.而后再做運(yùn)算(n-a)-n,可以得到-a.

(3)明文的符號(hào)由加密額外的比特信息標(biāo)識(shí),用此種方法能夠解決[-n,n]內(nèi)的問(wèn)題.通信雙方需要事先商定符號(hào)的數(shù)字標(biāo)識(shí),通常規(guī)定“0”代表“+”,“1”代表“-”.由運(yùn)算μ∈{0,1}計(jì)算出的密文(Enc(a),Enc(sμ)),通過(guò)解密運(yùn)算:

即可恢復(fù)出消息-a.

但是,上述加密負(fù)數(shù)的方法在需要對(duì)差商對(duì)應(yīng)的密文實(shí)施若干次同態(tài)運(yùn)算的環(huán)境下將變得異常復(fù)雜:一方面,多次同態(tài)運(yùn)算會(huì)導(dǎo)致明文運(yùn)算結(jié)果所處區(qū)間的變換,這會(huì)影響多方保密計(jì)算結(jié)果的準(zhǔn)確性;另一方面,在保密多方計(jì)算中,各參與方都不想泄露自己的、哪怕是1 比特的信息(在涉及坐標(biāo)運(yùn)算的保密計(jì)算中,坐標(biāo)符號(hào)的泄露有可能造成相對(duì)位置信息的泄露),又有哪個(gè)無(wú)私鑰的參與方愿意對(duì)外透露自己的符號(hào)信息呢?

由上述分析可得,現(xiàn)有的基于位置服務(wù)的保密探測(cè)方法絕大多數(shù)只能解決保密探測(cè)區(qū)域在預(yù)先設(shè)定半徑閾值的圓形內(nèi)的情形,這不能滿足用戶個(gè)性化的需求(用戶不再預(yù)先設(shè)定保密探測(cè)區(qū)域閾值的大小,保密探測(cè)區(qū)域可以是任意的多邊形).文獻(xiàn)[1]的協(xié)議提出了一種解決探測(cè)區(qū)域?yàn)槿我馔苟噙呅吻樾蔚暮芎玫姆椒?它雖然能夠滿足用戶個(gè)性化的需求(無(wú)需將探測(cè)區(qū)域設(shè)定為帶閾值的圓形區(qū)域),但是并未徹底解決保密探測(cè)計(jì)算中保密坐標(biāo)符號(hào)計(jì)算問(wèn)題.因此,對(duì)于涉及到保密計(jì)算(正、負(fù))符號(hào)的、利用同態(tài)加密實(shí)現(xiàn)的由多方協(xié)同參與的安全/保密幾何計(jì)算問(wèn)題以及基于位置服務(wù)的移動(dòng)、社交網(wǎng)絡(luò)隱私保護(hù)問(wèn)題則需要另辟新徑.

如今,社交網(wǎng)絡(luò)用戶又對(duì)保密地探測(cè)提出了新的個(gè)性化需求:保密社交意愿籌劃,即保密社交意愿探測(cè).保密社交意愿探測(cè)已經(jīng)成為基于位置服務(wù)的社交網(wǎng)絡(luò)用戶的一個(gè)新的個(gè)性化需求.我們將如下一類問(wèn)題稱為保密意愿探測(cè)問(wèn)題:擁有便攜智能設(shè)備的用戶間可以事先保密地探測(cè)他們的社交意愿——Alice 由她的便攜智能設(shè)備秘密地獲取Bob 是否處在自己愿意與Bob 約會(huì)(如果Bob 愿意赴約的話)的“理想?yún)^(qū)域內(nèi)”,Bob 由自己的便攜智能設(shè)備保密地表達(dá)自己是否愿意赴約的意愿,但雙方都不想泄露各自的位置信息(Alice 既不想泄露自己的位置,也不想泄露自己的“理想?yún)^(qū)域”;Bob 不想泄露自己的位置信息).

保密意愿探測(cè)可以視作保密近感探測(cè)協(xié)議[1]在移動(dòng)、社交網(wǎng)絡(luò)用戶個(gè)性化需求方面的深度拓展.雖然二者都是基于位置服務(wù)的移動(dòng)、社交網(wǎng)絡(luò)用戶隱私保護(hù)問(wèn)題,但它們有明顯的區(qū)別:保密近感探測(cè)問(wèn)題研究的是兩個(gè)用戶如何計(jì)算他們的實(shí)時(shí)位置是否在預(yù)先設(shè)定的距離閾值內(nèi)而不泄漏雙方各自的具體位置;保密意愿探測(cè)問(wèn)題研究的則是參與雙方如何計(jì)算出他們是否可以在某一區(qū)域內(nèi)共事而不泄漏具體的共事區(qū)域與雙方計(jì)劃共事的具體位置,即保密社交籌劃.

為了解決移動(dòng)、社交網(wǎng)絡(luò)用戶在社交籌劃方面隱私保護(hù)的個(gè)性化需求問(wèn)題,同時(shí)也為了解決基于同態(tài)加密方案與安全多方計(jì)算的保密近感探測(cè)(如文獻(xiàn)[1]的協(xié)議)中未能徹底解決的問(wèn)題(當(dāng)用戶參與計(jì)算區(qū)域的臨近兩點(diǎn)坐標(biāo)分量差值小于0 時(shí),文獻(xiàn)[1]的協(xié)議會(huì)輸出錯(cuò)誤的結(jié)果),本文首先提出了一個(gè)基于位置服務(wù)的移動(dòng)、社交網(wǎng)絡(luò)隱私保護(hù)問(wèn)題:保密社交意愿探測(cè).然后綜合采用安全多方幾何計(jì)算[24-26]、保密計(jì)算分?jǐn)?shù)(一種新的保密比較大小方法)、同態(tài)加密以及云外包計(jì)算等技術(shù)設(shè)計(jì)了一個(gè)高效的社交網(wǎng)絡(luò)保密意愿探測(cè)協(xié)議.

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

(1)構(gòu)造了一個(gè)由云輔助計(jì)算的新型同態(tài)加密方案,該方案在預(yù)處理階段由云服務(wù)器提前完成復(fù)雜的自模乘運(yùn)算加密階段的另一復(fù)雜運(yùn)算gmmodn2由等價(jià)的簡(jiǎn)單模乘運(yùn)算m?(g-1)modn2代替,因此只通過(guò)幾次簡(jiǎn)單的模乘運(yùn)算,就可以實(shí)現(xiàn)一次加密.

(2)提出了一種新的保密符號(hào)計(jì)算方法,并利用該方法和新構(gòu)造的基于云計(jì)算的同態(tài)加密方案,設(shè)計(jì)了一個(gè)新的保密意愿探測(cè)協(xié)議.該協(xié)議對(duì)于半誠(chéng)實(shí)參與者是安全的.

(3)提出了一種新的加密思想:由加密一方自主確定一次加密需要執(zhí)行多少次模乘運(yùn)算.

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

1.1 關(guān)于加密方案的安全性定義

定義1(不可區(qū)分安全游戲).“加密語(yǔ)義安全”通常利用一個(gè)(由敵手和加密系統(tǒng)產(chǎn)生者)兩方進(jìn)行的思維游戲進(jìn)行刻畫(huà).本文將引用文獻(xiàn)[27]中對(duì)于文獻(xiàn)[28]中關(guān)于公鑰加密方案的選擇明文攻擊不可區(qū)分性(indistinguishability under chosen-plaintext attack,簡(jiǎn)稱IND-CPA)游戲的翻譯表述(其中,E為任意一個(gè)公鑰加密方案,A為任意一個(gè)概率多項(xiàng)式時(shí)間的敵手,為A在攻擊E的不可區(qū)分游戲中的成功優(yōu)勢(shì)).

(1)輸入系統(tǒng)安全參數(shù)1k,生成密鑰對(duì)(Kpub,Kpri).

(2)A獲得公鑰Kpub,并且它能夠訪問(wèn)加密諭言機(jī)Enc(?),經(jīng)過(guò)一些加密問(wèn)詢后輸出兩個(gè)相同長(zhǎng)度的明文m0和m1.

(3)系統(tǒng)搭建者隨機(jī)選擇b∈{0,1},然后輸出一個(gè)挑戰(zhàn)密文c=Enc(mb).

(4)A繼續(xù)調(diào)用Enc(?),輸出一個(gè)比特位b′作為對(duì)b的猜測(cè)結(jié)果.

(5)若b′=b,則游戲輸出否則,輸出

如果存在一個(gè)可忽略的函數(shù)δ,滿足:

則方案E在選擇明文攻擊下具有不可區(qū)分安全性.

1.2 關(guān)于安全多方計(jì)算的安全性定義[27]

要證明一個(gè)安全多方計(jì)算協(xié)議的安全性,需要用到定義:理想保密計(jì)算協(xié)議、半誠(chéng)實(shí)參與者、協(xié)議π可被用于保密計(jì)算函數(shù)f(a,b).本文將引用文獻(xiàn)[27]中對(duì)于學(xué)者Goldreich 關(guān)于這3 個(gè)定義的翻譯描述.

定義2(理想保密計(jì)算協(xié)議)[27].假設(shè)TTP 是網(wǎng)絡(luò)中存在的一個(gè)絕對(duì)可信的第三方,作為協(xié)議的參與方,Alice與Bob 在TTP 協(xié)助下,可以按照如下方式協(xié)作完成一次安全計(jì)算:Alice 與Bob 各自將他們的秘密信息a和b分別秘密地發(fā)送給TTP,由TTP 獨(dú)立計(jì)算完函數(shù)f(a,b)后,再將計(jì)算出的函數(shù)值分別秘密地發(fā)送給Alice 和Bob.其中規(guī)定函數(shù)f滿足:已知a與b之一以及函數(shù)值f(a,b)時(shí),不能計(jì)算出a與b中的另一個(gè).顯然,網(wǎng)絡(luò)中這樣一個(gè)簡(jiǎn)單的協(xié)議是保密程度最高的安全兩方計(jì)算協(xié)議,除此之外,再也找不到一個(gè)用于計(jì)算f(a,b)的實(shí)際安全兩方計(jì)算協(xié)議在安全性上可以超越該協(xié)議.

定義3(半誠(chéng)實(shí)參與者)[27].不嚴(yán)格地說(shuō),作為某安全多方計(jì)算協(xié)議的半誠(chéng)實(shí)參與者,在其執(zhí)行協(xié)議的過(guò)程中絕對(duì)會(huì)按照協(xié)議規(guī)定,執(zhí)行安全計(jì)算協(xié)議的每一步,但其可能會(huì)在協(xié)議執(zhí)行過(guò)程中記錄所有中間結(jié)果,并試圖利用這些記錄數(shù)據(jù)去計(jì)算安全多方計(jì)算協(xié)議之外的有關(guān)其他參與者的隱私信息.

將計(jì)算概率多項(xiàng)式函數(shù)f=(f1,f2):{0,1}*×{0,1}*→{0,1}*×{0,1}*的協(xié)議記作π.給π輸入(a,b),在協(xié)議執(zhí)行過(guò)程中,Alice 和Bob 的視圖(view)分別記作其中,d∈{1,2},rd是Alice 或Bob 自己選擇的隨機(jī)數(shù),是Alice 或Bob 收到的第i個(gè)消息;將Alice 和Bob 協(xié)同執(zhí)行完協(xié)議得到的結(jié)果分別記作

定義4(協(xié)議π可被用于保密計(jì)算函數(shù)f(a,b))[27].Goldreich 如下定義一個(gè)安全兩方計(jì)算協(xié)議的安全性:如果存在概率多項(xiàng)式時(shí)間模擬算法S1與S2,使得

成立,則稱協(xié)議π可被用于保密計(jì)算函數(shù)f(a,b).其中,表示計(jì)算不可區(qū)分.

Goldreich 利用比特承諾和零知識(shí)證明理論設(shè)計(jì)了一個(gè)編譯器.向該編譯器輸入一個(gè)在半誠(chéng)實(shí)參模型下安全計(jì)算f的協(xié)議π時(shí),編譯器會(huì)自動(dòng)為我們編譯輸出一個(gè)安全協(xié)議π′,該協(xié)議在有惡意參與者參與協(xié)同計(jì)算情況下也能安全計(jì)算f.考慮到工程實(shí)際,本文規(guī)定本文構(gòu)造協(xié)議中的參與者皆為半誠(chéng)實(shí)類型.

1.3 Paillier同態(tài)加密方案[22]

Paillier 構(gòu)造的方案(如圖1 所示)可以利用密文的運(yùn)算在明文空間Zn上實(shí)現(xiàn)同態(tài)加運(yùn)算:E(x+y)=E(x)?E(y).該方案具有第1.1 節(jié)中定義1 定義的安全性:將等長(zhǎng)的兩個(gè)消息m0和m1加密,并將它們的密文分別記作C0與C1,對(duì)于任何實(shí)施選擇明文攻擊的敵手而言,計(jì)算上無(wú)法區(qū)分C0與C1,即

Fig.1 Paillier’s encryption scheme圖1 Paillier 加密方案

1.4 高階剩余類判定性問(wèn)題

定義5(高階剩余類判定性問(wèn)題).該問(wèn)題在文獻(xiàn)[11]中被稱作“decisional composite residuosity problem”,簡(jiǎn)稱為DCR).簡(jiǎn)單地講,如果給定兩個(gè)等長(zhǎng)大素?cái)?shù)的乘積n=pq(其中p與q保密)和一個(gè)與n互素的整數(shù)z,對(duì)于敵手而言,判定事件“是否存在一個(gè)y,滿足”成功的概率可以表述為一個(gè)忽略的函數(shù)[11].

文獻(xiàn)[27]從可證明安全的需求出發(fā),將其用形式化語(yǔ)言描述為如下形式:

設(shè)D是一種區(qū)分任意兩個(gè)分布的算法,以系統(tǒng)安全參數(shù)τ為自變量的函數(shù)AdvD(τ)表示敵手利用區(qū)分算法D能夠區(qū)分出Dran與DE的優(yōu)勢(shì)函數(shù).

DCR 一直是在現(xiàn)代密碼學(xué)中一個(gè)被公認(rèn)的難解問(wèn)題,關(guān)于DCR 難解性證明或闡述請(qǐng)參閱Paillier[22].所以,對(duì)于任意的敵手而言,利用任意多項(xiàng)式時(shí)間的概率算法D區(qū)分分布(n,R)的優(yōu)勢(shì)函數(shù)AdvD(τ)是一個(gè)可忽略的量,即存在一個(gè)關(guān)于安全參數(shù)τ的可忽略函數(shù)δ(τ),使得AdvD(τ)滿足:

2 帶云輔助計(jì)算的同態(tài)加密方案

對(duì)于Paillier 加密方案而言,主要的計(jì)算開(kāi)銷包括gmmodn2,rnmodn2和cλmodn2,其中,g=1+kn,.本節(jié)基于Paillier 加密方案和云外包計(jì)算,并采下述思想1 和思想2 設(shè)計(jì)了一個(gè)高效的同態(tài)加密方案.

思想1.在執(zhí)行加密算法的過(guò)程中,將運(yùn)算復(fù)雜度高的模指數(shù)運(yùn)算gmmodn2(或gλmodn2)用與之運(yùn)算結(jié)果等價(jià)的、運(yùn)算高效的模乘運(yùn)算1+m?(g-1)(modn2)(或1+λ?(g-1)(modn2))替代,從而實(shí)現(xiàn)快速而正確的加密.

思想2.將計(jì)算開(kāi)銷大的模指數(shù)運(yùn)算rnmodn2委托給云服務(wù)器.

2.1 具體方案

此同態(tài)加密系統(tǒng)由4 種隨機(jī)算法組成:云外包隨機(jī)數(shù)模指數(shù)運(yùn)算算法(COR)、密鑰生成算法(KGen)、加密算法(Enc)和解密算法(Dec),其中,云外包隨機(jī)數(shù)模指數(shù)運(yùn)算可以在預(yù)處理階段完成,也可以與密鑰生成算法并行執(zhí)行.在此,我們將該加密方案記作E=(COR,Kgen,Enc,Dec).

?KGen:產(chǎn)生長(zhǎng)度相等的兩個(gè)大素?cái)?shù)p,q,并計(jì)算二者的乘積(n=pq)與二者分別減1 后的最小公倍數(shù)(λ=lcm(p-1,q-1)),為加密方案輸出公鑰(Kpub=(n,1+kn),其中,與私鑰

?Enc:加密一方按照如下方式執(zhí)行加密計(jì)算:

(1)從云服務(wù)器上下載集合R.

(2)自由確定適量的自模乘運(yùn)算次數(shù)(θ),并從R上隨機(jī)選擇?(?＜＜n)個(gè)數(shù)(記作R1,R2,...,R?∈R),隨機(jī)選擇χ1,χ2,...,χ?∈{0,...,?},其中,2≤θ≤?(為了表述簡(jiǎn)單,在此約定文中此后的加密運(yùn)算將以兩個(gè)數(shù)為例:Ri,Rj∈R,i,j∈{0,…,?}).

(3)對(duì)于m＜n,計(jì)算其中,

?Dec:解密方執(zhí)行解密運(yùn)算:

2.2 正確性驗(yàn)證

(1)加密運(yùn)算中引入的隨機(jī)變量可以在解密運(yùn)算中被成功消除.

R雖然是公開(kāi)的,但都是加密者在加密運(yùn)算中隨機(jī)選擇的,因此,以為隨機(jī)種子,由隨機(jī)函數(shù)計(jì)算得到的Rx與計(jì)算(其中,是隨機(jī)選擇的)是等效的,因此,任何敵手由R計(jì)算Rx的困難性與破解Paillier加密方案的困難性是等價(jià)的.

2.2.2 替換運(yùn)算的正確性

定理1.1+m?(g-1)(modn2)的結(jié)果與模指數(shù)運(yùn)算gmmodn2的結(jié)果是等價(jià)的,即

又由二項(xiàng)式展開(kāi)定理得:

綜上可得:1+m?(g-1)(modn2)?gmmodn2.□

2.2.3 解密正確性

因?yàn)?/p>

所以有:

2.3 安全性分析

定理2.如果DCR 是難解問(wèn)題,則E=(COR,Kgen,Enc,Dec)具有第1.1 節(jié)中定義1 所定義的不可區(qū)分安全性.

證明:在此先回憶一下DCR 問(wèn)題挑戰(zhàn)者的工作方式.

?在安全時(shí)間1k內(nèi),通過(guò)執(zhí)行算法G(1k)算法產(chǎn)生兩個(gè)大素?cái)?shù)p和q,以及它們的乘積n.

?在Zn上隨機(jī)選取一個(gè)數(shù)r,并從{0,1}中均勻選取一個(gè)數(shù)f.

?若f為0,則將R置為rnmodn2;若f為1,則將R置成R.

設(shè)E=(COR,Kgen,Enc,Dec)是2.1 節(jié)中構(gòu)造的方案,將攻擊E=(COR,Kgen,Enc,Dec)時(shí),敵手使用的多項(xiàng)式時(shí)間算法記作A,下面利用算法A構(gòu)造一個(gè)算法B,用于解決DCR 問(wèn)題.該算法的具體工作方式如下.

(1)接收DCR 挑戰(zhàn)者發(fā)來(lái)的(n,(n,R));

(2)令pk=(n,1+kn);

(3)將1n和pk發(fā)送給A;

(4)接收A發(fā)來(lái)的消息m0和m1;

(5)均勻地選取d∈{0,1};

(7)用d′表示敵手A對(duì)d的猜測(cè)結(jié)果;

(8)輸出f′(如果d=d′,則置f′=0;如果d≠d′,則置f′=1).

因?yàn)樗惴˙只通過(guò)調(diào)用算法A實(shí)現(xiàn)且只調(diào)用了3 次,而作為構(gòu)成算法B的子算法A是在多項(xiàng)式時(shí)間內(nèi)可被完成的算法,所以通過(guò)3 次調(diào)用算法A而實(shí)現(xiàn)的算法B是一種在多項(xiàng)式時(shí)間內(nèi)可被完成的算法.因此,G(1k)也是一種在多項(xiàng)式時(shí)間內(nèi)完成的算法.于是,構(gòu)造算法B在DCR 安全游戲中獲勝的概率可以表示成貝葉斯公式形式:

當(dāng)f=0 時(shí),DCR 挑戰(zhàn)者置R=rnmodn2.這樣,由算法A構(gòu)造的算法B呈現(xiàn)給掌握算法A的敵手的視圖與掌握算法A的敵手在實(shí)際攻擊E=(COR,Kgen,Enc,Dec)的安全游戲中獲取的視圖相同.因此,掌握算法A的敵手在攻擊E=(COR,Kgen,Enc,Dec)的安全游戲中獲勝的概率等于d=d′在條件f=0 下的條件概率,即

當(dāng)f=1 時(shí),DCR 挑戰(zhàn)者將R置成R.因?yàn)槭蔷鶆蜻x取的,所以,執(zhí)行運(yùn)算后的結(jié)果在群Z/n2Z上是均勻分布的;又因?yàn)? 個(gè)隨機(jī)變量m0,m1,d相互獨(dú)立,因此,pk和C*沒(méi)有暴露關(guān)于d的任何消息,這意味著掌握算法A的敵手對(duì)于d的猜測(cè)結(jié)果d′與d相互獨(dú)立.若在{0,1}上隨機(jī)選取d,則d=0 或d=1的概率各為,故有:

成立.聯(lián)立公式(3)～公式(5),我們可以得到:

因此,算法B在DCR 安全游戲中獲勝的優(yōu)勢(shì)為

由第1.1 節(jié)中定義1 可知,在DCR 安全性游戲中,利用算法A構(gòu)造的算法B獲勝的優(yōu)勢(shì)是一個(gè)可忽略的量,所以是一個(gè)可忽略的值.這意味δ也是一個(gè)可忽略的量.所以利用算法A的敵手在攻擊方案E的IND-CPA 安全游戲中獲勝的優(yōu)勢(shì)是一個(gè)可忽略的量,即E=(COR,Kgen,Enc,Dec)具有IND-CPA 安全性.□

2.4 加密方案的效率分析

Table 1 Comparative analysis on the efficiency of encryption and decryption表1 加、解密效率對(duì)比分析

3 保密社交意愿探測(cè)協(xié)議

3.1 保密社交意愿應(yīng)用背景描述及其形式化

Alice(需求者)是保險(xiǎn)公司的職員,某天在某一個(gè)城市推銷保險(xiǎn)產(chǎn)品,她只想約談現(xiàn)在正好在某個(gè)區(qū)域內(nèi)的客戶(可能住在該區(qū)域,也可能正在該區(qū)域且有空閑時(shí)間),她與不想向不在該區(qū)域且不愿約談的用戶透露自己的活動(dòng)區(qū)域,例如她想約談客戶Bob,但Bob 只想讓Alice 知道他是否可被約談而不想透露自己的具體位置.Bob和Alice 怎樣做才能同時(shí)實(shí)現(xiàn)他們的各自的目的呢?然而,安全多方幾何計(jì)算為解決這種問(wèn)題提供了一種可行的方法.我們將Bob 和Alice 采用安全多方幾何計(jì)算思路實(shí)現(xiàn)保密測(cè)試社交意愿的問(wèn)題稱為保密社交意愿探測(cè)問(wèn)題,其形式化描述如下:

Alice 擁有一個(gè)有K個(gè)頂點(diǎn)構(gòu)成的私有凸多邊形P,表示她現(xiàn)在利益最大的活動(dòng)范圍.其中,該多邊形的邊是按逆時(shí)針?lè)较驑?biāo)注的,如圖2 所示(以K=7 為例).

Fig.2 Abstract geometrical figure of private social-willing testing圖2 保密社交意愿探測(cè)幾何抽象圖

Bob 擁有一個(gè)私有點(diǎn)pb=(bx,by),表示他現(xiàn)在所處的位置.Alice 想知道Bob 是否處在自己的想活動(dòng)的范圍內(nèi),Bob 不想透露自己的具體位置.我們?cè)O(shè)計(jì)一個(gè)這樣的安全多方計(jì)算協(xié)議要實(shí)現(xiàn)對(duì)Alice 與Bob 的隱私保護(hù).

?協(xié)議結(jié)束時(shí),Alice 只得到一個(gè)意愿探測(cè)的結(jié)果(一個(gè)布爾值),而B(niǎo)ob 的具體位置信息對(duì)于Alice 仍然是一個(gè)秘密.

?協(xié)議結(jié)束時(shí),最多只得到Alice 多邊形的邊數(shù)K-1(Bob 沒(méi)有得到意愿探測(cè)的結(jié)果),而Alice 的活動(dòng)區(qū)域的形狀、位置與活動(dòng)區(qū)域的大小對(duì)于Bob 仍然是一個(gè)秘密.

3.2 保密社交意愿探測(cè)協(xié)議

3.2.1 判定凸多邊形與一個(gè)點(diǎn)位置關(guān)系

非保密的近感探測(cè)問(wèn)題實(shí)際上就是判定某個(gè)凸多邊形P(有K個(gè)頂點(diǎn))是否包含一個(gè)點(diǎn)pb=(bx,by)的問(wèn)題.可以通過(guò)K次計(jì)算有向線段與點(diǎn)pb=(bx,by)的位置關(guān)系來(lái)實(shí)現(xiàn)[24-26,29].對(duì)于點(diǎn)pi,pb,pi+1構(gòu)成的有序元組〈pi,pb,pi+1〉在平面上可能對(duì)應(yīng)著3 種位置關(guān)系(如圖3 所示).

?正向:3 個(gè)點(diǎn)構(gòu)成的方向角∠pi,pb,pi+1為逆時(shí)針走向(如圖3(a)所示).

?反向:3 個(gè)點(diǎn)構(gòu)成的方向角∠pi,pb,pi+1為順時(shí)針走向(如圖3(b)所示).

?零向:3 個(gè)點(diǎn)構(gòu)成的方向角∠pi,pb,pi+1=180°,即pi,pb,pi+1共線(如圖3(c)所示).

Fig.3 Position relations between a point and a line segment圖3 點(diǎn)與線段的位置關(guān)系

假設(shè)點(diǎn)pi,pb,pi+1的坐標(biāo)分別為,則3 點(diǎn)構(gòu)成的方向角∠pi,pb,pi+1的方向可以通過(guò)計(jì)算下列行列式來(lái)確立:

其中,Di＞0,Di＜0,Di=0 分別對(duì)應(yīng)著圖3(a)～圖3(c).

因此,下面的算法可以正確計(jì)算出近感探測(cè)的結(jié)果.

凸多邊形與點(diǎn)的關(guān)系判定算法.

輸入:由K個(gè)按逆時(shí)針順序訪問(wèn)的頂點(diǎn)構(gòu)成的凸多邊形P,點(diǎn)pb.

輸出:“1”,如果pb在P內(nèi);“0”,否則pb不在P內(nèi).

(1)對(duì)于i∈{1,2,…,K-1}計(jì)算點(diǎn)pb與有向線段兩個(gè)端點(diǎn)所構(gòu)成的方向角∠pi,pb,pi+1的方向Di.

(2)如果對(duì)于?i∈{1,2,…,K-1}都有Di≤0,則返回“1”;否則,返回“0”.

3.2.2 保密社交意愿探測(cè)協(xié)議

利用上述凸多邊形與點(diǎn)的位置關(guān)系判定方法、第2.1 節(jié)中設(shè)計(jì)的帶云輔助計(jì)算的同態(tài)加密方案以及一種新的保密符號(hào)計(jì)算方法,設(shè)計(jì)了一個(gè)保密社交意愿探測(cè)協(xié)議.

保密社交意愿探測(cè)協(xié)議.

輸入:Alice 輸入由K個(gè)按逆時(shí)針順序訪問(wèn)的頂點(diǎn)構(gòu)成的凸多邊形P,Bob 輸入點(diǎn)pb.

輸出:“1”,如果pb在P內(nèi);“0”,否則pb不在P內(nèi).

2.Alice 運(yùn)行加密系統(tǒng)E=(COR,Kgen,Enc,Dec)的密鑰生成算法Kgen,生成公鑰Kpub=(n,1+kn)和私鑰Kpri=λ;

3.Alice 首先從云服務(wù)器上下載集合R并隨機(jī)選取,然后按照如下方式操作:

(1)對(duì)于j∈{1,2,…,K-1}計(jì)算(假設(shè)Alice 將χ1,χ2取作χ1=χ2=1,并置?=2):

4.對(duì)于i∈{1,2,…,K-1},Bob 收到后,按照如下方式進(jìn)行:

(2)從云服務(wù)器上下載集合R后,隨機(jī)選擇個(gè)數(shù):,其中,?是一個(gè)比1 大一些的小整數(shù).并計(jì)算:

5.對(duì)于i∈{1,2,…,K-1},收到以后,Alice計(jì)算:

6.通過(guò)判斷θi與“1”的關(guān)系,確定Di的符號(hào):

其中,Sign(?)為符號(hào)函數(shù).

7.如果對(duì)于?i∈{1,2,…,K-1}都有Di≤0,則返回“D=1”;否則,返回“D=0”.

3.3 保密社交意愿探測(cè)協(xié)議保密性分析

定理3.保密社交意愿探測(cè)協(xié)議可以安全地實(shí)現(xiàn)Alice,Bob 兩方的社交意愿探測(cè).

證明:該協(xié)議安全與否的關(guān)鍵是協(xié)議執(zhí)行后有沒(méi)有造成參與者私有信息的泄露.接下來(lái),我們將證明保密意愿探測(cè)協(xié)議在安全計(jì)算約談意愿的過(guò)程中,Alice(持有凸多邊形的活動(dòng)區(qū)域P,由頂點(diǎn)構(gòu)成)、Bob(持有位置pb)兩方除了得到“是否約談”外,都無(wú)法獲得有關(guān)對(duì)方私有數(shù)據(jù)的其他任何信息,即協(xié)議未給Alice、Bob 兩方造成信息泄露.

?對(duì)于Alice 數(shù)據(jù)的安全性

我們首先構(gòu)造一個(gè)模擬保密探測(cè)協(xié)議執(zhí)行的模擬器SB.該模擬器的輸入為:Alice 隨機(jī)選擇一個(gè)凸的活動(dòng)區(qū)域,Bob 的私有位置pb,那么由模擬器SB產(chǎn)生的視圖為,其中,1≤i≤k;而保密社交意愿探測(cè)協(xié)議的實(shí)際執(zhí)行產(chǎn)生的視圖為,其中1≤i≤k.因?yàn)锳lice 傳輸給Bob 的信息是用自己的公鑰(n,n+1)對(duì)自己的私有信息加密后的密文,又因方案E已被證明在選擇明文攻擊下具有語(yǔ)義不可區(qū)分安全,所以由加密方案E產(chǎn)生的密文是語(yǔ)義不可區(qū)分的,可得是不可區(qū)分的.從而可得與真實(shí)視圖是不可區(qū)分的,也就是說(shuō),滿足定義關(guān)系式(2).

?對(duì)于Bob 位置信息的私密性

我們構(gòu)造一個(gè)Bob,輸入其私有位置信息以及由其隨機(jī)選擇的就能模擬Alice 視圖的模擬器SA.于是,由模擬器SA產(chǎn)生的視圖為

綜上所述,Alice 和Bob 的私密性滿足安全定義的形式化等式(1)和等式(2).所以,保密社交意愿探測(cè)協(xié)議可以安全地實(shí)現(xiàn)Alice、Bob 兩方社交意愿的探測(cè).□

4 保密社交意愿探測(cè)協(xié)議效率分析

不失一般性,我們假定Alice 和Bob 為文獻(xiàn)[1]的協(xié)議和本文協(xié)議的參與者,并假定Bob 的坐標(biāo)為(bx,by),Alice提供的意愿區(qū)域?yàn)镵個(gè)頂點(diǎn)構(gòu)成的凸多邊形.為了進(jìn)行公平比較,此處將執(zhí)行協(xié)議時(shí)花費(fèi)的總開(kāi)銷統(tǒng)一用一次自模乘運(yùn)算()作為統(tǒng)計(jì)的基本單位.

Alice和Bob 在執(zhí)行文獻(xiàn)[1]的協(xié)議時(shí),總共至少需要K(8n+bx+by+2λ)次自模乘運(yùn)算().因?yàn)榛谠仆獍?jì)算的同態(tài)加密方案E中的計(jì)算可以在預(yù)處理階段由云服務(wù)器完成,并且Alice 和Bob 在預(yù)處理階段可以隨時(shí)隨地地從云服務(wù)器下載集合,所以得到集合的時(shí)間可以忽略不計(jì);又因?yàn)锳lice 和Bob 在得到集合后,利用集合中的元素,通過(guò)執(zhí)行有限次的模乘運(yùn)算(),即可秘密地得到,不再需要做n次自模乘運(yùn)算().因此,基于同態(tài)加密方案E的保密社交意愿探測(cè)協(xié)議時(shí),Alice 和Bob 總計(jì)需要花費(fèi)K(18+2bx+2by+2kb+2(?+2)+2λ)次自模乘運(yùn)算().顯然,本文的協(xié)議比文獻(xiàn)[1]的協(xié)議在運(yùn)算效率上有了質(zhì)變性的提升.

基于同態(tài)加密方案E的保密社交意愿探測(cè)協(xié)議可以解決Alice 出具的K個(gè)頂點(diǎn)相鄰頂點(diǎn)坐標(biāo)差小于0 的情形;而對(duì)于文獻(xiàn)[1]的協(xié)議而言,當(dāng)Alice 出具的K個(gè)頂點(diǎn)相鄰頂點(diǎn)坐標(biāo)差小于0 時(shí),它無(wú)法正確運(yùn)行.此外,文獻(xiàn)[1]的協(xié)議只能用于解決實(shí)時(shí)位置的近感探測(cè)問(wèn)題,已經(jīng)不能滿足社交網(wǎng)絡(luò)用戶新的個(gè)性化需求;而本協(xié)議不僅可以用于徹底解決文獻(xiàn)[1]的協(xié)議提出的近感探測(cè)問(wèn)題,還能滿足社交網(wǎng)絡(luò)用戶日益增長(zhǎng)的個(gè)性化需求:保密社交籌劃,即保密社交意愿探測(cè),解決的是保密探測(cè)領(lǐng)域中的新問(wèn)題.下表是保密社交探測(cè)協(xié)議和協(xié)議在效率(用執(zhí)行協(xié)議時(shí)各參與方在加密和解密算法中花費(fèi)的計(jì)算開(kāi)銷總和體現(xiàn))、解決問(wèn)題的能力(從能否解決保密探測(cè)區(qū)域相鄰兩點(diǎn)坐標(biāo)差商小于0 的情形體現(xiàn))以及能夠解決的問(wèn)題這3 個(gè)方面的對(duì)比.保密探測(cè)協(xié)議與文獻(xiàn)[1]的協(xié)議的對(duì)比分析見(jiàn)表2.

Table 2 Comparative analysis on private social-willing test and the protocol of Ref.[1]表2 保密探測(cè)協(xié)議與文獻(xiàn)[1]的協(xié)議的對(duì)比分析

5 結(jié)束語(yǔ)

本文對(duì)保密意愿探測(cè)問(wèn)題進(jìn)行了研究.為了高效地解決這一問(wèn)題,首先設(shè)計(jì)了一個(gè)帶云輔助計(jì)算的同態(tài)加密方案;然后,利用該加密方案設(shè)計(jì)了一個(gè)高效的保密意愿探測(cè)協(xié)議.分析結(jié)果表明,此協(xié)議在效率和安全性方面都優(yōu)于先前的類似協(xié)議,并且其安全性是在標(biāo)準(zhǔn)的ideal/real 模型下實(shí)現(xiàn)的.