Exploration of efficient and privacy-preserving skyline queries in cloud

Thumbnail Image



Journal Title

Journal ISSN

Volume Title


University of New Brunswick


As an important multi-criteria analysis with diverse applications in practice, skyline queries have attracted considerable interest in academic and industrial communities, demonstrating strong promise in various domains. Meanwhile, in the big data era, the growing data volume drives data owners to outsource their data to the cloud to reap economic benefits. However, privacy concerns compel the outsourced data and query requests to be encrypted and require performing skyline queries over encrypted data. Unfortunately, it inevitably lowers data utility and query efficiency. In some cases, even if encryption techniques are employed, an adversary can still infer the plaintexts by collecting the leaked information. Consequently, it is a challenging but interesting topic to explore efficient and privacy-preserving skyline query schemes. In this dissertation, we will focus on the practical and widely used skyline queries and explore how to design their privacy-preserving versions while ensuring efficiency. Specifically, the major contributions of the dissertation can be summarized as i) we propose an efficient and privacy-preserving dynamic skyline query scheme by employing symmetric homomorphic encryption, which outperforms the state-of-the-art scheme by two orders of magnitude in computational costs and at least 8.1× in the communication overhead; ii) based on the arithmetic secret sharing technique, we propose a new privacy-preserving dynamic skyline query scheme, termed PPsky, which can reduce the computational costs in the data outsourcing phase and address the key management issue of the previous work; iii) we propose a novel efficient and privacy-preserving interval skyline query scheme over encrypted time series data. The proposed scheme can effectively address the challenges posed by time series data, including the high dimension problem and continuous update problem; iv) we propose a privacy-preserving user-defined skyline query scheme with the single-server model, which is an order of magnitude more efficient than the existing scheme and does not have additional communications; v) we propose the first privacy-preserving reverse skyline query scheme on the single-server model and further design a communication-efficient version without sacrificing security. Finally, we formally analyze the security of all proposed privacy-preserving skyline query schemes in the dissertation and conduct extensive experiments to validate their efficiency.