Blind evaluation of location based queries using space transformation to preserve location privacy
Tóm tắt
In this paper we propose a fundamental approach to perform the class of Range and Nearest Neighbor (NN) queries, the core class of spatial queries used in location-based services, without revealing any location information about the query in order to preserve users’ private location information. The idea behind our approach is to utilize the power of one-way transformations to map the space of all objects and queries to another space and resolve spatial queries blindly in the transformed space. Traditional encryption based techniques, solutions based on the theory of private information retrieval, or the recently proposed anonymity and cloaking based approaches cannot provide stringent privacy guarantees without incurring costly computation and/or communication overhead. In contrast, we propose efficient algorithms to evaluate KNN and range queries privately in the Hilbert transformed space. We also propose a dual curve query resolution technique which further reduces the costs of performing range and KNN queries using a single Hilbert curve. We experimentally evaluate the performance of our proposed range and KNN query processing techniques and verify the strong level of privacy achieved with acceptable computation and communication overhead.
Tài liệu tham khảo
Asonov D (2004) Querying databases privately: a new approach to private information retrieval. Lecture notes in computer science, vol 3128. Springer
Beresford AR, Stajano F (2003) Location privacy in pervasive computing. IEEE Pervasive Computing 2(1):46–55
Bouganim L, Pucheral P (2002) Chip-secured data access: confidential data on untrusted servers. In: VLDB’02, pp 131–142
Chien H-Y, Jan J-K, Tseng Y-M (2002) An efficient and practical solution to remote authentication: smart card. Comput Secur 21(4):372–375
Chor B, Kushilevitz E, Goldreich O, Sudan M (1998) Private information retrieval. J ACM 45(6):965–981
Chung K-L, Tsai Y-H, Hu F-C (2000) Space-filling approach for fast window query on compressed images. IEEE Trans Image Process 9(12):2109–2116
Dingledine R, Mathewson N, Syverson PF (2004) Tor: the second-generation onion router. In: USENIX’04, pp 303–320
Faloutsos C, Jagadish H, Manolopoulos Y (1997) Analysis of the n-dimensional quadtree decomposition for arbitrary hyperectangles. IEEE Trans Knowl Data Eng 9(3):373–383
Faloutsos C, Roseman S (1989) Fractals for secondary key retrieval. In: PODS ’89: proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems. New York, NY, USA, pp 247–252
Gedik B, Liu L (2005) A customizable k-anonymity model for protecting location privacy. In: International conference on distributed computing systems (ICDPS), Columbos, Ohio
Ghinita G, Kalnis P, Khoshgozaran A, Shahabi C, Tan K-L (2008) Private queries in location based services: anonymizers are not necessary. In: SIGMOD’08, Vancouver, Canada
Gruteser M, Grunwald D (2003) Anonymous usage of location-based services through spatial and temporal cloaking. In: MobiSys. USENIX
Hilbert D (1891) Uber die stetige abbildung einer linie auf ein flachenstuck. Math Ann 38:459–460
Indyk P, Woodruff DP (2006) Polylogarithmic private approximations and efficient matching. In: Theory of cryptography, third theory of cryptography conference. New York, NY, USA, pp 245–264
Jagadish HV (1990) Linear clustering of objects with multiple atributes. In: Proceedings of the 1990 ACM SIGMOD international conference on management of data. ACM Press, Atlantic City, NJ, pp 332–342
Jagadish HV (1997) Analysis of the Hilbert curve for representing two-dimensional space. Inf Process Lett 62(1):17–22
Kalnis P, Ghinita G, Mouratidis K, Papadias D (2006) Preserving anonymity in location based services. A Technical Report
Khoshgozaran A, Shahabi C (2007) Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In: Advances in spatial and temporal databases, 10th international symposium, SSTD’07, 16–18 July, vol 4605. Boston, MA, USA, pp 239–257
Khoshgozaran A, Shahabi C, Shirani-Mehr H (2011) Location privacy: going beyond k-anonymity, cloaking and anonymizers. Knowl Inf Syst 26(3):435–465
Kushilevitz E, Ostrovsky R (1997) Replication is not needed: single database, computationally-private information retrieval. In: FOCS’97, pp 364–373
Lawder JK, King PJH (2001) Querying multi-dimensional data indexed using the Hilbert space-filling curve. SIGMOD Rec 30(1):19–24
Mokbel MF, Chow C-Y, Aref WG (2006) The new casper: query processing for location services without compromising privacy. In: Proceedings of the 32nd international conference on very large data bases. Korea, pp 763–774
Moon B, Jagadish HV, Faloutsos C, Saltz JH (2001) Analysis of the clustering properties of the Hilbert space-filling curve. IEEE Trans Knowl Data Eng 13(1):124–141
Preneel B (2003) Analysis and design of cryptographic hash functions. PhD thesis
Sagan H (1994) Space-filling curves. Springer
Samarati P, Sweeney L (1998) Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Technical Report SRI-CSL-98-04, SRI Computer Science Laboratory
Tsai Y-H, Chung K-L, Chen W-Y (2004) A strip-splitting-based optimal algorithm for decomposing a query window into maximal quadtree blocks. IEEE Trans Knowl Data Eng 16(4):519–523