Reasonable Estimated K Nearest Neighbor Queries with Locality and Query Privacy

Authors(2) :-Bade Ankamma Rao, Desu Sudhisha

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.

Authors and Affiliations

Bade Ankamma Rao
Department of MCA , St. Mary's Group of Institutions, Guntur, Andhra Pradesh, India
Desu Sudhisha
Department of MCA , St. Mary's Group of Institutions, Guntur, Andhra Pradesh, India

Location based query, location and query privacy, private information retrieval, Parlier cryptosystem, RSA.

  1. M. Bellare and P. Roadway. Optimal asymmetric encryption - how to encrypt with RSA. In Proc. Eurocrypt 1994.
  2. B. Bamba, L. Liu, P. Pesti, and T. Wang. Supporting anonymous location queries in mobile environments with PrivacyGrid. In Proc. WWW 2008.
  3. A. R. Beresford and F. Stajano. Location privacy in pervasive computing. IEEE Pervasive Computing 2(1), 2003.
  4. 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.
  5. T. ElGamal. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31 (4): 469-472, 1985.
  6. Y. Elmehdwi, B. K. Samanthula, W. Jiang. Secure k-nearest neigh-bor query over encrypted data in outsourced environments. In Proc. ICDE 2014.
  7. C. Gentry and Z. Ramzan. Single-database private information retrieval with constant communication rate. In Proc. ICALP’05, pages 803-815, 2005.
  8. 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.
  9. 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.
  10. G. Ghinita, R. Rughinis. An efficient privacy-reserving system for monitoring mobile users: making searchable encryption practical. in Proc. ACM CODASPY 2014.
  11. Haibo Hu, Jianliang Xu, Chushi Ren, and Byron Choi, Processing Private Queries over Untrusted Data Cloud through Privacy Homomorphism, In Proc. ICDE 2011.
  12. A. Khoshgozaran and C. Shahabi. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In Proc. SSTD 2007.
  13. 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.
  14. 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.
  15. 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.
  16. G. Myles, A. Friday, and N. Davies. Preserving privacy in envi-ronments with location-based applications. IEEE Pervasive Com-puting 2(1):5664, 2003.
  17. M. Naor and B. Pinkas. Oblivious transfer with adaptive queries. In Proc. CRYPTO 1999, pages 791 - 791.
  18. R. Ostrovsky and W. Skeith. A survey of single-database private information retrieval: techniques and applications. In Proc. PKC 2007, pages 393 - 411.
  19. P. Paillier. Public key cryptosystems based on composite degree residue classes. In Proc. EUROCRYPT 1999, pages 223 - 238.
  20. B. Palanisamy and L. Liu. Mobimix: Protecting location privacy with mix-zones over road networks. In Proc. ICDE 2011, pages 494 505.
  21. S. Papadopoulos, S. Bakiras, D. Papadias. Nearest neighbor search with strong location privacy. In Proc. VLDB 2010.
  22. 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.
  23. 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.
  24. Rabin, Michael. Digitalized signatures and public-key functions as intractable as factorization. MIT Laboratory for Computer Science, January 1979.
  25. 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.
  26. 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.
  27. P. Shankar, V. Ganapathy and L. Iftode. Privately querying location-based services with SybilQuery. In Proc. Ubicomp 2009, pages 31 - 40.
  28. L. Sweeney. k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl.-Based Syst. 10: 557 - 570, 2002.
  29. S. Wang, X. Ding, R. H. Deng, and F. Bao. Private information retrieval using trusted hardware. In Proc. ESORICS 2006.
  30. P. Williams and R. Sion. Usable PIR. In NDSS, 2008.
  31. W. K. Wong, D. W. Cheung, B. Kao, and N. Mamoulis. Secure kNN computation on encrypted databases. In Proc. SIGMOD 2009.

Publication Details

Published in : Volume 2 | Issue 4 | July-August 2017
Date of Publication : 2017-08-31
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 424-433
Manuscript Number : CSEIT1724101
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

Bade Ankamma Rao, Desu Sudhisha, "Reasonable Estimated K Nearest Neighbor Queries with Locality and Query Privacy", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 4, pp.424-433, July-August-2017.
Journal URL :

Article Preview