一種Hilbert編碼的本地化位置隱私保護(hù)方法

晏 燕,董卓越,徐 飛,馮 濤

(蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院,甘肅 蘭州 730050)

1 引 言

來(lái)源豐富的位置數(shù)據(jù)為通信設(shè)備、交通工具、航天儀器、農(nóng)機(jī)設(shè)備等提供了高精度的位置服務(wù),推動(dòng)了汽車導(dǎo)航、飛機(jī)引航、船舶遠(yuǎn)洋等領(lǐng)域的長(zhǎng)足發(fā)展。基于位置的各種大數(shù)據(jù)服務(wù)更是被廣泛應(yīng)用到人口分布統(tǒng)計(jì)[1]、城市規(guī)劃管理[2]、智能交通調(diào)度[3]、疾病疫情管控[4]等熱門領(lǐng)域。尤其是在當(dāng)前新冠疫情頻發(fā)的關(guān)鍵時(shí)期,健康碼、通信行程卡、密切接觸者自查程序等一系列基于位置的大數(shù)據(jù)應(yīng)用服務(wù)為流行病學(xué)調(diào)查、疫情分布與統(tǒng)計(jì)分析、人員和物資調(diào)度等疫情防控工作提供了極大的便利[5-6]。

在各種基于位置的服務(wù)(Location-Based Service,LBS)中,用戶需要將自己的精確位置提交給服務(wù)供應(yīng)商來(lái)?yè)Q取相關(guān)的服務(wù)。然而,位置信息與個(gè)人隱私具有高度的關(guān)聯(lián)性,對(duì)位置信息的不當(dāng)采集、推理、分析和挖掘,可能導(dǎo)致用戶家庭住址、生活習(xí)慣、健康狀況、經(jīng)濟(jì)條件、社交關(guān)系等隱私信息泄露[7],危害相關(guān)設(shè)備的物理安全與通信安全[8],甚至威脅用戶合法權(quán)益和生命財(cái)產(chǎn)安全。因此,解決位置信息的隱私保護(hù)問(wèn)題已經(jīng)成為位置大數(shù)據(jù)業(yè)務(wù)發(fā)展最為迫切的任務(wù)。

傳統(tǒng)的位置信息采集過(guò)程默認(rèn)對(duì)用戶位置信息進(jìn)行收集的平臺(tái)是真實(shí)并可信的。然而,在實(shí)際應(yīng)用中,即使第三方數(shù)據(jù)收集平臺(tái)不會(huì)主動(dòng)竊取和泄露用戶的敏感信息,依然無(wú)法有效地保障其收集和存儲(chǔ)的數(shù)據(jù)安全。近年來(lái),各種大型網(wǎng)站和云平臺(tái)的數(shù)據(jù)泄露事件和黑客攻擊事件層出不窮,因此導(dǎo)致的經(jīng)濟(jì)損失和惡劣影響屢創(chuàng)新高。面對(duì)上述問(wèn)題,本地化差分隱私技術(shù)(Local Differential Privacy,LDP)[9-10]應(yīng)運(yùn)而生,它將數(shù)據(jù)的隱私化處理過(guò)程轉(zhuǎn)移到用戶終端,使得用戶能夠依據(jù)個(gè)人需求處理和保護(hù)敏感信息,打破了對(duì)可信第三方數(shù)據(jù)收集平臺(tái)的依賴。因此,基于本地化差分隱私模型開(kāi)展空間位置數(shù)據(jù)的隱私保護(hù)方法研究,能夠?yàn)榻K端用戶提供更加徹底的隱私保護(hù)效果,有望真正解決制約位置大數(shù)據(jù)業(yè)務(wù)發(fā)展的隱私保護(hù)問(wèn)題。

為了解決現(xiàn)有位置信息本地化差分隱私保護(hù)方法編碼機(jī)制復(fù)雜、通信代價(jià)高、位置服務(wù)質(zhì)量低下等問(wèn)題,筆者提出基于希爾伯特編碼的本地化差分隱私位置保護(hù)方法(LDPHE)。主要貢獻(xiàn)如下:

(1) 根據(jù)LBS服務(wù)的最小范圍對(duì)二維平面空間進(jìn)行均勻網(wǎng)格劃分,結(jié)合希爾伯特曲線的劃分階數(shù)構(gòu)建簡(jiǎn)單高效的空間索引結(jié)構(gòu)。

(2) 設(shè)計(jì)相應(yīng)的希爾伯特編碼機(jī)制,將用戶所處的網(wǎng)格位置進(jìn)行編碼,實(shí)現(xiàn)位置數(shù)據(jù)的降維。

(3) 結(jié)合本地化差分隱私模型對(duì)希爾伯特編碼結(jié)果進(jìn)行隨機(jī)響應(yīng),實(shí)現(xiàn)用戶端的位置隱私保護(hù)。

2 相關(guān)工作

為了實(shí)現(xiàn)對(duì)位置信息的隱私保護(hù),國(guó)內(nèi)外學(xué)者提出了位置匿名、假名、位置模糊等多種解決方案。GRUTESER等[11]最先將關(guān)系數(shù)據(jù)庫(kù)中的K匿名概念引入基于位置服務(wù)的隱私保護(hù)領(lǐng)域,提出了位置K匿名模型。為了實(shí)現(xiàn)位置K匿名,一些方法將用戶的準(zhǔn)確位置點(diǎn)泛化成至少包含K個(gè)用戶的區(qū)域,另一些方法則利用包含真實(shí)位置在內(nèi)的大量冗余位置信息代替原始位置。GEDIK等[12]為L(zhǎng)BS服務(wù)的位置隱私保護(hù)設(shè)計(jì)了一種可擴(kuò)展的架構(gòu),該架構(gòu)包括開(kāi)發(fā)個(gè)性化位置匿名的模型和一套位置擾動(dòng)算法。GEDIK等[13]提出時(shí)空隱藏算法CliqueCloak,可以為用戶位置實(shí)現(xiàn)所需的指定匿名級(jí)別并保持所需匿名的最大時(shí)間和空間容差。NI等[14]在密集區(qū)域和稀疏區(qū)域分別構(gòu)造匿名域。SHEN等[15]提出基于局部敏感哈希算法的位置隱私保護(hù)方法,用乘客周圍的一組興趣點(diǎn)來(lái)代替用戶精確位置的GPS坐標(biāo)。宋成等[16]首先在匿名區(qū)域中選取2K個(gè)合理假位置,然后根據(jù)位置熵從中篩選出較優(yōu)的K-1個(gè)位置達(dá)到更好的匿名效果。ZHANG等[17]結(jié)合不規(guī)則多邊形思想生成多邊形匿名區(qū)域,并通過(guò)設(shè)置密度參數(shù)生成假位置。LIU等[18]考慮到攻擊者可能使用數(shù)據(jù)分析和爬蟲(chóng)等輔助信息來(lái)確定大致位置,因而基于概率密度函數(shù)生成虛擬的位置信息,實(shí)現(xiàn)LBS中具有隱私區(qū)域感知的用戶K匿名性。WANG等[19]基于用戶隱私要求和實(shí)時(shí)位置信息,首先采用貪婪策略生成安全的匿名區(qū)域,然后計(jì)算不同時(shí)間匿名用戶集的交集,利用動(dòng)態(tài)假名機(jī)制更新用戶身份信息。上述方法雖然可以保護(hù)用戶精確位置信息不被泄露,但卻使得位置服務(wù)質(zhì)量嚴(yán)重下降,增大了服務(wù)器的查詢處理開(kāi)銷。當(dāng)攻擊者掌握用戶位置的背景知識(shí)時(shí),上述方法的安全性沒(méi)有保障。

基于LDP模型對(duì)移動(dòng)終端和用戶位置進(jìn)行保護(hù),可以實(shí)現(xiàn)更加高效徹底的位置隱私保護(hù),杜絕因位置信息和軌跡泄露而導(dǎo)致的其他隱私風(fēng)險(xiǎn)。HAYASHIDA等[20]在發(fā)送用戶真實(shí)位置的同時(shí)基于LDP隨機(jī)生成并發(fā)送多個(gè)假位置,以實(shí)現(xiàn)對(duì)位置的混淆和隱私保護(hù)。CHEN等[21]提出的空間數(shù)據(jù)聚合方法通過(guò)Hadamard矩陣的隨機(jī)響應(yīng)機(jī)制實(shí)現(xiàn)位置數(shù)據(jù)的LDP保護(hù)。高志強(qiáng)等[22]以最強(qiáng)信號(hào)對(duì)應(yīng)的信息采集點(diǎn)代表用戶的位置,采用多階段隨機(jī)應(yīng)答機(jī)制實(shí)現(xiàn)滿足LDP模型的位置數(shù)據(jù)采集,保證不可信數(shù)據(jù)采集者利用非原始位置數(shù)據(jù)仍可以實(shí)現(xiàn)數(shù)據(jù)統(tǒng)計(jì)特征分析。ZHAO等[23]提出自頂向下的概率劃分算法來(lái)產(chǎn)生滿足LDP的位置記錄數(shù)據(jù),使用分區(qū)樹(shù)模型來(lái)提取位置記錄的基本信息,利用自適應(yīng)用戶分配方案和一系列優(yōu)化技術(shù)來(lái)提高位置數(shù)據(jù)的準(zhǔn)確性。HONG等[24]根據(jù)LDP預(yù)算和區(qū)域大小設(shè)計(jì)擾動(dòng)機(jī)制,對(duì)于每個(gè)用戶從一個(gè)二維聯(lián)合概率分布輸出一個(gè)擾動(dòng)位置。WANG等[25]利用希爾伯特曲線將用戶位置映射到一維空間中,再向其中加入拉普拉斯噪聲并將擾動(dòng)后的位置作為用戶的真實(shí)位置提交給服務(wù)提供商。張嘯劍等[26]提出的本地化差分隱私空間范圍查詢方法將二維空間進(jìn)行均勻網(wǎng)格分割,利用四叉樹(shù)結(jié)構(gòu)對(duì)所有網(wǎng)格區(qū)域進(jìn)行索引;用戶結(jié)合服務(wù)器共享的四分樹(shù)副本進(jìn)行位置編碼和層次隨機(jī)采樣,利用優(yōu)化隨機(jī)應(yīng)答機(jī)制對(duì)采樣層次中的節(jié)點(diǎn)進(jìn)行本地?cái)_動(dòng)處理;從而實(shí)現(xiàn)位置信息的編碼和LDP保護(hù)。霍崢等[27]提出的位置數(shù)據(jù)眾包采集方法通過(guò)構(gòu)造維諾圖對(duì)路網(wǎng)空間進(jìn)行分割。DAI等[28]提出基于LDP的空間眾包隱私感知框架,首先利用多元拉普拉斯方法對(duì)眾包參與者的位置進(jìn)行加噪處理,然后將噪聲點(diǎn)重新映射為位置,從而實(shí)現(xiàn)對(duì)位置隱私的本地化差分隱私保護(hù)。LUO等[29]提出基于LDP的車聯(lián)網(wǎng)數(shù)據(jù)隱私保護(hù)方案,將車載終端的位置數(shù)據(jù)通過(guò)離散化和隨機(jī)響應(yīng)方法進(jìn)行擾動(dòng),并通過(guò)安全通道發(fā)送到車聯(lián)網(wǎng)數(shù)據(jù)中心以支持對(duì)后續(xù)車聯(lián)網(wǎng)安全狀況的分析。

3 本地化差分隱私模型

在實(shí)際應(yīng)用中,即使數(shù)據(jù)收集平臺(tái)不會(huì)越權(quán)采集或者違規(guī)使用用戶的敏感信息,攻擊者仍然可能通過(guò)系統(tǒng)漏洞和各種攻擊方式對(duì)數(shù)據(jù)進(jìn)行竊取或者破壞。為了避免不可信第三方數(shù)據(jù)收集平臺(tái)導(dǎo)致的用戶隱私泄露,LDP模型充分考慮任意攻擊者的背景知識(shí),并對(duì)隱私保護(hù)程度進(jìn)行量化;每個(gè)數(shù)據(jù)產(chǎn)生者能夠獨(dú)立地對(duì)個(gè)體數(shù)據(jù)進(jìn)行隱私化處理,再將處理后的數(shù)據(jù)發(fā)送給數(shù)據(jù)收集者(如圖1所示)。原來(lái)由數(shù)據(jù)收集平臺(tái)承擔(dān)的集中化數(shù)據(jù)隱私保護(hù)過(guò)程被前置轉(zhuǎn)移到每個(gè)數(shù)據(jù)產(chǎn)生者,使其能夠單獨(dú)地處理和保護(hù)個(gè)人敏感信息,進(jìn)行更加徹底或符合個(gè)性化需求的隱私保護(hù)[30]。因此不再需要可信第三方的介入,同時(shí)也免除了不可信第三方數(shù)據(jù)收集者可能帶來(lái)的隱私攻擊。

圖1 基于本地化差分隱私的數(shù)據(jù)處理框架

3.1 本地化差分隱私

定義1(ε-本地化差分隱私[9-10]) 給定一個(gè)隱私算法M及其定義域T和值域W,若算法M對(duì)任意兩個(gè)數(shù)據(jù)t,t*∈T,得到相同的輸出結(jié)果S∈W滿足下列不等式,則算法M滿足ε-本地化差分隱私。

Pr[M(t)=S]≤eε×Pr[M(t*)=S] 。

(1)

定義1表明:本地化差分隱私模型通過(guò)控制兩個(gè)輸入數(shù)據(jù)在輸出結(jié)果上的相似性,從而保證算法滿足ε-本地化差分隱私。將本地化差分隱私模型應(yīng)用于位置隱私保護(hù)時(shí),根據(jù)隱私算法M的某個(gè)輸出結(jié)果,無(wú)法推斷出用戶的原始位置是t還是t*。定義1中的ε稱為隱私預(yù)算,其取值越小,隱私算法M的保護(hù)程度越高。

定理2(并行組合性[30]) 給定位置數(shù)據(jù)集合T,可以將其劃分為n個(gè)互不相交的子集T={T1,…,Tn};設(shè)M為滿足ε-本地化差分隱私的任一算法,則算法M在{T1,…,Tn}上滿足ε-本地化差分隱私。

3.2 隨機(jī)響應(yīng)機(jī)制

數(shù)據(jù)收集者借助隨機(jī)響應(yīng)機(jī)制對(duì)接收到的n個(gè)用戶的回答進(jìn)行統(tǒng)計(jì)分析。假設(shè)統(tǒng)計(jì)結(jié)果中答案為1的用戶數(shù)量為n1,答案為0的用戶數(shù)量為n-n1,可以通過(guò)式(2)對(duì)兩種答案的用戶比例進(jìn)行估計(jì):

(2)

其中,π為用戶數(shù)量的真實(shí)比例。

根據(jù)式(2)得到的統(tǒng)計(jì)比例并非真實(shí)比例的無(wú)偏估計(jì),因此,需要對(duì)統(tǒng)計(jì)結(jié)果進(jìn)行校正。構(gòu)建式(3)所示的似然函數(shù),并得到用戶數(shù)量比例π的極大似然估計(jì)如式(4)所示:

(3)

(4)

進(jìn)而可以根據(jù)式(5)得到校正后用戶數(shù)量的估計(jì)值E:

(5)

綜上所述,用戶通過(guò)隨機(jī)應(yīng)答保護(hù)了自身隱私;而根據(jù)參與回答的總用戶數(shù)量n、答案為1的用戶數(shù)量n1和擾動(dòng)概率p,可以準(zhǔn)確地估計(jì)出某類用戶的數(shù)量,保證了數(shù)據(jù)的可用性。

4 基于希爾伯特編碼的本地化位置隱私保護(hù)方法

本地化差分隱私位置保護(hù)通過(guò)在用戶端對(duì)原始位置的擾動(dòng)實(shí)現(xiàn)用戶位置隱私保護(hù),最直觀的方法是在整個(gè)空間值域中對(duì)用戶原始位置進(jìn)行隨機(jī)響應(yīng)。然而,大規(guī)模的位置空間值域通常較大,擾動(dòng)后的位置可能與原始位置相距甚遠(yuǎn),導(dǎo)致此類方法獲得的位置數(shù)據(jù)可用性較差。一些研究將空間值域進(jìn)行網(wǎng)格或者樹(shù)型結(jié)構(gòu)劃分,對(duì)用戶所處的劃分區(qū)域進(jìn)行編碼和隨機(jī)響應(yīng),雖然提高了位置數(shù)據(jù)的可用性,但是隨著劃分粒度的提高,算法的運(yùn)行效率也大幅降低。

筆者提出基于希爾伯特編碼的本地化差分隱私位置保護(hù)方法。首先由服務(wù)器端根據(jù)二維空間覆蓋范圍確定劃分粒度,將空間值域進(jìn)行均勻網(wǎng)格劃分,并對(duì)所有網(wǎng)格對(duì)應(yīng)的區(qū)域進(jìn)行希爾伯特編碼后發(fā)布給每個(gè)用戶;接著,在使用LBS類服務(wù)時(shí),用戶根據(jù)自身位置和服務(wù)器下發(fā)的參數(shù)確定所處的網(wǎng)格區(qū)域,查找相應(yīng)的希爾伯特編碼并采用隨機(jī)響應(yīng)擾動(dòng)機(jī)制進(jìn)行擾動(dòng)處理,將擾動(dòng)后的編碼代替原始經(jīng)緯度信息提交給服務(wù)器端;最后,服務(wù)器端利用希爾伯特解碼算法對(duì)收集到的所有擾動(dòng)編碼進(jìn)行還原,并按照初始網(wǎng)格劃分結(jié)構(gòu)對(duì)用戶數(shù)量和分布密度進(jìn)行統(tǒng)計(jì)分析。

4.1 二維空間的網(wǎng)格劃分與希爾伯特編碼

網(wǎng)格劃分是空間結(jié)構(gòu)分割的常用方法,被廣泛應(yīng)用于交通量統(tǒng)計(jì)和LBS類應(yīng)用中。根據(jù)位置數(shù)據(jù)范圍計(jì)數(shù)查詢服務(wù)的最小尺度將位置信息覆蓋的二維空間進(jìn)行均勻網(wǎng)格劃分,并采用希爾伯特編碼方法[32]對(duì)所有網(wǎng)格進(jìn)行編碼轉(zhuǎn)換,實(shí)現(xiàn)位置數(shù)據(jù)的降維。

希爾伯特曲線能夠?qū)⑽恢米鴺?biāo)從二維空間映射到一維編碼,并且保證在空間值域上相鄰的兩個(gè)點(diǎn)映射到一維編碼后也保持相鄰關(guān)系。圖2展示了一階希爾伯特曲線的效果,它將一個(gè)二維空間均勻劃分為4個(gè)網(wǎng)格并按照象限排序,每個(gè)網(wǎng)格中的數(shù)字編號(hào)是其所在網(wǎng)格區(qū)域的唯一標(biāo)識(shí)。在構(gòu)造如圖3所示的二階希爾伯特曲線時(shí),首先將一階劃分的每個(gè)象限再次均勻劃分為4個(gè)子塊;上層象限(1、2象限)的二階子塊內(nèi),希爾伯特曲線保持與一階相同的開(kāi)口方向;下層左側(cè)象限(0象限)的二階子塊內(nèi),希爾伯特曲線由一階曲線順時(shí)針旋轉(zhuǎn)90°得到;下層右側(cè)象限(3象限)的二階子塊內(nèi),希爾伯特曲線由一階曲線逆時(shí)針旋轉(zhuǎn)90°得到;最后,按照劃分階數(shù)和象限依次連接各個(gè)子塊,保證希爾伯特曲線的連通性質(zhì)。依此類推,可以通過(guò)i階希爾伯特曲線的子塊分割和子塊內(nèi)曲線旋轉(zhuǎn)得到(i+1)階的希爾伯特曲線。

圖2 一階Hilbert曲線示意圖

圖3 二階Hilbert曲線示意圖

定義2(希爾伯特曲線劃分階數(shù)) 對(duì)于值域?yàn)镈om(G)的二維平面空間范圍,根據(jù)式(6)確定其均勻網(wǎng)格劃分粒度N,其希爾伯特曲線劃分階數(shù)h可以按照式(7)計(jì)算:

N=(Dom(G)/10)1/2,

(6)

(7)

定義3(希爾伯特編碼轉(zhuǎn)換) 對(duì)于希爾伯特劃分階數(shù)為h,序號(hào)為(i,j)0≤i,j≤N的網(wǎng)格區(qū)域,用Q表示該區(qū)域所處的象限。設(shè)w=2h-1,可以根據(jù)下式計(jì)算該階網(wǎng)格區(qū)域編碼轉(zhuǎn)換后的序號(hào)(i′,j′):

(8)

算法1均勻網(wǎng)格劃分與希爾伯特編碼算法。

輸入:二維空間值域G;

輸出:所有網(wǎng)格的希爾伯特編碼Z。

① 根據(jù)公式(6)確定二維空間值域G的劃分粒度N;

② 根據(jù)劃分粒度N將二維空間劃分為均勻網(wǎng)格GN×N;

③ 按照式(7)確定希爾伯特曲線劃分階數(shù)h;

④ 初始化希爾伯特編碼Z={};

⑤ for each gird(i,j)0≤i,j≤Ndo/*對(duì)每個(gè)網(wǎng)格區(qū)域進(jìn)行希爾伯特編碼*/

⑥U={};

⑦ forh≠0 do/*按照階數(shù)遞增順序進(jìn)行網(wǎng)格希爾伯特編碼*/

⑧ 確定網(wǎng)格(i,j)所處的象限Q;

⑨U←Q;/*將Q值追加到象限序列U中*/

圖4以Storage數(shù)據(jù)集為例展示其三階希爾伯特曲線劃分與編碼的過(guò)程,某用戶所處的位置P位于序號(hào)為(3,3)的網(wǎng)格內(nèi)。在一階希爾伯特曲線劃分中,該用戶所處的網(wǎng)格屬于0號(hào)象限,所以其第一位希爾伯特編碼為0(對(duì)應(yīng)二進(jìn)制數(shù)00);根據(jù)式(8)得到下一階的序號(hào)為(3,3),在二階劃分范圍內(nèi)屬于2號(hào)象限,所以其第二位希爾伯特編碼為2(對(duì)應(yīng)二進(jìn)制數(shù)10);依次得到第三階序號(hào)為(1,1),對(duì)應(yīng)三階劃分范圍的2號(hào)象限,所以第三位希爾伯特編碼為2(對(duì)應(yīng)二進(jìn)制數(shù)10)。因此,最終得到用戶所處網(wǎng)格的希爾伯特編碼為{001010}。

圖4 均勻網(wǎng)格劃分

4.2 基于本地化差分隱私的隨機(jī)響應(yīng)機(jī)制

為了實(shí)現(xiàn)對(duì)用戶位置信息的本地化差分隱私保護(hù),所提方法將用戶所處網(wǎng)格的希爾伯特編碼進(jìn)行隨機(jī)響應(yīng)擾動(dòng)后提交給服務(wù)器端。

定義4(希爾伯特編碼隨機(jī)響應(yīng)) 對(duì)于算法1得到的用戶所處網(wǎng)格的希爾伯特編碼Z,隨機(jī)選擇其中的某一位并按照式(9)所示的概率函數(shù)進(jìn)行隨機(jī)響應(yīng)擾動(dòng):

(9)

算法2本地化差分隱私隨機(jī)響應(yīng)算法。

輸入:服務(wù)器端發(fā)送的二維空間值域G、希爾伯特曲線劃分階數(shù)h和所有網(wǎng)格的希爾伯特編碼Z;用戶ui的原始位置li;隱私預(yù)算ε;

輸出:用戶ui的擾動(dòng)位置編碼Z′i。

① 用戶ui根據(jù)服務(wù)器端發(fā)送的二維空間值域G和希爾伯特曲線劃分階數(shù)h,結(jié)合自身原始位置li確定所處的網(wǎng)格序號(hào)(i,j);

② 用戶ui根據(jù)所處的網(wǎng)格序號(hào)(i,j)從服務(wù)器端發(fā)送的所有網(wǎng)格希爾伯特編碼Z中提取自己所處網(wǎng)格的希爾伯特編碼Zi;

③ 從Zi中隨機(jī)選擇某一位bj;

④ ifbj=1 then

⑤ Pr[Z′i(b′j)=1|Zi(bj)]=exp(ε)/(1+exp(ε));

⑥ else

⑦ Pr[Z′i(b′j)=1|Zi(bj)]=1/(1+exp(ε));

⑧ end if

⑨ returnZ′i。

推論1根據(jù)算法2得到的用戶擾動(dòng)位置編碼滿足ε-本地化差分隱私。

證明:假設(shè)Vi是對(duì)用戶ui所處網(wǎng)格區(qū)域按照希爾伯特編碼算法(算法1)生成的向量,編碼長(zhǎng)度|Vi|=2h,其中h為希爾伯特曲線劃分階數(shù);Zi是根據(jù)算法2進(jìn)行隨機(jī)響應(yīng)擾動(dòng)后的輸出結(jié)果。根據(jù)本地化差分隱私的并行組合特性(定理2),有以下等式成立:

Pr[Zi|Vi]=Pr[Zi(zj)=1|Vi(vj)] ,

同理,給定V′i有以下等式成立:

Pr[Zi|V′i]=Pr[Zi(zj)=1|V′i(vj)] ,

則

根據(jù)本地化差分隱私的定義可得,算法2得到的用戶擾動(dòng)位置編碼滿足ε-本地化差分隱私。

4.3 服務(wù)器端希爾伯特解碼與統(tǒng)計(jì)分析

服務(wù)器端收集到所有用戶的希爾伯特編碼擾動(dòng)值后,首先根據(jù)希爾伯特解碼算法將擾動(dòng)后的編碼值還原為二維空間值域中的網(wǎng)格序號(hào),然后按照初始網(wǎng)格劃分結(jié)構(gòu)對(duì)用戶數(shù)量和分布密度進(jìn)行統(tǒng)計(jì)分析。

定義5(希爾伯特解碼轉(zhuǎn)換) 劃分階數(shù)為h的希爾伯特曲線對(duì)應(yīng)的編碼長(zhǎng)度為2h,將希爾伯特編碼的每?jī)晌晦D(zhuǎn)化為四進(jìn)制后得到編碼Z*。設(shè)編碼Z*的最后一位為r,可以按照式(10)恢復(fù)其對(duì)應(yīng)的網(wǎng)格序號(hào)(i′,j′)。令v=2,通過(guò)式(11)計(jì)算更新后的網(wǎng)格序號(hào)(i*,j*):

(10)

(11)

算法3希爾伯特解碼與統(tǒng)計(jì)算法。

輸入:所有用戶的希爾伯特編碼Z′={Z′1,Z′2,…,Z′i};

輸出:用戶數(shù)量分布密度IN×N。

① 初始化IN×N={};

② for eachZ′ido

⑥ 根據(jù)式(10)確定初始網(wǎng)格序號(hào)(i′,j′);

⑦v=2;

仍以圖4所示的位置數(shù)據(jù)集合為例。當(dāng)服務(wù)器端接收到某用戶發(fā)送的希爾伯特編碼Z′={001010}時(shí),首先將編碼的每?jī)晌晦D(zhuǎn)化為四進(jìn)制得Z*={0,2,2},將最后一位賦值給r=2,并由式(10)得到第三階劃分范圍內(nèi)對(duì)應(yīng)的序號(hào)為(1,1)。然后循環(huán)將每一階的編碼進(jìn)行序號(hào)轉(zhuǎn)換:當(dāng)v=2,r=2時(shí),由式(11)得到第二階劃分范圍內(nèi)對(duì)應(yīng)的序號(hào)為(3,3);當(dāng)v=4,r=0時(shí),由式(11)得到第一階劃分范圍內(nèi)對(duì)應(yīng)的序號(hào)為(3,3)。所以,最終確定該用戶所處位置對(duì)應(yīng)網(wǎng)格序號(hào)為(3,3),實(shí)現(xiàn)了服務(wù)器端對(duì)用戶位置范圍的準(zhǔn)確恢復(fù)。

5 實(shí)驗(yàn)結(jié)果與分析

為了對(duì)筆者提出的希爾伯特編碼本地化差分隱私位置保護(hù)方法進(jìn)行綜合評(píng)估和分析,從位置數(shù)據(jù)的可用性、服務(wù)器端統(tǒng)計(jì)分析精度、算法的運(yùn)行效率等方面,將文中方法與其他本地化差分隱私位置保護(hù)方法進(jìn)行比較。為了公平起見(jiàn),選擇同樣以位置空間結(jié)構(gòu)劃分和本地化差分隱私隨機(jī)響應(yīng)為基礎(chǔ)的PSDA算法[21]、LDPart算法[23]、GT-R算法[26]進(jìn)行比較分析。

實(shí)驗(yàn)數(shù)據(jù)分別選用由紐約出租車管理委員會(huì)提供的乘車記錄數(shù)據(jù)集Yellow_tripdata(2015年1月1日)、日本東京的LBSNs簽到數(shù)據(jù)集,以及由infochimps提供的美國(guó)48個(gè)州的地標(biāo)位置信息集Landmark。實(shí)驗(yàn)平臺(tái)選用8核AMD Ryzen 7 4700U(2.00 GHz)、16 GB內(nèi)存、Win10系統(tǒng)。所有算法程序均采用Python 3.8實(shí)現(xiàn)。各個(gè)實(shí)驗(yàn)數(shù)據(jù)集的具體細(xì)節(jié)與可視化結(jié)果分別如表1和圖5所示。

表1 數(shù)據(jù)集屬性

(a) Yellow_tripdata數(shù)據(jù)集可視化結(jié)果

5.1 位置數(shù)據(jù)的可用性

(12)

其中,ρ=0.001×|T|,|T|表示實(shí)驗(yàn)位置數(shù)據(jù)集合的大小。實(shí)驗(yàn)過(guò)程中設(shè)置隱私預(yù)算參數(shù)ε的取值范圍為0.1～1。查詢范圍q分別覆蓋實(shí)驗(yàn)數(shù)據(jù)集對(duì)應(yīng)二維空間的10%、20%、40%、50%。每種類型的查詢區(qū)域隨機(jī)生成500個(gè),以確定相對(duì)誤差的平均值。

圖6至圖8用對(duì)數(shù)坐標(biāo)展示了各種算法在不同數(shù)據(jù)集合上的相對(duì)誤差比較結(jié)果。在相同的實(shí)驗(yàn)數(shù)據(jù)集合上,各種算法的相對(duì)誤差都隨著隱私預(yù)算ε的增大而逐漸減小,其原因是隱私預(yù)算ε的增大使得隨機(jī)響應(yīng)的擾動(dòng)程度變小,因而擾動(dòng)后的位置與真實(shí)位置之間的誤差也減小了。

(a) 查詢范圍10%

(a) 查詢范圍10%

(a) 查詢范圍10%

在相同的實(shí)驗(yàn)數(shù)據(jù)集合上,隨著查詢范圍從小到大的增加,各種算法的相對(duì)誤差也有不同程度的下降。其原因在于當(dāng)查詢范圍較小時(shí),一些真實(shí)位置屬于查詢范圍內(nèi)的用戶在位置擾動(dòng)之后脫離了當(dāng)前的范圍,導(dǎo)致范圍計(jì)數(shù)查詢的相對(duì)誤差較高;隨著查詢范圍的增大,用戶擾動(dòng)位置脫離查詢范圍的情況減少,因此,范圍計(jì)數(shù)查詢的相對(duì)誤差也減小。

在相同數(shù)據(jù)集和查詢范圍下具體比較各種位置擾動(dòng)算法的相對(duì)誤差:LDPart和PSDA算法的查詢精度最差,LDPHE算法在大多數(shù)情況下優(yōu)于GT-R算法。其原因在于:對(duì)二維空間進(jìn)行相同粒度的網(wǎng)格劃分之后,LDPart算法需要對(duì)網(wǎng)格編碼的每一位都進(jìn)行隨機(jī)響應(yīng)擾動(dòng),因此擾動(dòng)后的網(wǎng)格編碼可能距離用戶原始網(wǎng)格較遠(yuǎn)。PSDA算法構(gòu)建阿達(dá)馬矩陣并對(duì)其中的一行進(jìn)行隨機(jī)響應(yīng)擾動(dòng),擾動(dòng)范圍相比LDPart算法有所下降,因而范圍計(jì)數(shù)查詢精度有所提高。GT-R算法使用四叉樹(shù)結(jié)構(gòu)對(duì)所有網(wǎng)格進(jìn)行索引,并隨機(jī)抽取四叉樹(shù)的某一層節(jié)點(diǎn)進(jìn)行隨機(jī)響應(yīng)擾動(dòng),因?yàn)闃?shù)結(jié)構(gòu)中同一層節(jié)點(diǎn)之間具有空間上的鄰近關(guān)系,所以擾動(dòng)范圍被進(jìn)一步優(yōu)化在空間鄰近的網(wǎng)格內(nèi),范圍計(jì)數(shù)查詢精度得以改善。而本文提出的LDPHE算法借助高階希爾伯特曲線進(jìn)行編碼和隨機(jī)響應(yīng),希爾伯特曲線良好的空間聚類特性使得擾動(dòng)后的網(wǎng)格位置不會(huì)過(guò)多的偏離原有網(wǎng)格,因此獲得了很好的范圍計(jì)數(shù)查詢精度。隱私預(yù)算ε的值越小,隨機(jī)響應(yīng)造成的擾動(dòng)程度越大,LDPHE算法在范圍計(jì)數(shù)查詢精度方面的優(yōu)勢(shì)將越加明顯。

5.2 服務(wù)器端統(tǒng)計(jì)分析精度

為了驗(yàn)證文中提出的LDPHE算法能夠保證服務(wù)器端位置數(shù)據(jù)統(tǒng)計(jì)分析的精度,根據(jù)空間劃分粒度對(duì)服務(wù)器端接受的用戶擾動(dòng)位置進(jìn)行區(qū)域密度統(tǒng)計(jì)分析,并將所有算法的區(qū)域密度統(tǒng)計(jì)結(jié)果與真實(shí)結(jié)果進(jìn)行比較。

圖9至圖11對(duì)比了不同原始位置數(shù)據(jù)經(jīng)過(guò)各種算法擾動(dòng)后的區(qū)域密度統(tǒng)計(jì)結(jié)果,從中不難發(fā)現(xiàn)本文所提LDPHE算法產(chǎn)生的擾動(dòng)位置在區(qū)域密度統(tǒng)計(jì)結(jié)果上更接近真實(shí)數(shù)據(jù)集合的統(tǒng)計(jì)分布特性。LDPart算法對(duì)用戶所處網(wǎng)格位置編碼的每一位都進(jìn)行擾動(dòng),導(dǎo)致擾動(dòng)結(jié)果與真實(shí)結(jié)果的相差范圍很大,在數(shù)據(jù)量較小的Yellow_tripdata數(shù)據(jù)集上尚能保持與原始統(tǒng)計(jì)分布近似的特性,在數(shù)據(jù)量較大的Tokyo數(shù)據(jù)集和Landmark數(shù)據(jù)集上已經(jīng)完全丟失原有統(tǒng)計(jì)分布特性,性能惡化明顯。PSDA算法選擇阿達(dá)馬矩陣中的一行進(jìn)行隨機(jī)響應(yīng)擾動(dòng),GT-R算法隨機(jī)抽取四叉樹(shù)索引結(jié)構(gòu)的某一層節(jié)點(diǎn)進(jìn)行隨機(jī)響應(yīng)擾動(dòng),因此它們的擾動(dòng)結(jié)果與真實(shí)結(jié)果的偏差范圍比LDPart算法明顯下降,在各種位置數(shù)據(jù)集合上都較好地保持了與原始統(tǒng)計(jì)分布近似的特性,產(chǎn)生的偏差較為均勻地分布在所有空間范圍內(nèi)。文中提出的LDPHE算法對(duì)用戶所處網(wǎng)格位置進(jìn)行編碼和解碼操作,隨機(jī)響應(yīng)只發(fā)生在希爾伯特編碼的某一位上,借助希爾伯特曲線良好的空間聚類特性使得擾動(dòng)后的網(wǎng)格位于原有網(wǎng)格附近,大量用戶的隨機(jī)響應(yīng)相互抵消了統(tǒng)計(jì)結(jié)果中的偏差,使得服務(wù)器端的區(qū)域密度統(tǒng)計(jì)結(jié)果在擾動(dòng)前后保持了較好的一致性。上述結(jié)果證明文中算法產(chǎn)生的擾動(dòng)位置能夠保證服務(wù)器端統(tǒng)計(jì)分布結(jié)果的準(zhǔn)確性,為后續(xù)位置大數(shù)據(jù)的分析挖掘和發(fā)布使用提供更好的質(zhì)量。

(a) 原始數(shù)據(jù)區(qū)域密度統(tǒng)計(jì)

(a) 原始數(shù)據(jù)區(qū)域密度統(tǒng)計(jì)

(a) 原始數(shù)據(jù)區(qū)域密度統(tǒng)計(jì)

5.3 算法效率分析

為了驗(yàn)證筆者提出的LDPHE算法的效率,將文中算法的運(yùn)行時(shí)間(不包括數(shù)據(jù)讀取時(shí)間)和上行通信數(shù)據(jù)量(用戶端向服務(wù)器端發(fā)送的數(shù)據(jù)量)與PSDA、LDPart、GT-R算法進(jìn)行比較分析。為了公平起見(jiàn),在相同數(shù)據(jù)集合上各種算法采用相同的初始網(wǎng)格劃分粒度N,每種算法重復(fù)運(yùn)行500次以確定運(yùn)行時(shí)間的平均值。

(a) Yellow_tripdata數(shù)據(jù)集運(yùn)行時(shí)間

表2 各種算法的上行數(shù)據(jù)量

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

物聯(lián)網(wǎng)、智能交通、基于位置的服務(wù)、移動(dòng)群智感知等大數(shù)據(jù)的熱門應(yīng)用領(lǐng)域時(shí)刻都在采集和使用用戶的位置信息,在給用戶帶來(lái)前所未有的便捷性的同時(shí),涉及的位置隱私保護(hù)問(wèn)題也引起了廣泛的關(guān)注。本地化差分隱私位置保護(hù)將位置信息的隱私化處理過(guò)程轉(zhuǎn)移到用戶終端,打破了對(duì)可信第三方平臺(tái)的依賴,能夠?yàn)榻K端用戶提供更加徹底的隱私保護(hù)效果。為了解決現(xiàn)有本地化差分隱私位置保護(hù)方法編碼機(jī)制復(fù)雜、位置數(shù)據(jù)可用性不足等問(wèn)題,文中提出一種基于希爾伯特編碼的本地化差分隱私位置保護(hù)方法。按照均勻網(wǎng)格結(jié)構(gòu)對(duì)二維平面空間進(jìn)行劃分,通過(guò)希爾伯特編碼實(shí)現(xiàn)位置數(shù)據(jù)的降維。用戶端根據(jù)本地化差分隱私模型對(duì)自身所處網(wǎng)格的希爾伯特編碼進(jìn)行隨機(jī)響應(yīng)擾動(dòng)處理;服務(wù)器端根據(jù)希爾伯特解碼算法對(duì)接收的擾動(dòng)位置編碼進(jìn)行恢復(fù)和統(tǒng)計(jì)分析。所提算法被證明滿足ε-本地化差分隱私,并通過(guò)真實(shí)位置數(shù)據(jù)集合驗(yàn)證了所提算法在位置數(shù)據(jù)可用性和算法效率方面的優(yōu)勢(shì)。