保密社交意愿探測?

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

1(西安工程大學 計算機科學學院,陜西 西安 710048)

2(陜西師范大學 計算機科學學院,陜西 西安 710119)

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

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

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

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

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

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

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

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

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

事實上,由解密運算:

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

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

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

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

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

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

即可恢復出消息-a.

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

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

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

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

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

本文的主要貢獻如下:

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

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

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

1 預備知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 高階剩余類判定性問題

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

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

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

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

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

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

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

思想2.將計算開銷大的模指數(shù)運算rnmodn2委托給云服務器.

2.1 具體方案

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

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

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

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

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

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

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

2.2 正確性驗證

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

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

2.2.2 替換運算的正確性

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

又由二項式展開定理得:

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

2.2.3 解密正確性

因為

所以有:

2.3 安全性分析

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

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

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

?在Zn上隨機選取一個數(shù)r,并從{0,1}中均勻選取一個數(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)時,敵手使用的多項式時間算法記作A,下面利用算法A構(gòu)造一個算法B,用于解決DCR 問題.該算法的具體工作方式如下.

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 加密方案的效率分析

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

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

3.1 保密社交意愿應用背景描述及其形式化

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

Alice 擁有一個有K個頂點構(gòu)成的私有凸多邊形P,表示她現(xiàn)在利益最大的活動范圍.其中,該多邊形的邊是按逆時針方向標注的,如圖2 所示(以K=7 為例).

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

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

?協(xié)議結(jié)束時,Alice 只得到一個意愿探測的結(jié)果(一個布爾值),而Bob 的具體位置信息對于Alice 仍然是一個秘密.

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

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

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

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

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

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

?零向:3 個點構(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 點與線段的位置關(guān)系

假設(shè)點pi,pb,pi+1的坐標分別為,則3 點構(gòu)成的方向角∠pi,pb,pi+1的方向可以通過計算下列行列式來確立:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?對于Bob 位置信息的私密性

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

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

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

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

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

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

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

5 結(jié)束語

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