Skip to main content
SpringerLink
Log in

A Novel Quantum Solution to Privacy-Preserving Nearest Neighbor Query in Location-Based Services

  • Published:
International Journal of Theoretical Physics Aims and scope Submit manuscript

Abstract

We present a cheating-sensitive quantum protocol for Privacy-Preserving Nearest Neighbor Query based on Oblivious Quantum Key Distribution and Quantum Encryption. Compared with the classical related protocols, our proposed protocol has higher security, because the security of our protocol is based on basic physical principles of quantum mechanics, instead of difficulty assumptions. Especially, our protocol takes single photons as quantum resources and only needs to perform single-photon projective measurement. Therefore, it is feasible to implement this protocol with the present technologies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Gruteser, M., Grunwald, D.: Anonymous usage of location-based services through spatial and temporal cloaking. International Conference on Mobile Systems Applications, and Services, DBLP. pp. 31–42 (2003)

  2. Chow, C.Y., Mokbel, M.F.: Privacy in location-based services: a system architecture perspective. Sigspatial Special 1(1), 23–27 (2009)

    Article  Google Scholar 

  3. Man, L.Y., Jensen, C.S., Huang, X., et al.: Space twist: managing the trade-offs among location privacy, query performance, and query accuracy in mobile services. In: Proceedings of International Conference on Data Engineering. IEEE, pp. 366–375 (2008)

  4. Gong, Z., Sun, G.Z., Xie, X.: Protecting privacy in Location-Based services using K-Anonymity without cloaked region. In: Proceedings of eleventh international conference on mobile data management. IEEE, pp. 366–371 (2010)

  5. Khoshgozaran, A., Shirani-Mehr, H., Shahabi, C.: Blind evaluation of location based queries using space transformation to preserve location privacy. GeoInformatica 17(3), 599–634 (2013)

    Article  Google Scholar 

  6. Yi, X., Paulet, R., Bertino, E., et al.: Practical k nearest neighbor queries with location privacy. In: Proceedings of International Conference on Data Engineering. IEEE, pp. 640–651 (2014)

  7. Paulet, R., Kaosar, M.G., Yi, X., et al.: Privacy-preserving and content-protecting location based queries. IEEE Trans. Knowl. Data Eng. 26(4), 1200–1210 (2014)

    Article  Google Scholar 

  8. Niu, B., Li, Q., Zhu, X., et al.: A fine-grained spatial cloaking scheme for privacy-aware users in location-based services. In: Proceedings of International Conference on Computer Communication and Networks. IEEE, pp. 1–8 (2014)

  9. Xu, J., Yu H., Xu C., et al.: A dynamic spatial cloaking algorithm for location privacy. In: Proceedings of IET International Conference on Information Science and Control Engineering. IET, pp. 2.66–2.66 (2014)

  10. Xu, N., Zhu, D., Liu, H., et al.: Combining spatial cloaking and dummy generation for location privacy preserving. In: Proceedings of International Conference on Advanced Data Mining & Applications. LNCS 7713, pp. 701–712 (2012)

  11. Giovannetti, V., Lloyd, S., Maccone, L.: Quantum private queries. Phys. Rev. Lett. 100(23), 230502 (2008)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  12. Jakobi M., Simon C., Gisin N., et al.: Practical private database queries based on a quantum-key-distribution protocol. Phys. Rev. A 83(1), 022301 (2011)

    Article  ADS  Google Scholar 

  13. Gao, F., Liu, B., Wen, Q.Y., et al.: Flexible quantum private queries based on quantum key distribution. Opt. Express 20(16), 17411–17420 (2012)

    Article  ADS  Google Scholar 

  14. Yang, Y.G., Sun, S.J., Wang, Y.: Quantum oblivious transfer based on a quantum symmetrically private information retrieval protocol. Int. J. Theor. Phys. 54 (2), 910–916 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  15. Zhang, J.L., Guo, F.Z., Gao, F., et al.: Private database queries based on counterfactual quantum key distribution. Phys. Rev. A 88(1), 195–201 (2013)

    Google Scholar 

  16. Yang, Y.G., Sun, S.J., Xu, P., et al.: Flexible protocol for quantum private query based on b92 protocol. Quantum Inf. Process 13(2), 805–813 (2014)

    Article  MathSciNet  Google Scholar 

  17. Wang, T.Y., Wang, S.Y., Ma, J.F.: Robust quantum private queries. Int. J. Theor. Phys. 55(6), 3309–3317 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  18. Liu, B., Gao, F., Huang, W., et al: QKD-Based quantum private query without a failure probability. Sci. China Phys. Mech. Astron. 58(9), 100301 (2015)

    Article  Google Scholar 

  19. Gao, F., Liu, B., Huang, W., et al.: Postprocessing of the oblivious key in quantum private query. IEEE J. Sel. Top. Quantum Electron. 21(2), 98–108 (2014)

    Google Scholar 

  20. Wei-Xu, S., Xing-Tong, L., Jian, W., et al.: Multi-bit quantum private query. Commun. Theor. Phys. 64(2), 299 (2015)

    ADS  MathSciNet  Google Scholar 

  21. Raynal, P.: Unambiguous state discrimination of two density matrices in Quantum Information Theory. arXiv:quant-ph/0611133 (2006)

  22. Herzog, U., Bergou, J.A.: Optimum measurement for unambiguously discriminating two mixed states: General considerations and special cases. J. Phys. Conf. Ser. 36(1), 49–54 (2005)

    Google Scholar 

  23. Lu, X.M., Luo, S., Oh, C.H.: Hierarchy of measurement-induced Fisher information for composite states. Phys. Rev. A 86(1), 1536–1538 (2012)

    Google Scholar 

  24. Martini, F.D., Giovannetti, V., Lloyd, S., et al.: Experimental quantum private queries with linear optics. Phys. Rev. A 80(1), 2460–2462 (2009)

    Article  Google Scholar 

  25. Chan, P., Luciomartinez, I., Mo, X., et al.: Performing private database queries in a real-world environment using a quantum protocol. Sci. Rep. 4(23), 81–81 (2014)

    Google Scholar 

  26. Zhou, N., Hua, T., Gong, L., Pei, D., Liao, Q.: Quantum image encryption based on generalized Arnold transform and double random phase encoding. Quantum Inf. Process 14(3), 1193–1213 (2015)

    Article  ADS  MathSciNet  MATH  Google Scholar 

  27. Zhou, N., Hu, Y., Gong, L., Li, G.: Quantum image encryption scheme with iterative generalized arnold transform and quantum image cycle shift operations. Quantum Inf. Process 16(5), UNSP164 (2017)

    Article  ADS  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This work was supported by National Natural Science Foundation of China (Nos. 61772001 and 11301002), and Talents Youth Fund of Anhui Province Universities (2013SQRL006ZD).

Author information

Authors and Affiliations

  1. School of Computer Science and Technology, Anhui University, Hefei, 230601, China

    Zhen-yu Luo, Run-hua Shi, Min Xu & Shun Zhang

Authors
  1. Zhen-yu Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Run-hua Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Min Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shun Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Run-hua Shi.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Luo, Zy., Shi, Rh., Xu, M. et al. A Novel Quantum Solution to Privacy-Preserving Nearest Neighbor Query in Location-Based Services. Int J Theor Phys 57, 1049–1059 (2018). https://doi.org/10.1007/s10773-017-3637-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10773-017-3637-7

Keywords

Search

Navigation