More Web Proxy on the site http://driver.im/

research-article

Low-Cost Hiding of the Query Pattern

Authors:

Maryam Sepehri,

Florian KerschbaumAuthors Info & Claims

ASIA CCS '21: Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security

Pages 593 - 603

https://doi.org/10.1145/3433210.3453103

Published: 04 June 2021 Publication History

Abstract

Several attacks have shown that the leakage from the access pattern in searchable encryption is dangerous. Attacks exploiting leakage from the query pattern are as dangerous, but less explored. While there are known, lightweight countermeasures to hide information in the access pattern by padding the ciphertexts, the same is not true for the query pattern. Oblivious RAM hides the query patterns, but requires a logarithmic overhead in the size of the database and hence will become even slower as data grows. In this paper we present a query smoothing algorithm to hide the frequency information in the query pattern of searchable encryption schemes by introducing fake queries. Our method only introduces a constant overhead of 7 to 13 fake queries per real query in our experiments. Furthermore, we show that our query smoothing algorithm can also be applied to range-searchable encryption schemes and then prevents all recent plaintext recovery attacks.

References

[1]

2016. The SEAL-ORAM library. https://github.com/InitialDLab/SEAL-ORAM.

[2]

2017. The Clusion library. https://github.com/encryptedsystems/Clusion.

[3]

Adi Akavia, Dan Feldman, and Hayim Shaul. 2018. Secure Search on Encrypted Data via Multi-Ring Sketch. In Proceedings of the 25th ACM Conference on Computer and Communications Security (CCS '18). 985--1001.

Digital Library

[4]

Johes Bater, Gregory Elliott, Craig Eggen, Satyender Goel, Abel N. Kho, and Jennie Rogers. 2017. SMCQL: Secure Query Processing for Private Data Networks. PVLDB, Vol. 10, 6 (2017), 673--684.

[5]

David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. 2015. Leakage-Abuse Attacks Against Searchable Encryption. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS '15). 668--679.

Digital Library

[6]

David Cash, Joseph Jaeger, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel-Catalin Rosu, and Michael Steiner. 2014. Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. In Proceedings of the 21st Network and Distributed System Security Symposium.

[7]

R. Curtmola, J. Garay, Seny Kamara, and R. Ostrovsky. 2006. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions. In 13th ACM Conference on Computer and Communications Security (CCS '06). 79--88.

[8]

Sabrina De Capitani Di Vimercati, Sara Foresti, Stefano Paraboschi, Gerardo Pelosi, and Pierangela Samarati. 2015. Shuffle Index: Efficient and Private Access to Outsourced Data. ACM Trans. Storage, Vol. 11, 4, Article 19 (Oct. 2015), 19:1--19:55 pages.

[9]

Ioannis Demertzis, Stavros Papadopoulos, Odysseas Papapetrou, Antonios Deligiannakis, and Minos Garofalakis. 2016. Practical Private Range Search Revisited. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD '16). 185--198.

Digital Library

[10]

Ioannis Demertzis, Rajdeep Talapatra, and Charalampos Papamanthou. 2018. Efficient Searchable Encryption Through Compression. Proc. VLDB Endow., Vol. 11, 11 (July 2018), 13.

Digital Library

[11]

Songyun Duan, Vamsidhar Thummala, and Shivnath Babu. 2009. Tuning Database Configuration Parameters with iTuned. Proceedings of the VLDB Endowment, Vol. 2, 1 (2009), 1246--1257.

Digital Library

[12]

Oded Goldreich and Rafail Ostrovsky. 1996. Software Protection and Simulation on Oblivious RAMs. J. ACM, Vol. 43, 3 (May'96), 431--473.

Digital Library

[13]

Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G. Paterson. 2019. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks. IACR Cryptology ePrint Archive, Vol. 2019 (2019), 11.

[14]

Paul Grubbs, Marie-Sarah Lacharite, Brice Minaud, and Kenneth G. Paterson. 2018. Pump Up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (Toronto, Canada) (CCS '18). 315--331.

[15]

Paul Grubbs, Richard McPherson, Muhammad Naveed, Thomas Ristenpart, and Vitaly Shmatikov. 2016. Breaking Web Applications Built On Top of Encrypted Data. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS '16). 1353--1364.

Digital Library

[16]

Paul Grubbs, Kevin Sekniqi, Vincent Bindschaedler, Muhammad Naveed, and Thomas Ristenpart. 2017. Leakage-Abuse Attacks against Order-Revealing Encryption. In Proceedings of the 2017 IEEE Symposium on Security and Privacy. 655--672.

[17]

Zichen Gui, Oliver Johnson, and Bogdan Warinschi. 2019. Encrypted Databases: New Volume Attacks against Range Queries. In Proceedings of the 2019 ACM Conference on Computer and Communications Security CCS.

Digital Library

[18]

Hakan Hacigümücs, Bala Iyer, Chen Li, and Sharad Mehrotra. 2002. 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, WI, USA) (SIGMOD'02). 216--227.

Digital Library

[19]

Florian Hahn and Florian Kerschbaum. 2014. Searchable Encryption with Secure and Efficient Updates. In Proceedings of the 2014 ACM Conference on Computer and Communications Security, Scottsdale. 310--320.

Digital Library

[20]

Florian Hahn and Florian Kerschbaum. 2016. Poly-Logarithmic Range Queries on Encrypted Data with Small Leakage. In Proceedings of the 2016 ACM Workshop on Cloud Computing Security. 23--34.

Digital Library

[21]

Thang Hoang, Attila A. Yavuz, F. Betül Durak, and Jorge Guajardo. 2018. Oblivious Dynamic Searchable Encryption on Distributed Cloud Systems. In Proceedings of the 32nd IFIP Data and Applications Security and Privacy Conference DBSec.

[22]

Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation. In Proceedings of the 19th Network and Distributed System Security Symposium.

[23]

Seny Kamara and Tarik Moataz. 2019. Computationally Volume-Hiding Structured Encryption. In Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques EUROCRYPT. 183--213.

Digital Library

[24]

Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. 2016. Generic Attacks on Secure Outsourced Databases. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS'16). 1329--1340.

Digital Library

[25]

Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. 2017. Accessing Data while Preserving Privacy. CoRR, Vol. abs/1706.01552 (2017). arxiv: 1706.01552 http://arxiv.org/abs/1706.01552

[26]

Florian Kerschbaum. 2015. Frequency-Hiding Order-Preserving Encryption. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS'15). 656--667.

Digital Library

[27]

Florian Kerschbaum and Anselme Tueno. 2019. An Efficiently Searchable Encrypted Data Structure for Range Queries. In Proceedings of the 24th European Symposium on Research in Computer Security.

Digital Library

[28]

M. Lacharite, B. Minaud, and K. G. Paterson. 2018. Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage. In 2018 IEEE Symposium on Security and Privacy (SP). 297--314. https://doi.org/10.1109/SP.2018.00002

[29]

Marie-Sarah Lacharité and Kenneth G. Paterson. 2015. A note on the optimality of frequency analysis vs. $ell_p$-optimization. IACR Cryptology ePrint Archive, Vol. 2015 (2015), 1158.

[30]

Marie-Sarah Lacharité and Kenneth G. Paterson. 2018. Frequency-smoothing encryption: preventing snapshot attacks on deterministically encrypted data. IACR Trans. Symmetric Cryptol., Vol. 2018, 1 (2018), 277--313.

[31]

Kasper Green Larsen and Jesper Buus Nielsen. 2018. Yes, There is an Oblivious RAM Lower Bound!. In Proceedings of the 38th International Cryptology Conference CRYPTO. 523--542.

Digital Library

[32]

Chang Liu, Liehuang Zhu, Mingzhong Wang, and Yu-An Tan. 2014. Search Pattern Leakage in Searchable Encryption: Attacks and New Construction. Inf. Sci., Vol. 265 (May'14), 176--188. https://doi.org/10.1016/j.ins.2013.11.021

Digital Library

[33]

D. J. Martin, D. Kifer, A. Machanavajjhala, J. Gehrke, and J. Y. Halpern. 2007. Worst-Case Background Knowledge for Privacy-Preserving Data Publishing. In Proceedings of the 23rd IEEE International Conference on Data Engineering. 126--135.

[34]

Muhammad Naveed. 2015. The Fallacy of Composition of Oblivious RAM and Searchable Encryption. IACR Cryptology ePrint Archive, Vol. 2015 (2015), 668.

[35]

Muhammad Naveed, Seny Kamara, and Charles V. Wright. 2015. Inference Attacks on Property-Preserving Encrypted Databases. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security (CCS'15). 644--655.

[36]

Simon Oya and Florian Kerschbaum. 2020. Hiding the Access Pattern is Not Enough: Exploiting Search Pattern Leakage in Searchable Encryption. CoRR, Vol. abs/2010.03465 (2020). arxiv: 2010.03465 https://arxiv.org/abs/2010.03465

[37]

Oguzhan Ozmen, Kenneth Salem, Jiri Schindler, and Steve Daniel. 2010. Workload-aware Storage Layout for Database Systems. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. 939--950.

Digital Library

[38]

Giuseppe Persiano and Kevin Yeo. 2019. Lower Bounds for Differentially Private RAMs. In Proceedings of the 38th International Conference on the Theory and Applications of Cryptographic Techniques EUROCRYPT. 404--434.

Digital Library

[39]

Casper Petersen, Jakob Grue Simonsen, and Christina Lioma. 2016. Power Law Distributions in Information Retrieval. ACM Transactions on Information Systems, Vol. 34, 2 (2016), 8:1--8:37.

Digital Library

[40]

Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan. 2011. CryptDB: Protecting Confidentiality with Encrypted Query Processing. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles (Cascais, Portugal) (SOSP'11). 85--100.

Digital Library

[41]

David M. W. Powers. 1998. Applications and Explanations of Zipf's Law. In Proceedings of the Joint Conferences on New Methods in Language Processing and Computational Natural Language Learning (Sydney, Australia) (NeMLaP3/CoNLL'98). Association for Computational Linguistics, Stroudsburg, PA, USA, 151--160. http://dl.acm.org/citation.cfm?id=1603899.1603924

Digital Library

[42]

Pierangela Samarati and Latanya Sweeney. 1998. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. Harvard Data Privacy Lab.

[43]

Kunwadee Sripanidkulchai. 2001. The Popularity of Gnutella Queries and its Implication on Scalability. http://www-2.cs.cmu.edu/ kunwadee/research/p2p/gnutella.html.

[44]

Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. 2013. Path ORAM: An Extremely Simple Oblivious RAM Protocol. In Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security (CCS'13). 299--310.

Digital Library

[45]

John Walker. 2006. Mathematics: Zipf's Law and the AOL Query Database. https://www.fourmilab.ch/fourmilog/archives/2006-08/000740.html.

[46]

Jiafan Wang and Sherman S. M. Chow. 2019. Forward and Backward-Secure Range-Searchable Symmetric Encryption. IACR Cryptol. ePrint Arch., Vol. 2019 (2019), 497. https://eprint.iacr.org/2019/497

[47]

Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. 2016. All Your Queries Are Belong to Us: The Power of File-Injection Attacks on Searchable Encryption. In 25th USENIX Security Symposium (USENIX Security). USENIX Association, Austin, TX, 707--720. https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/zhang

Cited By

Maiyya SVemula SAgrawal DEl Abbadi AKerschbaum F(2023)Waffle: An Online Oblivious Datastore for Protecting Data Access PatternsProceedings of the ACM on Management of Data10.1145/36267601:4(1-25)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626760
Han ZHu HYe Q(2023)ReFlat: A Robust Access Pattern Hiding Solution for General Cloud Query Processing Based on K-Isomorphism and Hardware EnclaveIEEE Transactions on Cloud Computing10.1109/TCC.2021.313735111:2(1474-1486)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TCC.2021.3137351
Li XDu YWang C(2023)RangeQC: A Query Control Framework for Range Query Leakage Quantification and Mitigation2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00017(749-759)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00017

Index Terms

Low-Cost Hiding of the Query Pattern
1. Security and privacy
  1. Security services
    1. Privacy-preserving protocols
  2. Systems security

Recommendations

Efficient Range Query Processing in Peer-to-Peer Systems

With the increasing popularity of the peer-to-peer (P2P) computing paradigm, many general range query schemes for distributed hash table (DHT)-based P2P systems have been proposed in recent years. Although those schemes can provide range query ...
Query indexing with containment-encoded intervals for efficient stream processing

Many continual range queries can be issued against data streams. To efficiently evaluate continual queries against a stream, a main memory-based query index with a small storage cost and a fast search time is needed, especially if the stream is rapid. ...
Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

In the last few years, there has been significant interest in developing methods to search over encrypted data. In the case of range queries, a simple solution is to encrypt the contents of the database using an order-preserving encryption (OPE) scheme (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASIA CCS '21: Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security

May 2021

975 pages

ISBN:9781450382878

DOI:10.1145/3433210

General Chairs:
Jiannong Cao
The Hong Kong Polytechnic University, Hong Kong
,
Man Ho Au
The University of Hong Kong, Hong Kong
,
Program Chairs:
Zhiqiang Lin
The Ohio State University, USA
,
Moti Yung
Google and Columbia University, USA

Copyright © 2021 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 ACM 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: 04 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASIA CCS '21

Sponsor:

SIGSAC

ASIA CCS '21: ACM Asia Conference on Computer and Communications Security

June 7 - 11, 2021

Virtual Event, Hong Kong

Acceptance Rates

Overall Acceptance Rate 418 of 2,322 submissions, 18%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
165
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)7

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Maiyya SVemula SAgrawal DEl Abbadi AKerschbaum F(2023)Waffle: An Online Oblivious Datastore for Protecting Data Access PatternsProceedings of the ACM on Management of Data10.1145/36267601:4(1-25)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626760
Han ZHu HYe Q(2023)ReFlat: A Robust Access Pattern Hiding Solution for General Cloud Query Processing Based on K-Isomorphism and Hardware EnclaveIEEE Transactions on Cloud Computing10.1109/TCC.2021.313735111:2(1474-1486)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TCC.2021.3137351
Li XDu YWang C(2023)RangeQC: A Query Control Framework for Range Query Leakage Quantification and Mitigation2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00017(749-759)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00017

View Options

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