Efficient, Locally-Enforceable Querier Privacy for Distributed Database Systems

Traditionally, the declarative nature of SQL is viewed as a major strength. It allows database users to simply describe what they want to retrieve without worrying about how the answer to their question is actually computed. However, in a decentralized setting, two different approaches to evaluating the same query may reveal vastly different information about the query being asked (and, hence, about the user) to participating servers. In the case that a user's query contains sensitive or private information, this is clearly problematic. In this dissertation, we address the problem of protecting query issuer privacy. We hypothesize that by extending SQL to allow for declarative specification of constraints on the attributes of query evaluation plans and accounting for such constraints during query optimization, users can produce efficient query evaluation plans that protect the private intensional regions of their queries without explicit server-side support. Towards supporting this hypothesis, we formalize a notion of intensional query privacy that we call (I, A)-privacy, and present PASQL, a set of extensions to SQL that allows users to specify (I, A)-privacy constraints to a query optimizer. We explore tradeoffs between the expressiveness of several PASQL variants, optimization time requirements, and the optimality of plans produced. We present two algorithms for optimizing queries with attached (I, A)-privacy constraints and formally establish their time and space complexities. We prove that one is capable of producing optimal results, though at the cost of greatly increased time and space requirements. We use the other as the basis of PAQO, our implementation of an (I, A)-privacy-aware query optimizer. We present an extensive experimental evaluation of PAQO to show that is is capable of efficiently generating plans to evaluate PASQL queries, and to confirm the results of our formal complexity analysis