Abstract
The Database-as-a-Service (DAS) model allowing users to outsource data to the clouds has been a promising paradigm. Since users’ data may contain private information and the cloud servers may not be fully trusted, it is desirable to encrypt the data before outsourcing and as a result, the functionality and efficiency has to be sacrificed. In this paper, we propose a privacy-enhancing range query processing scheme by utilizing polynomials and kNN technique. We prove that our scheme is secure under the widely adopted honest-but-curious model and the known background model. Since the secure indexes and trapdoors are indistinguishable and unlinkable, the data privacy can be protected even when the cloud server possesses additional information, such as the attribute domain and the distribution of this domain. In addition, results of experiments validating our proposed scheme are also provided.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Hacigumus, H., Iyer, B., Mehrotra, S.: Providing database as a service. In: Proceedings of the 2002 ICDE International Conference on Data Engineering, pp. 29–38 (2002)
Amazon Web Services. http://aws.amazon.com/running_databases/?nc2=h_ls
Hospital Network Hacked, 4.5 Million Records Stolen. http://money.cnn.com/2014/08/18/technology/security/hospital-chs-hack
Google Fires Engineer for Privacy Breach. http://edition.cnn.com/2010/TECH/web/09/15/google.privacy.firing
Yu, S., Wang, C., Ren, K., Lou, W.: Achieving secure, scalable, and fine-grained data access control in cloud computing. In: Proceedings of the 2010 INFOCOM International Conference on Computer Communications, pp. 1–9 (2010)
Song, D., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: Proceedings of the 2000 IEEE Symposium on Security and Privacy, pp. 44–55 (2000)
Goh, E.J.: Secure indexes. Cryptology ePrint Archive: Report 2003/216 (2003)
Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: Proceedings of the 2006 ACM CCS Conference on Computer and Communications Security, pp. 79–88 (2006)
Golle, P., Staddon, J., Waters, B.: Secure conjunctive keyword search over encrypted data. In: Jakobsson, M., Yung, M., Zhou, J. (eds.) ACNS 2004. LNCS, vol. 3089, pp. 31–45. Springer, Heidelberg (2004)
Ballard, L., Kamara, S., Monrose, F.: Achieving efficient conjunctive keyword searches over encrypted data. In: Qing, S., Mao, W., López, J., Wang, G. (eds.) ICICS 2005. LNCS, vol. 3783, pp. 414–426. Springer, Heidelberg (2005)
Cao, N., Wang, C., Li, M., Ren, K., Lou, W.: Privacy-preserving multi-keyword ranked search over encrypted cloud data. In: Proceedings of the 2011 IEEE INFOCOM International Conference on Computer Communications, pp. 222–233 (2011)
Yu, J., Lu, P., Zhu, Y., Xue, G., Li, M.: Toward secure multi-keyword top-k retrieval over encrypted cloud data. In: Proceedings of the 2013 IEEE TDSC Transactions on Dependable and Secure Computing, pp. 239–250 (2013)
Li, J., Wang, Q., Wang, C., Cao, N., Ren, K., Lou, W.: Fuzzy keyword search over encrypted data in cloud computing. In: Proceedings of the 2010 IEEE INFOCOM International Conference on Computer Communications, pp. 1–5 (2010)
Chuah, M., Hu, W.: Privacy-aware bed-tree based solution for fuzzy multi-keyword search over encrypted data. In: Proceedings of the 2011 ICDCSW International Conference on Distributed Computing Systems Workshops, pp. 273–281 (2011)
Kuzu, M., Islam, M.S., Kantarcioglu, M.: Efficient similarity search over encrypted data. In: Proceedings of the 2012 IEEE ICDE International Conference on Data Engineering, pp. 1156–1167 (2012)
Wang, B., Yu, S., Lou, W., Hou, Y.T.: Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud. In: Proceedings of the 2014 IEEE INFOCOM International Conference on Computer Communications, pp. 2112–2120 (2014)
Hacigumus, H., Iyer, B., Li, C., Mehrotra, S.: Executing SQL over encrypted data in the database-service-provider model. In: Proceedings of the 2002 ACM SIGMOD Special Interest Group on Management of Data, pp. 216–227 (2002)
Hore, B., Mehrotra, S., Tsudik, G.: A privacy-preserving index for range queries. In: Proceedings of the 2004 VLDB International Conference on Very Large Data Bases, pp. 720–731 (2004)
Wang, J., Du, X.: LOB: bucket based index for range queries. In: Proceedings of the 2008 WAIM International Conference on Web-Age Information Management, pp. 86–92 (2008)
Agrawal, R., Kiernan, J., Srikant, R., Xu, Y.: Order preserving encryption for numeric data. In: Proceedings of the 2004 ACM SIGMOD Special Interest Group on Management of Data, pp. 563–574 (2004)
Boldyreva, A., Chenette, N., Lee, Y., O’Neill, A.: Order-preserving symmetric encryption. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 224–241. Springer, Heidelberg (2009)
Damiani, E., Vimercati, S.D.C., Jajodia, S., Paraboschi, S., Samarati, P.: Balancing confidentiality and efficiency in untrusted relational DBMSs. In: Proceedings of the 2003 ACM CCS Conference on Computer and Communications Security, pp. 93–102 (2003)
Lu, Y.: Privacy-preserving logarithmic-time search on encrypted data in cloud. In: Proceedings of the 2012 NDSS Symposium Network and Distributed System Security Symposium (2012)
Pang, H., Zhang, J., Mouratidis, K.: Enhancing access privacy of range retrievals over B+-trees. IEEE TKDE Trans. Knowl. Data Eng. 25, 1533–1547 (2013)
Li, J., Omiecinski, E.R.: Efficiency and security trade-off in supporting range queries on encrypted databases. In: Jajodia, S., Wijesekera, D. (eds.) Data and Applications Security 2005. LNCS, vol. 3654, pp. 69–83. Springer, Heidelberg (2005)
Li, R., Liu, A.X., Wang, A.L., Bruhadeshwar, B.: Fast range query processing with strong privacy protection for cloud computing. In: Proceedings of the 2014 VLDB International Conference on Very Large Data Bases, pp. 1953–1964 (2014)
Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: Proceedings of the 2001 Annual ACM Symposium on Theory of Computing, pp. 639–648 (2001)
Wong, W.K., Cheung, D.W.L., Kao, B., Mamoulis, N.: Secure kNN computation on encrypted databases. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp. 139–152 (2009)
Pappas, V., Krell, F., Vo, B., Kolesnikov, V., Malkin, T., Choi, S.G., et al.: Blind Seer: a scalable private DBMS. In: Proceedings of the 2014 IEEE Symposium on Security and Privacy (SP), pp. 359–374 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Chi, J., Hong, C., Zhang, M., Zhang, Z. (2015). Privacy-Enhancing Range Query Processing over Encrypted Cloud Databases. In: Wang, J., et al. Web Information Systems Engineering – WISE 2015. WISE 2015. Lecture Notes in Computer Science(), vol 9419. Springer, Cham. https://doi.org/10.1007/978-3-319-26187-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-26187-4_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26186-7
Online ISBN: 978-3-319-26187-4
eBook Packages: Computer ScienceComputer Science (R0)