Honest-Majority Maliciously Secure Skyline Queries on Outsourced Data

The application of skyline queries on outsourced databases significantly aids online analysis, yet efficiently handling encrypted queries remains a formidable obstacle. Moreover, query outcomes are vulnerable to potential malicious cloud services. To circumvent these limitations, this work presents the Honest-Majority and Maliciously Skyline Query scheme (HMMSQ), which facilitates efficient skyline queries while safeguarding the privacy of datasets, queries, and skylines, as well as detecting malevolent activities. The core of HMMSQ is an optimized skyline diagram constructed by a novel skyline region-splitting algorithm for accurate skyline queries. Furthermore, it mitigates the frequency of dataset accesses by leveraging a multi-path R-tree for secure skyline retrieval. Notably, the majority of malicious behavior detection is focused on the servers, thereby minimizing user authentication overhead. The complexity and security are thoroughly analyzed, and experimental evaluations on various datasets demonstrate its efficiency and practicality in terms of computational cost and communication overhead. Remarkably, HMMSQ outperforms existing methods in query latency, achieving up to an order of magnitude improvement.