Speedy Privacy-Preserving Skyline Queries on Outsourced Data

Supporting efficient and secure skyline query services on outsourced data remains an ongoing challenge, given the fact that existing solutions either incur significant overhead due to the underlying algorithm traversing the entire dataset or raise privacy issues when specific data structures are introduced. Motivated by addressing these limitations, this work proposes the Speedy and Privacy-Preserving Skyline Query scheme (SPSQ) to support efficient skyline queries that preserve the privacy requirements of datasets, skylines, queries, and indirect privacy with low online computational costs. SPSQ is an optimized distributed skyline diagram constructed by a novel privacy-preserving set intersection with the deduplication algorithm. Moreover, it converts the skyline queries into a lightweight polynomial-based private information retrieval for diagrams to reduce user-perceived latency. The quadrant skyline is extracted directly while the retrieval scale of the dynamic skyline is rapidly reduced by around 100 \(\times \) . We also carefully analyze its security and conduct experimental evaluations on different datasets. The results show that our SPSQ is more efficient than current works, and it is at least an order of magnitude faster in computational complexity than the state-of-the-art with the same security level.