Do Hoang Giang; Ng Wee Keong

Multi-dimensional Range Query on Outsourced Database with Strong Privacy Guarantee

Full Text (PDF, 922KB), PP.13-23

Views: 0 Downloads: 0

Author(s)

Do Hoang Giang ^1,* Ng Wee Keong ¹

1. School of Computer Science and Engineering, Nanyang Technological University, Singapore

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2017.10.02

Received: 21 Jul. 2017 / Revised: 2 Aug. 2017 / Accepted: 7 Aug. 2017 / Published: 8 Oct. 2017

Index Terms

Secure Computation, Multi-dimensional Range Query, Cryptography

Abstract

Cloud services have provided important solutions for drastically reducing the cost of data management and maintenance. However, data outsourcing not only deprives clients of direct control over their data but also allows the server to gain direct access to the client data. Data encryption has been recognized as the solution to the privacy issue, but it also creates new challenges for both industry and academia. A naive question is whether the client still has the capability to query and obtain useful information when the data are encrypted and stored remotely. This paper investigates a solution to one of the most important types of query operations over encrypted data, namely multi-dimensional range queries. Our solution combines cryptographic techniques with the bucketization approach. We leverage a three-party architecture and secure multiparty computation to design and analyze the security of the protocols. Further, we discuss solutions for both static and dynamic datasets where new data records can be appended. First, we present the solutions for the case when the set of attributes in the query is pre-defined. Subsequently, we discuss the generalization.

Cite This Paper

Do Hoang Giang, Ng Wee Keong, "Multi-dimensional Range Query on Outsourced Database with Strong Privacy Guarantee", International Journal of Computer Network and Information Security(IJCNIS), Vol.9, No.10, pp.13-23, 2017. DOI:10.5815/ijcnis.2017.10.02

Reference

[1]Amazon Web Services (AWS) - Cloud Computing Services.
[2]Google App Engine.
[3]Microsoft Azure.
[4]D. Boneh and B. Waters, "Conjunctive, Subset, and Range Queries on Encrypted Data," in Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007.
[5]D. Boneh, E.-J. Goh and K. Nissim, "Evaluating 2-DNF Formulas on Ciphertexts," in Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005.
[6]E. Shi, J. Bethencourt, H. T.-H. Chan, D. X. Song and A. Perrig, "Multi-Dimensional Range Query over Encrypted Data," in 2007 IEEE Symposium on Security and Privacy S&P 2007, Oakland, California, USA, 20-23 May 2007.
[7]Y. Lu, "Privacy-preserving Logarithmic-time Search on Encrypted Data in Cloud," in 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5-8, 2012.
[8]B. Wang, Y. Hou, M. Li, H. Wang and H. Li, "Maple: scalable multi-dimensional range search over encrypted cloud data with tree-based index," in 9th ACM Symposium on Information, Computer and Communications Security, ASIA CCS '14, Kyoto, Japan - June 03 - 06, 2014.
[9]H. Hacigümüs, B. R. Iyer, C. Li and S. Mehrotra, "Executing SQL over encrypted data in the database-service-provider model," in Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3-6, 2002.
[10]B. Hore, S. Mehrotra and G. Tsudik, "A Privacy-Preserving Index for Range Queries," in Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August 31 - September 3, 2004.
[11]B. Hore, S. Mehrotra, M. Canim and M. Kantarcioglu, "Secure multidimensional range queries over outsourced data," {VLDB} J., vol. 21, pp. 333-358, 2012.
[12]R. Agrawal, J. Kiernan, R. Srikant and Y. Xu, "Order-preserving encryption for numeric data," in Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13-18, 2004, 2004.
[13]A. Boldyreva, N. Chenette, Y. Lee and A. O?eill, "Order-Preserving Symmetric Encryption," in Advances in Cryptology - EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009.
[14]A. Boldyreva, N. Chenette and A. O?eill, "Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions," in Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, CA, USA, August 14-18, 2011.
[15]C. Mavroforakis, N. Chenette, A. O?eill, G. Kollios and R. Canetti, "Modular Order-Preserving Encryption, Revisited," in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Australia, May 31 - June 4, 2015.
[16]O. Goldreich, "Towards a Theory of Software Protection and Simulation by Oblivious RAMs," in Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, New York, USA, 1987.
[17]O. Goldreich, "Software Protection and Simulation on Oblivious RAMs," J. ACM, vol. 43, no. 3, pp. 431-473, 1996.
[18]E. Stefanov, E. Shi and D. X. Song, "Towards Practical Oblivious RAM," in 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5-8, 2012.
[19]E. Shi, T.-H. H. Chan, E. Stefanov and M. Li, "Oblivious RAM with O((logN)3) Worst-Case Cost," in Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011.
[20]E. Stefanov, M. van Dijk, E. Shi, C. W. Fletcher, L. Ren, X. Yu and S. Devadas, "Path ORAM: an extremely simple oblivious RAM protocol," in 2013 {ACM} {SIGSAC} Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4-8, 2013.
[21]D. Boneh, C. Gentry, S. Halevi, F. Wang and D. J. Wu, "Private Database Queries Using Somewhat Homomorphic Encryption," in Applied Cryptography and Network Security - 11th International Conference, ACNS 2013, Canada, June 25-28, 2013.
[22]E. D. Cristofaro, Y. Lu and G. Tsudik, "Efficient Techniques for Privacy-Preserving Sharing of Sensitive Information," in Trust and Trustworthy Computing - 4th International Conference, TRUST 2011, Pittsburgh, PA, USA, June 22-24, 2011.
[23]M. S. Islam, M. Kuzu and M. Kantarcioglu, "Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation," in 19th Annual Network and Distributed System Security Symposium, NDSS 2012, San Diego, California, USA, February 5-8, 2012.
[24]LeFevre, Kristen, D. J. DeWitt and R. Ramakrishnan, "Mondrian Multidimensional K-Anonymity," in Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April 2006, Atlanta, GA, USA, 2016.
[25]R. Zhang, J. Shi and Y. Zhang, "Secure multidimensional range queries in sensor networks," in Proceedings of the 10th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2009, New Orleans, LA, USA, May 18-21, 2009.
[26]L. Kissner and D. X. Song, "Privacy-Preserving Set Operations," in Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005.
[27]D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M.-C. Rosu and M. Steiner, "Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries," in Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013.
[28]E. D. Cristofaro, P. Gasti and G. Tsudik, "Fast and Private Computation of Cardinality of Set Intersection and Union," in Cryptology and Network Security, 11th International Conference, CANS 2012, Darmstadt, Germany, December 12-14, 2012.

International Journal of Computer Network and Information Security (IJCNIS)