Back to search

Boston University

Differentially oblivious outsourced databases: from theory to practice

Abstract

dc:description.abstract

The 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 × 4

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/53346

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Qiu, Lina. Differentially oblivious outsourced databases: from theory to practice. doctoral thesis, Boston University, 2025. https://hdl.handle.net/2144/53346