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
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The tao of inference in privacy-protected databases. https://app.cochat.ai/papers/10.14778/3236187.3236217
- The paper
- Bindschaedler, V., Grubbs, P., Cash, D., Ristenpart, T., & Shmatikov, V. (2018). The tao of inference in privacy-protected databases. Proceedings of the VLDB Endowment. https://doi.org/10.14778/3236187.3236217
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.