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

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

TL;DR

SecSkyline is a high-performance framework designed to perform skyline queries—finding the "best" items across multiple criteria—on encrypted databases stored in the cloud. By replacing heavy, traditional encryption with lightweight additive secret sharing, the authors achieve a massive performance boost, outperforming previous state-of-the-art methods by up to 813x while maintaining strict privacy for data, queries, and access patterns.

What Problem Does This Paper Address?

In the world of big data, "skyline queries" are essential for decision-making. Imagine looking for a hotel that is both cheap and close to the beach; the "skyline" consists of all hotels that aren't strictly worse than another hotel in both price and distance.

When these databases are outsourced to the cloud (e.g., medical or financial records), they must be encrypted. However, performing a skyline query on encrypted data is notoriously difficult. Previous solutions relied on "heavy" cryptographic tools like Paillier encryption or Fully Homomorphic Encryption (FHE), which are computationally expensive. These older methods could take over 1,000 seconds just to process a tiny dataset of 1,000 records. Furthermore, simply hiding the data values isn't enough; an attacker could still learn sensitive information by observing which records are compared or which ones are returned (known as access patterns).

Methods

SecSkyline moves away from heavy encryption in favor of Additive Secret Sharing. In this model, data is split into two "shares" and distributed between two non-colluding cloud servers. Neither server can see the original data, but they can perform mathematical operations by communicating with each other.

The framework introduces three novel "secure components":

  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 in the secret-shared domain efficiently.
  2. secFetch (Secure Skyline Fetching): This component allows the servers to find the minimum value in a set of shares and fetch the corresponding record without either server knowing which record was chosen.
  3. secFilt (Secure Filtering): Once a skyline point is found, it (and all points it dominates) must be "removed" so the next point can be found. Instead of deleting records—which would leak information—SecSkyline obliviously replaces their values with a system-wide maximum (vMAX), effectively "hiding" them from future rounds of the search.

Datasets

The authors evaluated SecSkyline using both synthetic and real-world data:

  • Synthetic Datasets: Correlated (CORR), Independent (INDE), and Anti-correlated (ANTI) distributions. These are standard benchmarks used to see how data clustering affects query performance.
  • Real-World Dataset: An NBA Player Statistics dataset (sourced from Kaggle). It includes six attributes (points, rebounds, assists, etc.) for approximately 2,500 players, representing a practical multi-criteria decision-making scenario.

Key Insights and Ideas

  • Lightweight Cryptography is the Key: The "aha moment" is that for outsourced databases, the two-server secret-sharing model provides a much better balance of security and speed than traditional public-key encryption.
  • Hiding the "Why" and "Where": The paper emphasizes protecting access patterns. By using oblivious fetching and filtering, the cloud servers never learn which specific tuples are part of the skyline or how many points a particular skyline tuple dominates.
  • The vMAX Strategy: The use of a "virtual delete" (overwriting with a maximum value) is a clever way to maintain a constant processing flow, ensuring that the time taken for a query doesn't leak information about the underlying data distribution.

Key Results

  • Massive Speedup: Compared to the previous best-in-class (SMSQ), SecSkyline is up to 813x faster. Compared to earlier methods (FSSP), it is over 8,130x faster.
  • Practical Latency: For a dataset of 1,000 records with 2 dimensions, SecSkyline processes a query in roughly 0.7 to 1.1 seconds. Previous methods took hundreds or thousands of seconds for the same task.
  • Scalability: The system scales well to large datasets. It can handle 600,000 records in about 15–20 seconds on a single thread, a feat that would be practically impossible with older encrypted query techniques.
  • Accuracy: The system achieves 100% accuracy, producing the exact same results as a query performed on a plaintext (unencrypted) database.

Limitations and Future Work

  • Two-Server Requirement: The security model relies on the assumption that the two cloud servers do not collude (i.e., they don't share their secret pieces of the data with each other). If they collude, the privacy is broken.
  • Dimensionality Wall: While the system scales well with the number of records ($n$), the communication cost increases significantly as the number of dimensions ($m$) grows.
  • Future Directions: The authors suggest that future work could involve exploring even more complex query types or further optimizing the communication overhead for high-dimensional data.

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 <inline-formula><tex-math notation="LaTeX">$813\times$</tex-math></inline-formula> 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},
}

Loading related content...

Figure