SecSkyline: Fast Privacy-Preserving Skyline Queries over Encrypted Cloud Databases

Yifeng Zheng, Weibo Wang, Songlei Wang, Xiaohua Jia, Hejiao Huang, Cong Wang

Abstract

The well-known benefits of cloud computing have spurred the popularity of database service outsourcing, where one can resort to the cloud to conveniently store and query databases. Coming with such popular trend is the threat to data privacy, as the cloud gains access to the databases and queries which may contain sensitive information, like medical or financial data. A large body of work has been presented for querying encrypted databases, which has been mostly focused on secure keyword search. In this paper, we instead focus on the support for secure skyline query processing over encrypted outsourced databases, where little work has been done. Skyline query is an advanced kind of database query which is important for multi-criteria decision-making systems and applications. We propose SecSkyline, a new system framework building on lightweight cryptography for fast privacy-preserving skyline queries. SecSkyline ambitiously provides strong protection for not only the content confidentiality of the outsourced database, the query, and the result, but also for data patterns that may incur indirect data leakages, such as dominance relationships among data points and search access patterns. Extensive experiments demonstrate that SecSkyline is substantially superior to the state-of-the-art in query latency, with up to 813$\times$ improvement.

Introduction

In the era of big data, "skyline queries" have become essential for multi-criteria decision-making. Consider a user searching for a hotel that is both inexpensive and located near the beach; the "skyline" consists of all hotels that are not strictly worse than any other hotel in both price and distance. As sensitive databases (e.g., medical or financial records) are increasingly outsourced to cloud environments, protecting the privacy of these queries is paramount.

Performing skyline queries on encrypted data is notoriously difficult. Traditional solutions often rely on "heavy" cryptographic primitives like Paillier encryption or Fully Homomorphic Encryption (FHE). While secure, these methods are computationally expensive, often taking over 1,000 seconds to process a modest dataset of 1,000 records. Furthermore, hiding data values alone is insufficient; attackers can still infer sensitive information by observing access patterns—which records are compared or returned. SecSkyline addresses these challenges by utilizing lightweight additive secret sharing, achieving a massive performance boost of up to 813x over previous state-of-the-art methods while maintaining strict privacy for data, queries, and access patterns.

System Architecture

SecSkyline moves away from heavy public-key encryption in favor of a two-server model based on Additive Secret Sharing. In this architecture, the Data Owner splits the database into two "shares" and distributes them between two non-colluding cloud servers ($C_1$ and $C_2$).

The SecSkyline framework architecture, utilizing two non-colluding cloud servers (C1 and C2) to process encrypted queries via additive secret sharing.

Neither server can independently reconstruct the original data. However, by communicating with each other using secure protocols, they can perform the mathematical operations required for skyline queries without ever seeing the plaintext values. This model provides a superior balance of security and speed compared to traditional encryption.

Methodology

The SecSkyline framework introduces three novel secure components to handle the complexities of skyline processing in the secret-shared domain:

  1. secMap (Secure Database Mapping): To find the skyline relative to a specific query point $q$, the system must calculate the absolute difference between the query and every data point. SecSkyline uses a bit-decomposition strategy and a Parallel Prefix Adder (PPA) to extract the "Most Significant Bit" of a value, allowing it to compute absolute values efficiently.
  2. secFetch (Secure Skyline Fetching): This component enables the servers to identify the minimum value in a set of shares and fetch the corresponding record obliviously. Neither server learns which specific record was chosen during this process.
  3. secFilt (Secure Filtering): Once a skyline point is identified, it (and all points it dominates) must be "removed" to find the next point. To prevent leaking information through record deletion, SecSkyline replaces dominated values with a system-wide maximum (vMAX), effectively hiding them from future search rounds.
Visualization of skyline query mapping. Original points p are transformed into t relative to query point q to facilitate distance-based dominance calculations.

Experimental Evaluation

The authors evaluated SecSkyline using both synthetic and real-world datasets. Synthetic benchmarks included Correlated (CORR), Independent (INDE), and Anti-correlated (ANTI) distributions to test how data clustering affects performance. For real-world validation, the system was tested on an NBA Player Statistics dataset containing six attributes for approximately 2,500 players.

Key Results

  • Performance: SecSkyline is up to 813x faster than the previous best-in-class (SMSQ) and over 8,130x faster than earlier methods like FSSP.
  • Latency: For a dataset of 1,000 records (2 dimensions), SecSkyline processes a query in roughly 0.7 to 1.1 seconds, whereas previous methods required hundreds or thousands of seconds.
  • Scalability: The system scales effectively, handling 600,000 records in approximately 15–20 seconds on a single thread.
  • Accuracy: The framework achieves 100% accuracy, yielding results identical to queries performed on plaintext databases.

Conclusion and Future Work

SecSkyline demonstrates that lightweight cryptography is the key to practical, privacy-preserving database outsourcing. By protecting not just the data, but also the dominance relationships and access patterns, it provides robust security for sensitive applications.

While highly efficient, the system currently relies on the assumption that the two cloud servers do not collude. Additionally, while it scales well with the number of records, communication costs increase with the number of dimensions ($m$). Future research may focus on optimizing communication overhead for high-dimensional data and extending the framework to support even more complex query types.

Summary updated

Abstract

The well-known benefits of cloud computing have spurred the popularity of database service outsourcing, where one can resort to the cloud to conveniently store and query databases. Coming with such popular trend is the threat to data privacy, as the cloud gains access to the databases and queries which may contain sensitive information, like medical or financial data. A large body of work has been presented for querying encrypted databases, which has been mostly focused on secure keyword search. In this paper, we instead focus on the support for secure skyline query processing over encrypted outsourced databases, where little work has been done. Skyline query is an advanced kind of database query which is important for multi-criteria decision-making systems and applications. We propose SecSkyline, a new system framework building on lightweight cryptography for fast privacy-preserving skyline queries. SecSkyline ambitiously provides strong protection for not only the content confidentiality of the outsourced database, the query, and the result, but also for data patterns that may incur indirect data leakages, such as dominance relationships among data points and search access patterns. Extensive experiments demonstrate that SecSkyline is substantially superior to the state-of-the-art in query latency, with up to 813$\times$ improvement.
BibTeX
@article{zheng2023secskyline,
  author = {Yifeng Zheng and Weibo Wang and Songlei Wang and Xiaohua Jia and Hejiao Huang and Cong Wang},
  title = {{SecSkyline: Fast Privacy-Preserving Skyline Queries over Encrypted Cloud Databases}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  url = {https://openreview.net/forum?id=U-cqX80dDt},
}
Figure