The DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Inference Attacks on Property-Preserving Encrypted Databases
Abstract
Many encrypted database (EDB) systems have been proposed in the last few years as cloud computing has grown in popularity and data breaches have increased. The state-of-the-art EDB systems for relational databases can handle SQL queries over encrypted data and are competitive with commercial database systems. These systems, most of which are based on the design of CryptDB (SOSP 2011), achieve these properties by making use of property-preserving encryption schemes such as deterministic (DTE) and order- preserving encryption (OPE). In this paper, we study the concrete security provided by such systems. We present a series of attacks that recover the plaintext from DTE- and OPE-encrypted database columns using only the encrypted column and publicly-available auxiliary information. We consider well-known attacks, including frequency analysis and sorting, as well as new attacks based on combinatorial optimization.
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
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806 · cited 1×
“There are various approaches to search on encrypted data including searchable symmetric encryption (SSE) [20, 37], fully-homomorphic encryption (FHE) [23], oblivious RAMs (ORAM) [24], functional encryption [15], and property-preserving encryption (PPE) [11,12].”
Algorithms for the Assignment and Transportation Problems
Munkres, J. (1957) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0105003 · Cited by 3,986
Practical techniques for searches on encrypted data
Song, D. X., Wagner, D., & Perrig, A. (2002) · Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000 · doi:10.1109/secpri.2000.848445 · Cited by 3,350
Introduction to Modern Cryptography
Katz, J., & Lindell, Y. (2014) · Chapman & Hall/CRC eBooks · doi:10.1201/b17668 · Cited by 1,880
Searchable symmetric encryption: improved definitions and efficient constructions
Curtmola, R., Garay, J., Kamara, S., & Ostrovsky, R. (2006) · Proceedings of the 13th ACM conference on Computer and communications security · doi:10.1145/1180405.1180417 · Cited by 1,671
Self-citationSoftware protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
Burkard, R., Dell'Amico, M., & Martello, S. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898717754 · Cited by 1,394
Introduction to Modern Cryptography
Katz, J., & Lindell, Y. (2007) · doi:10.1201/9781420010756 · Cited by 1,238
Order preserving encryption for numeric data
Agrawal, R., Kiernan, J., Srikant, R., & Xu, Y. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007632 · Cited by 1,206
CryptDB: protecting confidentiality with encrypted query processing
Popa, R. A., Redfield, C. M. S., Zeldovich, N., & Balakrishnan, H. (2011) · Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles · doi:10.1145/2043556.2043566 · Cited by 1,155
Healthcare Cost and Utilization Project (HCUP)
(2016) · The SAGE Encyclopedia of Pharmacology and Society · doi:10.4135/9781483349985.n182 · Cited by 1,035
Functional Encryption: Definitions and Challenges
Boneh, D., Sahai, A., & Waters, B. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-19571-6_16 · Cited by 1,010
Order-Preserving Symmetric Encryption
Boldyreva, A., Chenette, N., Lee, Y., & O’Neill, A. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-01001-9_13 · Cited by 887
Deterministic and Efficiently Searchable Encryption
Bellare, M., Boldyreva, A., & O’Neill, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-74143-5_30 · Cited by 745
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
Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions
Boldyreva, A., Chenette, N., & O’Neill, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22792-9_33 · Cited by 498
Access Pattern disclosure on Searchable Encryption: Ramification, Attack and Mitigation.
Islam, M. S., Kuzu, M., & Kantarcıoğlu, M. (2012) · Cited by 491
Introduction to Modern Cryptography (Chapman & Hall/CRC Cryptography and Network Security Series)
Katz, J. I., & Lindell, Y. (2020) · Cited by 451
An Ideal-Security Protocol for Order-Preserving Encoding
Popa, R. A., Li, F. H., & Zeldovich, N. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.38 · Cited by 386
Fan, J., Xu, J., Ammar, M. H., & Moon, S. B. (2004) · Computer Networks · doi:10.1016/j.comnet.2004.03.033 · Cited by 288
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
Optimal Average-Complexity Ideal-Security Order-Preserving Encryption
Kerschbaum, F., & Schröpfer, A. (2014) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2660267.2660277 · Cited by 152
Orthogonal Security With Cipherbase
Arasu, A., Blanas, S., Eguro, K., et al. (2013) · Cited by 149
ORIGINS OF CRYPTOLOGY: THE ARAB CONTRIBUTIONS
Al-Kadit, I. A. (1992) · Cryptologia · doi:10.1080/0161-119291866801 · Cited by 84
Chaotic Order Preserving Encryption for Efficient and Secure Queries on Databases
Lee, S., Park, T., Lee, D., et al. (2009) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.e92.d.2207 · Cited by 41
On the Difficulty of Securing Web Applications Using CryptDB
Akin, I. H., & Sunar, B. (2014) · IEEE International Conference on Big Data and Cloud Computing (BDCloud) · doi:10.1109/bdcloud.2014.75 · Cited by 21
Cited by
A Pragmatic Introduction to Secure Multi-Party Computation
Evans, D., Kolesnikov, V., & Rosulek, M. (2018) · Foundations and Trends® in Privacy and Security · doi:10.1561/3300000019 · Cited by 321
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
EnclaveDB: A Secure Database Using SGX
Priebe, C., Vaswani, K., & Costa, M. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00025 · Cited by 284
Towards Public Verifiable and Forward-Privacy Encrypted Search by Using Blockchain
Guo, Y., Zhang, C., Wang, C., & Jia, X. (2022) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2022.3173291 · Cited by 263
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
- Naveed, M., Kamara, S., & Wright, C. V.
- Venue
- Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security
- Publisher
- ACM
- Published
- 2015-10-12
- Pages
- 644-655
- OpenAlex
- W2074388704
- Cited by
- 502
- References
- 29
- FWCI
- 32.38
- Type
- conference paper
- Language
- en
- Open access
- closed
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.