{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T01:11:30Z","timestamp":1790212290427,"version":"4.1.0"},"reference-count":86,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>\n            We design, implement, and evaluate a new methodology for inferring data stored in such encrypted databases. The cornerstone is the\n            <jats:italic>multinomial attack<\/jats:italic>\n            , 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.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.14778\/3236187.3236217","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1715-1728","source":"Crossref","is-referenced-by-count":56,"title":["The tao of inference in privacy-protected databases"],"prefix":"10.14778","volume":"11","author":[{"given":"Vincent","family":"Bindschaedler","sequence":"first","affiliation":[{"name":"UIUC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Grubbs","sequence":"additional","affiliation":[{"name":"Cornell Tech"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Cash","sequence":"additional","affiliation":[{"name":"University of Chicago"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Ristenpart","sequence":"additional","affiliation":[{"name":"Cornell Tech"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vitaly","family":"Shmatikov","sequence":"additional","affiliation":[{"name":"Cornell Tech"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/76894.76895"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007632"},{"key":"e_1_2_1_3_1","volume-title":"Anthem data breach. https:\/\/www.anthemfacts.com\/","year":"2016"},{"key":"e_1_2_1_4_1","volume-title":"CIDR","author":"Arasu Arvind","year":"2013"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-05445-7_19"},{"key":"e_1_2_1_7_1","volume-title":"The tao of inference in privacy-protected databases (full version). IACR ePrint","author":"Bindschaedler Vincent","year":"2017"},{"key":"e_1_2_1_8_1","volume-title":"CT-RSA.","author":"Black John","year":"2002"},{"key":"e_1_2_1_9_1","volume-title":"EUROCRYPT.","author":"Boldyreva Alexandra","year":"2009"},{"key":"e_1_2_1_10_1","volume-title":"Eurocrypt.","author":"Boneh Dan","year":"2015"},{"key":"e_1_2_1_11_1","volume-title":"USENIX HealthTech","author":"Chan Ellick","year":"2013"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-52993-5_24"},{"key":"e_1_2_1_13_1","volume-title":"http:\/\/www.ciphercloud.com\/","year":"2016"},{"key":"e_1_2_1_14_1","volume-title":"http:\/\/money.cnn.com\/2016\/09\/22\/technology\/yahoo-data-breach\/","author":"CNN.","year":"2016"},{"key":"e_1_2_1_15_1","first-page":"15","article-title":"Towards a methodology for statistical disclosure control","author":"Dalenius Tore","year":"1977","journal-title":"Statistik Tidskrift"},{"issue":"3","key":"e_1_2_1_16_1","article-title":"Finding a needle in a haystack or Identifying anonymous Census records","volume":"2","author":"Dalenius Tore","year":"1986","journal-title":"J. Offic. Stat."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/948109.948124"},{"key":"e_1_2_1_18_1","volume-title":"USAddress library. https:\/\/github.com\/datamade\/usaddress","year":"2016"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.485629"},{"key":"e_1_2_1_20_1","unstructured":"Pennsylvania State Department. PA voters. http:\/\/www.dos.pa.gov\/votingelections\/pages\/default.aspx 2016.  Pennsylvania State Department. PA voters. http:\/\/www.dos.pa.gov\/votingelections\/pages\/default.aspx 2016."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Josep Domingo-Ferrer. A survey of inference control methods for privacy-preserving data mining. http:\/\/vneumann.etse.urv.es\/webCrises\/publications\/bcpi\/domingo-ferrer_survey_SDC_corrected.pdf 2008.  Josep Domingo-Ferrer. A survey of inference control methods for privacy-preserving data mining. http:\/\/vneumann.etse.urv.es\/webCrises\/publications\/bcpi\/domingo-ferrer_survey_SDC_corrected.pdf 2008.","DOI":"10.1007\/978-0-387-70992-5_3"},{"key":"e_1_2_1_22_1","volume-title":"Encyclopedia of Database Systems","author":"Domingo-Ferrer Josep","year":"2009"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978379"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516657"},{"key":"e_1_2_1_26_1","unstructured":"eWeek. Navajo Systems. http:\/\/tinyurl.com\/y85obds6 2009.  eWeek. Navajo Systems. http:\/\/tinyurl.com\/y85obds6 2009."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24177-7_7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/772862.772864"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10501049"},{"key":"e_1_2_1_30_1","volume-title":"http:\/\/www.mifop.com\/?zone=\/unionactive\/view_page.cfm&page=About20MIFOP","author":"About FOP.","year":"2017"},{"key":"e_1_2_1_31_1","volume-title":"http:\/\/www.coloradofop.org\/?zone=\/unionactive\/private_view_page.cfm&page=Local20Lodge20Directory","author":"FOP.","year":"2017"},{"key":"e_1_2_1_32_1","volume-title":"http:\/\/www.floridastatefop.org\/howjoin.asp","author":"FOP.","year":"2017"},{"key":"e_1_2_1_33_1","volume-title":"http:\/\/www.ncfop69.org\/about-us\/","author":"North FOP.","year":"2017"},{"key":"e_1_2_1_34_1","volume-title":"http:\/\/www.okfop.org\/index.cfm?zone=\/unionactive\/view_page.cfm&page=About20us","author":"FOP.","year":"2017"},{"key":"e_1_2_1_35_1","volume-title":"http:\/\/www.pafop.org\/","author":"FOP.","year":"2017"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715949"},{"key":"e_1_2_1_37_1","volume-title":"Data segmentation in electronic health information exchange: policy considerations and analysis","author":"Goldstein Melissa","year":"2010"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978351"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3102980.3103007"},{"key":"e_1_2_1_40_1","volume-title":"S&P","author":"Grubbs Paul","year":"2017"},{"key":"e_1_2_1_41_1","volume-title":"USENIX HealthTech","author":"Gunter Carl","year":"2014"},{"key":"e_1_2_1_42_1","volume-title":"CRYPTO.","author":"Halevi Shai","year":"2003"},{"key":"e_1_2_1_43_1","volume-title":"CT-RSA.","author":"Halevi Shai","year":"2004"},{"key":"e_1_2_1_44_1","volume-title":"HCUP nationwide inpatient sample (NIS). https:\/\/www.hcup-us.ahrq.gov\/nisoverview.jsp","author":"Cost Healthcare","year":"2008"},{"key":"e_1_2_1_45_1","volume-title":"HCUP clinical classifications software (CCS) for ICD-9-CM. https:\/\/www.hcup-us.ahrq.gov\/toolssoftware\/ccs\/ccs.jsp","author":"Cost Healthcare","year":"2016"},{"key":"e_1_2_1_46_1","volume-title":"S&P","author":"Hinke Thomas H","year":"1988"},{"key":"e_1_2_1_47_1","unstructured":"IQrypt. IQrypt: Encrypt and query your database. http:\/\/www.iqrypt.com\/ 2016.  IQrypt. IQrypt: Encrypt and query your database. http:\/\/www.iqrypt.com\/ 2016."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2014.7040946"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813629"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660277"},{"key":"e_1_2_1_52_1","volume-title":"S&P","author":"Lacharit\u00e9 Marie-Sarah","year":"2018"},{"key":"e_1_2_1_53_1","unstructured":"Marie-Sarah Lacharit\u00e9 and Kenneth G Paterson. A note on the optimality of frequency analysis vs. &ell;<sub>p<\/sub>-optimization. http:\/\/eprint.iacr.org\/2015\/1158.pdf 2015.  Marie-Sarah Lacharit\u00e9 and Kenneth G Paterson. A note on the optimality of frequency analysis vs. &ell;<sub> p <\/sub>-optimization. http:\/\/eprint.iacr.org\/2015\/1158.pdf 2015."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978376"},{"key":"e_1_2_1_55_1","volume-title":"USENIX Security","author":"Luchaup Daniel","year":"2014"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660351"},{"key":"e_1_2_1_57_1","volume-title":"S&P","author":"Lunt Teresa F","year":"1989"},{"key":"e_1_2_1_58_1","volume-title":"https:\/\/msdn.microsoft.com\/en-us\/library\/mt163865.aspx","author":"Database Always Encrypted","year":"2016"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.33"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813651"},{"key":"e_1_2_1_61_1","volume-title":"Skyhigh Networks. https:\/\/www.skyhighnetworks.com\/","author":"Networks Skyhigh","year":"2017"},{"key":"e_1_2_1_62_1","volume-title":"Automatic linkage of vital records. Science, 130(3381)","author":"Newcombe H.","year":"1959"},{"key":"e_1_2_1_63_1","volume-title":"Newey and Daniel McFadden","author":"Whitney","year":"1994"},{"key":"e_1_2_1_64_1","unstructured":"State of Ohio. Ohio voters. http:\/\/ohiovoters.info\/ 2016.  State of Ohio. Ohio voters. http:\/\/ohiovoters.info\/ 2016."},{"key":"e_1_2_1_65_1","volume-title":"The data segmentation for privacy initiative. https:\/\/www.healthit.gov\/providers-professionals\/ds4p-initiative","author":"Chief Privacy Officer Office","year":"2016"},{"key":"e_1_2_1_66_1","volume-title":"HL7 implementation guide for DS4P initiative. https:\/\/www.hl7.org\/implement\/standards\/product_brief.cfm?product_id=354","author":"Office of the National Coordinator.","year":"2016"},{"key":"e_1_2_1_67_1","volume-title":"NSDI","author":"Papadimitriou Antonis","year":"2016"},{"key":"e_1_2_1_68_1","unstructured":"Perspecys. Perspecsys: A Blue Coat Company. http:\/\/perspecsys.com\/ 2016.  Perspecys. Perspecsys: A Blue Coat Company. http:\/\/perspecsys.com\/ 2016."},{"key":"e_1_2_1_69_1","volume-title":"Arx: A strongly encrypted database system. https:\/\/eprint.iacr.org\/2016\/591","author":"Poddar Rishabh","year":"2016"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.38"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_1_72_1","volume-title":"Guidelines for using the CryptDB system securely. https:\/\/eprint.iacr.org\/2015\/979","author":"Popa Raluca","year":"2015"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978345"},{"key":"e_1_2_1_74_1","unstructured":"Phillip Rogaway and Thomas Shrimpton. The SIV mode of operation for deterministic authenticated-encryption (key wrap) and misuse-resistant nonce-based authenticated-encryption. http:\/\/web.cs.ucdavis.edu\/~rogaway\/papers\/siv.pdf 2007.  Phillip Rogaway and Thomas Shrimpton. The SIV mode of operation for deterministic authenticated-encryption (key wrap) and misuse-resistant nonce-based authenticated-encryption. http:\/\/web.cs.ucdavis.edu\/~rogaway\/papers\/siv.pdf 2007."},{"key":"e_1_2_1_75_1","volume-title":"SAP SEEED Project. https:\/\/www.sics.se\/sites\/default\/files\/pub\/andreasschaad.pdf","author":"Schaad Andreas","year":"2016"},{"key":"e_1_2_1_76_1","volume-title":"Identification and retrieval of personal records from a statistical data bank. Methods Inf. Med., 14(1)","author":"Schl\u00f6rer J.","year":"1975"},{"key":"e_1_2_1_77_1","first-page":"25","article-title":"Weaving technology and policy together to maintain confidentiality. J. of Law","author":"Sweeney Latanya","year":"1997","journal-title":"Medicine and Ethics"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535573.2488336"},{"key":"e_1_2_1_79_1","unstructured":"US Census Bureau. American community survey (ACS). http:\/\/www.census.gov\/programs-surveys\/acs\/ 2016.  US Census Bureau. American community survey (ACS). http:\/\/www.census.gov\/programs-surveys\/acs\/ 2016."},{"key":"e_1_2_1_80_1","unstructured":"USPS. ZIP code database. http:\/\/www.unitedstateszipcodes.org\/zip-code-database\/ 2016.  USPS. ZIP code database. http:\/\/www.unitedstateszipcodes.org\/zip-code-database\/ 2016."},{"key":"e_1_2_1_81_1","volume-title":"Sony pictures entertainment hack. https:\/\/en.wikipedia.org\/wiki\/Sony_Pictures_Entertainment_hack","year":"2017"},{"key":"e_1_2_1_82_1","volume-title":"Target customer privacy. https:\/\/en.wikipedia.org\/wiki\/Target_Corporation#Customer_privacy","year":"2017"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4028-0"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0121-9"},{"key":"e_1_2_1_85_1","volume-title":"RateMyCop user ensnared in dumbest case ever. https:\/\/www.wired.com\/2010\/06\/dumbest-case-ever\/","year":"2010"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"},{"key":"e_1_2_1_87_1","volume-title":"NSDI","author":"Zheng Wenting","year":"2017"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3236187.3236217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:42:43Z","timestamp":1672220563000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3236187.3236217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":86,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.14778\/3236187.3236217"],"URL":"https:\/\/doi.org\/10.14778\/3236187.3236217","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}