基於隱私保護及擁有輕量使用者負擔之雲端K近鄰搜尋方法

A Privacy Preserving Cloud-based K-NN Search Scheme with Lightweight User Loads

徐咏誠(Yeong-Cherng Hsu)

指導教授 ： 吳家麟

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201701499

摘要

近年來由於雲端運算的普及，資料擁有者將資料放至雲端變得是一件相當方便的事情。擁有強大運算能力及大量儲存空間的雲端可以作為一個資料庫平台，讓資料擁有者將其收藏與他人分享，即提供給使用者做查詢。然而，基於隱私權保護，資料在上傳前都應先經加密程序加以保護。在這篇論文中，我們提出了一個新的基於隱私保護的雲端K近鄰搜尋法，此方法是讓使用者能夠在加密的雲端資料庫中找出對應特定查詢點的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.

並列關鍵字

K-NN ； privacy preserving ； cloud ； encryption ； security

參考文獻

[1] Guttman, Antonin. R-trees: a dynamic index structure for spatial searching. Vol. 14. No. 2. ACM, 1984.

[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.

[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.

[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.

[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.