Many encrypted database (EDB) systems have been proposed\u00a0in the last few years as cloud computing has grown\u00a0in popularity and data breaches have increased. The stateof-the-art\u00a0EDB systems for relational databases can handle\u00a0SQL queries over encrypted data and are competitive with\u00a0commercial database systems. These systems, most of which\u00a0are based on the design of CryptDB (SOSP 2011 ), achieve\u00a0these properties by making use of property-preserving encryption\u00a0schemes such as deterministic (DTE) and orderpreserving\u00a0encryption (OPE).<\/p>\n
In this paper, we study the concrete security provided by\u00a0such systems. We present a series of attacks that recover the\u00a0plaintext from DTE- and OPE-encrypted database columns\u00a0using only the encrypted column and publicly-available auxiliary\u00a0information. We consider well-known attacks, including\u00a0frequency analysis and sorting, as well as new attacks\u00a0based on combinatorial optimization.<\/p>\n
We evaluate these attacks empirically in an electronic medical\u00a0records (EMR) scenario using real patient data from\u00a0200 U.S. hospitals. When the encrypted database is operating\u00a0in a steady-state where enough encryption layers have\u00a0been peeled to permit the application to run its queries,\u00a0our experimental results show that an alarming amount of\u00a0sensitive information can be recovered. In particular, our attacks\u00a0correctly recovered certain OPE-encrypted attributes\u00a0(e.g., age and disease severity) for more than 80% of the patient\u00a0records from 95% of the hospitals; and certain DTEencrypted\u00a0attributes (e.g., sex, race, and mortality risk) for\u00a0more than 60% of the patient records from more than 60%\u00a0of the hospitals.<\/p>\n","protected":false},"excerpt":{"rendered":"
Many encrypted database (EDB) systems have been proposed\u00a0in the last few years as cloud computing has grown\u00a0in popularity and data breaches have increased. The stateof-the-art\u00a0EDB systems for relational databases can handle\u00a0SQL queries over encrypted data and are competitive with\u00a0commercial database systems. These systems, most of which\u00a0are based on the design of CryptDB (SOSP 2011 ), […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"ACM","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"Conference on Computer and Communications Security (CCS '15)","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"Conference on Computer and Communications Security (CCS '15)","msr_doi":"http:\/\/dx.doi.org\/10.1145\/2810103.2813651","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2015-10-12","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13563,13558],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-362084","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-data-platform-analytics","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_publishername":"ACM","msr_edition":"Conference on Computer and Communications Security (CCS '15)","msr_affiliation":"","msr_published_date":"2015-10-12","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"362087","msr_publicationurl":"","msr_doi":"http:\/\/dx.doi.org\/10.1145\/2810103.2813651","msr_publication_uploader":[{"type":"file","title":"edb","viewUrl":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2017\/02\/edb.pdf","id":362087,"label_id":0},{"type":"doi","title":"http:\/\/dx.doi.org\/10.1145\/2810103.2813651","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Muhammad Naveed","user_id":0,"rest_url":false},{"type":"text","value":"Seny Kamara","user_id":0,"rest_url":false},{"type":"text","value":"Charles V. Wright","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/362084","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/362084\/revisions"}],"predecessor-version":[{"id":535420,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/362084\/revisions\/535420"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=362084"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=362084"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=362084"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=362084"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=362084"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=362084"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=362084"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=362084"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=362084"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=362084"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=362084"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=362084"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=362084"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}