Secure Dynamic Skyline Queries Using Result Materialization
Secure Dynamic Skyline Queries Using Result Materialization
复制标题
DOI：
10.1109/icde51399.2021.00021
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Sepanta Zeighami;G. Ghinita;C. Shahabi
中科院分区：
文献类型：
--
作者：
Sepanta Zeighami;G. Ghinita;C. Shahabi
天际线计算是一种越来越流行的查询，具有广泛的适用性，许多领域。考虑到数据库外包的趋势，以及数据的敏感性（例如，在医疗保健中），必须评估加密数据集上的天际线。研究工作承认安全的天际线计算的重要性，但现有的解决方案有几个缺点：（i）它们只提供ad-hoc安全性;（ii）它们是昂贵的;或（iii）它们依赖于假设，如协议中存在多个非共谋方。受安全最近邻解决方案的启发，我们推测计算天际线的一种安全有效的方法是通过结果物化。然而，由于空间需求大，具体化对于天际线查询更具挑战性。我们表明，预计算的天际线的结果，同时最大限度地减少存储开销是NP-难的，我们提供了更有效地解决这个问题，同时保持存储在合理的水平。我们的算法是新颖的，也适用于定期的天际线计算，但我们专注于加密的设置，物化减少天际线查询的响应时间从几个小时到几秒钟。大量的实验表明，我们显然优于现有的工作在性能方面，我们的安全分析证明，我们得到一个小的（和可量化的）数据泄漏。
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.