Efficient privacy-preserving data merging and skyline computation over multi-source encrypted data

Efficient data merging from the significant amount of data routinely collected from various data sources is crucial in the uncovering of relevant and key information of interest (e.g., skyline). There are, however, privacy considerations during data merging and skyline operations, particularly when dealing with sensitive data (e.g., healthcare data). Existing focuses on data merging and skyline computation either do not (fully) consider data privacy or have low efficiency. Thus, in this paper, we aim to address both privacy and efficiency during data merging and skyline computations over multi-source encrypted data. Specifically, we integrate the leftist tree with public key encryption and index based skyline computation to achieve data merging and skyline computation over encrypted data. First, we design a non-interactive data comparison protocol using public key encryption technique. This allows us to compare encrypted and outsourced data under a single cloud server instead of two non-colluding cloud servers in previous studies. Then, we combine the leftist tree with public key encryption to achieve privacy-preserving data merging with high efficiency, namely, O(log(2)(n(1) + n(2))) computational complexity for merging two leftist trees of sizes n(1) and n(2). Third, we present an index and leftist tree based skyline computation algorithm, which can efficiently perform skyline query over the merged encrypted data. Then, detailed security analysis and performance evaluation demonstrate that our scheme is both secure and efficient for data merging and skyline computation. (C) 2019 Elsevier Inc. All rights reserved.