摘要
隨著大數據的發展，大規模的數據越來越多的以密文的形式存儲在雲伺服器中。本文重點討論了在雲伺服器中，如何對已加密的數據進行快速的範圍搜索。當可信任的數據持有者將加密的數據上傳到雲伺服器後，雲伺服器支持大量的用戶搜索數據，並在不可解密數據及查找範圍的前提下，對數據搜索進行精確的匹配。本文提出了通過建立安全索引的方式對一維、二維數據進行範圍查詢的模型，並用百萬的數據驗證了方法的可行性與正確性。
關鍵詞 隱私保護 範圍查詢 HMAC加密 數據索引
ABSTRACT
With the vigorous development and progress of big data, cloud server plays an important role in the data storage and processing.The paper focuses on fast range query based on the encrypted data . When trusted data owner upload the encrypted data to the cloud server, a large amount of users can search data from cloud server. The cloud server should accurately match the data range and return to the users .This paper established a fast range model based on encrypted data. With one million Twitter site data experimental verification, we prove that our model is feasible and efficiency.
KEY WORDS Privacy-Preserving Range Query HMAC Data Index
第一章 緒論
1.1 研究背景
為了數據運行的高可靠性、高運算性能和快速的計算能力，人們越來越多的利用雲伺服器來運行數據以及計算服務。而在雲計算中，隱私問題成為關鍵。
雲計算模型中涉及三個實體，數據持有者和客戶都是可信任的，雲伺服器是不可信任的，因此數據持有者和客戶的數據以及查詢範圍都以密文的形式發送給雲伺服器。
1.2 研究意義
當前的雲伺服器不支持加密數據搜索，如果解決了雲伺服器中加密數據搜索問題將會極大的改善數據安全問題並可應用於許多實際場景中，因此這個研究問題是非常重要也是今後必須解決的問題。而當前的方法[1,2,3,4]都不足以保護隱私並且高效的搜索，本文提出的算法將把隱私保護與快速搜索相結合，提出一種新的範圍搜索模型。
1.3 主要貢獻
本文主要做出如下貢獻：
1．在已有一維數據搜索模型基礎上提出了新的二維數據搜索模型。
2．對二維搜索模型做出了創新型的優化，使搜索效率有了明顯提高。
3．提出了將二維搜索模型應用到KNN[5,6]（K鄰近點搜索）等實際應用場景中，解決了實際的搜索問題。
1.4 搜索模型系統架構
對於一維數據和二維數據，我們都採用如圖1-1所示的搜索模型，這個模型由Alex最先提出[7]。
工作流程已在圖中標明：
①由數據持有者利用原始數據集建立一個加密數據索引。
②數據持有者用對稱密鑰K對原始數據集進行加密，得到加密數據集，並將加密數據集以及上一步得到的數據索引上傳給雲伺服器。
③客戶端將查找範圍進行HMAC加密後上傳給雲伺服器。
④雲服務利用加密數據索引對搜索範圍進行查找。
⑤雲伺服器將查詢到的加密數據返回給客戶，客戶利用對稱密鑰K對加密數據進行解密，得到原始數據。
第二章 一維數據搜索模型
對應於上一章的系統架構，本章對一維數據搜索[7]主要從數據持有者建立數據索引，客戶端上傳搜索範圍，雲伺服器進行範圍查詢這三個方面進行討論。
2.1 數據持有者建立數據索引
建立數據索引主要包括三個步驟：
1.進行前綴編碼：將原始數據表示成二進位形式，並用這個而二進行所有的前綴組成前綴編碼集合。
2.建立平衡二叉樹的數據索引：將上一步中的前綴編碼建立一棵平衡二叉樹，建樹方式與數據大小順序無關，從而保證索引結構不可分辨性。
3.進行HMAC加密[8]並映射到Bloom Filter[9]：對於上一步中建立的平衡二叉樹內的元素（數據的前綴編碼）進行HMAC加密。對於根節點，使用H個不同密鑰對原始數據進行加密，並且在樹的每一層引入一個v.R的隨機數進行二次加密，從而消除節點間相同元素的相關性。並將加密的值映射到一個Bloom Filter的位數組中，從而減小數據索引的空間大小。
2.2 客戶端上傳搜索範圍
客戶採用與數據持有者相同的前綴編碼方法對數據範圍進行前綴編碼，將查詢範圍轉化為最小的前綴編碼集S(a,b)，使這個集合的前綴數最少，且可以表示這個範圍。將S(a,b)同樣用與數據持有者相同的密鑰進行H次HMAC加密，將加密的數據集上傳給雲伺服器。
2.3 雲伺服器進行範圍查詢
對於客戶端傳來的加密搜索範圍，雲伺服器將每一個加密數據與樹型索引的每一個節點進行Bloom Filter的匹配，若匹配則可判斷該節點下的葉子節點中存在滿足範圍的數據，則繼續遍歷此子樹直到遍歷到葉子節點，雲伺服器將葉子節點指向的數據傳給客戶端，完成搜索過程。
第三章 二維數據搜索模型
不同於一維數據的前綴編碼，對於二維數據本文採用柵格編碼對數據進行轉換。
3.1 數據持有者建立數據索引
二維模型中建立數據索引也需要三個步驟：
1.柵格編碼[10]：
對於二維數據，本文將二維數據映射到一個平面，並對這個平面進行柵格的劃分，如圖3-1。將每一個點用K級的柵格編碼進行表示（本文對於柵格採用格子中心點坐標來表示此格子的編碼），即完成柵格編碼。
2.建立平衡四叉樹的數據索引,由於在二維平面中利用柵格劃分，每一級柵格都將平面分為四個部分，因此我們採用平衡四叉樹來存儲數據的索引。建立方法與一維模型中方法相同。
3.將上一步的數據索引進行HMAC加密並映射到Bloom Filter 中，具體方法與一維搜索模型方法相同。
3.2 客戶端上傳搜索範圍
與一維數據不同，二維數據（如地理位置）搜索上傳的範圍一般是以客戶端所在的地理位置為圓心，以r為搜索半徑的一個圓形搜索範圍，如圖3-2。在客戶端同樣採用柵格編碼的方法，將這個二維平面進行柵格的劃分。這個圓形的搜索範圍將包含如圖中填色的這些柵格。用這些柵格來表示客戶的搜索範圍。
下一步，對圓形搜索範圍所覆蓋的柵格編碼進行HMAC加密，並將加密的數據上傳給雲伺服器。
3.3 雲伺服器進行範圍查詢
雲伺服器對二維數據搜索過程與一維模型介紹方法基本相同，此處不做贅述。
3.4 二維數據搜索的優化
本文採用柵格編碼的方法已將搜索範圍轉化為一個簡單高效的表示方法，為了提高搜索速率，我們需要從數據索引的結構進行討論與優化。本章中通過優化數據索引的結構（廣度優化）以及搜索過程（深度優化）從而提高搜索的速率。
廣度優化指將相鄰的點儘量分配到數據索引的同一棵子樹中，這樣可以減少查詢次數。但為了數據安全，設置閾值T，當一個節點內數據個數大於T時，才可進行廣度優化。
深度優化是指，當一個節點內元素全部滿足範圍時，則直接返回其子樹的所有葉子結點。這就需要建立數據索引時，保存每個節點內的公共柵格編碼，從而使查詢時減少查詢的深度。
第四章 實驗驗證
4.1 實驗數據集
本文從推特網站上收集了一百萬個用戶的位置數據，數據包含用戶的ID，用戶位置的x坐標與y坐標。坐標以經度和緯度的格式存儲。我們分別進行三個實驗，實驗一是用二維搜索模型進行二維數據範圍的搜索，實驗二是採用優化的二維搜索模型對二位數據範圍進行搜索，實驗三是採用Alex提出的一維搜索模型進行二維數據範圍的搜索，並記錄每個實驗中數據索引的建立時間，數據索引的空間大小，範圍搜索的時間，範圍搜索的結果誤差等，並通過實驗間的對比來分析不同模型的優缺點。
4.2 實驗結果分析
4.2.1 搜索時間分析
在三組實驗參數設置相同的情況下，通過改變搜索範圍進行多次實驗，實驗結果都標明，利用優化的二維搜索模型進行搜索的效率大大高於其他兩組對比實驗，而一維搜索模型的實驗中搜索時間是最長的。
對於實驗二，保證其他參數不變，改變安全閾值T，當T值越大時，代表優化程度越低，實驗中搜索時間越長，當T大於總數據個數時，代表未進行優化，則實驗二搜索時間與實驗一相同。
4.2.2 數據索引建立時間分析
實驗中，通過記錄數據索引的建立時間可知，優化的二維搜索模型的數據索引建立時間遠大於其他兩個實驗組的數據索引建立時間，其他兩個實驗組建立時間相近，對於一百萬的數據，優化的二維搜索模型大約需要建立7000s，而其他兩個實驗組建立大約3000s。
4.2.3 搜索誤差分析
本文提到過，當對二維搜索範圍進行柵格編碼時，我們存儲的柵格是搜索範圍完全覆蓋的柵格，因此對於覆蓋一部分的柵格被我們忽略，這就產生了搜索結果的誤差。本文拿實驗一進行實驗，通過改變柵格級數來計算誤差。實驗結果標明，柵格級數越大，誤差越小，當柵格級數為15級時，誤差為百分之三。
第五章 結束語
本文在已提出的一維模型基礎上設計了針對二維數據範圍的搜索模型，使二維的加密數據可以以很高的效率進行搜索，並且同時保證了數據的安全性。在二維數據範圍搜索模型的基礎上，本文又對二維數據同時進行了深度優化以及廣度優化，將搜索速率大大的降低。
對於二維加密數據的搜索，在現實生活中也有很多應用的場景，如KNN搜索問題等，因此本文討論的問題具有很多實際的應用價值。
參考文獻
[1] B. Hore, S. Mehrotra, M. Canim, and M. Kantarcioglu. Secure multidimensional range queries over outsourced data. The VLDB Journal, 21(3):333–358, June 2012.
[2] B. Hore, S. Mehrotra, and G. Tsudik. A privacy-preserving index for range queries. In VLDB, pages 720–731, 2004.
[3] A. Boldyreva, N. Chenette, Y. Lee, and A. O』Neill. Order-preserving symmetric encryption. In EUROCRYPT, pages 224–241, 2009.
[4] A. Boldyreva, N. Chenette, and A. O』Neill. Order-preserving encryption revisited: Improved security analysis and alternative solutions. In CRYPTO, 2011.
[5] N. Li, T. Li, and S. Venkatasubramanian. t-closeness: Privacy beyond k-anonymity and l-diversity. In Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on, pages 106–115, April 2007.
[6] W. K. Wong, D. W.-L. Cheung, B. Kao, and N. Mamoulis. Secure knn computation on encrypted databases. In SIGMOD, pages 139–152, July 2009.
[7]Rui Li, Alex X. Liu, Ann L. Wang, Bezawada Bruhadeshwar:Fast Range Query Processing with Strong Privacy Protection for Cloud Computing. PVLDB?7(14): 1953-1964(2014)
[8] Praveen Gauravaram, Shoichi Hirose, Suganya Annadurai.An Update on the Analysis and Design of NMAC and HMAC Functions.International Journal of Network Security, 2008, Vol.7 (1), pp.49.
[9] Kumar A,Xu J.Space-Code bloom filter for efficient per-flow traffic measurement. Proc.of the IEEE INFOCOM2004.
[10] Hien To, Gabriel Ghinita, Cyrus Shahabi:A Framework for Protecting Worker Location Privacy in Spatial Crowdsourcing. PVLDB?7(10): 919-930 (2014).
(責編：溫靜、趙光霞)