这是indexloc提供的服务，不要输入任何密码
Skip to main content
Springer Nature Link
Log in

Secure range query over encrypted data in outsourced environments

  • Published:
World Wide Web Aims and scope Submit manuscript

Abstract

With the rapid development of cloud computing paradigm, data owners have the opportunity to outsource their databases and management tasks to the cloud. Due to privacy concerns, it is required for them to encrypt the databases prior to outsourcing. However, there are no existing techniques handling range queries in a fully secure way. Therefore, in this paper, we focus exactly on the secure processing of range queries over outsourced encrypted databases. To efficiently process secure range queries, the extraordinarily challenging task is how to perform fully secure range queries over encrypted data without the cloud ever decrypting the data. To address the challenge, we first propose a basic secure range queries algorithm which is not absolutely secure (i.e., leaking the privacy of access patterns and path patterns). To meet better security, we present a fully secure algorithm that preserves the privacy of the data, query, result, access patterns and path patterns. To improve the performance further, we also propose two schemes to accelerate query speed. At last, we empirically analyze and conduct a comprehensive performance evaluation using the real dataset to validate our ideas and the proposed secure algorithms.

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

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
Figure 16

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. [z] denotes the standard binary conversion (e.g., for m = 8, [6] = ’00000110’, where m represents the domain size in bits).

  2. (M)\(_{Min}^{Max}\) denotes the point with the minimum and the point with the maximum coordinate values in each dimension, respectively.

  3. http://snap.stanford.edu/data/roadNet-CA.html

  4. http://archive.ics.uci.edu/ml/datasets.html

References

  1. Bellare, M., Rogaway, P.: Optimal asymmetric encryption. Eurocrypto 950(6), 92–111 (1994)

    MathSciNet  MATH  Google Scholar 

  2. Chi, J., Hong, C., Zhang, M., et al.: Fast multi-dimensional range queries on encrypted cloud databases. In: IEEE International Conference on Databases Systems for Advanced Applications, pp 559–575. Springer, SuZhou (2017)

    Chapter  Google Scholar 

  3. Chi, J., Hong, C., Zhang, M., Zhang, Z.: Privacy-enhancing range query processing over encrypted cloud databases. In: WISE, pp 63–77 (2015)

  4. Cui, N., Li, J., Yang, X., et al.: When geo-text meets security: privacy-preserving boolean spatial keyword queries. In: ICDE. IEEE, Macao (2019)

  5. Cui, N., Yang, X., Wang, L., et al.: Secure range query over encrypted data in outsourced environments. In: International Conference on Database Systems for Advanced Applications. Springer, Cham (2018)

    Chapter  Google Scholar 

  6. Dai, Y., Shao, J., Hu, G., et al.: A resource-aware approach for authenticating privacy preserving GNN queries. World Wide Web (2017)

  7. Elmehdwi, Y., Samanthula, B.K., Jiang, W.: Secure K-nearest neighbor query over encrypted data in outsourced environments. In: The ICDE, pp 664–675. IEEE, Chicago (2014)

  8. Hore, B., Mehrotra, S., Canim, M., Kantarcioglu, M.: Secure multidimensional range queries over outsourced data. The VLDB Journal. 21(3), 333–358 (2012)

    Article  Google Scholar 

  9. Hore, B., Mehrotra, S., Tsudik, G.: A privacy-preserving index for range queries. In: Thirtieth International Conference on Very Large Data Bases VLDB Endowment, pp 720–731. ACM, Toronto (2004)

    Chapter  Google Scholar 

  10. Hu, H., Xu, J., Ren, C., Choi, B.: Processing private queries over untrusted data cloud through privacy homomorphism. In: ICDE, pp 601–612. IEEE, Hannover (2011)

  11. Kim, H.I., Kim, H.J., Chang, J.W.: A range query processing algorithm hiding data access patterns in outsourced database environment. In: International Conference on Data Mining and Big Data, pp 434–446. Springer, Cham (2016)

    Chapter  Google Scholar 

  12. Li, J., Cai, T., Mian, A., Li, R., Sellis, T., Yu, J.X.: Holistic influence maximization for targeted advertisements in spatial social networks. IEEE International Conference on Data Engineering (ICDE), pp. 1340–1343 (2018)

  13. Li, R., Liu, A.X., Wang, A.L., et al.: Fast and scalable range query processing with strong privacy protection for cloud computing. IEEE/ACM Trans. Networking 24 (4), 2305–2318 (2016)

    Article  Google Scholar 

  14. Li, J., Wang, X., Deng, K., Sellis, T., Yu, J.X., Yang, X.: Discovering influential community over large social networks. The 33rd IEEE International Conference on Data Engineering (ICDE), pp. 871–882 (2017)

  15. Li, S.P., Wong, M.H.: Privacy-preserving queries over outsourced data with access pattern protection. In: IEEE International Conference on Data Mining Workshop, pp 581–588. IEEE, Shenzhen (2014)

  16. Liu, A., Kai, Z., Lu, L., et al.: Efficient secure similarity computation on encrypted trajectory data. In: International Conference on Data Engineering, pp 66–77. IEEE, Seoul (2015)

  17. Liu, J., Yang, J., Xiong, L., et al.: Secure skyline queries on cloud platform. In: International Conference on Data Engineering, pp 633–645. IEEE, San Diego (2017)

  18. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: International Conference on Theory and Application of Cryptographic Techniques, pp 223–238. Springer, Prague (1999)

  19. Rivest, R.L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 26(2), 96–99 (1978)

    MathSciNet  MATH  Google Scholar 

  20. Samanthula, B.K.K., Hu, C., Jiang, W.: An efficient and probabilistic secure bit-decomposition. In: The ASIA CCS, pp 541–546. ACM, Hangzhou (2013)

  21. Shi, E., Bethencourt, J., Chan, T.H., et al.: Multi-dimensional range query over encrypted data. In: Security and Privacy, pp 350–364. IEEE (2007)

  22. Wang, B., Hou, Y., Li, M., Wang, H., Li, H.: Maple: scalable multi-dimensional range search over encrypted cloud data with tree-based index. In: The ASIA CCS, pp 111–122. ACM, Kyoto (2014)

  23. Wang, B., Li, M., Wang, H.: Geometric range search on encrypted spatial data. IEEE Trans. Inf. Forensics Secur. 11(4), 704–719 (2016)

    Google Scholar 

  24. Wang, P., Ravishankar, C.V.: Secure and efficient range queries on outsourced databases using \(\widehat {R}\)-Trees. In: IEEE International Conference on Data Engineering, pp 314–325. IEEE, Brisbane (2013)

  25. Wu, W., Parampalli, U., Liu, J., et al.: Privacy preserving k-nearest neighbor classification over encrypted database in outsourced cloud environments. World Wide Web (11)1–23 (2018)

  26. Wu, Z., Xu, G., Lu, C., et al.: An effective approach for the protection of privacy text data in the cloudDB. World Wide Web (2017)

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, Northeastern University, Shenyang, China

    Ningning Cui, Xiaochun Yang & Bin Wang

  2. School of Computer Science and Technology, Beijing Institute of Technology, Beijing, China

    Jing Geng

  3. School of Computer Science and Engineering, Deakin University, Melbourne, Australia

    Jianxin Li

Authors
  1. Ningning Cui
    View author publications

    Search author on:PubMed Google Scholar

  2. Xiaochun Yang
    View author publications

    Search author on:PubMed Google Scholar

  3. Bin Wang
    View author publications

    Search author on:PubMed Google Scholar

  4. Jing Geng
    View author publications

    Search author on:PubMed Google Scholar

  5. Jianxin Li
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Ningning Cui.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article belongs to the Topical Collection: Special Issue on Trust, Privacy, and Security in Crowdsourcing Computing

Guest Editors: An Liu, Guanfeng Liu, Mehmet A. Orgun, and Qing Li

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cui, N., Yang, X., Wang, B. et al. Secure range query over encrypted data in outsourced environments. World Wide Web 23, 491–517 (2020). https://doi.org/10.1007/s11280-019-00726-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Version of record:

  • Issue date:

  • DOI: https://doi.org/10.1007/s11280-019-00726-5

Keywords

Profiles

  1. Jianxin Li View author profile