運用秘密資訊擷取機制之隱私保護地理位置服務

A Novel Privacy Preserving Location-Based Service Protocol with Secret Circular Shift for k-NN Search

連奕婷(I-Ting Lien)

指導教授 ： 吳家麟

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

https://doi.org/10.6342/NTU.2012.01170

摘要

無資料

關鍵字

隱私權保護 ； k最近鄰法 ； 地理位置服務 ； 空間填充曲線 ； 同態加密系統

並列摘要

Location-based service (LBS) is booming up in recent years with the rapid growth of mobile devices and the emerging of cloud computing paradigm. Among the challenges to establish LBS, the user privacy issue becomes the most important concerns. A successful privacy-preserving LBS must be secure
and provide accurate query (e.g., k-nearest neighbor) results. In this work, we propose a Private Circular Query Protocol (PCQP) to deal with the privacy and the accuracy issues of privacy-preserving LBS. The protocol consists
of a space filling curve and a public-key homomorphic cryptosystem. We connect the points of interest (POIs) on a map to form circular structure with the aid of Moore curve and utilize the homomorphism of Paillier cryptosystem to perform secret circular shifts of POI-related information (POI-info) stored on the server side. Since the POI-info after shifting and the amount of shifts are encrypted, LBS providers (e.g., servers) have no knowledge about the user’s location during query process. The protocol can resist correlation attack and support multi-user scenario as long as the pre-described secret circular shift is performed before each query, in other words, the robustness of the proposed protocol is the same as that of one-time pad encryption scheme. As a result, the security level of the proposed protocol is close to perfect secrecy without the aid of a trusted third party and simulation results show that the k-NN query accuracy rate of the proposed protocol is higher than 90% even when k is large.

並列關鍵字

Privacy Preserving ； k-Nearest Neighbor ； Location-Based service ； Space-Filling Curve ； Homomorphic Cryptosystem

參考文獻

[2] C.-Y. Chow, M. F. Mokbel, andW. G. Aref. Casper*: Query processing for location services without compromising privacy. ACM Trans. Database Syst., 34:24:1–24:48,

[4] M. Gruteser, D. Grunwalddepartment, and C. Science. Anonymous usage of location-based services through spatial and temporal cloaking. pages 31–42, 2003.

[5] J. Hoffstein, J. Pipher, and J. H. Silverman. Ntru: A ring-based public key cryptosystem. In J. Buhler, editor, ANTS, volume 1423 of Lecture Notes in Computer Science, pages 267–288. Springer, 1998.

[6] A.-A. Hossain, A. Hossain, H.-K. Yoo, and J.-W. Chang. H-star: Hilbert-order based star network expansion cloaking algorithm in road networks. pages 81 –88, aug. 2011.

[8] P. Kalnis, G. Ghinita, K. Mouratidis, and D. Papadias. Preventing location-based identity inference in anonymous spatial queries. IEEE Trans. on Knowl. and Data Eng., 19:1719–1733, December 2007.