期刊
2021 IEEE 37TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2021)
卷 -, 期 -, 页码 157-168出版社
IEEE COMPUTER SOC
DOI: 10.1109/ICDE51399.2021.00021
关键词
Skyline queries; searchable encryption
资金
- NSF [IS-1910950, IIS-1909806, CNS-2027794]
- USC Integrated Media Systems Center (IMSC)
Research recognizes the importance of secure skyline computation, but existing solutions have several shortcomings, such as high costs and reliance on assumptions like the presence of multiple non-colluding parties. A secure and efficient way to compute skylines is through result materialization, but this is more challenging for skyline queries due to large space requirements. Materialization reduces the response time of skyline queries from hours to seconds in the encrypted setting, with experiments showing improved performance and minimal data leakage.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据