  Motivated by cloud security concerns, there is an increasing interest in
database systems that can store and support queries over encrypted data. A
common architecture for such systems is to use a trusted component such as a
cryptographic co-processor for query processing that is used to securely
decrypt data and perform computations in plaintext. The trusted component has
limited memory, so most of the (input and intermediate) data is kept encrypted
in an untrusted storage and moved to the trusted component on ``demand.''
  In this setting, even with strong encryption, the data access pattern from
untrusted storage has the potential to reveal sensitive information; indeed,
all existing systems that use a trusted component for query processing over
encrypted data have this vulnerability. In this paper, we undertake the first
formal study of secure query processing, where an adversary having full
knowledge of the query (text) and observing the query execution learns nothing
about the underlying database other than the result size of the query on the
database. We introduce a simpler notion, oblivious query processing, and show
formally that a query admits secure query processing iff it admits oblivious
query processing. We present oblivious query processing algorithms for a rich
class of database queries involving selections, joins, grouping and
aggregation. For queries not handled by our algorithms, we provide some initial
evidence that designing oblivious (and therefore secure) algorithms would be
hard via reductions from two simple, well-studied problems that are generally
believed to be hard. Our study of oblivious query processing also reveals
interesting connections to database join theory.
