PTreeB: Efficient and Privacy-Preserving k-d Tree Building over Vertically Distributed Data in Cloud

Big data have witnessed a growing trend towards vertically distributed storage, with various queries on vertically organized data recognized as effective means for unlocking data's inherent value. Several solutions have emerged for enabling privacy-preserving queries on vertically distributed data using secure multi-party computation techniques. However, these approaches often involve substantial communication overheads among data owners and place significant computational burdens on them, rendering them impractical for resource-constrained data owners. Outsourcing vertically distributed queries to the cloud can substantially alleviate the computational burdens on data owners, and efficient index construction is crucial for outsourced queries on vertical data. In light of this, we present the pioneering “Privacy-Preserving k-d Tree Building” (PTreeB) scheme for vertically distributed outsourced data in this study. Our scheme begins with the development of a private random dimension choosing algorithm (PCDim) and a private equality test (PET) algorithm, leveraging additive Paillier homomorphic encryption. Subsequently, these algorithms, along with various efficiency-enhancing strategies, including pre-sorting each data owner's data and adopting a dual-key system for data privacy protection, form the foundation of our PTreeB scheme. We rigorously demonstrate the security of our scheme, and its efficiency is validated through extensive experimentation.

I. Introduction

Cloud computing has ushered in a new era for storing and managing data, especially in the realm of big data. The increasing number of privacy regulations has compelled data owners to encrypt their outsourced data to safeguard personal information against potential leaks [1], [2]. However, this encryption inevitably impacts the usefulness of the outsourced data. To address this challenge, it becomes imperative to construct indexes for the outsourced data, enabling stream-lined query processing and complex computations. When the outsourced data is owned by a single data owner, they can create indexes from the plaintext data and then outsource both the encrypted indexes and the dataset to the cloud. These indexes empower cloud servers to efficiently process queries on encrypted data, including various types like similarity and range queries. Multiple schemes [3], [4] have been proposed for building efficient query indexes suitable for retrieving ciphertexts. Unfortunately, the prerequisite for developing such indexes is the central storage of data.