Privacy-Conscious Query Authentication for Outsourced and Cloud Databases

Data outsourcing and database-as-a-service (DaaS) have been gaining tremendous popularity over the recent years, and are forecasted to experience another boom with emerging cloud database solutions from Amazon SimpleDB, Google BigTable, Oracle via AWS, Microsoft SQL Azure. However, delegating data and service to a third party always inherits security harassment. Besides losing data security, the compromised server also puts the querying client in jeopardy – the compromised server may tamper the answer and mislead the client. To address this, the research community proposed a stream of solutions, collectively called query authentication. In these solutions, the data owner publishes not only the data, but also signed endorsements of all data being published. Given a query, the querying client should receive both the query results and a verification proof that can be used to reconstruct the endorsements and thus verify the correctness of results.

All existing works in the literature assume that during the verification process, the client can always be trusted and entitled to receive data values on the querying attribute(s). However, this severely jeopardizes the privacy of the data owner. For example, an Employees table contains a sensitive field “salary” whose values should be hidden from the client. The data owner grants the “selection”, but not the “projection” privilege of this field. Thus, the client can query the relationship between age and salary as in “SELECT age FROM Employees WHERE salary > $40000 and salary < $80000” without knowing the salary of any employee. However, with query authentication in effect, this privacy no longer holds as existing methods require the server to disclose to the client some “salary” values.

In this project, we study the new authentication problem arising in the above privacy- conscious query model where the querying attribute(s) are unavailable to the client. This model reflects the reality of business where data are either private assets of the owner or concern third-party privacy as in the above example. While this model invalidates existing authentication methods, it brings us opportunities to explore query authentication from a whole new angle. We will comprehensively design new data structures and protocols for a variety of data types and query types. For real-time and interactive queries, we will also seek new mechanism that trades authenticity for efficiency. We believe this project will benefit the research community, the outsourcing database industry, and Hong Kong society who shows strong concerns in recent privacy incidents.