基于屬性基隱私信息檢索的位置隱私保護(hù)方法

杜剛， 張 張國(guó)印

(1.哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001； 2.佳木斯大學(xué) 信息電子技術(shù)學(xué)院,黑龍江 佳木斯 154007； 3.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

隨著基于位置服務(wù)(location based service， LBS)的廣泛應(yīng)用，越來(lái)越多的人們開始關(guān)注該服務(wù)中的隱私泄露問(wèn)題[1-2]。當(dāng)前較為普遍的隱私保護(hù)方法有泛化[3- 4]、模糊[5-6]、加密[7-8]以及空間變換[9]等，但上述方法都面臨同樣的問(wèn)題，即在LBS服務(wù)器提供服務(wù)的過(guò)程中不可避免地要獲知用戶的真實(shí)意圖，進(jìn)而可根據(jù)諸如興趣點(diǎn)類型、查詢種類等信息分析獲得用戶隱私。隱私信息檢索(private information retrieval, PIR)是應(yīng)對(duì)這種潛在隱私泄露的有效辦法[10-11]。該方法對(duì)LBS服務(wù)器中的數(shù)據(jù)加密，通過(guò)二進(jìn)制的可計(jì)算PIR和硬件PIR實(shí)現(xiàn)零信息泄露的結(jié)果檢索。Wightman等[12]根據(jù)這一觀點(diǎn)，基于經(jīng)緯度的地理差異，提出了基于地圖查詢的PIR。楊松濤等[13]基于該技術(shù)建立了基于位置服務(wù)的盲查詢方法。

但是，由于基于位置服務(wù)本身的特性，使得這種以索引為基礎(chǔ)的隱私信息檢索在執(zhí)行過(guò)程中需搜尋較大規(guī)模的數(shù)據(jù)條目，這增加了反饋結(jié)果的處理時(shí)間，影響了服務(wù)質(zhì)量[14]。Hu等[15]提出用分層索引提升索引效率。Yi等[16]則提出了模糊索引的概念。通常情況下，基于位置服務(wù)是一種針對(duì)用戶提交信息進(jìn)行反饋的服務(wù)，其反饋結(jié)果主要針對(duì)用戶屬性信息獲得的查詢結(jié)果[17-18]。因此，使用屬性作為索引進(jìn)行隱私信息檢索將會(huì)減少處理數(shù)據(jù)量，提高檢索效率，減少對(duì)服務(wù)質(zhì)量的影響?；谏鲜鲇^點(diǎn)，本文基于屬性基加密提出了一種可應(yīng)用于位置隱私保護(hù)的屬性基PIR方法，該方法在有效的保護(hù)用戶隱私信息的同時(shí)，能給提供比索引為基礎(chǔ)的隱私信息檢索方法更好的服務(wù)質(zhì)量。最后，通過(guò)安全性分析和比較實(shí)驗(yàn)，進(jìn)一步證明本文所提出的方法在隱私保護(hù)能力方面和算法執(zhí)行效率方面的優(yōu)越性。

1 隱私保護(hù)相關(guān)定義

1.1 系統(tǒng)架構(gòu)及攻擊假設(shè)

與傳統(tǒng)隱私保護(hù)方法不同，基于隱私信息檢索的位置隱私保護(hù)方法并不需要可信或非可信第三方，因此該方法采用如圖1所示的二層系統(tǒng)架構(gòu)。

圖1 二層系統(tǒng)架構(gòu)示意Fig.1 The system structure of two entities

從圖1中可以看出，該架構(gòu)中存在2個(gè)實(shí)體，即用戶和LBS服務(wù)器。用戶是指在固定位置或移動(dòng)過(guò)程中，通過(guò)自身設(shè)備向LBS服務(wù)器請(qǐng)求服務(wù)的使用者；而LBS服務(wù)器是在獲得用戶請(qǐng)求信息后向用戶提供服務(wù)結(jié)果的服務(wù)提供者。通常，LBS服務(wù)器由政府或大型企業(yè)提供因此是真實(shí)可信的，但所有信息均由該實(shí)體處理，使得該實(shí)體易成為攻擊焦點(diǎn)，且在巨大商業(yè)利益誘惑下存在泄露用戶隱私的可能。因此，本文假設(shè)該實(shí)體為半可信實(shí)體，既能夠提供位置服務(wù)，又可對(duì)用戶隱私信息進(jìn)行收集并分析，因此需將用戶信息隱藏防止LBS服務(wù)器獲得用戶隱私。

1.2 隱私保護(hù)需求

針對(duì)1.1中給出的以LBS服務(wù)器為潛在攻擊者的攻擊假設(shè)，若需保護(hù)用戶的隱私信息，在整個(gè)基于位置服務(wù)的過(guò)程中需降低對(duì)LBS服務(wù)器的信息公布量，同時(shí)還需要獲得所需要的查詢服務(wù)結(jié)果。因此，基于用戶屬性特點(diǎn)，有如下隱私保護(hù)和服務(wù)需求：

1) LBS服務(wù)器無(wú)法準(zhǔn)確識(shí)別由用戶查詢信息轉(zhuǎn)化的屬性信息；

2) LBS服務(wù)器能夠根據(jù)用戶提交的加密查詢信息反饋查詢結(jié)果；

3) 隱私處理以及服務(wù)獲取過(guò)程應(yīng)在用戶可接受時(shí)間范圍內(nèi)完成。

基于上述需求，本文設(shè)計(jì)并提出了隱私保護(hù)方法。

2 屬性基PIR方法及算法

2.1 屬性基PIR方法

通常，用戶請(qǐng)求基于位置服務(wù)反饋時(shí)需向LBS服務(wù)器提交查詢，該查詢一般為：距離我最近的飯店、當(dāng)前道路上的加油站或者到某酒店的最短路程等。這些信息可形式化為Q={(x,y),t,c}，其中(x,y)為用戶所在位置，t為提出查詢的時(shí)間，c為查詢的內(nèi)容。因此，上述信息可以用用戶屬性加以代替，即存在用戶屬性A={A1,A2,…,An}中的每一個(gè)屬性對(duì)應(yīng)查詢中的一個(gè)形式化表述內(nèi)容。因此，上述查詢的隱私保護(hù)可轉(zhuǎn)換為用戶屬性隱私信息檢索，并解密反饋信息的處理過(guò)程。這一過(guò)程可表示為如圖2所示的LBS服務(wù)器和用戶之間的信息傳遞協(xié)議。

圖2 屬性基PIR傳遞協(xié)議Fig.2 The protocol of attribute based PIR

2.2 屬性基PIR方法執(zhí)行過(guò)程

按照屬性基PIR的處理協(xié)議，隱私檢索方法存在2個(gè)處理階段，分別為L(zhǎng)BS服務(wù)器信息處理和用戶信息處理。為便于對(duì)屬性PIR的理解，本文借鑒文獻(xiàn)[12]所提供的隱私信息檢索方法，將這2個(gè)階段按照時(shí)間順序加以表述。為便于理解，表1給出了屬性PIR處理中所使用的參數(shù)及所表示的含義。

式中：g是G的生成器，G是p階大素?cái)?shù)循環(huán)群，F(xiàn)(·)是多項(xiàng)式時(shí)間概率算法。

表1 屬性PIR所涉及的參數(shù)Table 1 Parameters used in attribute based PIR

h←gβ

對(duì)于每個(gè)i分別計(jì)算：

ui←g1hri，vi←gri，Xi←gsi，Yi←gti

算法1用戶加密查詢處理

輸入：用戶查詢信息轉(zhuǎn)換后的屬性信息G和私鑰β←Zp

輸出：加密后的用戶查詢信息T(G)

2 計(jì)算h←gβ;

3for(i=1,i<=n,i++)

4ui←g1hri，vi←gri;

5Xi←gsi，Yi←gti;

9end

10returnT(G)={Ui,Vi,Xi,Yi};

算法1中，第3～9行通過(guò)for循環(huán)實(shí)現(xiàn)對(duì)每個(gè)屬性對(duì)應(yīng)的查詢進(jìn)行加密，并獲得加密查詢信息T(G)，該過(guò)程若不考慮累乘其時(shí)間復(fù)雜度為O(n)，但在算法的6～8行對(duì)屬性信息進(jìn)行了累乘計(jì)算，因而實(shí)際的時(shí)間復(fù)雜度將達(dá)到O(n2)。

當(dāng)LBS服務(wù)器收到用戶發(fā)送的T(G)時(shí)，對(duì)于保存的興趣點(diǎn)數(shù)據(jù)M，以及數(shù)據(jù)屬性A，|A|=k，LBS服務(wù)器完成如下計(jì)算：

同時(shí)計(jì)算：

C3=Wt·M

LBS服務(wù)器獲得加密信息CT=(C0,C1,C2,C3)，并將其發(fā)送給用戶。上述處理可表示為如算法2所示的計(jì)算處理過(guò)程。

算法2LBS服務(wù)器進(jìn)行隱私信息檢索

輸入：用戶提交的加密查詢信息T(G)

輸出：LBS服務(wù)器基于屬性PIR處理后的加密查詢結(jié)果CT。

1for(i=1,i<=k,i++)

2 計(jì)算Pi,Qi,Wi;

3end

4 隨機(jī)選擇l1～lk,t;

5 累乘計(jì)算P和W;

6 計(jì)算C0,C1,C2,C3;

7returnCT=(C0,C1,C2,C3);

算法2通過(guò)for循環(huán)對(duì)LBS服務(wù)器內(nèi)保存的所有屬性處理后獲得反饋的查詢結(jié)果，并向用戶發(fā)送含有n個(gè)屬性的查詢結(jié)果集合。此時(shí)，for循環(huán)的規(guī)模遠(yuǎn)大于算法1中的for循環(huán)，即k?n。此時(shí)算法2的時(shí)間復(fù)雜度為O(k)+O(n)=O(k)。

用戶在收到由LBS服務(wù)器發(fā)送過(guò)來(lái)的信息CT后，計(jì)算：

((gt·∑i∈Aηili)-β·(gt·∑i∈Arili·ht·∑i∈Aηili))-β·

(gt·∑i∈Aθili)-β·gt·∑i∈Aβrili·ht·∑i∈Aθili·M=M

由此可在M中過(guò)濾出所需要的查詢信息。最后對(duì)CT的處理過(guò)程可簡(jiǎn)化為算法3所示的處理過(guò)程。

算法3加密反饋信息解密

輸入：LBS服務(wù)器反饋的加密查詢結(jié)果CT;

輸出：明文M′。

2returnM′;

算法3對(duì)每個(gè)屬性信息進(jìn)行了累加計(jì)算，處理后獲得針對(duì)用戶提交屬性的查詢結(jié)果信息。該算法的時(shí)間復(fù)雜度為O(n)。

綜上，經(jīng)過(guò)3個(gè)算法的處理實(shí)現(xiàn)了屬性基PIR的處理過(guò)程，用戶可通過(guò)秘密的信息檢索過(guò)程獲得所需的查詢反饋。

3 性能評(píng)估

3.1 隱私保護(hù)和可用性分析

屬性基PIR的安全性取決于LBS服務(wù)器無(wú)法準(zhǔn)確識(shí)別由用戶查詢信息轉(zhuǎn)化的屬性信息。其可用性取決于對(duì)查詢結(jié)果的準(zhǔn)確反饋以及在有效的時(shí)間內(nèi)的計(jì)算處理。

為進(jìn)一步說(shuō)明本文所提出算法的隱私保護(hù)能力，設(shè)存在一個(gè)在挑戰(zhàn)者A和用戶U之間的博弈來(lái)證明隱私保護(hù)強(qiáng)度。假設(shè)挑戰(zhàn)者A準(zhǔn)備了2組屬性(a1,a2)，并將這2個(gè)查詢發(fā)送給用戶U。U隨機(jī)選擇c∈(1,2)并表示為ac，同時(shí)將2組屬性加密，然后將任意一組屬性M發(fā)送給挑戰(zhàn)者A。如果挑戰(zhàn)者A能夠計(jì)算得出c′ 滿足p(ac′)≠p(ac)，則A獲勝。若A獲勝，則需對(duì)于任意一組屬性，存在p(ai∈ac|ac∈M)≠p(aj∈ac|ac∈M)?(0

對(duì)于另一組屬性，有：

在本文算法的處理下，攻擊者可獲得的是加密后的屬性信息，在不能獲得解密密鑰的前提下，攻擊者只能進(jìn)行猜測(cè)，此時(shí)2次猜測(cè)成功的概率彼此相等，有pi=pj,?(0

3.2 實(shí)驗(yàn)設(shè)定

通過(guò)上一節(jié)給出的屬性基PIR在隱私保護(hù)和可用性方面的理論分析可知，該算法能夠保障用戶的隱私且具有良好的執(zhí)行效率。本節(jié)將通過(guò)與其他幾種基于位置服務(wù)的隱私保護(hù)算法之間的對(duì)比，進(jìn)一步證明所提出方法的優(yōu)越性。參與比較的算法有：基于索引的可計(jì)算PIR[10]，基于分層索引的層次PIR[15]，基于模糊索引的近似PIR[16]，基于屬性泛化的屬性基加密算法[17]以及基于屬性模糊的關(guān)聯(lián)概率不可區(qū)分算法[5]。實(shí)驗(yàn)將使用北京出租車行駛數(shù)據(jù)，并在Intel Core i5 1.70 GHz CPU、4gb RAM筆記本電腦上利用Matlab R2017a在Windows 7×64操作系統(tǒng)上完成測(cè)試，所有結(jié)果均是取計(jì)算500次后的平均值作為比較結(jié)果并繪制完成結(jié)果圖。

3.3 測(cè)試結(jié)果及分析

表2給出了幾種算法在不同安全環(huán)境下、查詢準(zhǔn)確性以及算法運(yùn)行時(shí)間上的效果比較。

表2 不同算法效果比較Table 2 The comparison effects of different algorithms

圖3給出了幾種不同算法在屬性數(shù)量變化下的攻擊者猜測(cè)成功概率。從該圖中可以看出，本文方法因使用屬性基PIR，所以隨屬性增加，攻擊者攻擊成功的概率變化不大。同樣使用PIR技術(shù)的可計(jì)算PIR、層次PIR以及近似PIR等3種方法的攻擊成功概率也變化不大，這是因采用PIR索引差異導(dǎo)致的攻擊效果差異。而屬性基加密算法，盡管采用屬性加密來(lái)防止屬性被攻擊者識(shí)別，但該算法一方面需提交用戶真實(shí)位置，導(dǎo)致被識(shí)別的概率高于PIR；另一方面隨著屬性數(shù)量的增加，其保護(hù)性逐漸降低，因此其攻擊成功率要高于上述幾種基于PIR的算法。最后，關(guān)聯(lián)概率不可區(qū)分算法采用的是位置模糊，并未對(duì)用戶的屬性信息加以保護(hù)，其被攻擊者有效識(shí)別的概率高于其他算法，攻擊成功率最高。

圖4給出了幾種不同算法在查詢次數(shù)變化下的攻擊成功概率。從該圖中可以看出，隨著查詢次數(shù)的增加，所有算法都不可避免地存在更高的被攻擊者識(shí)別的概率。這是因?yàn)殡S著查詢次數(shù)的增加，用戶將暴露更多的潛在信息給LBS服務(wù)器，這些信息可作為背景知識(shí)被攻擊者所利用，進(jìn)而提升攻擊成功率。在這些方法中，本文方法因采用屬性基PIR，其被暴露屬性的可能性較低，攻擊者利用屬性關(guān)聯(lián)獲取用戶隱私信息的成功率要低于其他PIR算法。而其他PIR算法，諸如計(jì)算PIR、層次PIR以及近似PIR等3種方法，由于采用加密技術(shù)，使得可暴露的信息量要少于泛化或模糊的算法，因此其攻擊成功率要低于屬性基加密算法和和關(guān)聯(lián)概率不可區(qū)分算法。最后，屬性基加密算法可針對(duì)的屬性要高于關(guān)聯(lián)概率不可區(qū)分算法，其攻擊成功率要低于關(guān)聯(lián)概率不可區(qū)分算法，而關(guān)聯(lián)概率不可區(qū)分算法則是幾種算法中最易被攻擊者攻破并獲取用戶隱私信息的算法。

圖3 不同算法的攻擊成功概率vs.屬性數(shù)量Fig.3 The success ratio of guessing the privacy vs. the number of attributes

圖4 不同算法的攻擊成功概率vs.查詢次數(shù)Fig.4 The success ratio of guessing the privacy vs. the number of requests

圖5給出了幾種不同算法在屬性數(shù)量變化下的算法執(zhí)行時(shí)間差異。從該圖中可以看出，所有算法的執(zhí)行時(shí)間均隨用戶屬性數(shù)量的增加而增長(zhǎng)，這是因?yàn)閷傩约用芩惴ㄒ约捌渌惴?，都需?duì)增加的屬性進(jìn)行加密、泛化或模糊處理，上述過(guò)程增加了處理時(shí)間。在這些算法中，本文算法由于采用了屬性基檢索，其執(zhí)行時(shí)間要低于采用索引檢索的PIR算法，且由于對(duì)多個(gè)屬性同時(shí)加密，其執(zhí)行時(shí)間要低于用戶協(xié)作的屬性基加密算法，僅高于采用偏移的關(guān)聯(lián)概率不可區(qū)分算法。其他幾種PIR則按照可計(jì)算PIR，層次PIR以及近似PIR的順序，其算法執(zhí)行時(shí)間相應(yīng)減少。

圖5 不同算法的算法執(zhí)行時(shí)間vs.屬性數(shù)量Fig.5 The running time of various algorithms vs. the number of attributes

圖6給出了不同算法在查詢次數(shù)變化下的算法執(zhí)行時(shí)間差異。從該圖可看出，隨查詢次數(shù)的增加，所有算法的執(zhí)行時(shí)間均逐漸增長(zhǎng)，這是由于每次查詢需重新執(zhí)行隱私保護(hù)算法，其執(zhí)行時(shí)間隨查詢次數(shù)逐漸增加。本文方法由于采用屬性基檢索，其算法處理步驟相對(duì)較少，因而其執(zhí)行時(shí)間最少。而屬性基加密算法由于采用協(xié)作用戶提供查詢結(jié)果，因此在多次查詢的情況下，其算法執(zhí)行時(shí)間稍高。關(guān)聯(lián)概率不可區(qū)分算法需要計(jì)算各位置間的關(guān)聯(lián)概率，且需要滿足差分隱私約束，因而其執(zhí)行時(shí)間要高于前2個(gè)算法。最后，計(jì)算PIR、層次PIR以及近似PIR則按照索引執(zhí)行的難易程度，其算法執(zhí)行時(shí)間依次增加。

圖6 不同算法的算法執(zhí)行時(shí)間vs.查詢次數(shù)Fig.6 The running time of various algorithms vs. the number of requests

綜上，可認(rèn)為本文所提出的屬性基隱私信息檢索方法在安全性和算法執(zhí)行效率等方面要優(yōu)于其他同類算法。

4 結(jié)論

1) 通過(guò)安全性和性能分析以及同類算法的對(duì)比實(shí)驗(yàn)，可認(rèn)為本文所提出的方案具有更好的隱私保護(hù)能力和算法執(zhí)行效率。

2) 在研究過(guò)程中還發(fā)現(xiàn)，這種基于加密手段的隱私保護(hù)算法其計(jì)算時(shí)間仍高于匿名策略的隱私保護(hù)算法，但其隱私保護(hù)能力更高。所以，本文所提出的方案更適合在一些計(jì)算能夠較強(qiáng)的移動(dòng)設(shè)備上使用。

由于本文方案是利用移動(dòng)用戶屬性完成的隱私信息檢索，今后的工作將在較少屬性范圍內(nèi)的特征屬性匹配檢索方面展開，以進(jìn)一步減少算法執(zhí)行時(shí)間。