基于非可信用戶協(xié)作的位置隱私保護機制*

王 輝， 朱國宇， 申自浩， 田可可

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

0 引 言

近年來，隨著無線通信技術(shù)以及定位技術(shù)[1]的發(fā)展，基于位置的服務(wù)(location-based service，LBS)與人們關(guān)系日益密切。在移動互聯(lián)網(wǎng)中基于位置服務(wù)的應(yīng)用程序日益增加，人們的生活也更加便捷[2]。基于位置服務(wù)的應(yīng)用程序通過將用戶的興趣點和位置信息發(fā)送到LBS服務(wù)器，用戶就可以獲得各種各樣的基于位置的服務(wù)。如“美團”根據(jù)用戶提供的位置信息進行個性化的服務(wù)。用戶搜索“小吃”，“美團”時，就會將興趣點“小吃”和用戶位置等信息發(fā)送給美團的LBS服務(wù)器，”美團”就會將用戶附近的小吃商戶展示給用戶。

然而，若在生成、存儲和使用位置信息的過程中沒有科學(xué)的保護措施，用戶的健康狀況、財務(wù)信息、社會關(guān)系、興趣愛好和情緒狀態(tài)等敏感信息可能被泄露，攻擊者能夠根據(jù)這些信息散播惡意廣告和竊取用戶財物。因此，在滿足用戶基于位置服務(wù)的前提下，保護用戶的隱私信息不被泄露成為了亟待解決的問題。

近年來，國內(nèi)外研究學(xué)者提出了多種位置隱私保護方法，其中K匿名模型[3]是最常用的方法之一。其基本思想[4]是：用一個包含目標用戶在內(nèi)的k個用戶的匿名區(qū)域代替用戶的真實位置,從而使攻擊者無法區(qū)分出目標用戶的真實位置。如圖1(a)所示。該模型系統(tǒng)結(jié)構(gòu)主要有三種:客戶端服務(wù)器結(jié)構(gòu)、集中式結(jié)構(gòu)和分布式結(jié)構(gòu)。

在客戶端服務(wù)器結(jié)構(gòu)[5]中，用戶利用歷史信息(包括歷史位置信息和歷史查詢信息等)通過算法對真實的查詢請求進行匿名處理，進而達到保護用戶位置隱私的目的。但是此結(jié)構(gòu)的系統(tǒng)對客戶端要求較高，需要一定的存儲能力和計算能力，優(yōu)勢為不需要其他實體參與。集中式結(jié)構(gòu)[6]，一般需要引入第三方匿名服務(wù)器，負責(zé)處理用戶的查詢請求，代替真實用戶發(fā)送請求信息，并將服務(wù)器返回結(jié)果發(fā)送給用戶。缺點是易產(chǎn)生單點故障和瓶頸問題，優(yōu)點是降低了對客戶端的性能要求。

分布式結(jié)構(gòu)[7,8]，各個移動用戶之間相互協(xié)作，分享部分位置信息，并形成匿名空間，達到K匿名效果，經(jīng)過處理達到保護位置隱私的目的。缺點為易產(chǎn)生通信延遲和易受串通攻擊，優(yōu)點為有效避免了單點故障和瓶頸問題。

隨著數(shù)據(jù)挖掘技術(shù)[9]的發(fā)展，K匿名模型的算法易受到攻擊者的語義攻擊，且在抵抗串通攻擊和推理攻擊的能力上較弱。針對這些問題，本文提出了多跳傳輸(multi-hop transmission,MHT)模型,該模型不僅適用于快照查詢，還能應(yīng)用在連續(xù)查詢中，并且能夠在抵抗攻擊者串通攻擊、推理攻擊和語義攻擊下提供精確的位置服務(wù)。在相同資源下，該模型的隱私保護強度強于K匿名模型。

1 系統(tǒng)結(jié)構(gòu)與相關(guān)定義

1.1 系統(tǒng)結(jié)構(gòu)

MHT機制系統(tǒng)由用戶、可信云計算中心、LBS服務(wù)器三部分組成，如圖1(b)。

用戶：通常是智能終端(如手機、平板等)，需具有以下功能：1)定位功能(如GPS,北斗等),能夠獲得用戶的當(dāng)前位置;2)與位置服務(wù)提供商進行通信，可以通過蜂窩網(wǎng)絡(luò)(如4 G、5 G等)傳輸信息;3)能夠和其他用戶短距離的通信(如WiFi，藍牙等)。當(dāng)用戶發(fā)送自身查詢請求時為目標用戶，參與其他用戶的查詢請求時為鄰居用戶。目標用戶是能夠發(fā)送經(jīng)過處理的查詢請求信息，具備一定的計算能力，具有加解密能力。鄰居用戶是輔助目標用戶進行查詢，具有轉(zhuǎn)發(fā)能力、存儲能力和與LBS服務(wù)器交互能力。

可信云計算中心(trusted cloud computing center，TC3)：將每個進入網(wǎng)絡(luò)的用戶或者已在網(wǎng)絡(luò)的用戶周期發(fā)出的請求，根據(jù)各自位置隱私保護需求選擇下一跳鄰居用戶，并將可選的下一跳鄰居用戶的集合返回給相應(yīng)用戶。

LBS服務(wù)器：能夠根據(jù)請求信息進行檢索，并將結(jié)果打包反饋給發(fā)送該請求的用戶。具有加解密處理能力。

圖1 K匿名機制與MHT機制示意

圖1中空心小圓圈和實心點均為實際存在的用戶，實心五角星為目標用戶。圖1(a)中虛框為形成匿名區(qū)域。圖1(b)為MHT機制示意圖。

1.2 相關(guān)定義

定義1信息傳輸軌跡:目標用戶發(fā)送請求到LBS服務(wù)器的信息傳輸軌跡。表示為

MQ={u0,u1,u2,…uh,S}

式中h(h∈N+)為用戶隱私保護強度,即跳數(shù);u0為目標用戶，u1到uh為鄰居用戶，分別稱為一跳鄰居用戶，二跳鄰居用戶，……，h跳鄰居用戶;S為LBS服務(wù)器。如圖 1(b)中實線和虛線箭頭所連接的用戶及LBS服務(wù)器分別形成一條信息傳輸軌跡。

定義2函數(shù)向量積：定義?和⊕兩種函數(shù)和向量的運算關(guān)系。表示為

(1)

式中 [pmin,pmax]為最優(yōu)價值范圍，r為價值評估的范圍擴展容忍度，使得rpmin為無法容忍的下限，(1+r)pmax為無法容忍的上限。表示為

(2)

定義3競拍底價Price:目標用戶尋找鄰居用戶時，欲參與目標用戶請求過程的用戶能夠提供的條件量化值。

1)任意用戶i競拍底價滿足下式

Pricei(disti,θi,Cnti)=[f(disti)f(θi)f(Cnti)]?M·Wi

=[f(disti)?M*1f(θi)?M*2f(Cnti)?M*3]·Wi

(3)

式中Cnti為用戶i當(dāng)前時刻同時參與信息傳輸軌跡的個數(shù)。M為缺省屬性參數(shù)矩陣

式中Rmin，Rmax;θminθmax;Cntmin,Cntmax分別為距離、弧度、輔助軌跡個數(shù)最優(yōu)價值范圍最小值與最大值；λR,λθ,λCnt分別為不同價值評估的范圍擴展容忍度。

2)對于n個用戶的競爭底價組成的3×n矩陣U,其競拍底價滿足下式

φ=Price⊕U

=[Price⊕U*1Price⊕U*2…Price⊕U*n]

(4)

式中U*i(i=1,2,…,n)為矩陣U的第i列向量，且U*i=[distiθiCnti]T。

定義4云計算信息MSGU2C用戶發(fā)送給TC3的數(shù)據(jù)格式，滿足下式

MSGU2C={LOCu,Wu,Mu,ADRu,NUMQ}

式中LOCu為用戶u的所在位置；Wu為用戶的權(quán)重向量；Mu為用戶u的缺省屬性參數(shù)矩陣；ADRu為用戶u的通信地址；NUMQ為TC3返回的用戶的個數(shù)。

定義5請求信息MSGU2S目標用戶的請求信息格式，滿足下式

MSGU2S={h,Nrdm,EPKS(POI,Loc,r,PKU)}

式中Nrdm為隨機值，E為非對稱加密函數(shù)；POI為目標用戶的興趣點信息；Loc為目標用戶的經(jīng)緯度坐標；r為查詢半徑；PKS,PKU分別為LBS服務(wù)器和目標用戶的公鑰。

定義6請求返回信息MSGS2ULBS服務(wù)器處理請求信息之后的返回信息，滿足下式

MSGS2U={Nrdm,EPKU(Result)}

式中Result為LBS服務(wù)器處理用戶請求信息的結(jié)果。

定義7路由表Li記錄信息傳輸軌跡中的用戶i的上一跳路由，滿足下式

Li={Nrdm,ADR}

當(dāng)用戶i參與多條信息傳輸軌跡時，Nrdm區(qū)分不同的信息傳輸軌跡。

2 MHT機制

2.1 競拍機制

不同用戶參與目標用戶的查詢請求時，提供的隱私保護幫助也有差異。當(dāng)用戶參與信息傳輸軌跡越多，其本身的查詢請求的安全性越高，所以用戶會競爭參與其他用戶的查詢請求過程，假設(shè)不會拒絕其他用戶的輔助請求。因此在用戶選擇下一跳鄰居用戶時引入競拍機制，將用戶的各個屬性信息進行量化，并加權(quán)處理，最后得到的量化值為該用戶的競拍底價，用于和其他用戶競爭參與目標用戶查詢請求。

2.2 尋找下一跳鄰居用戶集合

2.3 查詢實現(xiàn)過程

目標用戶根據(jù)算法構(gòu)造信息傳輸軌跡，并將查詢信息正向沿著信息傳輸軌跡傳輸查詢請求，當(dāng)LBS服務(wù)器收到查詢請求后，在數(shù)據(jù)庫檢索符合條件記錄，并將查詢結(jié)果沿著信息傳輸軌跡逆向傳輸，直到返回給目標用戶。

3)循環(huán)執(zhí)行步驟(2)，直到MSGU2S發(fā)送到LBS服務(wù)器。

4)LBS服務(wù)器收到MSGU2S后，先進行解密處理，根據(jù)目標用戶查詢請求搜索本地數(shù)據(jù)庫，并構(gòu)造結(jié)果集，然后用目標用戶的公鑰PKU進行加密處理，構(gòu)造查詢請求返回信息MSGS2U,發(fā)送給信息傳輸軌跡中的跳鄰居用戶。

5)信息傳輸軌跡MQ中的用戶收到MSGS2U后，按照本地路由中地址發(fā)送給上一跳鄰居用戶。

6)循環(huán)執(zhí)行步驟(5)，直到目標用戶收到信息MSGS2U。最后用私鑰進行解密得到查詢結(jié)果。

3 性能分析

對于時間開銷。h跳鄰居用戶發(fā)送給LBS服務(wù)器時，會在網(wǎng)絡(luò)中的多個路由節(jié)點進行轉(zhuǎn)發(fā)，最終由服務(wù)器接收并處理。查詢請求在信息傳輸軌跡傳輸完成后，再由h跳鄰居用戶進行數(shù)據(jù)包轉(zhuǎn)發(fā)，相當(dāng)于目標用戶直接向LBS服務(wù)器發(fā)送請求時多進行h次轉(zhuǎn)發(fā)處理。由于鄰居用戶僅做轉(zhuǎn)發(fā)處理，相比于K匿名機制，MHT機制的處理時間多出了h跳轉(zhuǎn)發(fā)的時間，實際中該時間是毫秒(ms)級的，所以,MHT機制并不會明顯增加時間開銷。

4 安全分析

4.1 抵抗串通攻擊

假設(shè)攻擊者集合為Adv={v1,v2,…,vm}，并分4種情況進行說明。

1)?ui(i∈[1,h])使得ui∈Adv，即存在惡意的鄰居用戶。ui根據(jù)收到的MSGU2S，無法分析加密部分。ui僅知道上一跳鄰居用戶和下一跳鄰居用戶的信息，除目標用戶外的任何用戶不可能獲得完整的MQ。

3)LBS∈Adv，即LBS服務(wù)器不可信。LBS服務(wù)器不能完整的獲得信息傳輸軌跡MQ，且MSGU2S中不包含任何目標用戶的相關(guān)信息。

4)?ui(i∈[1,h])且TC3,LBS∈Adv。由于跳數(shù)h只有目標用戶知道，即使是第一跳鄰居用戶，也僅知道其上一跳用戶的得到該請求信息時的跳數(shù)，并不能確定上一跳鄰居用戶就是目標用戶。攻擊者不能確定信息傳輸軌跡中的全部用戶。

4.2 抵抗推理攻擊

假設(shè)Ns表示整個網(wǎng)絡(luò)集合，PE(Event)代表Event成功時的概率。對于信息傳輸軌跡上的用戶ui和uj且?(0≤i≠j≤h)，若判斷目標用戶是ui或uj的概率相等，就說明能夠抵抗推理攻擊。即當(dāng)下式成立時完成證明

PE(ui∈MQ|MQ∈Ns)=PE(uj∈MQ|MQ∈Ns)

(5)

因為PE(ui∈MQ|MQ∈Ns)=PE(ui∈MQ∩MQ∈Ns)/PE(MQ∈Ns)=PE(ui∈Ns)/PE(MQ∈Ns)，同理有PE(uj∈MQ|MQ∈Ns)=PE(uj∈Ns)/PE(MQ∈Ns)，不論PE(MQ∈Ns)的值為多少，式(5)化簡結(jié)果為PE(ui∈Ns)=PE(uj∈Ns)，顯然成立，故式(5)得證。

4.3 被識別概率

根據(jù)4.2節(jié)分析，理論上用戶被識別的概率趨近于零。對于信息傳輸軌跡MQ中的用戶ui(i∈[0,h])，其參與的信息傳輸軌跡個數(shù)為ci，從中識別出MQ的概率為1/ci，即為p(ui)=1/ci。根據(jù)乘法原理，當(dāng)攻擊者不知道跳數(shù)h(假設(shè)h為何值的概率均為1/h)時的被識別概率為

(6)

當(dāng)攻擊者獲得h的值時，其被識別概率為

(7)

圖2為用戶u0使用不同的位置隱私保護模型的理想狀態(tài)下被識別概率對比。輔助用戶為n代表K匿名機制的k為n+1,MHT機制的跳數(shù)為n,c=2和c=3分別代表MHT機制的鄰居用戶均同時參與2條和3條信息傳輸軌跡。

圖2 K匿名機制和MHT機制被識別概率對比

5 結(jié)束語

本文分析了LBS常見的系統(tǒng)結(jié)構(gòu)模型的優(yōu)缺點，在非可信實體參與真實用戶位置服務(wù)的情況下，對用戶的查詢請求進行加密處理，經(jīng)過h個鄰居用戶的輔助，發(fā)送到LBS服務(wù)器，LBS服務(wù)器處理后，將查詢結(jié)果進行加密，并沿信息傳輸軌跡逆向反饋給目標用戶。并通過性能分析和安全分析，突出了MHT機制的優(yōu)勢。