Efficient and Privacy-Preserving Multi-Party Skyline Queries Over Encrypted Data
Xiaofeng Ding, Zuan Wang, Pan Zhou, Kim‐Kwang Raymond Choo, Hai Jin
Abstract
One existing challenge associated with large scale skyline queries on cloud services, particularly when dealing with private information such as biomedical data, is supporting multi-party queries with curious-but-honest parties on encrypted data. In addition, existing solutions designed for performing secure skyline queries incur significant communication and computation costs due to ciphertext calculation. Thus, in this paper, we demonstrate the potential of supporting privacy-preserving multi-party skyline queries on encrypted data using additive homomorphic and proxy re-encryption cryptosystems. However, the secure computation based on these cryptosystems will further slow down query efficiency. To improve the efficiency of comparison on encrypted data, we redesign two lightweight secure comparison protocols. Meanwhile, we present an efficient method named “blind-reading” to securely obtain the skyline point. We also propose a novel method, Privacy Matrix, designed to reduce the scale of the dataset so that the computational cost is significantly decreased without privacy leakage. Then, we construct our secure skyline query protocol by integrating lightweight secure comparison protocols, “blind-reading” and Privacy Matrix techniques. Finally, we evaluate the security of our protocol, where we show it is secure without leaking information. The performance evaluation also shows that our proposed approach significantly improves the efficiency (at least ×4.5 faster) compared to the-state-of-art and has the scalability of query processing under large datasets.