Two Can Keep a Secret: A Distributed Architecture for Secure Database Services

Recent trends towards database outsourcing, as well as concerns and laws governing data privacy, have led to great interest in enabling secure database services. Previous approaches to enabling such a service have been based on data encryption, causing a large overhead in query processing. We propose a new, dis- tributed architecture that allows an organiza- tion to outsource its data management to two untrusted servers while preserving data pri- vacy. We show how the presence of two servers enables e cient partitioning of data so that the contents at any one server are guaranteed not to breach data privacy. We show how to optimize and execute queries in this architec- ture, and discuss new challenges that emerge in designing the database schema.