Secure Dynamic Skyline Queries Using Result Materialization

Overview

Abstract

Skyline computation is an increasingly popular query, with broad applicability to many domains. Given the trend to outsource databases, and due to the sensitive nature of the data (e.g., in healthcare), it is essential to evaluate skylines on encrypted datasets. Research efforts acknowledged the importance of secure skyline computation, but existing solutions suffer from several shortcomings: (i) they only provide ad-hoc security; (ii) they are prohibitively expensive; or (iii) they rely on assumptions such as the presence of multiple non-colluding parties in the protocol. 
Inspired by solutions for secure nearest-neighbors, we conjecture that a secure and efficient way to compute skylines is through result materialization. However,  materialization is much more challenging for skylines queries due to large space requirements. We show that pre-computing skyline results while minimizing storage overhead is NP-hard, and we provide heuristics that solve the problem more efficiently, while maintaining storage at reasonable levels. Our algorithms are novel and also applicable to regular skyline computation, but we focus on the encrypted setting where materialization reduces the response time of skyline queries from hours to seconds. Extensive experiments show that we clearly outperform existing work in terms of performance, and our security analysis proves that we obtain a small (and quantifiable) data leakage.

Brief Biography

Dr. Gabriel Ghinita is an Associate Professor at University of Massachusetts, Boston. Recently, he spent his sabbatical year (2018/19) as a Visiting Associate Professor at University of Southern California. Prior to joining UMB in Fall 2011, he was a Research Associate affiliated with the Purdue Cyber Center and the Purdue Center for Education and Research in Information Assurance and Security (CERIAS).  He also held several visiting scholar appointments with Hong Kong University, City University of Hong Kong, and Nanyang Technological University, Singapore. 
Dr. Ghinita's research focuses on data security and privacy, with emphasis on protecting geospatial data. His earlier work published in ACM SIGMOD 2008 was the first to support practical nearest-neighbor queries with cryptographic-strength protection. His work on protecting location privacy received an Outstanding Paper Award at the ACM SIGSPATIAL  2009 conference, and a  Distinguished  Paper  Award  at  the  2014 ACM  Conference on Data and Application Security and Privacy (CODASPY). 
Dr. Ghinita served as Associate Editor for IEEE Transactions on Dependable and Secure Computing (TDSC) and as PC chair for the ACM Conference on Data and Application Security and Privacy (CODASPY). He serves regularly as reviewer for top journals and conferences such as IEEE TPDS, IEEE TKDE, IEEE TMC, IEEE TDSC, IEEE TIFS, ACM TODS, VLDBJ, PVLDB and IEEE ICDE.