SecSky: A Secure Dynamic Skyline Query Scheme With Data Privacy

Jiale Zhao, Yong Ma, Jiangtao Cui, Yanguo Peng, Kangshun Li, Tengyu Wang

Abstract

Skyline computation is a critical multi-objective optimization problem. While research has focused on efficiency, security in cloud environments is often overlooked. Plaintext data in the cloud is vulnerable to leaks. Encrypting data is a solution, but performing efficient skyline queries on ciphertext remains challenging. This paper presents SecSky, a framework combining an improved B+ tree structure and symmetric encryption for secure storage. By applying pruning techniques, SecSky achieves efficient skyline queries and dynamic updates directly on encrypted data. Theoretical and simulation results demonstrate that SecSky maintains high efficiency while ensuring robust data privacy.

Introduction: The Challenge of Secure Skyline Queries

A skyline query identifies "optimal" data points in a multi-dimensional dataset where no other point is better across all dimensions. A classic example is searching for a hotel that minimizes both price and distance to the beach.

Figure 3: A visual representation of a skyline query where points P1, P2, and P5 form the skyline, as no other points dominate them in both price and distance.

As databases migrate to the cloud, executing these queries securely is paramount. Plaintext storage exposes sensitive information to potential breaches. Traditional encryption like AES prevents the cloud server from performing the necessary comparisons for skyline computation. While Homomorphic Encryption offers high security, its computational overhead is often prohibitive for real-time applications and dynamic data updates.

The SecSky Framework

SecSky addresses these challenges through a multi-layered approach involving data owners, cloud servers, and end-users.

Figure 5: The SecSky system architecture illustrating the flow of encrypted data from the owner to the cloud, and the secure query process initiated by the user.

Core Components

  1. Order-Revealing Encryption (ORE): SecSky utilizes a "left/right" ORE framework. This symmetric encryption allows the cloud server to determine the relative order of two ciphertexts (e.g., $E(x) > E(y)$) without decrypting the underlying values, enabling comparisons directly on encrypted data.
  2. Improved B+ Tree Structure: To facilitate efficient searching and dynamic updates, the standard B+ tree is modified with two-way pointers between leaf nodes. This allows the query algorithm to traverse sorted encrypted data bidirectionally.
  3. Pruning-Based Query Logic: Rather than exhaustive comparisons, SecSky employs a pruning strategy. By partitioning data based on dimensions and identifying reference points, the system can quickly discard large groups of dominated data points, significantly reducing the computational load.

Experimental Evaluation

The framework was rigorously tested using synthetic benchmarks representing different data distributions:

  • Correlated: Attributes vary together (e.g., higher quality often correlates with higher price).
  • Independent: No statistical relationship between attributes.
  • Anti-correlated: The most challenging scenario, where a "good" value in one dimension typically implies a "bad" value in another.

Experiments involved datasets of up to 9,000 records for initial queries, with an additional 8,000 records used to evaluate dynamic insertion and deletion performance.

Key Results

  • Efficiency Gains: On correlated datasets, SecSky outperformed existing models like SCALE by over two orders of magnitude.
  • Low Privacy Overhead: The performance difference between SecSky and plaintext queries was less than one order of magnitude, representing a minimal "privacy tax."
  • Robustness: SecSky maintained superior efficiency even in anti-correlated scenarios compared to previous secure schemes.

Conclusion and Future Directions

SecSky demonstrates that practical, secure, and dynamic skyline queries are achievable in cloud environments. By balancing the efficiency of ORE with optimized data structures, it provides a scalable solution for privacy-preserving multi-objective optimization. Future work will focus on parallelizing the algorithm for distributed cloud environments and exploring methods to further minimize the information leakage inherent in order-revealing encryption.

Summary updated

Abstract

Skyline computation is a typical multi-objective optimization problem and has been a hot spot for current research. Most of them have concentrated on improving the efficiency of skyline computing, while the security issues associated with executing skyline computation in the cloud server are rarely taken into account. The cloud data stored in plaintext form is attacked by hackers or malicious administrators, resulting in potential leakage of users’ private information. One of the most effective approaches to solve this problem is to encrypt the private data before storing it in the cloud server. However, how to compute the skyline on the encrypted data stored on a cloud server efficiently is still challenging. In this paper, we present a novel framework called SecSky. Firstly, the improved B+ tree structure and symmetric encryption were combined to construct a secure storage structure. Then, the pruning idea was applied to reduce unnecessary calculation and to achieve efficient skyline query and dynamic update. The whole process was directly completed on the ciphertext data. Finally, both the security and the efficiency of SecSky were analyzed through theoretical proof and simulation experiments. The results showed that our scheme is of sound efficiency on the premise of ensuring private data security.
BibTeX
@inproceedings{zhao2020secsky,
  author = {Jiale Zhao and Yong Ma and Jiangtao Cui and Yanguo Peng and Kangshun Li and Tengyu Wang},
  title = {{SecSky: A Secure Dynamic Skyline Query Scheme With Data Privacy}},
  booktitle = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.3047950},
}
Figure