張 峰，倪巍偉

（東南大學 計算機科學與工程學院，南京 211189；東南大學 計算機網絡與信息集成教育部重點實驗室，南京 211189）

1 引 言

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

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

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

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

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

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

論文主要貢獻包括：

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

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

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

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

2 相關工作

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

2．1 常見位置隱私保護方法

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

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

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

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

2．2 基于PIR的位置隱私保護方法

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

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

3 問題描述與相關概念

3．1 問題描述

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

基于PIR的保護位置隱私近鄰查詢方法需解決以下問題：

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

（2）用戶可以在本地通過PIR請求快速生成候選解集．

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

3．2 相關概念

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

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

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

例如，對于數(shù)據(jù)庫DB＝｛O1，O2，O3｝，n＝3，如果偽隨機數(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｝．假設符號PIR（id）表示要查詢的POI實體的標志符．用戶要查詢O1，則id＝1，利用π規(guī)則加密id為3．因此向服務器提交PIR（3）（即采用PIR檢索方法向用同樣規(guī)則加密了的數(shù)據(jù)庫查詢標志符為3的POI）．

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

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

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

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

表1 HPT表結構示意Tab．1 The structure of HPT

表2 NPT表結構示意Tab．2 The structure of NPT

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

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

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

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

4．1 基本思想

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

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

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

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

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

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

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

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

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

4．2 模式攻擊處理

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

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

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

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

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

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！＝φ）

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

7．Integer index＝b1．blocknumber（）；／／index記錄塊號

8．for each POI Pin block b1

9．if（P?。絅ULL）

10．entires P＝b1．pop（）；／／取出塊內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?。溅眨?/p>

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

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｝．按照這個規(guī)則可以加密數(shù)據(jù)庫DB中所有塊內的POI．然后DB按次序儲存DBπ內的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 候選解集生成

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

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

算法2候選解集生成算法

輸入：用戶位置Q，DB1加密重排后的數(shù)據(jù)庫DBπ＿1，查詢目標數(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］／／依次取出塊內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．對c內每一個POI P·id隱私檢索PIR（id）并入S；

19．end for

20．return S；

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

性質1候選集S中一定包含真實的kNN．

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

4．4 算法描述

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

算法3 PRN（Q，k，π）

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

輸出：kNN查詢信息

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

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

3．調用候選集生成算法產生候選集entries＿DBπ＿1；

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

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

6．if（P?。絅ULL）

7．PIR（P·ptr）檢索對應的DBπ＿2＿block并將塊內實體入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；／／返回查詢結果

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

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

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

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

4．5 算法分析

本節(jié)對PRN＿kNN算法的隱私保護強度以及算法時間復雜度進行分析．

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

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

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

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

5 實驗分析

5．1 實驗環(huán)境

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

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

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

5．2 實驗結果分析

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

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

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

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

圖6 候選集大小以及查詢時長（granularity＝256）Fig．6 Candidate size and search cost

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

6 總結與展望

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

［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］．計算機研究與發(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ù)隱私保護研究綜述［J］．軟件學報，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．