From: "Lori A. Bailey" Subject: EE Seminar - December 1, 2015, 4:30 pm, E-Quad B205 - Muhammad Naveed Date: November 13, 2015 at 10:41:48 AM EST To: ee-seminar@Princeton.EDU Reply-To: "Lori A. Bailey"

Speaker: Muhammad Naveed University of Illinois at Urbana-Champaign Title: Inference Attacks on Property-Preserving Encrypted Databases Date: December 1, 2015 Time: 4:30 p.m. Room: E-Quad, Room B205 Host: Prof. Prateek Mittal

Abstract: 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.

The paper appeared at ACM CCS 2015 and is available at: http://research.microsoft.com/en-us/um/people/senyk/pubs/edb.pdf http://research.microsoft.com/en-us/um/people/senyk/pubs/edb.pdf.

Biography: Muhammad Naveed is a fifth (and final) year PhD student in computer science at the University of Illinois at Urbana-Champaign. He is currently visiting Prof. Elaine Shi at the Cornell University. He develops provably-secure and practical cryptographic systems for real applications. He also works on systems security and genomics privacy. He is a recipient of the 2015 Google PhD fellowship in Security, the Sohaib and Sara Abbasi fellowship (2011–2016), and CS@Illinois C.W. Gear Outstanding Graduate Student Award. See his homepage www.cryptoonline.com http://www.cryptoonline.com/ for more details.