Privacy in outsourced databases
Gene Tsudik, Einar Mykletun · 2006
Rapid advances in storage, computing and networking technologies have fueled great interest in the Software-as-a-Service model. One manifestation of this model is that of Outsourced Databases wherein organizations outsource their database management needs to dedicated, potentially untrusted, database service providers. Data are amongst organizations' most valued assets and it is essential to provide, adequate security measures to protect this stored data from both malicious outsiders and the service provider itself. Providing efficient mechanisms to ensure the privacy of data stored at database service providers is the main focus of this thesis. We consider three variations of outsourced database models, each with different levels of trust placed in the database service provider. In our first instance we assume the provider to be trusted with clients' database contents. We propose a novel database storage model optimized for encryption techniques that minimizes cryptographic overhead. In our second model the service provider is not trusted with clients' data, requiring database contents to be stored in encrypted form at all time. We build upon previous work and propose techniques for executing aggregation style queries directly over encrypted data. We also describe a cryptographic attack on a previously proposed encryption scheme aimed at facilitating such aggregation queries. Lastly, we consider an outsourced database model where the server is equipped with a tamper resistant secure coprocessor that is responsible for query execution. The coprocessors limited on-board storage capabilities forces encrypted relations to be stored at the untrusted server, creating the challenge of preventing the server from tracking and identifying tuples during query processing. We introduce privacy preserving techniques and give examples of query processing algorithms that highlight these techniques. Here too we describe an attack on a previously proposed solution that uses an outsourced database model similar to ours for secure execution of sovereign joins. This thesis provides privacy preserving solutions for various outsourced database models with distinct levels of trust in the service providers. It is our hope and wish that this work advances research in the area of security in outsourced databases, such as to bring this application model closer towards becoming a reality.