research-article

Poly-Logarithmic Range Queries on Encrypted Data with Small Leakage

Authors:

Florian KerschbaumAuthors Info & Claims

CCSW '16: Proceedings of the 2016 ACM on Cloud Computing Security Workshop

Pages 23 - 34

https://doi.org/10.1145/2996429.2996437

Published: 28 October 2016 Publication History

Abstract

Privacy-preserving range queries allow encrypting data while still enabling queries on ciphertexts if their corresponding plaintexts fall within a requested range. This provides a data owner the possibility to outsource data collections to a cloud service provider without sacrificing privacy nor losing functionality of filtering this data. However, existing methods for range queries either leak additional information (like the ordering of the complete data set) or slow down the search process tremendously by requiring to query each ciphertext in the data collection. We present a novel scheme that only leaks the access pattern while supporting amortized poly-logarithmic search time. Our construction is based on the novel idea of enabling the cloud service provider to compare requested range queries. By doing so, the cloud service provider can use the access pattern to speed-up search time for range queries in the future. On the one hand, values that have fallen within a queried range, are stored in an interactively built index for future requests. On the other hand, values that have not been queried do not leak any information to the cloud service provider and stay perfectly secure. In order to show its practicability we have implemented our scheme and give a detailed runtime evaluation.

References

[1]

Agrawal, R., Kiernan, J., Srikant, R., and Xu, Y. Order preserving encryption for numeric data. In Proceedings of the ACM International Conference on Management of Data (2004), SIGMOD.

Digital Library

[2]

Bellare, M., Boldyreva, A., and O'Neill, A. Deterministic and efficiently searchable encryption. In Proceedings of the 27th International Conference on Advances in Cryptology (2007), CRYPTO.

Digital Library

[3]

Bishop, A., Jain, A., and Kowalczyk, L. Function-hiding inner product encryption. In Advances in Cryptology (2015), ASIACRYPT.

[4]

Boldyreva, A., Chenette, N., Lee, Y., and O'Neill, A. Order-preserving symmetric encryption. In Proceedings of the 28th International Conference on Advances in Cryptology (2009), EUROCRYPT.

[5]

Boneh, D., Di Crescenzo, G., Ostrovsky, R., and Persiano, G. Public key encryption with keyword search. In Advances in Cryptology (2004), EUROCRYPT.

[6]

Boneh, D., and Waters, B. Conjunctive, subset, and range queries on encrypted data. In Proceedings of the 4th Theory of Cryptography Conference (2007), TCC.

Digital Library

[7]

Catrina, O., and Kerschbaum, F. Fostering the uptake of secure multiparty computation in e-commerce. In Proceedings of the third International Conference on Availability, Reliability and Security (2008), ARES.

Digital Library

[8]

Chang, Y.-C., and Mitzenmacher, M. Privacy preserving keyword searches on remote encrypted data. In Proccedings of the International Conference on Applied Cryptography and Network Security (2005), ACNS.

Digital Library

[9]

Curtmola, R., Garay, J., Kamara, S., and Ostrovsky, R. Searchable symmetric encryption: improved definitions and efficient constructions. In Proceedings of the 13th ACM Conference on Computer and Communications Security (2006), CCS.

Digital Library

[10]

Demertzis, I., Papadopoulos, S., Papapetrou, O., Deligiannakis, A., and Garofalakis, M. Practical private range search revisited.

[11]

Gentry, C. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009.

Digital Library

[12]

Goh, E.-J. Secure indexes. IACR Cryptology ePrint Archive, 216 (2003).

[13]

Guttman, A. R-trees: a dynamic index structure for spatial searching. In Proceedings of the ACM International Conference on Management of Data (1984), SIGMOD.

Digital Library

[14]

Hahn, F., and Kerschbaum, F. Searchable encryption with secure and efficient updates. In Proceedings of the 21st ACM Conference on Computer and Communications Security (2014), CCS.

Digital Library

[15]

Hore, B., Mehrotra, S., and Tsudik, G. A privacy-preserving index for range queries. In Proceedings of the 30th International Conference on Very Large Data Bases (2004), VLDB.

Digital Library

[16]

Kerschbaum, F. Building a privacy-preserving benchmarking enterprise system. Enterprise Information Systems 2, 4 (2008).

Digital Library

[17]

Kerschbaum, F. Practical privacy-preserving benchmarking. In Proceedings of the IFIP International Information Security Conference (2008), SEC, pp. 17--31.

[18]

Kerschbaum, F. A verifiable, centralized, coercion-free reputation system. In Proceedings of the 8th ACM Workshop on Privacy in the Electronic Society (2009), WPES.

Digital Library

[19]

Kerschbaum, F. Frequency-hiding order-preserving encryption. In Proceedings of the 22nd ACM Conference on Computer and Communications Security (2015), CCS.

Digital Library

[20]

Kerschbaum, F., and Oertel, N. Privacy-preserving pattern matching for anomaly detection in rfid anti-counterfeiting. In International Workshop on Radio Frequency Identification: Security and Privacy Issues (2010), RFIDSec.

Digital Library

[21]

Kerschbaum, F., and Schröpfer, A. Optimal average-complexity ideal-security order-preserving encryption. In Proceedings of the 21st ACM Conference on Computer and Communications Security (2014), CCS.

Digital Library

[22]

Kerschbaum, F., and Terzidis, O. Filtering for private collaborative benchmarking. Emerging Trends in Information and Communication Security (2006).

Digital Library

[23]

Lu, Y. Privacy-preserving logarithmic-time search on encrypted data in cloud. In Proceedings of the 19th Network and Distributed System Security Symposium (2012), NDSS.

[24]

Lynn, B. PBC library - the pairing-based cryptography library. https://crypto.stanford.edu/pbc.

[25]

Naveed, M., Kamara, S., and Wright, C. V. Inference attacks on property-preserving encrypted databases. In Proceedings of the 22nd ACM Conference on Computer and Communications Security (2015), CCS.

Digital Library

[26]

Popa, R. A., Redfield, C. M. S., Zeldovich, N., and Balakrishnan, H. Cryptdb: protecting confidentiality with encrypted query processing. In Proceedings of the 23rd ACM Symposium on Operating Systems Principles (2011), SOSP.

Digital Library

[27]

Shen, E., Shi, E., and Waters, B. Predicate privacy in encryption systems. In Proceedings of the 6th Theory of Cryptography Conference (2009), TCC.

Digital Library

[28]

Shi, E., Bethencourt, J., Chan, H. T.-H., Song, D. X., and Perrig, A. Multi-dimensional range query over encrypted data. In Proceedings of the 2007 Symposium on Security and Privacy (2007), S&P.

Digital Library

[29]

Song, D. X., Wagner, D., and Perrig, A. Practical techniques for searches on encrypted data. In Proceedings of the 21st IEEE Symposium on Security and Privacy (2000), S&P.

Digital Library

[30]

Wang, B., Hou, Y., Li, M., Wang, H., and Li, H. Maple: Scalable multi-dimensional range search over encrypted cloud data with tree-based index. In Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security (2014), ASIA CCS.

Digital Library

[31]

Wang, P., and Ravishankar, C. Secure and efficient range queries on outsourced databases using R-trees. In Proceedings of the 30th IEEE International Conference on Data Engineering (2013), ICDE.

Digital Library

Cited By

Kwon HHur JHahn C(2022)Order-Hiding Range Query Over Encrypted Cloud DataIEEE Access10.1109/ACCESS.2022.319242110(75604-75618)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3192421
Sepehri MKerschbaum FCao JHo Au MLin ZYung M(2021)Low-Cost Hiding of the Query PatternProceedings of the 2021 ACM Asia Conference on Computer and Communications Security10.1145/3433210.3453103(593-603)Online publication date: 24-May-2021
https://dl.acm.org/doi/10.1145/3433210.3453103
Emura KIto KOhigashi T(2020)Secure-channel free searchable encryption with multiple keywords: A generic construction, an instantiation, and its implementationJournal of Computer and System Sciences10.1016/j.jcss.2020.06.003Online publication date: Jun-2020
https://doi.org/10.1016/j.jcss.2020.06.003
Show More Cited By

Index Terms

Poly-Logarithmic Range Queries on Encrypted Data with Small Leakage
1. Networks
  1. Network services
    1. Cloud computing
2. Security and privacy
  1. Database and storage security
    1. Management and querying of encrypted data
  2. Security services
    1. Privacy-preserving protocols

Recommendations

Dynamic Verifiable Encrypted Keyword Search

Outsourcing data storage to the cloud securely and retrieving the remote data in an efficient way is a very significant research topic, with high relevance to secure cloud deployment. With the ever growing security and privacy concerns, encrypting the ...
Shared and searchable encrypted data for untrusted servers
DBSEC 2008

Current security mechanisms are not suitable for organisations that outsource their data management to untrusted servers. Encrypting and decrypting sensitive data at the client side is the normal approach in this situation but has high communication and ...
Multiuser private queries over encrypted databases

Searchable encryption schemes allow users to perform keyword-based searches on an encrypted database. Almost all existing such schemes only consider the scenario where a single user acts as both the data owner and the querier. However, most databases in ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCSW '16: Proceedings of the 2016 ACM on Cloud Computing Security Workshop

October 2016

116 pages

ISBN:9781450345729

DOI:10.1145/2996429

Conference Chairs:
Mathias Payer
Purdue University, USA
,
Stefan Mangard
IAIK TU Graz, Austria
,
General Chairs:
Edgar Weippl
SBA Research, Austria
,
Stefan Katzenbeisser
Technische Universität Darmstadt, Germany
,
Program Chairs:
Elli Androulaki
IBM Research-Zurich, Switzerland
,
Michael K. Reiter
University of North Carolina at Chapel Hill, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CCS'16

Sponsor:

SIGSAC

CCS'16: 2016 ACM SIGSAC Conference on Computer and Communications Security

October 28, 2016

Vienna, Austria

Acceptance Rates

CCSW '16 Paper Acceptance Rate 8 of 23 submissions, 35%;

Overall Acceptance Rate 37 of 108 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
202
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kwon HHur JHahn C(2022)Order-Hiding Range Query Over Encrypted Cloud DataIEEE Access10.1109/ACCESS.2022.319242110(75604-75618)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3192421
Sepehri MKerschbaum FCao JHo Au MLin ZYung M(2021)Low-Cost Hiding of the Query PatternProceedings of the 2021 ACM Asia Conference on Computer and Communications Security10.1145/3433210.3453103(593-603)Online publication date: 24-May-2021
https://dl.acm.org/doi/10.1145/3433210.3453103
Emura KIto KOhigashi T(2020)Secure-channel free searchable encryption with multiple keywords: A generic construction, an instantiation, and its implementationJournal of Computer and System Sciences10.1016/j.jcss.2020.06.003Online publication date: Jun-2020
https://doi.org/10.1016/j.jcss.2020.06.003
Kornaropoulos EPapamanthou CTamassia R(2019)Data Recovery on Encrypted Databases with k-Nearest Neighbor Query Leakage2019 IEEE Symposium on Security and Privacy (SP)10.1109/SP.2019.00015(1033-1050)Online publication date: May-2019
https://doi.org/10.1109/SP.2019.00015
Pouliot DGriffy SWright C(2019)The Strength of Weak Randomization: Easily Deployable, Efficiently Searchable Encryption with Minimal Leakage2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN.2019.00059(517-529)Online publication date: Jun-2019
https://doi.org/10.1109/DSN.2019.00059
Kerschbaum FTueno A(2019)An Efficiently Searchable Encrypted Data Structure for Range QueriesComputer Security – ESORICS 201910.1007/978-3-030-29962-0_17(344-364)Online publication date: 15-Sep-2019
https://doi.org/10.1007/978-3-030-29962-0_17
Hahn FLoza NKerschbaum FDas GJermaine CBernstein P(2018)Practical and Secure Substring SearchProceedings of the 2018 International Conference on Management of Data10.1145/3183713.3183754(163-176)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3183713.3183754
Demertzis IPapadopoulos SPapapetrou ODeligiannakis AGarofalakis MPapamanthou C(2018)Practical Private Range Search in DepthACM Transactions on Database Systems10.1145/316797143:1(1-52)Online publication date: 12-Mar-2018
https://dl.acm.org/doi/10.1145/3167971
Lacharite MMinaud BPaterson K(2018)Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage2018 IEEE Symposium on Security and Privacy (SP)10.1109/SP.2018.00002(297-314)Online publication date: May-2018
https://doi.org/10.1109/SP.2018.00002
Maseedu JPasupuleti S(2018)Attribute based Range Search over Encrypted Data for Privacy Preserving in Cloud Computing2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI)10.1109/ICACCI.2018.8554559(323-329)Online publication date: Sep-2018
https://doi.org/10.1109/ICACCI.2018.8554559
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents