楊囡囡,宋 成

( 河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454003)

0 引 言

隨著移動(dòng)終端設(shè)備、通信技術(shù)、定位技術(shù)及地理信息系統(tǒng)的迅猛發(fā)展,用戶對(duì)位置服務(wù)(location based service,LBS)[1]的依賴性大幅增強(qiáng),如短距離導(dǎo)航[2]、滴滴打車、手機(jī)點(diǎn)菜等。但用戶在享受位置服務(wù)便利的同時(shí),用戶的個(gè)人興趣、行蹤軌跡等隱私信息也存在泄露的風(fēng)險(xiǎn)。若攻擊者獲取用戶位置信息,或許給用戶的人身安全造成威脅。隨著人們生活節(jié)奏的加快,在確保安全性的基礎(chǔ)上,用戶對(duì)位置實(shí)時(shí)性要求也越來(lái)越高。因此,位置隱私保護(hù)技術(shù)的安全和效率是當(dāng)前信息安全領(lǐng)域的熱點(diǎn)之一[3-4]。

近年來(lái),學(xué)者們針對(duì)位置隱私問(wèn)題展開(kāi)大量研究,并取得了一系列的成果。文獻(xiàn)[5]構(gòu)建一個(gè)包含位置隱私和細(xì)粒度訪問(wèn)控制的雙服務(wù)器體系架構(gòu),提出一種基于安全多方計(jì)算和同態(tài)加密機(jī)制的雙重位置加密協(xié)議和密文位置搜索協(xié)議,實(shí)現(xiàn)了安全精確的K近鄰檢索,但同態(tài)加密機(jī)制算法復(fù)雜,計(jì)算量較大。文獻(xiàn)[6]提出一種雙曲線查詢解析技術(shù),采用單向轉(zhuǎn)換加密,將用戶位置坐標(biāo)轉(zhuǎn)換成Hilbert序列,該方案在數(shù)據(jù)轉(zhuǎn)換過(guò)程需要額外的處理機(jī)制來(lái)保證較高準(zhǔn)確度,使得處理復(fù)雜度、計(jì)算量增加。文獻(xiàn)[7]在LBS端和用戶端使用屬性加密算法,實(shí)現(xiàn)位置查詢服務(wù)和反饋中零信息泄露,但通信和計(jì)算相對(duì)復(fù)雜。文獻(xiàn)[8]通過(guò)n元線性方程組的解實(shí)現(xiàn)匿名,若系數(shù)矩陣的秩小于n,則有無(wú)窮多解,將解和真實(shí)身份進(jìn)行哈希值作為假身份標(biāo)識(shí),當(dāng)有用戶加入或退出時(shí),對(duì)應(yīng)的數(shù)據(jù)表需要更新。文獻(xiàn)[9]利用模冪運(yùn)算實(shí)現(xiàn)匿名,但在整個(gè)過(guò)程中匿名認(rèn)證的空間復(fù)雜度高,效率較低。文獻(xiàn)[10]利用哈希實(shí)現(xiàn)匿名,但攻擊者可根據(jù)用戶與可信第三方的交互信息求解假名和身份標(biāo)識(shí)之間的對(duì)應(yīng)關(guān)系。文獻(xiàn)[11]使用具有標(biāo)志性的位置點(diǎn)代替真實(shí)用戶發(fā)起查詢,但查詢結(jié)果依賴于代替位置點(diǎn)信息,其服務(wù)質(zhì)量難以保證。文獻(xiàn)[12]在敏感路段進(jìn)行等級(jí)劃分,根據(jù)位置樹(shù)的高度分配相應(yīng)的隱私預(yù)算,添加Laplace噪聲,盡管數(shù)據(jù)可用性較高,但服務(wù)質(zhì)量有待提升。文獻(xiàn)[13]基于半可信第三方服務(wù)的隱私保護(hù)系統(tǒng)結(jié)構(gòu),在網(wǎng)格內(nèi)使用歷史查詢概率和位置偏移構(gòu)建k匿名集,雖然Stackelberg博弈優(yōu)化隱私保護(hù)水平,但系統(tǒng)整體運(yùn)行效率不高。文獻(xiàn)[14]使用服務(wù)相似地圖,將滿足用戶服務(wù)質(zhì)量的區(qū)域與真實(shí)用戶所在區(qū)域合并構(gòu)成匿名候選區(qū),在候選區(qū)域中使用位置熵構(gòu)建K-匿名集,并在K-匿名集中使用貪心策略選擇一個(gè)位置點(diǎn)代替真實(shí)用戶進(jìn)行服務(wù)請(qǐng)求,但用戶的位置隱私信息通過(guò)區(qū)域連續(xù)關(guān)聯(lián)性可被獲取。文獻(xiàn)[15]提出無(wú)可信第三方的K-匿名假位置技術(shù),使用語(yǔ)義差異、查詢概率以及位置的分散均勻程度構(gòu)造假位置集,避免攻擊者結(jié)合背景知識(shí)攻擊,但移動(dòng)用戶端計(jì)算開(kāi)銷大。文獻(xiàn)[16]考慮現(xiàn)在的隱私技術(shù)很少關(guān)注位置語(yǔ)義信息,結(jié)合k-匿名、l-語(yǔ)義多樣性、差分隱私等技術(shù)來(lái)保證匿名區(qū)域的隱私性。雖然半可信第三方可平衡計(jì)算開(kāi)銷,但需要合理分配隱私預(yù)算。

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

1.1 位置隱私保護(hù)系統(tǒng)架構(gòu)

位置隱私保護(hù)系統(tǒng)架構(gòu)如圖1所示,系統(tǒng)架構(gòu)由3部分組成：移動(dòng)用戶終端、可信匿名服務(wù)器和LBS服務(wù)器,各部分的功能如下。

圖1 位置隱私保護(hù)系統(tǒng)架構(gòu)Fig.1 Location privacy protection system architecture

1)移動(dòng)用戶終端。向可信匿名服務(wù)器發(fā)送匿名化請(qǐng)求,篩選出最優(yōu)的假位置集,向LBS服務(wù)器發(fā)送查詢請(qǐng)求并接收LBS服務(wù)器查詢結(jié)果。

2)可信匿名服務(wù)器。處理移動(dòng)用戶端發(fā)送的匿名化請(qǐng)求,并將注冊(cè)結(jié)果返回給用戶,公布系統(tǒng)參數(shù)。

3)LBS服務(wù)器。批量認(rèn)證用戶,處理移動(dòng)用戶終端發(fā)位置服務(wù)請(qǐng)求并將查詢結(jié)果返回給用戶。

1.2 位置熵

位置熵起源于香農(nóng)熵[17],是一種度量隱私保護(hù)方法,熵越大,真實(shí)用戶不被識(shí)別的可能性越大。假設(shè)在N×N個(gè)位置單元候選區(qū)域中有k個(gè)候選假位置構(gòu)成的匿名集合,oi為匿名集合第i個(gè)位置的查詢概率(i=1,2,…,k),則匿名集合中每個(gè)位置單元是真實(shí)用戶的概率為

(1)

在N×N個(gè)位置單元候選區(qū)域中有k個(gè)候選假位置構(gòu)成的匿名集合,匿名集合中某一位置單元的查詢概率為Oi,那么位置熵為

(2)

2 位置隱私保護(hù)方案

2.1 系統(tǒng)初始化階段

步驟1設(shè)Fp表示階為p的有限域,定義一個(gè)橢圓曲線E：y2=x3+ax+bmodp,其中a,b∈Fp,在E上選擇一個(gè)階為q,生成元為p的加法群Gp。

步驟4可信匿名服務(wù)器公開(kāi)系統(tǒng)參數(shù)(a,b,p,q,Gp,Ppub,P,H1,H2,H3),x作為系統(tǒng)私鑰保存。

2.2 注冊(cè)階段

步驟3用戶終端收到消息后,驗(yàn)證luP=PKu-Ppub是否成立,若成立則計(jì)算私鑰SKi=ni+li;否則,返回第1步重新請(qǐng)求。假身份、公鑰和私鑰分別為PIDi、PKi、SKi。

2.3 假位置生成與選取階段

步驟1以用戶所在的位置單元為中心向四周均勻擴(kuò)展成合適大小的矩形,其長(zhǎng)為a個(gè)網(wǎng)格,寬為b個(gè)網(wǎng)格,在所選矩形區(qū)域中均勻使用隨機(jī)點(diǎn)算法生成假位置li=(xi,yi),結(jié)合真實(shí)地圖背景信息判斷假位置是否合理,如果不合理,則重新生成。

步驟3判斷假位置集合L中的元素是否小于2k個(gè),若小于則返回第1步繼續(xù)生成;否則,執(zhí)行下一步。

步驟4根據(jù)(1)式計(jì)算位置集L中每個(gè)假位置的查詢概率Oi,然后從2k個(gè)假位置中選擇Oi較高的k-1個(gè)假位置構(gòu)成最終假位置集合Lend=(l1,l2,…,lk-1)。

步驟5用戶為真實(shí)位置和假位置集合Lend分配假身份標(biāo)識(shí)PIDi。

2.4 位置服務(wù)請(qǐng)求階段

3 方案分析

3.1 正確性分析

1)驗(yàn)證luP=PKu-Ppub。

PKu-Ppub=ruP-xP=(ru-x)P=luP

[(a2n2+SK2β2)P-?2]+…+

[(aknk+SKkβk)P-?k]=

[(a1n1+(n1+r1-x)β1)P-?1]+[(a2n2+

(n2+r2-x)β2)P-?2]+…+[(aknk+

(nk+rk-x)βk)P-?k]=

[(a1n1P+(n1P+r1P-xP)β1)-?1]+

[(a2n2P+(n2P+r2P-xP)β2)-?2]+…+

[(aknkP+(nkP+rkP-xP)βk)-?k]=

[(a1N1+(N1P+PK1-Ppub)β1)-?1]+

[(a2N2+(N2P+PK2-Ppub)β2)-?2]+…+

[(akNk+(NkP+PKk-Ppub)βk)-?k]=

[?1+(N1P+PK1-Ppub)β1-?1]+

[?2+(N2P+PK2-Ppub)β2-?2]+…+

[?k+(NkP+PKk-Ppub)βk-?k]=

(N1P+PK1-Ppub)β1+(N2P+PK2-Ppub)β2+…+

3)驗(yàn)證zuP-?u=F+(Nu+PKu-Ppub)βu

zuP-?u=(f+Bu)P-?u=

(f+(aunu+SKuβu))P-?u=

(f+(aunu+(nu+ru-x)βu))P-?u=

fP+(aunuP+(nuP+ruP-xP)βu)-?u=

F+(auNu+(Nu+PKu-Ppub)βu)-?u=

F+(?u+(Nu+PKu-Ppub)βu)-?u=

F+?u+(Nu+PKu-Ppub)βu-?u=

F+(Nu+PKu-Ppub)βu。

3.2 安全性分析

3.2.1 匿名性

匿名性的驗(yàn)證步驟如下。

步驟1攻擊者A發(fā)起詢問(wèn)獲取系統(tǒng)公開(kāi)參數(shù){a,b,p,q,Gp,Ppub,P,H1,H2,H3}和相關(guān)參數(shù)。

步驟2攻擊者A選取k個(gè)不同的信息m1,m2,…,mk。

步驟3用戶U選取隨機(jī)位u∈{1,2,…,k}(對(duì)攻擊者A保密),mu為用戶的真實(shí)查詢內(nèi)容。然后將m1,m2,…,mu,…,mk發(fā)送給LBS服務(wù)器。

步驟4LBS服務(wù)器對(duì)接收到的信息m1,m2,…,mk加密得到c1,c2,…,ck并發(fā)送給用戶U。

步驟5若用戶U收到密文c1,c2,…,ck與m1,m2,…,mk相對(duì)應(yīng),則將c1,c2,…,ck按照隨機(jī)順序發(fā)送給攻擊者A;否則,停止游戲。

攻擊者A贏得游戲的優(yōu)勢(shì)為：Adv(A)=|Pr(A)|,其中Pr(A)表示攻擊者A能夠解密獲得mu,即解密獲得用戶真實(shí)查詢結(jié)果的概率。

定理1如果攻擊者A能以可忽略的概率贏得該游戲,那么該方案滿足匿名性。

證明如果攻擊者A得到加密結(jié)果c1,c2,…,ck,其中cu=mu⊕H3(BuP+Du),攻擊者A嘗試以解密密文的方式獲取消息mu,需要在猜測(cè)正確u的基礎(chǔ)上,求解H3(BuP+Du),即需要知道系統(tǒng)秘鑰x以及參數(shù)nu、au、ru,則必須通過(guò)Ppub=xP、Nu=nuP、?u=auNu、PKu=ruP求解x、nu、au、ru,面臨求解橢圓曲線離散對(duì)數(shù)問(wèn)題。所以攻擊者A能夠解密用戶U的隱私信息mu的概率Adv(A)=|Pr(A)|可忽略不計(jì),即該方案滿足匿名性。

3.2.2 不可偽造性

定理2如果攻擊者A在多項(xiàng)式時(shí)間內(nèi)不能假冒可信匿名服務(wù)器偽造用戶注冊(cè)信息,那么該方案滿足不可偽造性。

證明如果攻擊者A可以在多項(xiàng)式時(shí)間內(nèi)以不可忽略的概率注冊(cè)與用戶U相同的注冊(cè)信息,即攻擊者A可以在多項(xiàng)式時(shí)間內(nèi)以不可忽略的概率計(jì)算出系統(tǒng)私鑰x和參數(shù)ru,使等式luP=PKu-Ppub成立。

挑戰(zhàn)者C運(yùn)行并生成系統(tǒng)參數(shù)(a,b,p,q,Gp,Ppub,P,H1,H2,H3),并向攻擊者A公布,其中Ppub=xP,x為系統(tǒng)私鑰,并對(duì)攻擊者A保密。

在偽造過(guò)程中由于攻擊者A不能獲取系統(tǒng)主密鑰x和隨機(jī)數(shù)ru,無(wú)法使等式luP=PKu-Ppub成立。若攻擊者嘗試通過(guò)等式Ppub=xP、PKu=ruP獲取系統(tǒng)主密鑰x和參數(shù)ru,則面臨求解橢圓曲線離散對(duì)數(shù)難題。因此,攻擊者A在多項(xiàng)式時(shí)間內(nèi)不能以不可忽略的概率解決橢圓曲線離散對(duì)數(shù)問(wèn)題,即該方案滿足不可偽造性。

3.2.3 抗假冒攻擊

定理3在求解橢圓曲線離散對(duì)數(shù)問(wèn)題是困難的情況下,如果攻擊者A在多項(xiàng)式時(shí)間內(nèi)不能冒充用戶發(fā)送正確的簽名,那么該方案抗假冒攻擊。

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

本方案從假位置生成效率和隱私保護(hù)程度兩方面對(duì)方案進(jìn)行仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)在1.60 GHz英特爾i5CPU、8 GB內(nèi)存的PC機(jī)和Matlab 2018b仿真軟件的環(huán)境下進(jìn)行。實(shí)驗(yàn)選取2.5 km×2.5 km的真實(shí)地理地圖,將地圖劃分成100個(gè)位置單元,實(shí)驗(yàn)中的主要影響參數(shù)為匿名度k。

3.3.1 效率分析

方案以生成時(shí)間作為假位置生成效率,匿名度與假位置集合生成的時(shí)間關(guān)系如圖2所示。圖2中,3種方案生成假位置的執(zhí)行時(shí)間都隨著k的增大而增大。在匿名度較小時(shí),文獻(xiàn)[15]與本方案所需時(shí)間相近,隨著匿名度的增大,語(yǔ)義差異、查詢概率相近及假位置的分布,導(dǎo)致文獻(xiàn)[15]假位置集生成時(shí)間增大。文獻(xiàn)[16]在選取假位置時(shí)使用k-匿名、l-多樣性、差分隱私來(lái)保證匿名區(qū)域的隱私性。根據(jù)l-語(yǔ)義多樣性在道路網(wǎng)上將各部分劃分成不同的區(qū)域,然后在用戶所在的區(qū)域結(jié)合差分隱私和k-匿名選出最優(yōu)的假位置集,使得文獻(xiàn)[16]方案運(yùn)行效率低。

圖2 匿名度與假位置集合生成的時(shí)間關(guān)系Fig.2 Relationship between anonymity and the generation time of false location set

本文方案在響應(yīng)請(qǐng)求服務(wù)時(shí)不僅效率有所提高,而且減少了信息交互次數(shù)。文獻(xiàn)[15-16]構(gòu)建K-匿名后,向LBS服務(wù)器發(fā)送k個(gè)連續(xù)的查詢請(qǐng)求,LBS在進(jìn)行查詢服務(wù)前需逐個(gè)認(rèn)證用戶,然后依次進(jìn)行查詢處理。而本方案在構(gòu)建k-匿名后,用戶將k個(gè)用戶簽名消息和查詢請(qǐng)求一次性發(fā)送給LBS,LBS收到服務(wù)請(qǐng)求后,通過(guò)批處理的方式一次性對(duì)k個(gè)用戶的匿名身份進(jìn)行認(rèn)證,然后處理k個(gè)用戶的服務(wù)請(qǐng)求,最后將k個(gè)服務(wù)請(qǐng)求結(jié)果一次性發(fā)送給用戶,從而提高認(rèn)證效率并且減少LBS與用戶之間的信息交互次數(shù)。

3.3.2 位置熵

位置熵是衡量假位置的重要因素。位置熵越大隱私保護(hù)程度越大。匿名度與位置熵關(guān)系如圖3所示。由圖3可知本文方案與文獻(xiàn)[15]、隨機(jī)方案的位置熵隨著匿名度的增大而增大。隨機(jī)方案對(duì)假位置的合理性考慮不充分,所以隱私保護(hù)效果一般。文獻(xiàn)[15]在選取假位置時(shí)充分考慮到語(yǔ)義多樣化、地理位置盡量分散使得假位置更加合理,但本方案的位置熵始終優(yōu)于文獻(xiàn)[15]。因此,隱私保護(hù)效果更好。

圖3 匿名度與位置熵關(guān)系Fig.3 Relationship between anonymity and position entropy

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

為了解決移動(dòng)用戶位置隱私泄露問(wèn)題,本文提出一個(gè)基于橢圓曲線密碼體制的k匿名批量認(rèn)證的位置隱私保護(hù)方案,采用批處理,減少信息交互次數(shù),提升了執(zhí)行效率;通過(guò)在匿名區(qū)域中結(jié)合隨機(jī)位置點(diǎn)生成算法和位置熵篩選最優(yōu)的k-1個(gè)假位置,增強(qiáng)用戶隱私保護(hù)度。安全性分析表明,本文方案滿足匿名性、不可偽造性、抗假冒攻擊等安全特性。仿真實(shí)驗(yàn)表明,本文方案在效率和隱私保護(hù)度方面具有一定的優(yōu)勢(shì)。