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.
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.
Core Components
- 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.
- 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.
- 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