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

TLDR

Database outsourcing and privacy regulations have spurred interest in secure database services, yet existing encryption‑based solutions impose significant query‑processing overhead. The authors propose a distributed architecture that lets an organization outsource data management to two untrusted servers while maintaining data privacy. By partitioning data across the two servers, the system ensures that no single server holds privacy‑breaching information and enables efficient query optimization and execution. The architecture achieves efficient query processing with privacy guarantees, though it introduces new challenges in designing the database schema.

Abstract

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, distributed architecture that allows an organization to outsource its data management to {\em two} untrusted servers while preserving data privacy. We show how the presence of two servers enables efficient 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 architecture, and discuss new challenges that emerge in designing the database schema.