保密社交意愿探測?

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

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

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

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

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

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

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

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

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

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

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

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

事實上,由解密運算:

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

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

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

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

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

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

即可恢復出消息-a.

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

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

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

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

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

本文的主要貢獻如下:

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

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

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

1 預備知識

1.1 關于加密方案的安全性定義

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

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

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

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

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

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

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

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

1.2 關于安全多方計算的安全性定義[27]

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

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

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

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

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

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

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

1.3 Paillier同態加密方案[22]

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

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

1.4 高階剩余類判定性問題

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

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

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

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

2 帶云輔助計算的同態加密方案

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

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

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

2.1 具體方案

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

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

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

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

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

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

?Dec:解密方執行解密運算:

2.2 正確性驗證

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

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

2.2.2 替換運算的正確性

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

又由二項式展開定理得:

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

2.2.3 解密正確性

因為

所以有:

2.3 安全性分析

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

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

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

?在Zn上隨機選取一個數r,并從{0,1}中均勻選取一個數f.

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

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

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

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

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

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

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

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

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

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

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

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

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

因此,算法B在DCR 安全游戲中獲勝的優勢為

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

2.4 加密方案的效率分析

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

3 保密社交意愿探測協議

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

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

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

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

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

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

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

3.2 保密社交意愿探測協議

3.2.1 判定凸多邊形與一個點位置關系

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

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

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

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

Fig.3 Position relations between a point and a line segment圖3 點與線段的位置關系

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

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

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

凸多邊形與點的關系判定算法.

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

輸出:“1”,如果pb在P內;“0”,否則pb不在P內.

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

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

3.2.2 保密社交意愿探測協議

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

保密社交意愿探測協議.

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

輸出:“1”,如果pb在P內;“0”,否則pb不在P內.

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

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

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

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

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

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

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

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

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

3.3 保密社交意愿探測協議保密性分析

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

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

?對于Alice 數據的安全性

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

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

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

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

4 保密社交意愿探測協議效率分析

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

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

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

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

5 結束語

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