臺灣博碩士論文加值系統

近年來由於雲端運算的普及，資料擁有者將資料放至雲端變得是一件相當方便的事情。擁有強大運算能力及大量儲存空間的雲端可以作為一個資料庫平台，讓資料擁有者將其收藏與他人分享，即提供給使用者做查詢。然而，基於隱私權保護，資料在上傳前都應先經加密程序加以保護。在這篇論文中，我們提出了一個新的基於隱私保護的雲端K近鄰搜尋法，此方法是讓使用者能夠在加密的雲端資料庫中找出對應特定查詢點的K個最近的鄰居。比起現有的其他方法，我們的方法可將更多搜尋所需的運算量移至雲端，而且資料擁有者不需要將他的加密金鑰分給其他人。安全性的分析證明此方法能夠同時保護資料及查詢的隱私性，又由於我們將資料庫交由樹狀結構來管理，搜尋複雜度可以比線性搜尋來的更快。最後，實驗結果顯示出本文所提出之整體方法對於使用者來說負擔很低且相當有效率。

With the growing popularity of cloud computing, it is convenient for data owners to outsource their data to a cloud server. By utilizing the massive storage and computational resources in cloud, data owners can also provide a platform for users to make query requests. However, due to the privacy concerns, sensitive data should be encrypted before outsourcing. In this work, a novel privacy preserving K-nearest neighbor (K-NN) search scheme over the encrypted outsourced cloud dataset is proposed. The problem is about letting cloud server to find K nearest points with respect to an encrypted query on the encrypted dataset, which was outsourced by data owner, and return the searched results to the querying user. Comparing with other existing methods, our approach leverages the resources of cloud more by shifting most of the required computational loads, from data owner and query user, to the cloud server. Also, there is no need for data owner to share his secret key with others. Security analyses prove that both data privacy and query privacy are preserved in the proposed scheme. Moreover, complexity analysis shows sub-linear search complexity can be achieved due to the use of a tree structure, in our approach. Finally, experimental results demonstrate the practicability and the efficiency of our method.

口試委員審定書 ii
誌謝 iii
摘要 iv
Abstract v
List of Figures vii
List of Tables viii
Introduction 1
Related Works 4
Preliminaries 7
3.1 Paillier Cryptosystem 7
3.2 Order-preserving Encryption 8
3.3 R-tree 10
3.3.1 Bulk-loading 11
3.3.2 K-NN search over R-tree 12
The Proposed Scheme 13
4.1 Overview 13
4.2 Encryption Method 14
4.3 Security Building Blocks 15
4.3.1 R-tree construction on the encrypted domain 15
4.3.2 Secure compare and secure mOPE 17
4.3.3 Secure Square Euclidean Distance 18
Security Analysis 23
5.1 Indistinguishability under Order Chosen Plaintext Attack 23
5.2 Privacy Preserving of Data 24
5.3 Privacy Preserving of Query 25
Performance Evaluation 26
6.1 Complexity Analysis 26
6.2 Experimental Results 28
Conclusion and Future Works 34
Bibliography 35

[1]Guttman, Antonin. R-trees: a dynamic index structure for spatial searching. Vol. 14. No. 2. ACM, 1984.
[2]Popa, Raluca Ada, Frank H. Li, and Nickolai Zeldovich. "An ideal-security protocol for order-preserving encoding." Security and Privacy (SP), 2013 IEEE Symposium on. IEEE, 2013.
[3]Paillier, Pascal. "Public-key cryptosystems based on composite degree residuosity classes." International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 1999.
[4]Wong, Wai Kit, et al. "Secure knn computation on encrypted databases." Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. ACM, 2009.
[5]Hu, Haibo, et al. "Processing private queries over untrusted data cloud through privacy homomorphism." Data Engineering (ICDE), 2011 IEEE 27th International Conference on. IEEE, 2011.
[6]Yao, Bin, Feifei Li, and Xiaokui Xiao. "Secure nearest neighbor revisited." Data Engineering (ICDE), 2013 IEEE 29th International Conference on. IEEE, 2013.
[7]Elmehdwi, Yousef, Bharath K. Samanthula, and Wei Jiang. "Secure k-nearest neighbor query over encrypted data in outsourced environments." Data Engineering (ICDE), 2014 IEEE 30th International Conference on. IEEE, 2014.
[8]Wang, Boyang, Yantian Hou, and Ming Li. "Practical and secure nearest neighbor search on encrypted large-scale data." Computer Communications, IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on. IEEE, 2016.
[9]Xu, Rui, et al. "Privacy-preserving k-nearest neighbour query on outsourced database." Australasian Conference on Information Security and Privacy. Springer International Publishing, 2016.
[10]Zhou, Lu, Youwen Zhu, and Aniello Castiglione. "Efficient k-NN query over encrypted data in cloud with limited key-disclosure and offline data owner." Computers & Security, 2016.
[11]Zhu, Youwen, Zhiqiu Huang, and Tsuyoshi Takagi. "Secure and controllable k-nn query over encrypted cloud data with key confidentiality." Journal of Parallel and Distributed Computing 89: 1-12, 2016.
[12]Jonathan Katz, Y. L. "Introduction to Modern Cryptography." 2007.
[13]Agrawal, Rakesh, et al. "Order preserving encryption for numeric data." Proceedings of the 2004 ACM SIGMOD international conference on Management of data. ACM, 2004.
[14]Boldyreva, Alexandra, et al. "Order-preserving symmetric encryption." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 2009.
[15]Leutenegger, Scott T., Mario A. Lopez, and Jeffrey Edgington. "STR: A simple and efficient algorithm for R-tree packing." Data Engineering, 1997. Proceedings. 13th international conference on. IEEE, 1997.
[16]Hjaltason, Gísli R., and Hanan Samet. "Distance browsing in spatial databases." ACM Transactions on Database Systems (TODS) 24.2: 265-318, 1999.
[17]Henrich, Andreas. "A Distance Scan Algorithm for Spatial Access Structures." ACM-GIS. 1994.
[18]Goldreich, Oded. "Foundation of cryptography (in two volumes: Basic tools and basic applications)." 2001.