The tao of inference in privacy-protected databases
The DOI matches its Crossref record; 60 of the 61 references it cites were found in a registry or an index.
Abstract
To protect database confidentiality even in the face of full compromise while supporting standard functionality, recent academic proposals and commercial products rely on a mix of encryption schemes. The recommendation is to apply strong, semantically secure encryption to the "sensitive" columns and protect other columns with property-revealing encryption (PRE) that supports operations such as sorting. We design, implement, and evaluate a new methodology for inferring data stored in such encrypted databases. The cornerstone is the multinomial attack , a new inference technique that is analytically optimal and empirically outperforms prior heuristic attacks against PRE-encrypted data. We also extend the multinomial attack to take advantage of correlations across multiple columns. This recovers PRE-encrypted data with sufficient accuracy to then apply machine learning and record linkage methods to infer columns protected by semantically secure encryption or redaction. We evaluate our methodology on medical, census, and union-membership datasets, showing for the first time how to infer full database records. For PRE-encrypted attributes such as demographics and ZIP codes, our attack outperforms the best prior heuristic by a factor of 16. Unlike any prior technique, we also infer attributes, such as incomes and medical diagnoses, protected by strong encryption. For example, when we infer that a patient in a hospital-discharge dataset has a mental health or substance abuse condition, this prediction is 97% accurate.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Dwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
Protocols for secure computations
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.88 · Cited by 2,696
Fellegi, I. P., & Sunter, A. B. (1969) · Journal of the American Statistical Association · doi:10.1080/01621459.1969.10501049 · Cited by 2,475
Robust De-anonymization of Large Sparse Datasets
Narayanan, A., & Shmatikov, V. (2008) · 2008 IEEE Symposium on Security and Privacy (sp 2008) · doi:10.1109/sp.2008.33 · Cited by 2,372 · cited 3×
“Our linkage methods draw on known techniques for linking datasets on quasi-identifiers [77] and incomplete, noisy common attributes [59].”
BackgroundMethodSelf-citationHow to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
Chapter 36 Large sample estimation and hypothesis testing
Newey, W. K., & McFadden, D. (1994) · Handbook of Econometrics · doi:10.1016/s1573-4412(05)80005-4 · Cited by 1,743
Encyclopedia of Database Systems
(2009) · Springer eBooks · doi:10.1007/978-0-387-39940-9 · Cited by 1,739
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
Security-control methods for statistical databases: a comparative study
Adam, N. R., & Worthmann, J. C. (1989) · ACM Computing Surveys · doi:10.1145/76894.76895 · Cited by 969
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
The American Community Survey: Summary of a Workshop
(2001) · National Academies Press eBooks · doi:10.17226/10051 · Cited by 859
Newcombe, H. B., Kennedy, J. M., Axford, S. J., & James, A. P. (1959) · Science · doi:10.1126/science.130.3381.954 · Cited by 770
Elements of Statistical Disclosure Control
Willenborg, L., & de Waal, T. (2001) · Lecture Notes in Statistics · doi:10.1007/978-1-4613-0121-9 · Cited by 649
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
Opaque: an oblivious and encrypted distributed analytics platform
Zheng, W., Dave, A., Beekman, J. G., Popa, R. A., Gonzalez, J. E., & Stoica, I. G. (2017) · Networked Systems Design and Implementation · Cited by 440
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
Weaving Technology and Policy Together to Maintain Confidentiality
Sweeney, L. (1997) · Journal of Law, Medicine & Ethics · doi:10.1111/j.1748-720x.1997.tb01885.x · Cited by 375
Processing analytical queries over encrypted data
Tu, S., Kaashoek, M. F., Madden, S., & Zeldovich, N. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2535573.2488336 · Cited by 359
Balancing confidentiality and efficiency in untrusted relational DBMSs
Damiani, E., Vimercati, S. D. C., Jajodia, S., Paraboschi, S., & Samarati, P. (2003) · Proceedings of the 10th ACM conference on Computer and communications security · doi:10.1145/948109.948124 · Cited by 338
Statistical Disclosure Control in Practice
Willenborg, L., & de Waal, T. (1996) · Lecture Notes in Statistics · doi:10.1007/978-1-4612-4028-0 · Cited by 298
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
Bellare, M., Ristenpart, T., Rogaway, P., & Stegers, T. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-05445-7_19 · Cited by 274
Self-citationThe inference problem: a survey
Farkas, C., & Jajodia, S. (2002) · ACM SIGKDD Explorations Newsletter · doi:10.1145/772862.772864 · Cited by 267
Halevi, S., & Rogaway, P. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_28 · Cited by 261
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
Orthogonal Security With Cipherbase
Arasu, A., Blanas, S., Eguro, K., Kaushik, R., Kossmann, D., Ramamurthy, R., & Venkatesan, R. (2013) · Conference on Innovative Data Systems Research · Cited by 222
A Parallelizable Enciphering Mode
Halevi, S., & Rogaway, P. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24660-2_23 · Cited by 220
Ciphers with Arbitrary Finite Domains
Black, J., & Rogaway, P. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45760-7_9 · Cited by 205
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
Self-citationRich 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
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
Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage
Lacharite, M.-S., Minaud, B., & Paterson, K. G. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00002 · Cited by 173
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
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
Self-citationHow To Construct Random Functions
Goldreich, O., Goldwasser, S., & Micali, S. (1984) · 25th Annual Symposium onFoundations of Computer Science, 1984. · doi:10.1109/sfcs.1984.715949 · Cited by 163
Big Data Analytics over Encrypted Datasets with Seabed
Papadimitriou, A., Bhagwan, R., Chandran, N., Ramjee, R., Haberlen, A., Singh, H., Modi, A., & Badrinarayanan, S. (2016) · ScholarlyCommons (University of Pennsylvania) · Cited by 162
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
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
Protocol misidentification made easy with format-transforming encryption
Dyer, K. P., Coull, S. E., Ristenpart, T., & Shrimpton, T. (2013) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2508859.2516657 · Cited by 144
Self-citationArx: 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
Self-citationInference Control in Statistical Databases
Domingo‐Ferrer, J. (2009) · Springer eBooks · doi:10.1007/978-0-387-39940-9_203 · Cited by 120
Inference aggregation detection in database management systems
Hinke, T. H. (2003) · Proceedings. 1988 IEEE Symposium on Security and Privacy · doi:10.1109/secpri.1988.8101 · Cited by 112
Computing on masked data: a high performance method for improving big data veracity
Kepner, J., Gadepally, V. N., Michaleas, P. W., Schear, N., Varia, M., Yerukhimovich, A., & Cunningham, R. K. (2014) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2014.7040946 · Cited by 100
A Survey of Inference Control Methods for Privacy-Preserving Data Mining
Domingo‐Ferrer, J. (2008) · The Kluwer international series on advances in database systems · doi:10.1007/978-0-387-70992-5_3 · Cited by 89
Why Your Encrypted Database Is Not Secure
Grubbs, P., Ristenpart, T., & Shmatikov, V. (2017) · Workshop on Hot Topics in Operating Systems · doi:10.1145/3102980.3103007 · Cited by 86
Self-citationIdentification and Retrieval of Personal Records from a Statistical Data Bank
Schlörer, J. (1975) · Methods of Information in Medicine · doi:10.1055/s-0038-1635690 · Cited by 84
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
Fader, A. N., Matsuno, R. K., Sinno, A., Tanner, E. J., Long, K. C., Bristow, R. E., & Dowdy, S. C. (2015) · Gynecologic Oncology · doi:10.1016/j.ygyno.2015.01.385 · Cited by 80
Aggregation and inference: facts and fallacies
Lunt, T. F. (2003) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/secpri.1989.36284 · Cited by 78
Wizard: a database inference analysis and detection system
Delugach, H. S., & Hinke, T. H. (1996) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.485629 · Cited by 61
LibFTE: a toolkit for constructing practical, format-abiding encryption schemes
Luchaup, D., Dyer, K. P., Jha, S., Ristenpart, T., & Shrimpton, T. (2014) · USENIX Security Symposium · Cited by 26
Self-citationA note on the optimality of frequency analysis vs. ℓp-optimizationPreprint
Lacharité, M.-S., & Paterson, K. G. (2015) · IACR Cryptology ePrint Archive · doi:10.5281/zenodo.2594706 · Cited by 21
Guidelines for Using the CryptDB System Securely.Preprint
Popa, R. A., Zeldovich, N., & Balakrishnan, H. (2015) · IACR Cryptology ePrint Archive · Cited by 20
Data Segmentation in Electronic Health Information Exchange: Policy Considerations and Analysis
Goldstein, M. M., Rein, A. L., Heesters, M. M., Hughes, P., Williams, B., & Weinstein, S. A. (2010) · Cited by 15
From Keys to Databases - Real-World Applications of Secure Multi-Party Computation.
Archer, D. W., Bogdanov, D., Lindell, Y., Kamm, L., Nielsen, K., Pagter, J. I., Smart, N. P., & Wright, R. N. (2018) · Research at the University of Copenhagen (University of Copenhagen) · Cited by 13
Understanding the challenges with medical data segmentation for privacy
Chan, E. M., Lam, P. E., & Mitchell, J. C. (2013) · Cited by 12
Formatted Encryption Beyond Regular Languages
Luchaup, D., Shrimpton, T., Ristenpart, T., & Jha, S. (2014) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2660267.2660351 · Cited by 9
Self-citationDecision Support for Data Segmentation (DS2): Application to Pull Architectures for {HIE}
Gunter, C. A., Berry, M., & French, M. A. (2014) · Cited by 3
Research works printed but not linked: 33
- 2016, Anthem data breach. https://www.anthemfacts.com/
- Arasu Arvind, 2013, CIDR
- Bindschaedler Vincent, 2017, The tao of inference in privacy-protected databases (full version). IACR ePrint
- Black John, 2002, CT-RSA.
- Boldyreva Alexandra, 2009, EUROCRYPT.
- Boneh Dan, 2015, Eurocrypt.
- Chan Ellick, 2013, USENIX HealthTech
- 2016, http://www.ciphercloud.com/
- Dalenius Tore, 1977, Towards a methodology for statistical disclosure control, Statistik Tidskrift, 15
- Dalenius Tore, 1986, Finding a needle in a haystack or Identifying anonymous Census records, J. Offic. Stat., 2
- About FOP., 2017, http://www.mifop.com/?zone=/unionactive/view_page.cfm&page=About20MIFOP
- FOP., 2017, http://www.coloradofop.org/?zone=/unionactive/private_view_page.cfm&page=Local20Lodge20Directory
- FOP., 2017, http://www.floridastatefop.org/howjoin.asp
- North FOP., 2017, http://www.ncfop69.org/about-us/
- FOP., 2017, http://www.okfop.org/index.cfm?zone=/unionactive/view_page.cfm&page=About20us
- FOP., 2017, http://www.pafop.org/
- Grubbs Paul, 2017, S&P
- Gunter Carl, 2014, USENIX HealthTech
- Halevi Shai, 2003, CRYPTO.
- Halevi Shai, 2004, CT-RSA.
- Hinke Thomas H, 1988, S&P
- Lacharité Marie-Sarah, 2018, S&P
- Luchaup Daniel, 2014, USENIX Security
- Lunt Teresa F, 1989, S&P
- Database Always Encrypted, 2016, https://msdn.microsoft.com/en-us/library/mt163865.aspx
- Networks Skyhigh, 2017, Skyhigh Networks. https://www.skyhighnetworks.com/
- Newcombe H., 1959, Automatic linkage of vital records. Science, 130(3381)
- Whitney, 1994, Newey and Daniel McFadden
- Office of the National Coordinator., 2016, HL7 implementation guide for DS4P initiative. https://www.hl7.org/implement/standards/product_brief.cfm?product_id=354
- Papadimitriou Antonis, 2016, NSDI
- Schaad Andreas, 2016, SAP SEEED Project. https://www.sics.se/sites/default/files/pub/andreasschaad.pdf
- 10.5555/1382436.1382751 · doi:10.5555/1382436.1382751
- Zheng Wenting, 2017, NSDI
Cited by
Secure, privacy-preserving and federated machine learning in medical imaging
Kaissis, G. A., Makowski, M. R., Rückert, D., & Braren, R. F. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-020-0186-1 · Cited by 1,676
Thieme, A., Belgrave, D., & Doherty, G. (2020) · ACM Transactions on Computer-Human Interaction · doi:10.1145/3398069 · Cited by 406
“[18] Vincent Bindschaedler, Paul Grubbs, David Cash, Thomas Ristenpart, and Vitaly Shmatikov.”
BackgroundPump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries
Grubbs, P., Lacharité, M.-S., Minaud, B., & Paterson, K. G. (2018) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3243734.3243864 · Cited by 179
Self-citationLearning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks
Grubbs, P., Lacharité, M.-S., Minaud, B., & Paterson, K. G. (2019) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2019.00030 · Cited by 158
Self-citationShrinkwrap: efficient SQL query processing in differentially private data federations
Bater, J., He, X., Ehrich, W., Machanavajjhala, A., & Rogers, J. (2018) · Proceedings of the VLDB Endowment · doi:10.14778/3291264.3291274 · Cited by 141
Metadata
- Authors
- Bindschaedler, V., Grubbs, P., Cash, D., Ristenpart, T., & Shmatikov, V.
- Affiliations
- University of Illinois Urbana-Champaign (US)
- Cornell Tech (US)
- University of Chicago (US)
- Venue
- Proceedings of the VLDB Endowment
- Published
- 2018-07
- Volume
- 11
- Issue
- 11
- Pages
- 1715-1728
- ISSN
- 2150-8097 (ISSN-L)
- OpenAlex
- W2889227180
- Cited by
- 75
- References
- 61
- Citations by year
- 2026: 4 · 2025: 4 · 2024: 5 · 2023: 6 · 2022: 16 · 2021: 13 · 2020: 14 · 2019: 9 · 2018: 4
- FWCI
- 5.63
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Proceedings of the VLDB Endowment (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Artificial Intelligence › Internet Traffic Analysis and Secure E-voting
- Keywords
- inference attacks, redaction, data linkage, attribute inference, medical records, census data
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.