research-article
Authors: Dominique Dittert, Thomas Schneider, and Amos Treiber
CCSW '23: Proceedings of the 2023 on Cloud Computing Security Workshop
November 2023
Pages 3 - 15
Published: 26 November 2023 Publication History
- 0citation
- 42
- Downloads
Metrics
Total Citations0Total Downloads42Last 12 Months42
Last 6 weeks4
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
Get Access
- Get Access
- References
- Media
- Tables
- Share
Abstract
The well-defined information leakage of Encrypted Search Algorithms (ESAs) is predominantly analyzed by crafting so-called leakage attacks. These attacks utilize adversarially known auxiliary data and the observed leakage to attack an ESA instance built on a user's data. Known-data attacks require the auxiliary data to be a subset of the user's data. In contrast, sampled-data attacks merely rely on auxiliary data that is, in some sense, statistically close to the user's data and hence reflect a much more realistic attack scenario where the auxiliary data stems from a publicly available data source instead of the private user's data.
Unfortunately, it is unclear what "statistically close" means in the context of sampled-data attacks. This leaves open how to measure whether data is close enough for attacks to become a considerable threat. Furthermore, sampled-data attacks have so far not been evaluated in the more realistic attack scenario where the auxiliary data stems from a source different to the one emulating the user's data. Instead, auxiliary and user data have been emulated with data from one source being split into distinct training and testing sets. This leaves open whether and how well attacks work in the mentioned attack scenario with data from different sources.
In this work, we address these open questions by providing a measurable metric for statistical closeness in encrypted keyword search. Using real-world data, we show a clear exponential relation between our metric and attack performance. We uncover new data that are intuitively similar yet stem from different sources. We discover that said data are not "close enough" for sampled-data attacks to perform well. Furthermore, we provide a re-evaluation of sampled-data keyword attacks with varying evaluation parameters and uncover that some evaluation choices can significantly affect evaluation results.
References
[1]
Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, and Yirong Xu. 2004. Order preserving encryption for numeric data. In International Conference on Management of Data (SIGMOD).
Digital Library
[2]
Ghous Amjad, Seny Kamara, and Tarik Moataz. 2019. Breach-Resistant Structured Encryption. In Proceedings on Privacy Enhancing Technologies (PoPETS), Vol. 2019.
[3]
Mihir Bellare, Alexandra Boldyreva, and Adam O'Neill. 2007. Deterministic and efficiently searchable encryption. In Annual International Cryptology Conference (CRYPTO).
[4]
Laura Blackstone, Seny Kamara, and Tarik Moataz. 2020. Revisiting Leakage Abuse Attacks. In Network and Distributed System Security Symposium (NDSS).
[5]
Dan Boneh, Amit Sahai, and Brent Waters. 2011. Functional encryption: Definitions and challenges. In Theory of Cryptography Conference (TCC).
[6]
David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. 2015. Leakage-Abuse Attacks Against Searchable Encryption. In ACM SIGSAC Conference on Computer and Communications Security (CCS).
[7]
Yan-Cheng Chang and Michael Mitzenmacher. 2005. Privacy preserving keyword searches on remote encrypted data. In International Conference on Applied Cryptography and Network Security (ACNS).
Digital Library
[8]
Melissa Chase and Seny Kamara. 2010. Structured encryption and controlled disclosure. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT).
[9]
William W. Cohen. 2015. Enron Corpus. Accessed 2023-05-07, https://www.cs.cmu.edu/ ./enron/.
[10]
Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Searchable symmetric encryption: Improved definitions and efficient constructions. In ACM SIGSAC Conference on Computer and Communications Security (CCS).
Digital Library
[11]
Marc Damie, Florian Hahn, and Andreas Peter. 2021. A Highly Accurate Query-Recovery Attack against Searchable Encryption using Non-Indexed Documents. In USENIX Security Symposium (USENIX Security).
[12]
Debian Mailing Lists. 2022. debian-security-announce. Accessed 2022--10-04, https://lists.debian.org/debian-security-announce/.
[13]
Maria Esch, Jinbo Chen, Stephan Weise, Keywan Hassani-Pak, Uwe Scholz, and Matthias Lange. 2014. A Query Suggestion Workflow for Life Science IR-Systems. Journal of Integrative Bioinformatics (2014).
[14]
Benjamin Fuller, Mayank Varia, Arkady Yerukhimovich, Emily Shen, Ariel Hamlin, Vijay Gadepally, Richard Shay, John Darby Mitchell, and Robert K Cunningham. 2017. SoK: Cryptographically protected database search. In IEEE Symposium on Security and Privacy (S&P).
[15]
Craig Gentry. 2009. Fully hom*omorphic encryption using ideal lattices. In ACM Symposium on Theory of Computing (STOC).
Digital Library
[16]
Eu-Jin Goh. 2003. Secure Indexes. IACR ePrint, Vol. 216 (2003).
[17]
Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to play any mental game. In ACM Symposium on Theory of Computing (STOC).
Digital Library
[18]
Oded Goldreich and Rafail Ostrovsky. 1996. Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM), Vol. 43, 3 (1996).
Digital Library
[19]
Paul Grubbs, Marie-Sarah Lacharité, Brice Minaud, and Kenneth G Paterson. 2018. Pump up the volume: Practical database reconstruction from volume leakage on range queries. In ACM SIGSAC Conference on Computer and Communications Security (CCS).
Digital Library
[20]
Zichen Gui, Kenneth G Paterson, and Sikhar Patranabis. 2023 a. Rethinking Searchable Symmetric Encryption. In IEEE Symposium on Security and Privacy (S&P).
[21]
Zichen Gui, Kenneth G Paterson, and Tianxin Tang. 2023 b. Security Analysis of $$MongoDB$$ Queryable Encryption. In 32nd USENIX Security Symposium (USENIX Security 23). 7445--7462.
[22]
Islam Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation. In Networkand Distributed System Security Symposium (NDSS).
[23]
Mireya Jurado, Catuscia Palamidessi, and Geoffrey Smith. 2021. A formal information-theoretic leakage analysis of order-revealing encryption. In IEEE Computer Security Foundations Symposium (CSF).
[24]
Mireya Jurado and Geoffrey Smith. 2019. Quantifying information leakage of deterministic encryption. In ACM SIGSAC Conference on Cloud Computing Security Workshop (CCSW).
Digital Library
[25]
Seny Kamara, Abdelkarim Kati, Tarik Moataz, Jamie DeMaria, Andrew Park, and Amos Treiber. 2023. MAPLE: MArkov Process Leakage attacks on Encrypted Search. IACR ePrint, Vol. 810 (2023).
[26]
Seny Kamara, Abdelkarim Kati, Tarik Moataz, Thomas Schneider, Amos Treiber, and Michael Yonli. 2022. SoK: Cryptanalysis of Encrypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data. In IEEE European Symposium on Security and Privacy (EuroS&P).
[27]
Seny Kamara and Tarik Moataz. 2023. Bayesian Leakage Analysis: A Framework for Analyzing Leakage in Encrypted Search. IACR ePrint, Vol. 813 (2023).
[28]
Evgenios M Kornaropoulos, Nathaniel Moyer, Charalampos Papamanthou, and Alexandros Psomas. 2022. Leakage Inversion: Towards Quantifying Privacy in Searchable Encryption. In ACM SIGSAC Conference on Computer and Communications Security (CCS).
Digital Library
[29]
Philippe Lamesch, Kate Dreher, David Swarbreck, Rajkumar Sasidharan, Leonore Reiser, and Eva Huala. 2010. Using The Arabidopsis Information Resource (TAIR) to Find Information About Arabidopsis Genes. Current Protocols in Bioinformatics, Vol. 30, 1 (6 2010).
[30]
Chang Liu, Liehuang Zhu, Mingzhong Wang, and Yu an Tan. 2014. Search pattern leakage in searchable encryption: Attacks and new construction. Information Sciences, Vol. 265 (2014).
Digital Library
[31]
Google LLC. 2023. Google Trends. Accessed 2023-05-07, https://trends.google.com/trends.
[32]
MongoDB. 2023. MongoDB Manual. Accessed 2023-07--10, https://www.mongodb.com/docs/manual/core/queryable-encryption/.
[33]
Simon Oya and Florian Kerschbaum. 2020a. Hiding the Access Pattern is Not Enough: Exploiting Search Pattern Leakage in Searchable Encryption. In USENIX Security Symposium (USENIX Security).
[34]
Simon Oya and Florian Kerschbaum. 2020b. Pre-Processed Google Trends Data. Accessed 2023-05-07, https://github.com/simon-oya/USENIX21-sap-code/blob/master/datasets_pro/enron_db.pkl.
[35]
Simon Oya and Florian Kerschbaum. 2022. IHOP: Improved Statistical Query Recovery against Searchable Symmetric Encryption through Quadratic Optimization. In USENIX Security Symposium (USENIX Security).
[36]
Rishabh Poddar, Stephanie Wang, Jianan Lu, and Raluca Ada Popa. 2020. Practical volume-based attacks on encrypted databases. In IEEE European Symposium on Security and Privacy (EuroS&P).
[37]
Ruben Groot Roessink, Andreas Peter, and Florian Hahn. 2021. Experimental Review of the IKK Query Recovery Attack: Assumptions, Recovery Rate and Improvements. In International Conference on Applied Cryptography and Network Security (ACNS).
[38]
Dawn Xiaoding Song, David Wagner, and Adrian Perrig. 2000. Practical techniques for searches on encrypted data. In IEEE Symposium on Security and Privacy (S&P).
[39]
Ubuntu Mailing Lists. 2022. The ubuntu-security-announce Archives. Accessed 2022--10--12, https://lists.ubuntu.com/archives/ubuntu-security-announce/.
[40]
Charles V Wright and David Pouliot. 2017. Early detection and analysis of leakage abuse vulnerabilities. IACR ePrint, Vol. 1052 (2017).
[41]
Andrew C Yao. 1982. Protocols for secure computations. In Annual Symposium on Foundations of Computer Science (FOCS).
[42]
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 USENIX Security Symposium (USENIX Security). io
Index Terms
Too Close for Comfort? Measuring Success of Sampled-Data Leakage Attacks Against Encrypted Search
Security and privacy
Cryptography
Cryptanalysis and other attacks
Database and storage security
Management and querying of encrypted data
Security services
Privacy-preserving protocols
Recommendations
- Leakage-Abuse Attacks Against Forward and Backward Private Searchable Symmetric Encryption
CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
Dynamic searchable symmetric encryption (DSSE) enables a server to efficiently search and update over encrypted files. To minimize the leakage during updates, a security notion named forward and backward privacy is expected for newly proposed DSSE ...
Read More
- Fully Leakage-Resilient Non-malleable Identification Schemes in the Bounded-Retrieval Model
IWSEC 2015: Proceedings of the 10th International Workshop on Advances in Information and Computer Security - Volume 9241
Alwen, Dodis and Wichs first formulated the security notions of identification ID schemes resilient to key-leakage attacks, which is called leakage-resilient ID schemes. In fact, the notions they considered are the so-called active security where the ...
Read More
- Measuring and ranking attacks based on vulnerability analysis
As the number of software vulnerabilities increases, the research on software vulnerabilities becomes a focusing point in information security. A vulnerability could be exploited to attack the information asset with the weakness related to the ...
Read More
Comments
Information & Contributors
Information
Published In
CCSW '23: Proceedings of the 2023 on Cloud Computing Security Workshop
November 2023
95 pages
ISBN:9798400702594
DOI:10.1145/3605763
- Program Chairs:
- Francesco Regazzoni
University of Amsterdam, The Netherlands and Università della Svizzera italiana, Switzerland
, - Apostolos Fournaris
Industrial Systems Institute/Research Center ATHENA, Greece
Copyright © 2023 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 [emailprotected].
Sponsors
- SIGSAC: ACM Special Interest Group on Security, Audit, and Control
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 26 November 2023
Permissions
Request permissions for this article.
Check for updates
Author Tags
- encrypted search
- leakage attacks
- privacy metric
Qualifiers
- Research-article
Funding Sources
- European Research Council (ERC)
- Deutsche Forschungsgemeinschaft (DFG)
Conference
CCS '23
Sponsor:
- SIGSAC
CCS '23: ACM SIGSAC Conference on Computer and Communications Security
November 26, 2023
Copenhagen, Denmark
Acceptance Rates
Overall Acceptance Rate 37 of 108 submissions, 34%
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
Total Citations
42
Total Downloads
- Downloads (Last 12 months)42
- Downloads (Last 6 weeks)4
Other Metrics
View Author Metrics
Citations
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.
Sign in
Full Access
Get this Publication
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderMedia
Figures
Other
Tables
