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

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.

1 Introduction

Due to the well-known benefits of cloud computing [1], [2], there has been growing popularity of enterprises or organizations leveraging commercial clouds to store and query their databases (e.g., [3], [4], [5], [6], to list a few). However, as databases may contain rich sensitive and proprietary information (like databases of medical records or financial records), deploying such database services in the cloud may raise critical privacy concerns. Therefore, there is an urgent demand that security must be embedded in such database outsourcing services, providing protection for the information-rich databases, private queries, as well as query results. In the literature, a large body of work has been presented for querying encrypted databases, which has been mostly focused on secure keyword search [7], [8], [9], [10].