一種面向移動終端的K匿名位置隱私保護(hù)方案

宋 成，金 彤，倪水平，賀軍義，杜守恒

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

隨著計(jì)算機(jī)技術(shù)、全球定位系統(tǒng)和無線通信網(wǎng)絡(luò)的發(fā)展，基于位置服務(wù)(Location Based Service，LBS)技術(shù)[1-3]得到日益廣泛的應(yīng)用，如車載導(dǎo)航、網(wǎng)約車、外賣、網(wǎng)上購票等，給用戶的生活帶來了極大的便利，并不斷改變著人們的日常行為模式。在用戶對位置服務(wù)的依賴性與日俱增的同時，個人位置隱私泄露的風(fēng)險(xiǎn)無處不在。運(yùn)動的用戶在請求位置服務(wù)過程中，需要實(shí)時向位置服務(wù)服務(wù)器提交自己當(dāng)前的位置信息和需要查詢的信息，根據(jù)時空關(guān)聯(lián)性，可構(gòu)建用戶的位置軌跡數(shù)據(jù)信息。而根據(jù)用戶軌跡能夠推斷出用戶在何時去了何地、用戶的家庭住址、工作地點(diǎn)等敏感位置，進(jìn)而可推斷用戶的健康狀況、宗教信仰、生活習(xí)慣等隱私信息。如果攻擊者獲取用戶的位置信息，將會給用戶造成與位置相關(guān)的隱私泄露的風(fēng)險(xiǎn)。因此，位置隱私保護(hù)技術(shù)是當(dāng)前移動網(wǎng)絡(luò)安全領(lǐng)域研究的熱點(diǎn)之一。

針對當(dāng)前位置隱私保護(hù)存在的問題，結(jié)合K匿名技術(shù)和不經(jīng)意傳輸協(xié)議的思想，提出一種面向移動終端的K匿名位置隱私保護(hù)方案。方案中，用戶首先將包含真實(shí)用戶在內(nèi)的k個身份標(biāo)識作為注冊請求發(fā)送給位置服務(wù)服務(wù)器，位置服務(wù)服務(wù)器為k個身份標(biāo)識生成假名和對應(yīng)的公私鑰對；然后，移動終端將生成并選取假位置，基于不經(jīng)意傳輸協(xié)議與位置服務(wù)服務(wù)器完成位置服務(wù)查詢。

1 相關(guān)工作

近年來，國內(nèi)外學(xué)者在位置隱私保護(hù)技術(shù)方面做了大量的工作，并取得一系列的成果。根據(jù)位置隱私保護(hù)體系結(jié)構(gòu)的不同，這些成果大致可分為兩類：一類為基于可信匿名中心的位置隱私保護(hù)技術(shù)，另一類為基于移動終端的位置隱私保護(hù)技術(shù)。

基于可信匿名中心的結(jié)構(gòu)又稱為基于可信第三方結(jié)構(gòu)，由GEDIK和LIU[4]首次提出。基于可信匿名中心結(jié)構(gòu)的位置隱私保護(hù)方案通過在用戶和位置服務(wù)服務(wù)器之間引入可信匿名中心；可信匿名中心通常結(jié)合一些隱私保護(hù)技術(shù)[5-8]對用戶服務(wù)請求消息匿名化，同時負(fù)責(zé)完成用戶與位置服務(wù)服務(wù)器之間的消息轉(zhuǎn)發(fā)，進(jìn)而實(shí)現(xiàn)對用戶位置隱私的保護(hù)，并降低用戶端存儲開銷和計(jì)算開銷。K匿名技術(shù)[9-11]是目前應(yīng)用最為廣泛的一種位置隱私保護(hù)技術(shù)，其主要思想是形成至少包含其他k-1個不同用戶的匿名區(qū)域，然后用匿名區(qū)域取代真實(shí)用戶信息向位置服務(wù)服務(wù)器發(fā)送服務(wù)請求，從而降低用戶位置精度，使攻擊者識別匿名區(qū)域中真實(shí)用戶的概率不超過1/k。針對傳統(tǒng)K匿名技術(shù)只能對預(yù)定義的固定屬性進(jìn)行匿名化處理的局限性，OTGONBAYAR等[12]將不同的語義描述數(shù)據(jù)進(jìn)行分區(qū)，合并語義相似的數(shù)據(jù)，提出一種合并相近語義數(shù)據(jù)流的K匿名的方法，降低信息丟失率。K匿名能夠阻止身份信息的泄露。但無法阻止屬性信息的泄露，為了驗(yàn)證該問題，TU等[13]在軌跡數(shù)據(jù)發(fā)布過程中成功實(shí)現(xiàn)了語義攻擊，并結(jié)合K匿名、L多樣性和T相似度這3種數(shù)據(jù)脫敏方法，提出一種阻止語義和重新識別攻擊的隱私保護(hù)方案。另一種常用的位置隱私保護(hù)技術(shù)是混合區(qū)域技術(shù)[14]，用戶進(jìn)入混合區(qū)域時，停止同位置服務(wù)服務(wù)器的所有通信，離開時通過可信匿名中心更換用戶假名，進(jìn)而防止攻擊者根據(jù)用戶連續(xù)提交位置的關(guān)聯(lián)性來跟蹤用戶。由于大型混合區(qū)域會嚴(yán)重影響服務(wù)質(zhì)量，MEMON等[15]根據(jù)交通系統(tǒng)和停車位置的相關(guān)程度，構(gòu)建多重混合區(qū)域，在確保匿名性的基礎(chǔ)上解決了混合區(qū)域內(nèi)的用戶多樣性問題。

可信匿名中心雖可作為可信第三方結(jié)構(gòu)的核心，但現(xiàn)實(shí)生活中完全可信的匿名中心難以存在。即使存在，依舊存在被攻擊者破解的風(fēng)險(xiǎn)。一旦可信匿名中心被攻破，所帶來的泄露風(fēng)險(xiǎn)更加嚴(yán)重。同時，由于匿名中心負(fù)責(zé)匿名化的計(jì)算以及消息轉(zhuǎn)發(fā)存儲等功能，可能會成為系統(tǒng)性能的瓶頸。針對單匿名中心的不足，張等[16]引入分布式多匿名服務(wù)器，通過位置預(yù)測機(jī)制和假位置選擇機(jī)制獲取G-1個查詢混淆位置，形成匿名域，然后隨機(jī)選擇一個匿名服務(wù)器完成服務(wù)；但該結(jié)構(gòu)會造成系統(tǒng)整體成本上升。PENG等[17]使用半可信中間實(shí)體執(zhí)行匿名和篩選功能，利用希伯特曲線轉(zhuǎn)換用戶位置信息，實(shí)現(xiàn)用戶位置隱私信息的保護(hù)；但半可信中間實(shí)體依然會成為系統(tǒng)性能的瓶頸。

隨著移動終端性能的不斷提升，其計(jì)算和存儲能力得到了巨大的提高。因此，基于移動終端的隱私保護(hù)方案具備了可行性，能夠避免傳統(tǒng)方案的安全性能對可信匿名中心的依賴和性能瓶頸問題。一些學(xué)者已經(jīng)在這方面做了大量研究工作，如李等[18]提出利用隱馬爾科夫轉(zhuǎn)移矩陣模型預(yù)測用戶的運(yùn)動軌跡，并將用戶下一時刻的預(yù)測位置作為前一時刻的查詢內(nèi)容；HAYASHIDA等[19]提出利用旅行推銷商貪心算法生成虛假軌跡，通過虛假軌跡與真實(shí)軌跡相交來隱藏用戶的位置信息；PENG等[20]提出通過生成虛假查詢信息混淆真實(shí)軌跡，并通過用戶間的協(xié)作緩存收集消息。毛典輝等[21]提出構(gòu)建多粒度抽象路網(wǎng)與位置情境模型，根據(jù)用戶個性化設(shè)置，實(shí)現(xiàn)自適應(yīng)選取查詢點(diǎn)和查詢區(qū)域。盡管這些方案避開了對可信匿名中心的依賴，但它們只考慮了用戶端的隱私性，而忽視了位置服務(wù)服務(wù)器端的隱私性。如果單一用戶可以通過已獲得的部分信息推導(dǎo)出LBS服務(wù)器的全部信息，則這將造成其他用戶的個人信息外泄和位置服務(wù)服務(wù)器的失效。因此，位置服務(wù)服務(wù)器端的隱私性同樣需要保護(hù)。

2 預(yù)備知識

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

如圖1所示，移動終端用戶通過衛(wèi)星定位系統(tǒng)獲取自身位置信息并在其周圍生成k-1假位置(對應(yīng)注冊的k-1個假身份)及相應(yīng)的偽查詢內(nèi)容，然后通過附近的基站連接網(wǎng)絡(luò)，將包含偽查詢和真實(shí)查詢請求的k個請求發(fā)送給位置服務(wù)服務(wù)器。位置服務(wù)服務(wù)器接收并處理相應(yīng)的請求，將加密后的興趣點(diǎn)集通過基站返回給移動終端。移動終端用戶對加密結(jié)果集進(jìn)行解密，獲得興趣點(diǎn)的相關(guān)信息(如店鋪名稱、地理位置、交通路線等)。完整系統(tǒng)架構(gòu)模型由兩部分類實(shí)體組成：移動終端和位置服務(wù)服務(wù)器。各部分的作用如下：

(1) 移動終端：負(fù)責(zé)位置服務(wù)服務(wù)器發(fā)送匿名化處理請求，生成并篩選假位置節(jié)點(diǎn)，向位置服務(wù)服務(wù)器發(fā)送位置查詢服務(wù)請求，并接收來自位置服務(wù)服務(wù)器的查詢服務(wù)結(jié)果。

(2) LBS服務(wù)器：負(fù)責(zé)用戶的注冊，位置服務(wù)查詢及查詢結(jié)果的響應(yīng)。

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

2.2 雙線性映射

設(shè)q是一個大素?cái)?shù)，G1和G2分別為兩個階均為q的加法群和乘法群，G1到G2的雙線性映射e：G1×G2→G2滿足以下性質(zhì)：

(1) 雙線性：任意P，Q，R∈G1，a，b∈Z*q，滿足e(aP，bQ)=e(P，Q)ab，e(P+Q，R)=e(P，R)e(Q，R)和e(P，Q+R)=e(P，Q)e(P，R)。

(2) 非退化性：存在P，Q∈G1，使得e(P，Q)≠1G1，其中1G1為群G1的單位元。

(3) 可計(jì)算性：任意P，Q∈G1，都存在一個有效算法計(jì)算e(P，Q)。

(4) 對稱性：任意P，Q∈G1，滿足e(P，Q)=e(Q，P)。

2.3 位置熵

假設(shè)某匿名區(qū)域R內(nèi)有k個候選位置節(jié)點(diǎn)，k個位置節(jié)點(diǎn)被查詢概率分別為Yi(i=1，2，…，k)，那么每個位置成為真實(shí)位置的概率為

(1)

給定一個包含k個候選位置的匿名區(qū)域R，每個位置在匿名區(qū)域R內(nèi)成為真實(shí)位置的概率記為Pr(i)，那么它的位置熵值為

(2)

利用式(1)和(2)可得節(jié)點(diǎn)位置熵，候選位置節(jié)點(diǎn)熵值越高，隱私保護(hù)水平越高。

3 面向終端的K匿名隱私保護(hù)方案

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

步驟1 選擇2個階為q的循環(huán)群G1，G2；其中，G1為加法循環(huán)群，G2為乘法循環(huán)群，q是一個大素?cái)?shù)。e：G1×G2→G2表示一個雙線性映射。

步驟2 定義3個哈希函數(shù)H1，H2和H3。其中，H1：{0，1}*→G*1，H2：G2→{0，1}n，H3為SHA256的哈希函數(shù)，n表示一個整數(shù)，{0，1}*表示任意長度的二進(jìn)制串。

步驟3 位置服務(wù)服務(wù)器選取一隨機(jī)數(shù)s∈Z*q作為系統(tǒng)私鑰，計(jì)算其公鑰：PK=sP，其中，P為G1的生成元。

步驟4 位置服務(wù)服務(wù)器保存系統(tǒng)私鑰s并公開系統(tǒng)公共參數(shù)：{G1，G2，e，n，q，P，PK，H1，H2}。

3.2 用戶注冊階段

步驟1 移動終端將k個身份信息{ID1，ID2，…，IDk}作為注冊請求發(fā)送給位置服務(wù)服務(wù)器，其中用戶身份IDu位于請求消息的第u個位置，u∈{1，2，…，k}，u由用戶選擇。

步驟2 位置服務(wù)服務(wù)器使用偽隨機(jī)生成器生成鹽值IDsalty，分別計(jì)算對應(yīng)的假名PIDi=H3(IDi+IDsalty)，對應(yīng)的公鑰UiPK=H1(IDi)和私鑰UisK=sUiPK，然后生成信息{(PID1，U1PK，U1SK)，(PID2，U2PK，U2SK)，…，(PIDk，UkPK，UkSK)}并通過安全信道反饋給用戶。

步驟3 用戶收到消息后計(jì)算UPK=H1(IDu)，并判斷等式e(USK，P)=e(UPK，PK)是否成立。若等式成立，則用戶得到正確的假身份、公鑰和私鑰；否則，用戶所得消息失效，返回步驟1。

3.3 假位置生成與選取階段

步驟1 移動終端以用戶B的位置LB為中心點(diǎn)，采用矩形區(qū)域內(nèi)均勻分布隨機(jī)點(diǎn)算法生成一個假位置Li，假設(shè)矩形區(qū)域?yàn)椋篬a，b]×[e，f]，獨(dú)立生成D(0，1)內(nèi)均勻隨機(jī)數(shù)αi和βi，計(jì)算xi=(b-a)βi+a和yi=(f-e)αi+e，分別得到[a，b]和[e，f]內(nèi)均勻生成的隨機(jī)點(diǎn)Li=(xi，yi)。再根據(jù)地圖的背景信息判斷該位置的合理性；若為山川、河流等位置，則放棄該位置重新生成；否則，計(jì)算該點(diǎn)相對于點(diǎn)LB=(xB，yB)的歐幾里得距離dis(LB，Li)=((xB-xi)2-(yB-yi)2)1/2。

步驟2 移動終端判斷不等式Rmin≤dis(LB，Li)≤Rmax是否成立，其中Rmin和Rmax分別表示中心點(diǎn)到新生成假位置的最短距離和最遠(yuǎn)距離。如果滿足，則讓ci=Li，并將其加入位置集合C={c1，c2，c3，…，ci-1}中，即C={c1，c2，c3，…，ci-1}∪{ci}；如果不滿足，則重新返回步驟1。

步驟3 若得到的假位置數(shù)量不足2k個，則返回步驟1繼續(xù)生成；否則，執(zhí)行下一步。

步驟4 根據(jù)式(1)計(jì)算每個假位置成為真實(shí)位置概率Pr(i)，然后從2k個假位置中選取成為真實(shí)位置概率Pr(i)較高的k-1個假位置{L1，L2，…，Lk-1}組成較優(yōu)假位置集合CEnd。

步驟5 移動終端為包括自身在內(nèi)的k個位置節(jié)點(diǎn)分配虛假身份標(biāo)識。

3.4 位置服務(wù)請求階段

步驟1 位置服務(wù)服務(wù)器隨機(jī)選取d1，d2，…，dn∈Z*q，其中，n≥k，分別計(jì)算P1=d1PK，P2=d2PK，…，Pn=dnPK，并將其作為選擇基點(diǎn)公布。

步驟2 用戶B隨機(jī)選擇a1，a2，…，ak∈Z*q，計(jì)算vi=aiPi，其中i=1，2，…，k。

步驟3 用戶B結(jié)合生成的假身份，位置節(jié)點(diǎn)信息和偽查詢內(nèi)容組成查詢集合：Msg={(PID1，L1，Q1，v1)，(PID2，L2，Q2，v2)，…，(PIDu，Lu，Qu，vu)，…，(PIDk，Lk，Qk，vk)}，發(fā)送給位置服務(wù)服務(wù)器，其中，Lu表示真實(shí)節(jié)點(diǎn)位置，Qu表示真實(shí)查詢請求。

步驟4 位置服務(wù)服務(wù)器接收到位置服務(wù)請求后，獲取k個查詢結(jié)果{m1，m2，…，mu，…，mk}，然后選取隨機(jī)數(shù)r∈Z*q，計(jì)算Y0=rPK，Yi=rvi和ci=mi⊕H2(e(Pi+sPK，UBPK)r)，并將{Y0，(Y1，Y2，…，Yu，…，Yk)，(c1，c2，…，cu，…，ck)}發(fā)送給用戶B，其中，UBPK，UBSK分別表示用戶B的公私鑰對。

步驟5 用戶B收到消息后，判斷等式e(vu，Y0)=e(Yu，PK)是否成立。若成立，則用戶B計(jì)算au的乘法逆元a-1u∈Z*q，解密密鑰Vu=a-1uYu，mu=cu⊕H2(e(Vu，UBPK)e(Y0，UBSK))，從而獲取查詢結(jié)果(若是多個服務(wù)請求，則計(jì)算多個查詢結(jié)果)；若不成立，則用戶B放棄該查詢結(jié)果，返回步驟1，重新服務(wù)請求。

4 方案分析

4.1 安全性分析

4.1.1 匿名性

定義1匿名游戲。

步驟1 攻擊者A發(fā)起詢問獲取系統(tǒng)公開參數(shù){G1，G2，e，n，q，P，PK，H1，H2}，LBS服務(wù)器公開的選擇基點(diǎn)P1，P2，…，Pn以及Y0，Y1，Y2，…，Yk；

步驟2 攻擊者A選取k個完全不同的信息m1，m2，…，mk，作為用戶B的候選查詢結(jié)果；

步驟3 用戶B選取隨機(jī)位u∈{1，2，…，k}，然后將{m1，m2，…，mu，…，mk}發(fā)送給LBS服務(wù)器，其中u對攻擊者A保密；

步驟4 位置服務(wù)服務(wù)器對{m1，m2，…，mu，…，mk}進(jìn)行加密并返回結(jié)果{c1，c2，…，cu，…，ck}給用戶B；

步驟5 若用戶B收到的密文結(jié)果{c1，c2，…，cu，…，ck}與{m1，m2，…，mu，…，mk}相對應(yīng)，則將密文按照隨機(jī)順序發(fā)送給攻擊者A；否則，終止游戲；

步驟6 若攻擊者A通過對密文結(jié)果的解密能夠輸出mu=mu，則攻擊者A贏得這場游戲。

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

4.1.2 抗重放攻擊

定義2攻擊者A通過重新發(fā)送LBS服務(wù)器已處理的用戶注冊請求消息和位置服務(wù)請求消息，試圖獲得與用戶B相同的結(jié)果。攻擊者A能夠知曉的信息包括：系統(tǒng)公開參數(shù){G1，G2，e，n，q，P，PK，H1，H2}，用戶B的注冊請求消息{ID1，ID2，…，IDk}，位置服務(wù)請求消息Msg，LBS服務(wù)器公開的選擇基點(diǎn)P1，P2，…，Pn。

定理2如果攻擊者A以可忽略的概率獲得與用戶B相同的注冊結(jié)果和位置請求服務(wù)結(jié)果，那么方案可抗重放攻擊。

4.1.3 不可偽造性

(1) 初始化階段。挑戰(zhàn)者C產(chǎn)生公開的系統(tǒng)參數(shù){G1，G2，e，n，q，P，PK，H1，H2}和保密的主密鑰s。

(2) 訓(xùn)練階段。攻擊者A向挑戰(zhàn)者C發(fā)送身份信息IDi，請求預(yù)言機(jī)H1的應(yīng)答，挑戰(zhàn)者C運(yùn)行密鑰生成器算法，生成相應(yīng)的公私鑰對并返回給攻擊者A。這一過程可重復(fù)訓(xùn)練，多項(xiàng)式有界次。

定理3方案的隨機(jī)預(yù)言模型中，如果攻擊者A無法在多項(xiàng)式時間內(nèi)求解LBS服務(wù)器的私鑰s和臨時會話私鑰r，則本方案滿足不可偽造性。

證明：系統(tǒng)初始化階段，挑戰(zhàn)者C向攻擊者A公開參數(shù){G1，G2，e，n，q，P，PK，H1，H2}和用戶與LBS服務(wù)器間的通信消息，其中PK=sP，s為系統(tǒng)生成的隨機(jī)數(shù)，對攻擊者A保密。

用戶注冊階段，攻擊者A向隨機(jī)預(yù)言機(jī)H1進(jìn)行適應(yīng)性詢問，查詢獲取相應(yīng)的哈希值。具體過程如下：

攻擊者A向挑戰(zhàn)者C請求身份信息IDi的哈希值H1(IDi)，挑戰(zhàn)者C檢測請求-應(yīng)答列表中是否存在：

(1) 如果存在，則將相應(yīng)的應(yīng)答發(fā)送給攻擊者A；

(2) 如果不存在，則隨機(jī)生成wi∈∈Z*q，并計(jì)算H1(IDi)，然后將{wi，H1(IDi)}發(fā)送給攻擊者A，再把該請求-應(yīng)答存儲到列表中。

攻擊者A在詢問的過程中始終無法獲取系統(tǒng)私鑰s，無法使得等式e(U’SK，P)=e(UPK，PK)成立。若攻擊者預(yù)通過系統(tǒng)公開參數(shù){P，PK}和PK=sP推導(dǎo)系統(tǒng)私鑰s，則將面臨求解橢圓曲線離散對數(shù)難題。同理，位置服務(wù)請求階段，系統(tǒng)選擇的臨時會話密鑰r對攻擊者A保密，因此攻擊者A無法偽造正確的Y′u使等式e(vu，Y0)=e(Y′u，PK)成立。如果攻擊者A預(yù)通過Y0=rPK推導(dǎo)r，則將面臨求解橢圓曲線離散對數(shù)難題。

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

圖2 匿名度K與通信開銷的關(guān)系

基于位置隱私保護(hù)系統(tǒng)架構(gòu)模型，從系統(tǒng)性能和隱私度兩方面對方案進(jìn)行仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)在64位的Windows10操作系統(tǒng)、2.80 GHz 英特爾i7 CPU、8 GB內(nèi)存的PC機(jī)和Matlab仿真軟件的環(huán)境下進(jìn)行。實(shí)驗(yàn)選取5 km×5 km的真實(shí)地理地圖，以給定的用戶真實(shí)位置為中心，生成矩形區(qū)域[a，b]×[e，f]，大小為100 m×100 m。實(shí)驗(yàn)中的主要影響參數(shù)為匿名度K，表示單次位置服務(wù)過程中移動終端向LBS服務(wù)器發(fā)送的服務(wù)請求數(shù)量。

5.1 系統(tǒng)性能

5.1.1 通信開銷

系統(tǒng)的通信開銷影響移動終端的流量成本。一次完整的位置服務(wù)請求過程，通信開銷主要發(fā)生在用戶注冊階段和位置服務(wù)請求階段，主要通信數(shù)據(jù)包括：用戶注冊請求消息、用戶注冊結(jié)果、位置服務(wù)請求消息和加密結(jié)果集合。通信開銷的大小由數(shù)據(jù)包的大小和與匿名度K決定。仿真實(shí)驗(yàn)參數(shù)K的選取范圍為[5，20]，如圖2所示，該方案和對比方案的通信開銷與匿名度K均呈線性關(guān)系。由于文獻(xiàn)[16]是基于第三方匿名中心的方案，其通信需經(jīng)過匿名中心，其通信開銷隨著匿名度K的增加，相對于其他兩個比較方案明顯增長的快。盡管文獻(xiàn)[18]也是基于終端的方案，由于需要頻繁調(diào)用GPS服務(wù)來完成地圖分割算法，在相同的匿名度K的情況下，其通信開銷略高于本方案。即該方案能夠減少現(xiàn)階段K匿名技術(shù)的通信開銷，降低移動終端的流量成本，并具有一定的優(yōu)勢。

5.1.2 效率

圖3 匿名度K與執(zhí)行時間的關(guān)系

系統(tǒng)效率指用戶從發(fā)起查詢請求到獲得興趣點(diǎn)相關(guān)信息所執(zhí)行的時間。該方案與對比方案算法執(zhí)行時間主要由假位置生成和選取階段貢獻(xiàn)；由于匿名度K值決定了生成假位置的數(shù)量以及最優(yōu)假位置的數(shù)量，因此執(zhí)行時間隨著匿名度K的變化而變化；仿真實(shí)驗(yàn)參數(shù)K選取范圍設(shè)為[10，80]。仿真結(jié)果如圖3所示。

在匿名度K值較小時，該方案的執(zhí)行時間與方案[18]的相近，無明顯優(yōu)勢，但隨著K逐漸增大，由于方案[18]構(gòu)造維諾多邊形，其執(zhí)行時間增速明顯加快，當(dāng)匿名度K>73時，其執(zhí)行時間超過方案[16]。該方案與方案[16]執(zhí)行時間隨著K的增大，基本呈線性穩(wěn)定增長，但方案[16]算法的復(fù)雜性和執(zhí)行效率較低。

圖4 匿名度K與位置熵的關(guān)系

5.2 隱私度

方案的隱私安全與假位置的選取有關(guān)，通過在用戶周圍生成假位置，隱藏真實(shí)用戶位置。位置隱私度通常通過位置熵進(jìn)行度量，衡量假位置生成和選取階段所選取的候選節(jié)點(diǎn)質(zhì)量標(biāo)準(zhǔn)，熵值越高，隱私保護(hù)水平越高。在包括真實(shí)位置在內(nèi)的所有位置點(diǎn)發(fā)生概率均相等的情況下，位置熵達(dá)到理想最大值。匿名度K越大，對用戶真實(shí)位置的混淆效果會越好；但是匿名度K過大，會給方案的通信開銷和效率造成影響；本仿真中匿名度K值取[10，100]。仿真結(jié)果如圖4所示，3種方案的隱私度均隨著匿名度K的增加而增加，當(dāng)匿名度K值到達(dá)一定數(shù)值后，其增長速度越來越趨于平緩，這是因?yàn)槟涿麉^(qū)域內(nèi)的假位置過于密集，其混淆能力趨于飽和，再增加假位置數(shù)量，對隱私保護(hù)效果收效甚微。由于隨機(jī)方案沒有考慮到地圖信息和假位置的合理性，因此其隱私效果最不理想，盡管文獻(xiàn)[18]的方案在隨機(jī)選取k-1個假位置時考慮了其合理性，但該方案從2k個合理假位置中選取較優(yōu)的k-1個假位置，其隱私效果優(yōu)于文獻(xiàn)[18]的方案。

6 結(jié)束語

筆者提出了一種面向移動終端的K匿名位置隱私保護(hù)方案，采用安全高效的不經(jīng)意傳輸協(xié)議，避免了傳統(tǒng)方案對可信匿名中心的依賴，并且提高了方案的執(zhí)行效率，降低了通信開銷。通過在匿名區(qū)域隨機(jī)選取2k個合理假位置，然后根據(jù)位置熵，從中選取較優(yōu)的k-1個假位置，提高了方案的位置隱私度。通過安全性分析，方案滿足匿名性，抗重放攻擊和不可偽造性等安全特性；通過對方案通信開銷、執(zhí)行效率和隱私度進(jìn)行仿真實(shí)驗(yàn)，結(jié)果顯示文中方案優(yōu)于其它方案。因此，筆者所提出的方案對位置隱私保護(hù)相關(guān)安全領(lǐng)域的研究具有一定的理論意義和應(yīng)用價(jià)值。