Reasonable Estimated K Nearest Neighbor Queries with Locality and Query Privacy
Keywords:
Location based query, location and query privacy, private information retrieval, Parlier cryptosystem, RSA.Abstract
In mobile communication, spatial queries pose a serious threat to user location privacy because the location of a query may reveal sensitive information about the mobile user. In this paper, we study approximate k nearest neighbor (KNN) queries where the mobile user queries the location-based service (LBS) provider about approximate k nearest points of interest (POIs) based on his current location. We propose a basic solution and a generic solution for the mobile user to preserve his location and query privacy in approximate KNN queries. The proposed solutions are mainly built on the Parlier public-key cryptosystem and can provide both location and query privacy. To preserve query privacy, our basic solution allows the mobile user to retrieve one type of POIs, for example, approximate k nearest car parks, without revealing to the LBS provider what type of points is retrieved. Our generic solution can be applied to multiple discrete type attributes of private location-based queries. Compared with existing solutions for KNN queries with location privacy, our solution is more efficient. Experiments have shown that our solution is practical for KNN queries.
References
- M. Bellare and P. Roadway. Optimal asymmetric encryption - how to encrypt with RSA. In Proc. Eurocrypt 1994.
- B. Bamba, L. Liu, P. Pesti, and T. Wang. Supporting anonymous location queries in mobile environments with PrivacyGrid. In Proc. WWW 2008.
- A. R. Beresford and F. Stajano. Location privacy in pervasive computing. IEEE Pervasive Computing 2(1), 2003.
- C. Y. Chow, M. F. Mokbel, and X. Liu. A peer-to-peer spatial cloaking algorithm for anonymous location-based services. In Proc. ACM GIS 2006.
- T. ElGamal. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31 (4): 469-472, 1985.
- Y. Elmehdwi, B. K. Samanthula, W. Jiang. Secure k-nearest neigh-bor query over encrypted data in outsourced environments. In Proc. ICDE 2014.
- C. Gentry and Z. Ramzan. Single-database private information retrieval with constant communication rate. In Proc. ICALP’05, pages 803-815, 2005.
- G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, and K.-L. Tan. Private queries in location-based services: Anonymizers are not necessary. In Proc. ACM SIGMOD 2008.
- G. Ghinita, P. Kalnis, M. Kantarcioglu, and E. Bertino. Approx-imate and exact hybrid algorithms for private nearest-neighbor queries with database protection. GeoInformatica 15(14): 699-726, 2010.
- G. Ghinita, R. Rughinis. An efficient privacy-reserving system for monitoring mobile users: making searchable encryption practical. in Proc. ACM CODASPY 2014.
- Haibo Hu, Jianliang Xu, Chushi Ren, and Byron Choi, Processing Private Queries over Untrusted Data Cloud through Privacy Homomorphism, In Proc. ICDE 2011.
- A. Khoshgozaran and C. Shahabi. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In Proc. SSTD 2007.
- H. Kido, Y. Yanagisawa, and T. Satoh. An anonymous commu-nication technique using dummies for location-based services. In Proc. ICPS 2005, pages 88 - 97.
- E. Kushilevitz and R. Ostrovsky. Replication is not needed: single database, computationally-private information retrieval. In Proc. 38th Annual Symposium on Foundations of Computer Science, pages 364-373, 1997.
- M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The new casper: query processing for location services without compromising privacy. In Proc. VLDB 2006.
- G. Myles, A. Friday, and N. Davies. Preserving privacy in envi-ronments with location-based applications. IEEE Pervasive Com-puting 2(1):5664, 2003.
- M. Naor and B. Pinkas. Oblivious transfer with adaptive queries. In Proc. CRYPTO 1999, pages 791 - 791.
- R. Ostrovsky and W. Skeith. A survey of single-database private information retrieval: techniques and applications. In Proc. PKC 2007, pages 393 - 411.
- P. Paillier. Public key cryptosystems based on composite degree residue classes. In Proc. EUROCRYPT 1999, pages 223 - 238.
- B. Palanisamy and L. Liu. Mobimix: Protecting location privacy with mix-zones over road networks. In Proc. ICDE 2011, pages 494 505.
- S. Papadopoulos, S. Bakiras, D. Papadias. Nearest neighbor search with strong location privacy. In Proc. VLDB 2010.
- R. Paulet, M. Golam Kaosar, X. Yi, and E. Bertino. Privacy-preserving and content-protecting location based queries. In Proc. ICDE 2012, pages 44 - 53.
- R. Paulet, M. Golam Kaosar, X. Yi, and E. Bertino. Privacy-preserving and content-protecting location based queries. IEEE Transactions on Knowledge and Data Engineering, accepted in 2013.
- Rabin, Michael. Digitalized signatures and public-key functions as intractable as factorization. MIT Laboratory for Computer Science, January 1979.
- R. Rivest, A. Shamir and L. Adleman. A method for obtaining dig-ital signatures and public-key cryptosystems. Communications of the ACM 21 (2): 120-126, 1978.
- R. Schlegel, C. Chow, Q. Huang, D. Wong. User-defined privacy grid system for continuous location-based services. IEEE Trans-actions on Mobile Computing, Jan. 2015.
- P. Shankar, V. Ganapathy and L. Iftode. Privately querying location-based services with SybilQuery. In Proc. Ubicomp 2009, pages 31 - 40.
- L. Sweeney. k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl.-Based Syst. 10: 557 - 570, 2002.
- S. Wang, X. Ding, R. H. Deng, and F. Bao. Private information retrieval using trusted hardware. In Proc. ESORICS 2006.
- P. Williams and R. Sion. Usable PIR. In NDSS, 2008.
- W. K. Wong, D. W. Cheung, B. Kao, and N. Mamoulis. Secure kNN computation on encrypted databases. In Proc. SIGMOD 2009.
Downloads
Published
Issue
Section
License
Copyright (c) IJSRCSEIT
This work is licensed under a Creative Commons Attribution 4.0 International License.