基于偽隨機(jī)數(shù)加密的保護(hù)位置隱私近鄰查詢方法

張 峰，倪巍偉

（東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 211189；東南大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)與信息集成教育部重點(diǎn)實(shí)驗(yàn)室，南京 211189）

1 引 言

空間定位與移動(dòng)通信技術(shù)的發(fā)展促進(jìn)了位置服務(wù)（LBS，location based service）的普及，人們能夠方便地享受關(guān)于自身位置的一些近鄰查詢服務(wù)，諸如查找“距我最近的餐廳”，“我附近最近的幾個(gè)加油站”等［1］．然而，位置服務(wù)需要查詢者向服務(wù)提供方共享其位置信息，存在隱私泄露風(fēng)險(xiǎn)，包括位置服務(wù)提供商在內(nèi)的潛在攻擊者可以利用用戶位置和查詢內(nèi)容鑒別查詢者身份，進(jìn)而獲取其隱私信息．保護(hù)位置隱私需要，用戶希望在不向服務(wù)提供方共享精確位置的同時(shí)獲得位置服務(wù)．近年來(lái)，保護(hù)位置隱私近鄰查詢得到了研究者的持續(xù)關(guān)注．

目前，保護(hù)位置隱私近鄰查詢主要采用空間混淆［2－6］、數(shù)據(jù)變換［7－8］、假位置擾動(dòng)［9－11］及隱私信息檢索（PIR，Private Information Retrieval）技術(shù)［12－15］．空間混淆的原理是可信第三方接受查詢者查詢請(qǐng)求并將查詢者位置隱藏為泛化區(qū)域，之后將隱藏后位置及查詢請(qǐng)求提交LBS服務(wù)器處理，服務(wù)器將關(guān)于泛化區(qū)域的查詢結(jié)果反饋可信第三方篩選出目標(biāo)結(jié)果并返回查詢者．該技術(shù)主要缺點(diǎn)是可信第三方易成為系統(tǒng)瓶頸、服務(wù)器端處理較復(fù)雜．假位置擾動(dòng)采用發(fā)起一系列關(guān)于假位置的查詢，查詢者通過(guò)分析假位置、查詢結(jié)果與真實(shí)位置的幾何位置關(guān)系，篩選目標(biāo)結(jié)果，存在保護(hù)強(qiáng)度不足以及假位置選擇困難等問(wèn)題．?dāng)?shù)據(jù)變換技術(shù)將查詢者位置及POI坐標(biāo)映射到另一個(gè)數(shù)據(jù)空間，實(shí)現(xiàn)保護(hù)位置隱私查詢．該技術(shù)主要存在查詢準(zhǔn)確性較低的缺陷．

相較上述三種技術(shù)，PIR技術(shù)能夠提供更高的位置隱私保護(hù)強(qiáng)度［13］．不同于傳統(tǒng)位置隱私保護(hù)技術(shù)多數(shù)致力于客戶端和服務(wù)器通信安全的保護(hù)，PIR還關(guān)注服務(wù)器端的安全，用戶可以檢索一個(gè)不可信的服務(wù)器上的任意數(shù)據(jù)項(xiàng)而無(wú)需暴露用戶檢索的數(shù)據(jù)項(xiàng)信息．目前所采用的PIR技術(shù)多數(shù)基于計(jì)算能力，即假設(shè)攻擊者不具有計(jì)算求解某個(gè)難題的能力而保證用戶對(duì)感興趣數(shù)據(jù)的私密訪問(wèn)．盡管PIR技術(shù)具有隱私保護(hù)強(qiáng)度高、無(wú)需可信第三方以及查詢結(jié)果準(zhǔn)確的特點(diǎn)．但現(xiàn)有基于該技術(shù)的查詢方法多數(shù)存在預(yù)處理時(shí)間長(zhǎng)、查詢效率較低的不足：

（1）基于PIR的查詢方法通常針對(duì)所定義的攻擊模式，制定查詢計(jì)劃，導(dǎo)致預(yù)處理時(shí)間增加，且服務(wù)器端POI一旦發(fā)生改變，查詢計(jì)劃也需修改，動(dòng)態(tài)性較差．

（2）保護(hù)位置隱私查詢通常生成一個(gè)包含真實(shí)查詢結(jié)果的候選集．現(xiàn)有基于PIR的算法多數(shù)側(cè)重減小候選集規(guī)模，而忽略候選集的生成效率．此外，在POI的存儲(chǔ)組織上，多以單元格為基本單位，容易造成數(shù)據(jù)塊中出現(xiàn)大量假POI，浪費(fèi)儲(chǔ)存空間．

針對(duì)上述問(wèn)題，提出一種基于隱私信息檢索的保護(hù)位置隱私近鄰查詢方法PRN＿kNN（Pseudo－random number encryption based privacy－preserving kNN query），通過(guò)引入Hilbert曲線編碼，使用戶可以在本地快速生成k近鄰候選集；同時(shí)，引入偽隨機(jī)數(shù)加密規(guī)則替代傳統(tǒng)方法中查詢計(jì)劃，克服預(yù)處理時(shí)間長(zhǎng)以及查詢計(jì)劃動(dòng)態(tài)性差的不足，達(dá)到抵御模式攻擊和增強(qiáng)位置保護(hù)強(qiáng)度的效果．

論文主要貢獻(xiàn)包括：

（1）提出了一種基于隱私信息檢索的保護(hù)位置隱私近鄰查詢方法PRN＿kNN，引入偽隨機(jī)數(shù)加密規(guī)則替代傳統(tǒng)方法中查詢計(jì)劃，克服預(yù)處理時(shí)間長(zhǎng)及查詢計(jì)劃動(dòng)態(tài)性差的缺點(diǎn)；

（2）利用Hilbert曲線加密原空間并連續(xù)組織存儲(chǔ)POI實(shí)體，實(shí)現(xiàn)k近鄰候選集生成的本地化和快速化；

（3）在真實(shí)數(shù)據(jù)集上對(duì)所提方法進(jìn)行實(shí)驗(yàn)分析，驗(yàn)證所提方法的有效性．

論文組織結(jié)構(gòu)如下：第二章對(duì)相關(guān)工作進(jìn)行概述；第三章進(jìn)行問(wèn)題描述并介紹相關(guān)概念；第四章給出基于偽隨機(jī)數(shù)加密規(guī)則的PRN＿kNN算法，并結(jié)合實(shí)例對(duì)算法進(jìn)行分析；第五章對(duì)所提方法進(jìn)行實(shí)驗(yàn)分析，驗(yàn)證其有效性；最后，總結(jié)全文并展望下一步工作．

2 相關(guān)工作

近年來(lái)，位置服務(wù)領(lǐng)域研究者針對(duì)保護(hù)位置隱私查詢場(chǎng)景，提出了一系列位置隱私保護(hù)方法．主要包括空間混淆，數(shù)據(jù)變換，假位置擾動(dòng)，隱私信息檢索等．

2．1 常見(jiàn)位置隱私保護(hù)方法

空間混淆技術(shù)將查詢用戶位置提交可信第三方匿名服務(wù)器處理，生成包含用戶位置的匿名區(qū)域代替查詢者精確位置提交LBS服務(wù)器進(jìn)行查詢處理．例如文［2］提出了基于k匿名的空間混淆機(jī)制，將傳統(tǒng)隱私保護(hù)數(shù)據(jù)發(fā)布領(lǐng)域的k匿名模型應(yīng)用于位置服務(wù)中位置隱私保護(hù)．文［4］提出了CliqueCloak方法，支持個(gè)性化的隱私保護(hù)參數(shù)k；文［3］對(duì)在支持個(gè)性化隱私參數(shù)k基礎(chǔ)上，提出支持用戶自定義混淆區(qū)域規(guī)模的Casper方法．文［6］在匿名區(qū)域中，引入假用戶協(xié)作機(jī)制．基于空間混淆的保護(hù)位置隱私查詢機(jī)制往往依賴可信第三方服務(wù)器的位置匿名處理，可信第三方服務(wù)器容易成為系統(tǒng)性能和安全的瓶頸．

數(shù)據(jù)變換技術(shù)原理是將查詢者位置及POI坐標(biāo)轉(zhuǎn)換到另一個(gè)數(shù)據(jù)空間，要求數(shù)據(jù)轉(zhuǎn)換方法能盡可能保持原數(shù)據(jù)空間數(shù)據(jù)對(duì)象間的幾何位置關(guān)系，以保證查詢服務(wù)的準(zhǔn)確性．文［7］介紹了多種不可逆數(shù)據(jù)變換方法，例如基于POI位置關(guān)系的加密方法和基于網(wǎng)格技術(shù)的映射；文［8］提出了基于Hilbert編碼的保護(hù)位置隱私近鄰查詢機(jī)制，將二維位置坐標(biāo)映射到一維Hilbert空間，借助Hilbert曲線參數(shù)實(shí)現(xiàn)位置隱私保護(hù)．其優(yōu)點(diǎn)是不依賴可信第三方，且具有較高的位置隱藏與查詢處理效率，但多數(shù)數(shù)據(jù)變換難以嚴(yán)格保證變換前后數(shù)據(jù)空間任意對(duì)象間幾何關(guān)系的不改變，往往難以獲取準(zhǔn)確查詢結(jié)果，為了提高查詢結(jié)果的準(zhǔn)確度，通常需要設(shè)計(jì)額外的處理機(jī)制，導(dǎo)致處理復(fù)雜度的增加．

假位置擾動(dòng)采用假位置代替查詢者真實(shí)位置，查詢者不斷向LBS服務(wù)器發(fā)起關(guān)于所選假位置的緊鄰查詢請(qǐng)求，并根據(jù)服務(wù)器反饋的查詢結(jié)果與自身真實(shí)位置的約束關(guān)系，判斷所返回結(jié)果是否為真實(shí)查詢結(jié)果．例如文［9］提出基于假位置擾動(dòng)的保護(hù)位置隱私近鄰查詢方法SpaceTwist；文［11］進(jìn)一步提出基于中心服務(wù)器的改進(jìn)方法，使得SpaceTwist滿足k匿名約束．假位置擾動(dòng)方法依賴于不可預(yù)知輪次的假位置迭代查詢，存在隱私強(qiáng)度難以控制、且保護(hù)強(qiáng)度偏弱的缺陷，攻擊者通過(guò)分析所選取假位置及查詢中間結(jié)果能夠?qū)⒉樵冋呶恢面i定在較小的目標(biāo)區(qū)域內(nèi)，存在隱私泄露風(fēng)險(xiǎn)．

基于上述三種技術(shù)分別存在依賴可信第三方，準(zhǔn)確性不足和隱私保護(hù)強(qiáng)度偏弱的缺點(diǎn)，近年來(lái)，基于隱私信息檢索的技術(shù)得到研究者的持續(xù)關(guān)注，基于PIR的隱私保護(hù)方法具有強(qiáng)度高，不依賴可信第三方以及高準(zhǔn)確性查詢的特點(diǎn)［16］．

2．2 基于PIR的位置隱私保護(hù)方法

現(xiàn)有的PIR技術(shù)多數(shù)基于二次同余問(wèn)題．二次同余問(wèn)題的難度與因子分解難度相當(dāng)［12］．用戶向內(nèi)置于服務(wù)器端的安全硬件［17］發(fā)出PIR請(qǐng)求，安全硬件指定查詢向量，其中僅含有一個(gè)非二次同余數(shù)，利用二次同余性質(zhì)，通過(guò)判斷返回的數(shù)是否為二次同余，確定查詢位為0或1，該方法同樣適用檢索POI存儲(chǔ)塊（POI塊長(zhǎng)固定）［14］．

文［12］證明了隱私信息檢索能夠有效保護(hù)用戶隱私不泄漏．文［13］提出三種索引結(jié)構(gòu)，并據(jù)此提出三種基于PIR隱私檢索方法，其中兩種存在區(qū)域劃分和層次建立預(yù)處理時(shí)長(zhǎng)不足，亦難以抵制模式攻擊的缺陷．文［14］采用kd－tree和R－tree數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)最近鄰近似查詢，利用Voronoi多邊形完成精確最近鄰查詢，但存在準(zhǔn)確性不足及多邊形分割預(yù)處理代價(jià)大的缺陷，同時(shí)也只能處理最近鄰查詢．針對(duì)上述問(wèn)題，文［15］引入查詢計(jì)劃?rùn)C(jī)制抵御模式攻擊，使得被不同頻次訪問(wèn)的POI不易被區(qū)分，但依舊存在以下問(wèn)題：（1）查詢計(jì)劃要求不同用戶對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)次數(shù)相同，需要對(duì)訪問(wèn)次數(shù)進(jìn)行預(yù)計(jì)算，而POI位置一旦改變，預(yù)計(jì)算結(jié)果將失效，存在動(dòng)態(tài)性差的不足；（2）數(shù)據(jù)庫(kù)中POI的存儲(chǔ)以地圖的單元格為基本單位，對(duì)相對(duì)稀疏的區(qū)域，需要大量假POI填充數(shù)據(jù)塊，增加了無(wú)效檢索的開(kāi)銷；（3）采用CPM算法［18］生成候選解集，該算法實(shí)現(xiàn)了訪問(wèn)最少的單元格生成候選解集，但存在確定待訪問(wèn)單元格的時(shí)間代價(jià)太大的問(wèn)題，影響查詢處理效率．

3 問(wèn)題描述與相關(guān)概念

3．1 問(wèn)題描述

前已述及，現(xiàn)有的基于PIR的保護(hù)位置隱私查詢方法多數(shù)存在預(yù)處理時(shí)間長(zhǎng)、候選解集生成效率低等不足．例如，文［13］提出方法存在區(qū)域劃分與層次建立預(yù)處理時(shí)間長(zhǎng)問(wèn)題；文［15］提出的BNC＿kNN（Benchmark PIR based kNN query）方法，引入查詢計(jì)劃使得用戶按相同次數(shù)訪問(wèn)數(shù)據(jù)庫(kù)，導(dǎo)致預(yù)處理時(shí)間急劇增加．

基于PIR的保護(hù)位置隱私近鄰查詢方法需解決以下問(wèn)題：

（1）查詢預(yù)處理階段，能夠在兼顧隱私安全前提下，減少預(yù)處理時(shí)間；

（2）用戶可以在本地通過(guò)PIR請(qǐng)求快速生成候選解集．

（3）能夠防止攻擊者借助不同用戶訪問(wèn)數(shù)據(jù)庫(kù)的頻次特征發(fā)起的模式攻擊．

3．2 相關(guān)概念

現(xiàn)有基于PIR隱私檢索方法在預(yù)處理階段存在時(shí)間較長(zhǎng)不足．對(duì)給定k近鄰查詢，假設(shè)查詢者Q1和Q2訪問(wèn)數(shù)據(jù)庫(kù)的次數(shù)分別為cnt1、cnt2．當(dāng)cnt1不等于cnt2時(shí)，攻擊者根據(jù)截獲查詢者向服務(wù)器發(fā)出的查詢請(qǐng)求頻次，能夠以一定概率確定查詢者下次要查詢的POI，甚至能夠定位查詢者，這種攻擊方式稱為模式攻擊．針對(duì)模式攻擊問(wèn)題，文［15］引入查詢計(jì)劃，使得用戶按相同次數(shù)訪問(wèn)數(shù)據(jù)庫(kù)．BNC＿kNN算法對(duì)k近鄰查詢給定統(tǒng)一的訪問(wèn)數(shù)據(jù)庫(kù)次數(shù)，使得攻擊者不能區(qū)分查詢者．但預(yù)處理階段生成查詢計(jì)劃相當(dāng)耗時(shí)，且不支持動(dòng)態(tài)查詢．文獻(xiàn)［13］提出的兩種檢索技術(shù)同樣存在預(yù)處理耗時(shí)大的問(wèn)題．

偽隨機(jī)數(shù)是隨機(jī)生成的排列數(shù)序列，偽隨機(jī)數(shù)加密規(guī)則能夠起到模糊和加密查詢的效果，同樣可以重排和加密數(shù)據(jù)庫(kù)．考慮引入了偽隨機(jī)數(shù)規(guī)則加密數(shù)據(jù)庫(kù)和相應(yīng)查詢，達(dá)到無(wú)法辨別查詢內(nèi)容、保護(hù)查詢者的目的，即使查詢次數(shù)不一樣，由于不能確定推斷查詢者和查詢內(nèi)容，同樣可以抵御模式攻擊；此外，偽隨機(jī)數(shù)的生成還具有參數(shù)單一，流程相對(duì)簡(jiǎn)單等特點(diǎn)．

定義1偽隨機(jī)數(shù)加密規(guī)則．對(duì)于有n個(gè)元素的數(shù)據(jù)庫(kù)DB，按規(guī)則π將DB轉(zhuǎn)換成DBπ：DBπ［i］＝DB［π［i］］，規(guī)則π為1，2，…，n的一個(gè)全排列表示，又稱偽隨機(jī)數(shù)重排規(guī)則．

例如，對(duì)于數(shù)據(jù)庫(kù)DB＝｛O1，O2，O3｝，n＝3，如果偽隨機(jī)數(shù)規(guī)則π是｛2，3，1｝，則DBπ［1］＝DB［π［1］］＝DB［2］＝O2，DBπ［2］＝DB［π［2］］＝DB［3］＝O3，DBπ［3］＝DB［π［3］］＝DB［1］＝O1．因此，DBπ＝｛O2，O3，O1｝．假設(shè)符號(hào)PIR（id）表示要查詢的POI實(shí)體的標(biāo)志符．用戶要查詢O1，則id＝1，利用π規(guī)則加密id為3．因此向服務(wù)器提交PIR（3）（即采用PIR檢索方法向用同樣規(guī)則加密了的數(shù)據(jù)庫(kù)查詢標(biāo)志符為3的POI）．

能否快速生成候選解集直接影響查詢效率，文［13］采用閉包增長(zhǎng)，層次查詢以及希爾伯特區(qū)域查詢生成候選解集，前兩者效率不及CPM［18］，盡管希爾伯特區(qū)域查詢可以快速確定候選集，卻因需要提交整個(gè)候選解集矩陣閉包，使得定位k近鄰重復(fù)了相當(dāng)多的無(wú)用查詢．文［15］執(zhí)行算法CPM，能滿足候選解集的規(guī)模最小，卻以生成候選解集的時(shí)間消耗為代價(jià)，使得查詢效率低下．為了解決這一問(wèn)題，考慮利用Hilbert曲線保留近似鄰接的性質(zhì)，設(shè)置HPT以及NPT兩張表，分別存儲(chǔ)經(jīng)SDK譯碼后POI的Hilbert值及每個(gè)單元格中POI編碼信息．

定義2 Hilbert編碼．二維平面下的Hilbert曲線記為HN2，其參數(shù)為SDK（X0，Y0，θ，N，ξ）．其中（X0，Y0）表示曲線的起點(diǎn)坐標(biāo)；θ表示曲線的走勢(shì)方向；N表示曲線的階；ξ表示曲線的規(guī)模因子（0≤ξ≤22N－1）．

圖1 Hilbert曲線加密的空間Fig．1 The encrypted space with Hilbert curve

圖1描述了經(jīng)Hilbert曲線編碼后的某數(shù)據(jù)區(qū)域，數(shù)據(jù)區(qū)域規(guī)模為8＊8，包含20個(gè)POI．假設(shè)X0＝P1．x，Y0＝P1．y，N＝3，通過(guò)θ規(guī)定曲線順時(shí)針走勢(shì)以及ξ定義其規(guī)模為22N－1．表1、表2分別為HPT和NPT的表結(jié)構(gòu)，分別存儲(chǔ)經(jīng)Hilbert曲線加密的POI以及單元格．圖1中20個(gè)POI加密后值為：H（P1）＝0，H（P2）＝2，…，H（P20）＝61．

表1 HPT表結(jié)構(gòu)示意Tab．1 The structure of HPT

表2 NPT表結(jié)構(gòu)示意Tab．2 The structure of NPT

HPT以及NPT表以B＋樹(shù)形式組織，用戶Q查詢k近鄰時(shí)，首先計(jì)算出其當(dāng)前位置的Hilbert值H（Q），根據(jù)Hilbert曲線的近似鄰接性質(zhì)，可以快速找到Q的k近鄰候選集．查詢者通過(guò)向安全硬件發(fā)起PIR請(qǐng)求，服務(wù)器做出對(duì)數(shù)據(jù)庫(kù)中POI的訪問(wèn)，盡管數(shù)據(jù)庫(kù)的組織對(duì)用戶是透明的，但PIR查詢卻依賴其組織形式．文［15］中采用行列確定的單元格為基本單位儲(chǔ)存POI，當(dāng)數(shù)據(jù)塊不夠儲(chǔ)存時(shí)，將多出的POI插在末尾，而當(dāng)數(shù)據(jù)庫(kù)塊未填滿時(shí)，采用假POI代替，將導(dǎo)致一些塊包含大量假POI，增大了平均檢索數(shù)據(jù)庫(kù)次數(shù)．文［13］提出基于POI記錄長(zhǎng)度閾值λ的分割存儲(chǔ)方法，解決POI實(shí)體記錄不等長(zhǎng)帶來(lái)的空間浪費(fèi)問(wèn)題，提高了空間利用率，然而需要遍歷所有POI實(shí)體并計(jì)算其長(zhǎng)度以便進(jìn)行分割存儲(chǔ)處理，存在預(yù)處理耗時(shí)較大問(wèn)題．本文所提算法考慮不以單元格為基本存儲(chǔ)單位，對(duì)原空間中POI進(jìn)行Hilbert編碼加密后，按Hilbert編碼值依次存入數(shù)據(jù)庫(kù)DB1和DB2，前者存儲(chǔ)查詢內(nèi)容的索引，后者用于存儲(chǔ)查詢內(nèi)容．DB1和DB2的塊大小與結(jié)構(gòu)沿用文［15］所采用結(jié)構(gòu)，DB1存儲(chǔ)的POI實(shí)體結(jié)構(gòu)為＜P·id，P·x，P·y，P·ptr＞，分別對(duì)應(yīng)POI的標(biāo)志符、平面坐標(biāo)、指向DB2中存儲(chǔ)該P(yáng)OI詳細(xì)信息的索引；DB2中存儲(chǔ)POI實(shí)體相關(guān)信息結(jié)構(gòu)＜P·id，P·tail＞，P·tail為該P(yáng)OI的詳細(xì)信息．例如在某次最近鄰Pr（id＝r）查詢中，用戶通過(guò)客戶端向服務(wù)器發(fā)出隱私檢索請(qǐng)求PIR（r），安全硬件對(duì)數(shù)據(jù)庫(kù)DB1進(jìn)行檢索，取得指向DB2中存有點(diǎn)Pr的詳細(xì)信息（也是用戶所要查詢的信息）的塊地址Pr·ptr，然后，安全硬件利用該地址對(duì)DB2相應(yīng)塊隱私檢索并將包含所要查詢的信息Pr·tail的POI返回給用戶．不同之處在于本文所提方法將POI經(jīng)偽隨機(jī)數(shù)加密后，逐一放入塊中，而不以地圖單元格為塊存儲(chǔ)單位．

定義3強(qiáng)隱私保護(hù)系統(tǒng)．給定一個(gè)kNN查詢系統(tǒng)，攻擊者在不破解安全硬件和偽隨機(jī)數(shù)規(guī)則兩個(gè)條件下，推斷這k個(gè)POI的概率小于等于其中n為POI的全部數(shù)目．稱該系統(tǒng)為強(qiáng)隱私保護(hù)系統(tǒng)．

首先采用偽隨機(jī)數(shù)規(guī)則對(duì)用戶查詢請(qǐng)求進(jìn)行加密，并將加密后查詢請(qǐng)求提交安全硬件，安全硬件接受用戶的查詢請(qǐng)求，并對(duì)數(shù)據(jù)庫(kù)進(jìn)行隱私信息檢索，隱私信息檢索過(guò)程本身具有高隱私保護(hù)強(qiáng)度，又經(jīng)過(guò)偽隨機(jī)規(guī)則處理，雙重保護(hù)下查詢機(jī)制將具有更強(qiáng)的隱私保護(hù)強(qiáng)度．

4 保護(hù)位置隱私近鄰查詢方法PRN＿kNN

4．1 基本思想

本文提出的PRN＿kNN方法通過(guò)引入Hilbert曲線加密原二維平面中的POI實(shí)體，使得用戶可以在本地快速查詢k近鄰的候選解集，候選解集包含真實(shí)的k近鄰的標(biāo)志符．在此基礎(chǔ)上，引入偽隨機(jī)數(shù)加密規(guī)則替代傳統(tǒng)方法中查詢計(jì)劃，克服了查詢機(jī)制預(yù)處理時(shí)間長(zhǎng)以及查詢計(jì)劃的動(dòng)態(tài)性差的缺點(diǎn)，同時(shí)達(dá)到抵御模式攻擊和增強(qiáng)保護(hù)強(qiáng)度的效果．在POI存儲(chǔ)組織方面，改進(jìn)文［15］的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，不再以單元格為基本存儲(chǔ)單位，按照POI標(biāo)志符順序存儲(chǔ)，以提高存儲(chǔ)效率和平均檢索盤(pán)塊次數(shù)．

圖2 系統(tǒng)流程Fig．2 The PRN－kNN system architecture

系統(tǒng)流程見(jiàn)圖2，客戶端向安全硬件發(fā)送PIR請(qǐng)求前，服務(wù)器先對(duì)存儲(chǔ)POI的數(shù)據(jù)庫(kù)DB利用規(guī)則π加密成DBπ．在查詢階段，安全硬件對(duì)數(shù)據(jù)庫(kù)DBπ直接進(jìn)行隱私檢索，并將查詢結(jié)果交付服務(wù)器，服務(wù)器將根據(jù)網(wǎng)絡(luò)狀況進(jìn)行流量控制，返回查詢客戶端．

查詢系統(tǒng)包含三部分：客戶端，安全硬件，數(shù)據(jù)庫(kù)．其中安全硬件機(jī)制由內(nèi)置服務(wù)器端的硬件實(shí)現(xiàn)．整個(gè)查詢過(guò)程可分為以下四步：

第1步：利用偽隨機(jī)數(shù)規(guī)則加密數(shù)據(jù)庫(kù)DB1，DB2；

第2步：對(duì)查詢同樣加密，并向安全硬件發(fā)出多輪PIR請(qǐng)求，獲取候選解集；

第3步：根據(jù)候選解集中點(diǎn)距查詢者的距離遠(yuǎn)近，確定查詢者的k近鄰；

第4步：利用kNN所在塊的索引地址，向安全硬件發(fā)出多輪PIR請(qǐng)求，返回查詢結(jié)果．

分析易知，整個(gè)查詢過(guò)程，服務(wù)器端內(nèi)置的安全硬件承擔(dān)了主要工作．它負(fù)責(zé)執(zhí)行PIR和加解密偽隨機(jī)數(shù)規(guī)則．客戶端并不要求高處理能力，它在了解數(shù)據(jù)庫(kù)組織和偽隨機(jī)數(shù)規(guī)則前提下，不斷提出PIR請(qǐng)求，直至返回查詢的內(nèi)容．

4．2 模式攻擊處理

模式攻擊指攻擊者借助所掌握不同用戶訪問(wèn)數(shù)據(jù)庫(kù)的不同頻次，推斷用戶下一次檢索目標(biāo)的攻擊方式．BNC＿kNN針對(duì)該問(wèn)題提出了查詢計(jì)劃，要求用戶按相同次數(shù)訪問(wèn)數(shù)據(jù)庫(kù)，以保證攻擊者不能根據(jù)訪問(wèn)頻次差異去窺測(cè)用戶隱私．PRN＿kNN克服了BNC＿kNN預(yù)處理時(shí)間長(zhǎng)等問(wèn)題，算法采用偽隨機(jī)數(shù)加密規(guī)則對(duì)數(shù)據(jù)塊中的實(shí)體加密重排，即便攻擊者獲得了各POI的訪問(wèn)頻次，但這些POI是經(jīng)過(guò)隨機(jī)重排的，并不代表真實(shí)實(shí)體的頻次，從而混淆查詢，避免了模式攻擊的發(fā)生．

偽隨機(jī)數(shù)加密規(guī)則首先對(duì)數(shù)據(jù)塊中的POI利用規(guī)則π隨機(jī)重排，然后將其放入指定數(shù)據(jù)塊中，生成了加密數(shù)據(jù)庫(kù)DBπ．在用戶查詢階段，客戶端同樣利用規(guī)則π對(duì)要查詢的POI編號(hào)加密，發(fā)送給服務(wù)器，服務(wù)器端的安全硬件利用加密后的編號(hào)對(duì)數(shù)據(jù)庫(kù)DBπ發(fā)出PIR請(qǐng)求，接收返回的數(shù)據(jù)后，直接返回給客戶端．具體加密流程見(jiàn)算法1．

算法1偽隨機(jī)數(shù)重排算法

輸入：DB，原數(shù)據(jù)庫(kù)記錄，π加密規(guī)則

輸出：DBπ加密后的數(shù)據(jù)庫(kù)

1．entries＿DB＝φ；／／POI輸入緩沖區(qū)

2．out＿DB＝φ；／／POI輸出緩沖區(qū)

3．for each block bin DB

4．entries＿DB．push（b）；

5．if（entries＿DB?。溅眨?/p>

6．blockb1＝entries＿DB．pop（）；／／取出塊

7．Integer index＝b1．blocknumber（）；／／index記錄塊號(hào)

8．for each POI Pin block b1

9．if（P！＝NULL）

10．entires P＝b1．pop（）；／／取出塊內(nèi)POI

11．DBπ［P·id］＝DB［π［P·id］］；／／加密POI

12．block temp．push（P）；

13．if（temp．isfull（））／／若塊滿加入輸出緩沖區(qū)

14．out＿DB．push（temp）；

15．if（out＿DB！＝φ）

16．block b2＝out＿DB．pop（）；／／取輸出緩沖區(qū)內(nèi)塊

17．DBπ．insert（index，b2）；／／加密后的塊插入DBπ［index］位置

18．end if

19．end if

20．end if

21．end for

22．end if

23．end for

24．return DBπ；

以圖1中數(shù)據(jù)集DB＝｛P1，P2，P3，P4，P5，…，P20｝為例，給定的排列規(guī)則π為［20，19，18，…，1］，利用DBπ［i］＝DB［π［i］］．可以得出DBπ＝｛P20，P19，P18，P17，P16，…，P1｝．按照這個(gè)規(guī)則可以加密數(shù)據(jù)庫(kù)DB中所有塊內(nèi)的POI．然后DB按次序儲(chǔ)存DBπ內(nèi)的POI．得到B1，1＝｛P20｝，B1，4＝｛P17，P16，P15｝，B1，16＝｛P3，P2，P1｝；B2，1＝｛P20，P19，P18｝，B2，4＝｛P11，P10，P9｝，B2，7＝｛P2，P1｝．

4．3 候選解集生成

候選解集的生成直接影響查詢效率，對(duì)于k近鄰查詢，用戶通過(guò)在DB1上初步查詢，生成大于等于k個(gè)近鄰目標(biāo)．這些POI構(gòu)成候選解集，進(jìn)一步的篩選距離最近的k個(gè)對(duì)象，再通過(guò)查找這些對(duì)象包含的索引信息，對(duì)DB2發(fā)出PIR請(qǐng)求，返回最終的查詢結(jié)果．

客戶端首先生成查詢位置Q的Hilbert編碼H（Q），然后從位置Q開(kāi)始沿著加密曲線雙向遍歷單元格，利用NPT找出其內(nèi)的POI，并向安全硬件發(fā)出PIR請(qǐng)求直到返回的POI數(shù)目大于等于k為止．整個(gè)生成過(guò)程如算法2所示．

算法2候選解集生成算法

輸入：用戶位置Q，DB1加密重排后的數(shù)據(jù)庫(kù)DBπ＿1，查詢目標(biāo)數(shù)k

輸出：S候選集

1．S＝φ；／／初始化候選集為空

2．WhileS．size＜k ／／候選集規(guī)模大小k

3．H－index h＝H（Q）；／／Q所在單元格的希爾伯特值

4．for int i＝0；；i＋＋

5．h±＝i；／／雙向近鄰搜索

6．if（h≤22N－1） ／／N表示地圖G的粒度

7．Integer index＝NPT［h］；

8．for each POI Pin NPT［h］／／依次取出塊內(nèi)POI并入集合S

9．POI P＝PIR（P．π［index］）；

10．S．push（P）；／／POI入集合S

11．end for

12．end if

13．end for

14．end while

15．dist＿k＝distance fromQto its kth NN in entries＿DB1；／／利用第k近鄰生成kNN候選集S

16．c＿set＝set of yet unseen cells overlapping with circleC（Q，dist＿k）；／／剩余未掃描的單元格

17．for each cell cin c＿set

18．對(duì)c內(nèi)每一個(gè)POI P·id隱私檢索PIR（id）并入S；

19．end for

20．return S；

仍以圖1為例，假設(shè)用戶所在位置Q和P7同一單元格，k＝3，已知H（Q）＝16，查找NPT，發(fā)現(xiàn)該單元格內(nèi)僅有P7，將P7加進(jìn)集合S．繼續(xù)沿著曲線遍歷編碼值為17、15的單元格，對(duì)單元格內(nèi)的POI進(jìn)行PIR檢索，將得到的P8添加進(jìn)集合S．當(dāng)遍歷到編碼值為18和14的單元格時(shí)，得到的P9也加入集合S．此外，S中正好包含3個(gè)POI，接著以Q為圓心，Q到P9的距離為半徑作圓，交點(diǎn)有12，15，16，17，18，19，其中15，16，17，18已經(jīng)訪問(wèn)過(guò)，只需搜索單元格12，19即可，將P4，P5，P6入S．算法返回S作為候選集，供進(jìn)一步查詢使用．

性質(zhì)1候選集S中一定包含真實(shí)的kNN．

證 明 利用反證法，假設(shè)P∈kNN，同時(shí)滿足P?S，也就是真正kNN內(nèi)一點(diǎn)P，不包含于集合S，P’是S內(nèi)距離用戶Q最遠(yuǎn)的POI，半徑為R．因?yàn)镻?S，所以dist（Q，P）＞R，又因?yàn)镻∈kNN，所以dist（Q，P）≤R，矛盾，所以，P不存在．原命題得證．

4．4 算法描述

算法PRN＿kNN需要由用戶指定查詢值k以及給定一個(gè)偽隨機(jī)數(shù)規(guī)則π．算法分三步，第一步，調(diào)用算法1，對(duì)數(shù)據(jù)庫(kù)中POI加密．第二步，調(diào)用候選集生成算法，產(chǎn)生候選集返回給客戶端．第三步，客戶端對(duì)候選集中的POI，根據(jù)到用戶位置Q的距離，一般是歐幾里得距離排序，保留前k個(gè)POI，這k個(gè)POI索引包含了DB2中含有這些POI的塊．第四步，通過(guò)這k個(gè)POI中的P·ptr，確定DB2中相應(yīng)塊，再次PIR檢索并將最終查詢結(jié)果返回給客戶端．

算法3 PRN（Q，k，π）

輸入：查詢者位置Q，近鄰查詢數(shù)目k，偽隨機(jī)數(shù)規(guī)則π

輸出：kNN查詢信息

1．令entries＿DBπ＿1＝φ，entries＿DBπ＿2＝φ，kNN＝φ；／／分別表示DBπ＿1、DBπ＿2的緩沖容器

2．調(diào)用偽隨機(jī)數(shù)重排算法加密DB1和DB2；／／生成加密重排后的數(shù)據(jù)庫(kù)

3．調(diào)用候選集生成算法產(chǎn)生候選集entries＿DBπ＿1；

4．kNN＿DBπ＿1＝set of kNN result entries in entries＿DBπ＿1；／／取候選集前k個(gè)POI

5．for each POI Pin kNN＿DBπ＿1

6．if（P！＝NULL）

7．PIR（P·ptr）檢索對(duì)應(yīng)的DBπ＿2＿block并將塊內(nèi)實(shí)體入entries＿DBπ＿2；

8．end for

9．for each POI P1in kNN＿DBπ＿1

10．for each POI P2in entries＿DBπ＿2

11．if（P1·id＝P2·id）

12．Insert P2into kNN；／／將包含查詢信息（tail）的P2入集合kNN

13．end if

14．end for

15．end for

16．return kNN；／／返回查詢結(jié)果

PRN＿kNN算法中，第1—2行為第一階段，第3行為第二階段，第4行為第三階段，第5—16行為第四階段．下面結(jié)合圖3給出示例，假設(shè)查詢者發(fā)起2NN查詢．

客戶端沿著Hilbert曲線依次遍歷Hilbert編碼為H（Q），H（Q）±1，H（Q）±2，…的單元格，結(jié)合NPT以及HPT經(jīng)PIR檢索獲得P8、P9兩個(gè)近似的鄰近POI．利用4．2給出的偽隨機(jī)數(shù)加密規(guī)則確定它們?cè)谥嘏藕蟮臄?shù)據(jù)庫(kù)中位置為P13、P12．再次利用NPT以及HPT，確定它們分別位于重排后的B1，10，B1，9，多輪PIR檢索下面重排后DBπ＿1矩陣B1，10和B1，9．安全硬件利用π規(guī)則加密兩塊中的POI對(duì)象P13、P12，并反饋給客戶端．如下圖矩陣所示，左側(cè)表示加密后的DB1，右側(cè)表示加密后的DB2，安全硬件對(duì)加密后的數(shù)據(jù)庫(kù)實(shí)現(xiàn)PIR訪問(wèn)，圖中NaN表示數(shù)據(jù)庫(kù)矩陣未滿時(shí)，插入的空閑塊．

圖3 2NN查詢Fig．3 The example of 2 nearest neighbers

客戶端收到加密后的POI為P13、P12，解密獲取原空間中的P8、P9．以Q為圓心，Q到P9的距離dist（Q，P9）為半徑作圓，圓與地圖區(qū)域所包含單元格的交點(diǎn)的Hilbert值為12、13、16、17、18、19、20、31．利用NPT以及HPT訪問(wèn)還未檢索過(guò)的POI對(duì)象P4、P5、P6、P7，第一階段對(duì)這四個(gè)點(diǎn)進(jìn)行PIR訪問(wèn)，客戶端在獲取P4、P5、P6、P7、P8、P9六個(gè)點(diǎn)后，利用歐氏距離排序，得出實(shí)際的2NN為P8、P6．第三階段，客戶端向安全硬件發(fā)送加密后的P13、P15查詢請(qǐng)求，安全硬件直接利用P·ptr確定上面給出的重排后的DBπ＿2矩陣中的塊B2，5．PIR檢索該塊并返回，客戶端收到解密信息，通過(guò)P8、P6的P·id連接B2，5中的POI對(duì)象P6、P7、P8，取得最終要求的P·tail．

4．5 算法分析

本節(jié)對(duì)PRN＿kNN算法的隱私保護(hù)強(qiáng)度以及算法時(shí)間復(fù)雜度進(jìn)行分析．

在位置隱私保護(hù)方面，算法主要從三方面提供保證，安全硬件、Hilbert編碼以及偽隨機(jī)數(shù)加密．安全硬件提供對(duì)外PIR請(qǐng)求接口，對(duì)內(nèi)的隱私檢索數(shù)據(jù)庫(kù)，安全強(qiáng)度高，Hilbert編碼和偽隨機(jī)數(shù)加密起到加密空間和重排POI效果，實(shí)現(xiàn)了多重隱私保護(hù)．

性質(zhì)2基于PRN＿kNN方法的查詢系統(tǒng)為強(qiáng)隱私保護(hù)系統(tǒng)．

證 明 由于k＜＜n，攻擊者在客戶端與服務(wù)器通信過(guò)程中截獲查詢請(qǐng)求，即使連續(xù)記錄偽隨機(jī)數(shù)加密后的POI編號(hào)，仍不能推斷偽隨機(jī)數(shù)加密規(guī)則，同時(shí)在安全硬件對(duì)數(shù)據(jù)庫(kù)I／O過(guò)程中，滿足基于計(jì)算的隱私信息檢索原理．此外，數(shù)據(jù)塊中的POI實(shí)體也經(jīng)過(guò)加密處理，攻擊者短時(shí)間內(nèi)不能破解PIR請(qǐng)求．因此，對(duì)kNN查詢，滿足“獨(dú)立同分布”查詢性質(zhì)，推斷kNN查詢概率小于等于

與傳統(tǒng)的BNC＿kNN算法一樣，PRN＿kNN除本地生成候選解集，篩選真實(shí)POI以及POI詳細(xì)信息查詢?nèi)A段外，還需對(duì)加密數(shù)據(jù)庫(kù)進(jìn)行預(yù)處理．因?yàn)樯婕八蠵OI的重排，所以時(shí)間復(fù)雜度為O（n），相較文［13］查詢計(jì)劃復(fù)雜度為O（n2）代價(jià)更低．PRN＿kNN滿足輕客戶端重服務(wù)器思想，本地客戶端計(jì)算代價(jià)小，只需執(zhí)行kNN算法以及利用偽隨機(jī)數(shù)規(guī)則加解密發(fā)送和接受的POI，檢索工作完全由內(nèi)置于服務(wù)器端的安全硬件承擔(dān)．文［8］給出采用希爾伯特曲線加密查詢kNN時(shí)間復(fù)雜度為其中N表示曲線的階數(shù)，n表示POI數(shù)量．PRN＿kNN預(yù)處理后的查詢時(shí)間復(fù)雜度主要由三部分構(gòu)成：生成候選集、排序候選集求出真實(shí)查詢的POI以及檢索數(shù)據(jù)庫(kù)塊．總的時(shí)間復(fù)雜度為空間復(fù)雜度在于常駐內(nèi)存的NPT以及HPT兩張表，規(guī)模為O（n）．

5 實(shí)驗(yàn)分析

5．1 實(shí)驗(yàn)環(huán)境

算法采用C＋＋11實(shí)現(xiàn)，計(jì)算機(jī)硬件配置如下：AMDPhenomIIN6603．0GHZ處理器、4GB內(nèi)存，操作系統(tǒng)為Win7．實(shí)驗(yàn)數(shù)據(jù)來(lái)源于美國(guó)東北部郵局地點(diǎn)，數(shù)據(jù)集包含123K個(gè)POI．區(qū)域面積為106×106（數(shù)據(jù)經(jīng)過(guò)規(guī)格化，不含單位），規(guī)格化后POI分布?jí)嚎s如圖4所示．

圖4 真實(shí)數(shù)據(jù)集分布Fig．4 Real data set distribution

假設(shè)每個(gè)POI中tail屬性占用1 KB，導(dǎo)致數(shù)據(jù)庫(kù)大小為128 M．同時(shí)假設(shè)每個(gè)數(shù)據(jù)塊大小為4 KB．我們采用模擬的安全硬件，利用二次同余以及偽隨機(jī)數(shù)規(guī)則檢索數(shù)據(jù)．實(shí)驗(yàn)?zāi)M一個(gè)雙工的網(wǎng)絡(luò)通信信道，客戶端帶寬為1 Mbps，與LBS一次來(lái)回通信（round－trip－time）為10 ms．

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

本節(jié)對(duì)PRN＿kNN以及基于PIR的經(jīng)典保護(hù)位置隱私查詢算法BNC＿kNN進(jìn)行查詢效率的對(duì)比分析（安全性方面兩者采用相同的安全硬件機(jī)制，不同在于PRN＿kNN引入偽隨機(jī)數(shù)規(guī)則替代BNC＿kNN所采用的查詢計(jì)劃，兩算法均可避免模式攻擊）．分別從地圖G的粒度（granularity）選擇、第一階段候選集規(guī)模大小、訪問(wèn)DB1時(shí)長(zhǎng)（候選解集生成時(shí)間）以及總的查詢時(shí)長(zhǎng)四個(gè)方面對(duì)比算法性能．

如圖5所示，不同粒度會(huì)影響查詢效率，因?yàn)榱６鹊牟煌?，?dǎo)致單元格內(nèi)POI數(shù)量發(fā)生變化，同時(shí)導(dǎo)致數(shù)據(jù)庫(kù)組織發(fā)生變化．圖5（a）和（b）分別表示k＝1和k＝5時(shí)，不同粒度下查詢總時(shí)長(zhǎng)．粒度太小導(dǎo)致單元格數(shù)量急劇增加，數(shù)據(jù)庫(kù)塊數(shù)量跟著增加，I／O增加，時(shí)耗變長(zhǎng)；粒度過(guò)大時(shí)，盡管單元格數(shù)量較少，但會(huì)使數(shù)據(jù)塊中存儲(chǔ)大量假POI實(shí)體，浪費(fèi)空間，檢索次數(shù)也增加．可以得出BNC＿kNN對(duì)粒度更加敏感，而PRN＿kNN則更為穩(wěn)定．

圖5 粒度對(duì)查詢效率影響Fig．5 Performance vs G granularity

實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)粒度在256附近時(shí)，兩算法查詢效率均較高．公平起見(jiàn)，后續(xù)實(shí)驗(yàn)的粒度均取256．

圖6 候選集大小以及查詢時(shí)長(zhǎng)（granularity＝256）Fig．6 Candidate size and search cost

圖6（a）表明隨著k＝1到k＝20變化，PRN＿kNN得到候選解集規(guī)模始終比BNC＿kNN稍大，這是因?yàn)槲模?8］在理論證明CPM算法所需訪問(wèn)遍歷的單元格最少．但是對(duì)DB1數(shù)據(jù)塊的訪問(wèn)時(shí)長(zhǎng)，PRN＿kNN更短，特別當(dāng)k＞10時(shí)，差距更趨明顯．因?yàn)镃PM算法采用R樹(shù)型結(jié)構(gòu)存儲(chǔ)塊執(zhí)行，需要采用回溯尋找最佳單元格，而PRN＿kNN算法中，沿著已經(jīng)編碼NPT索引實(shí)現(xiàn)檢索，結(jié)構(gòu)更加簡(jiǎn)單，速度更快．圖6（b）表明PRN＿kNN算法盡管候選集規(guī)模比BNC＿kNN算法偏大，但其對(duì)數(shù)據(jù)庫(kù)的檢索效率明顯更優(yōu)．如圖6（c）所示，隨著k值增加，PRN＿kNN算法查詢代價(jià)及代價(jià)增長(zhǎng)幅度上均優(yōu)于BNC＿kNN算法．

6 總結(jié)與展望

針對(duì)已有基于PIR的保護(hù)位置隱私近鄰查詢方法存在的查詢效率等方面不足，提出了基于偽隨機(jī)數(shù)的保護(hù)位置隱私k近鄰查詢方法PRN＿kNN，采用偽隨機(jī)數(shù)重排數(shù)據(jù)庫(kù)和查詢請(qǐng)求，使得攻擊者即便掌握數(shù)據(jù)庫(kù)訪問(wèn)頻次仍無(wú)法根據(jù)查詢次數(shù)與受歡迎程度推斷出目標(biāo)POI，避免模式攻擊，在此基礎(chǔ)上，引入Hilbert曲線編碼，使客戶端快速實(shí)現(xiàn)候選解集的本地化生成．理論分析和實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性．PRN＿kNN算法尚未考慮網(wǎng)絡(luò)通信現(xiàn)實(shí)情形，下一步將考慮基于PIR的保護(hù)位置隱私查詢中流量控制及通信效率等問(wèn)題．

［1］ROUSSOPOULOS N，KELLEY S，VINCENT F．Nearest neighbor queries［C］／／Proceedings of the ACM Special Interest Group on Management of Data（SIGMOD’95）．California，USA，1995：71－79．

［2］GRUTESER M，GRUNWAL D．Anonymous usage of location based services through spatial and temporal cloaking［C］／／Proceedings of the International Conference on Mobile Systems，Applications，and Services（MobiSys’03）．California，USA，2003：31－42．

［3］MOKBEL M F，CHOW C Y，AREF W G．The new casper：Query processing for location services without compromising privacy［C］／／Proceedings of the International Conference on Very Large Data Bases（VLDB’06）．Seoul，Korea，2006：763－774．

［4］GEDIK B，LIU L．Location privacy in mobile systems：A personalized anonymization model［C］／／Proceedings of the IEEE International Conference on Distributed Computing Systems（ICDCS’05）．Ohio，USA，2005：620－629．

［5］朱懷杰，王佳英，王斌，等．障礙空間中保持位置隱私的最近鄰查詢方法［J］．計(jì)算機(jī)研究與發(fā)展．2014，51（1）：115－125．

［6］FIROOZJAEI M D，YU J，KIM H．Privacy preserving nearest neighbor search based on topologies in cellular networks［C］／／Proceedings of the IEEE International Conference on Advanced Information Networking and Applications Workshops．Suwon，Korea，2015：146－149．

［7］INDYK P，WOODRUFF D，Polylogarithmic private approximations and efficient matching［C］／／Proceedings of the Third Theory of Cryptography Conference（TCC’06），New York，USA，2006：245－264．

［8］KHOSHGOZARAN A，SHAHABI C．Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy［C］／／Proceedings of the International Symposium on Spatial and Temporal Databases（SSTD’07），Massachusetts，USA，2007：239－257．

［9］YIU M L，JENSEN C S，HUANG X，et al．Spacetwist：Managing the trade－offs among location privacy，query performance，and query accuracy in mobile services［C］／／Proceedings of the IEEE International Conference on Data Engineering（ICDE’08）．Cancun，Mexico，2008：366－375．

［10］NI W W，ZHENG J W，CHONG Z H．HilAnchor：Location privacy protection in the presence of users’preferences［J］．Journal of Computer Science and Technology，2012，27（2）：413－427．

［11］GONG Z，SUN G，XIE X．Protecting privacy in location－based servicesusing k－anonymity without cloaked region［C］／／Proceedings of the International Conference on Mobile Data Management（MDM’10）．Missouri，USA，2010：366－371．

［12］CHOR B，GOLDREICH O，KUSHILEVITZ E，et al．Private information retrieval［C］／／Proceedings of the Thirty－sixth Annual Symposium on Foundations of Computer Science（FOCS’95）．Wisconsin，USA，1995：41－50．

［13］KHOSHGOZARAN A，SHAHABI C，SHIRANI－MEHR H．Location privacy：Moving beyond k－anonymity，cloaking and anonymizers［J］．Knowledge and Information Systems，2011，26（3）：435－465．

［14］GHINITA G，KAINIS P，KHOSHGOZARAN A，et al．Private queries in location based services：Anonymizersare not necessary［C］／／Proceedings of the ACM Special Interest Group on Management of Data（SIGMOD’08）．British Columbia，Canada，2008：121－132．

［15］PAPADOPOULOS S，BAKIRAS S，PAPADIAS D．Nearest neighbor search with strong location Privacy［C］／／Proceedings of the International Conference on Very Large Data Bases Endowment（VLDB’10）．Singapore，2010，3（1）：619－629．

［16］王璐，孟小峰．位置大數(shù)據(jù)隱私保護(hù)研究綜述［J］．軟件學(xué)報(bào)，2014，25（4）：693－712．

［17］WILLIAMS P，SION R．Usable PIR［C］／／Proceedings of the Network and Distributed System Security Symposium（NDSS’08）．California，USA，2008：1－11．

［18］MOURATIDIS K，HADJIELEFTHERIOU M，PAPADIAS D．Conceptual partitioning：An efficient method for continuous nearest neighbor monitoring［C］／／Proceedings of the ACM Special Interest Group on Management of Data（SIGMOD’05）．Maryland，USA，2005：634－645．