Inference Attacks on Property-Preserving Encrypted Databases

被引:297
作者
Naveed, Muhammad [1 ,2 ]
Kamara, Seny [2 ]
Wright, Charles V. [3 ]
机构
[1] UIUC, Champaign, IL 61820 USA
[2] Microsoft Res, Redmond, WA USA
[3] Portland State Univ, Portland, OR 97207 USA
来源
CCS'15: PROCEEDINGS OF THE 22ND ACM SIGSAC CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY | 2015年
关键词
inference attacks; encrypted databases; property-preserving encryption; deterministic encryption; order-preserving encryption;
D O I
10.1145/2810103.2813651
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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. We evaluate these attacks empirically in an electronic medical records (EMR) scenario using real patient data from 200 U.S. hospitals. When the encrypted database is operating in a steady-state where enough encryption layers have been peeled to permit the application to run its queries, our experimental results show that an alarming amount of sensitive information can be recovered. In particular, our attacks correctly recovered certain OPE-encrypted attributes (e.g., age and disease severity) for more than 80% of the patient records from 95% of the hospitals; and certain DTE-encrypted attributes (e.g., sex, race, and mortality risk) for more than 60% of the patient records from more than 60% of the hospitals.
引用
收藏
页码:644 / 655
页数:12
相关论文
共 34 条
[1]  
Agrawal R., 2004, P ACM SIGMOD INT C M, P563
[2]  
Akin I. H., 2014, PRISEC
[3]  
Al-Kadit I.A., 1992, Cryptologia, V16, P97, DOI DOI 10.1080/0161-119291866801
[4]  
[Anonymous], 2012, NDSS 2012
[5]  
[Anonymous], NAVAL RES LOGISTICS
[6]  
[Anonymous], 2008, HC1P DAT HEALTHC COS
[7]  
[Anonymous], 2012, Soc. Ind. Appl. Math
[8]  
Arasu Arvind, 2013, CIDR
[9]  
Bellare M, 2007, LECT NOTES COMPUT SC, V4622, P535
[10]  
Boldyreva A, 2011, LECT NOTES COMPUT SC, V6841, P578, DOI 10.1007/978-3-642-22792-9_33