Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage
Open accessThe DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
We analyse the security of database encryption schemes supporting range queries against persistent adversaries. The bulk of our work applies to a generic setting, where the adversary's view is limited to the set of records matched by each query (known as access pattern leakage). We also consider a more specific setting where rank information is also leaked, which is inherent inherent to multiple recent encryption schemes supporting range queries. We provide three attacks. First, we consider full reconstruction, which aims to recover the value of every record, fully negating encryption. We show that for dense datasets, full reconstruction is possible within an expected number of queries N log N + O(N), where N is the number of distinct plaintext values. This directly improves on a quadratic bound in the same setting by Kellaris et al. (CCS 2016). Second, we present an approximate reconstruction attack recovering all plaintext values in a dense dataset within a constant ratio of error, requiring the access pattern leakage of only O(N) queries. Third, we devise an attack in the common setting where the adversary has access to an auxiliary distribution for the target dataset. This third attack proves highly effective on age data from real-world medical data sets. In our experiments, observing only 25 queries was sufficient to reconstruct a majority of records to within 5 years. In combination, our attacks show that current approaches to enabling range queries offer little security when the threat model goes beyond snapshot attacks to include a persistent server-side adversary.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Leakage-Abuse Attacks Against Searchable Encryption
Cash, D., Grubbs, P., Perry, J., & Ristenpart, T. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813700 · Cited by 609 · cited 1×
“This has led to serious attacks being found against some of the early schemes [1], [2], [3], [4], [5], [6], [7] – a good summary of this line of research is available in [8].”
BackgroundInference Attacks on Property-Preserving Encrypted Databases
Naveed, M., Kamara, S., & Wright, C. V. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813651 · Cited by 502 · cited 6×
“However, it should be noted that schemes such as [10], [11] that rely on order-preserving or order-revealing encryption (OPE/ORE) are already vulnerable to powerful statistical inference attacks by snapshot adversaries, such as [2].”
BackgroundInfluentialGeneric Attacks on Secure Outsourced Databases
Kellaris, G., Kollios, G., Nissim, K., & O'Neill, A. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978386 · Cited by 284 · cited 10×
“have already shown that O(N(2) logN) queries are enough to achieve full reconstruction for dense databases [9].”
BackgroundResultInfluentialBlind Seer: A Scalable Private DBMS
Pappas, V., Krell, F., Vo, B., Kolesnikov, V., Malkin, T., Choi, S. G., George, W., Keromytis, A., & Bellovin, S. (2014) · 2014 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2014.30 · Cited by 237 · cited 1×
“[12], as well as a scheme by Faber et al.”
MethodBoneh, D., Lewi, K., Raykova, M., Sahai, A., Zhandry, M., & Zimmerman, J. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-46803-6_19 · Cited by 227 · cited 1×
“However, it should be noted that schemes such as [10], [11] that rely on order-preserving or order-revealing encryption (OPE/ORE) are already vulnerable to powerful statistical inference attacks by snapshot adversaries, such as [2].”
BackgroundLeakage-Abuse Attacks against Order-Revealing Encryption
Grubbs, P., Sekniqi, K., Bindschaedler, V., Naveed, M., & Ristenpart, T. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.44 · Cited by 203 · cited 4×
“This has led to serious attacks being found against some of the early schemes [1], [2], [3], [4], [5], [6], [7] – a good summary of this line of research is available in [8].”
BackgroundInfluentialRich Queries on Encrypted Data: Beyond Exact Matches
Faber, S., Jarecki, S., Krawczyk, H., Nguyen, Q., Rosu, M., & Steiner, M. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-24177-7_7 · Cited by 199 · cited 1×
“[13]; they also include approaches based on Range Predicate Encryption, such as [14].”
MethodCryptology ePrint Archive: Report 2018/737
Pulls, T., & Dahlberg, R. (2018) · Cited by 194
Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds
Lewi, K., & Wu, D. J. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978376 · Cited by 193 · cited 1×
“The second group includes a variety of recent schemes, such as Lewi and Wu’s ORE2 construction [15] (used in EncKV [16]), Arx [17] (which mentions ongoing collaboration with health data cloud provider Chino and European medical project UNCAP to deploy their scheme), FH-OPE [18], and Cipherbase [19].”
BackgroundPractical Order-Revealing Encryption with Limited Leakage
Chenette, N., Lewi, K., Weis, S. A., & Wu, D. J. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-52993-5_24 · Cited by 170 · cited 1×
“However, it should be noted that schemes such as [10], [11] that rely on order-preserving or order-revealing encryption (OPE/ORE) are already vulnerable to powerful statistical inference attacks by snapshot adversaries, such as [2].”
Background
Cited by
The tao of inference in privacy-protected databases
Bindschaedler, V., Grubbs, P., Cash, D., Ristenpart, T., & Shmatikov, V. (2018) · Proceedings of the VLDB Endowment · doi:10.14778/3236187.3236217 · Cited by 75
Metadata
- Authors
- Lacharite, M.-S., Minaud, B., & Paterson, K. G.
- Venue
- 2018 IEEE Symposium on Security and Privacy (SP)
- Publisher
- IEEE
- Published
- 2018-05
- Pages
- 297-314
- ISSN
- 1081-6011 (ISSN-L)
- OpenAlex
- W2794508460
- Cited by
- 173
- References
- 19
- FWCI
- 8.95
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.