CoChat

Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage

Open access
Lacharite, Marie-Sarah, Minaud, Brice, Paterson, Kenneth G. · 2018 · 2018 IEEE Symposium on Security and Privacy (SP)
Cited by 173

The 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/sp.2018.00002

Cites

19 of 19 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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].”
    Background
  • Inference 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].”
    BackgroundInfluential
  • Generic 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].”
    BackgroundResultInfluential
  • Blind 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.”
    Method
  • Semantically Secure Order-Revealing Encryption: Multi-input Functional Encryption Without Obfuscation

    Boneh, 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].”
    Background
  • Leakage-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].”
    BackgroundInfluential
  • Rich 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].”
    Method
  • Cryptology 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].”
    Background
  • Practical 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
  • Breaking Web Applications Built On Top of Encrypted Data

    Grubbs, P., McPherson, R., Naveed, M., Ristenpart, T., & Shmatikov, V. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978351 · Cited by 169 · 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].”
    Background
  • Frequency-Hiding Order-Preserving Encryption

    Kerschbaum, F. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813629 · Cited by 161 · cited 6×

    “Indeed, significant progress seems to have been achieved against snapshot adversaries: although FH-OPE is still vulnerable to some attacks [7], the Lewi-Wu scheme as well as Arx offer, at least in principle, a high level of security against snapshot attackers4, in a way that precludes the type of statistical inference…”
    BackgroundMethodInfluential
  • SoK: Cryptographically Protected Database Search

    Fuller, B. W., Varia, M., Yerukhimovich, A., Shen, E., Hamlin, A., Gadepally, V. N., Shay, R., Mitchell, J. D., & Cunningham, R. K. (2017) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2017.10 · Cited by 136 · 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].”
    Background
  • Arx: A Strongly Encrypted Database System.Preprint

    Poddar, R., Boelter, T., & Popa, R. A. (2016) · IACR Cryptology ePrint Archive · Cited by 129

  • What Else is Revealed by Order-Revealing Encryption?

    Durak, F. B., DuBuisson, T. M., & Cash, D. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978379 · Cited by 127 · 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].”
    Background
  • Privacy-preserving Logarithmic-time Search on Encrypted Data in Cloud.

    Lu, Y. (2012) · Network and Distributed System Security Symposium · Cited by 120

  • POPE: Partial Order Preserving Encoding

    Roche, D. S., Apon, D., Choi, S. G., & Yerukhimovich, A. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978345 · Cited by 83 · cited 1×

    “[20], and a scheme with similar leakage by Hahn and Kerschbaum [21], should also be mentioned: although they mainly target scenarios where the database is not dense, our third attack still applies.”
    Background
  • Transaction processing on confidential data using cipherbase

    Arasu, A., Eguro, K., Joglekar, M., Kaushik, R., Kossmann, D., & Ramamurthy, R. (2015) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2015.7113304 · Cited by 71 · 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].”
    Background
  • EncKV: An Encrypted Key-value Store with Rich Queries

    Yuan, X., Guo, Y., Wang, X., Wang, C., Li, B., & Jia, X. (2017) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/3052973.3052977 · Cited by 54 · 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].”
    Background

Cited by

See all 173

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.