InfoSec Seminar: New Results on Secure Outsourced Database Storage

Speaker: Prof Adam O'Neill, Georgetown University
UCL Contact: Vasilios Mavroudis (Visitors from outside UCL please email in advance).
Date/Time: 20 Jul 17, 16:00 - 17:00
Venue: Gordon Street (25) Maths 500

Abstract

The problem of securely outsourcing storage of a confidential database to an untrusted server while supporting efficient query processing has received considerable attention in theory and practice. A promising approach is to use ``leaky'' encryption on attribute values that allow certain fundamental operations for efficient query processing to be performed. We show new positive and negative results in this setting. On the positive side, we show a new construction of order-revealing encryption (ORE) that has the least leakage to date of any scheme except for impractical ones based on multilinear maps. ORE allows order comparison on encrypted values and hence efficient range query processing. Our scheme is based on bilinear maps and for n-bit plaintexts, ciphertexts consist of about 4n group elements and order comparison requires about n^2 pairings. On the negative side, we show that any outsourced database protocol for range queries that leaks either the access pattern or the communication volume exactly is subject to ``reconstruction attacks'' where the untrusted server learns the confidential attribute values after polynomially-many queries in the domain size. This motivates the search for different ways of using tools like ORE in outsourced database protocols than existing work. Based on joint works with David Cash (Rutgers), Feng-Hao Liu (Florida Atlantic University), Cong Zhang (Rutgers), Kobbi Nissim (Georgetown), George Kellaris (Harvard), and George Kollios (Boston University).

Prof Adam O'Neill

Adam O'Neill is an Assistant Professor of Computer Science at Georgetown University in Washington, DC. He received a B.A. in Computer Science and Mathematics from the University of California at San Diego in 2005 and a Ph.D. in Computer Science from the Georgia Institute of Technology in 2010. His research interests are in cryptography.