Boston University
Differentially oblivious outsourced databases: from theory to practice
Abstract
dc:description.abstractThe migration of organizational data to public clouds represents a paradigm shift in resource management, offering cost-effective solutions while raising critical concerns about data security and privacy, particularly for sensitive workloads such as financial transactions and medical records. Although cloud providers offer various security primitives for end-to-end data protection, data processing on the server remains vulnerable to side-channel attacks. Honest-but-curious adversaries, such as the cloud server, can infer sensitive information by analyzing a program's execution transcript, including access patterns (the physical addresses accessed) and communication volumes (the lengths of messages exchanged), even when strong encryption is in place. Oblivious query evaluation has emerged as a promising approach to mitigating such side-channel attacks in encrypted database outsourcing. Differential Obliviousness (DO) requires the execution transcripts to satisfy differential privacy (DP), which enables meaningful processing of the data in the cloud and quantifiable privacy loss. In this dissertation, we introduce data management frameworks designed for static and dynamic data that provide DO guarantees against honest-but-curious adversaries. The framework for static data, leveraging Trusted Execution Environments (TEE) or Secure Multi-Party Computation (MPC) as the underlying security primitive, introduces a comprehensive suite of DO analytical query processing algorithms, built upon novel constructions of Private Data Structures within the atomic DP storage model. The framework offers three key benefits: (1) Bounded privacy loss—enabling efficient query processing, including complex queries such as select-joins and multi-way joins, while maintaining strict privacy guarantees. (2) Lossless processing—ensuring exact responses for non-aggregate queries without data omissions. (3) Nontrivial utility—allowing straightforward implementation of all strategies while achieving a satisfactory trade-off among runtime, storage, and communication volume. The framework for dynamic data extends these capabilities and enables efficient handling of inserts and deletes through adaptive oblivious storage that can dynamically adjust its capacity based on workload demands. Our work represents a step forward toward realizing seamless migration to privacy-preserving outsourced databases.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- doctoral
- Discipline thesis:degree_discipline
- Computer Science
- Grantor
- Boston University
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Qiu, Lina
- Advisor dc:contributor.advisor
-
- Kollios, George
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/53346