PhD Thesis Defense: Weiqi Feng, Practical Encrypted Databases with Oblivious and Expressive Query Processing
Content
Speaker:
Abstract:
Cloud computing and rapid data growth have driven many organizations to outsource large datasets to cloud databases in order to reduce management costs. However, these datasets often contain sensitive information, necessitating encryption to ensure compliance and security. Encrypted databases (EDBs) have thus emerged as a critical technology, enabling secure and efficient query processing over encrypted data. Despite substantial progress, existing EDB systems face two key challenges. First, practicality: stronger security often reduces performance; for example, oblivious query processing suffers from significant bottlenecks that hinder its real-world applicability. Second, functionality: many EDBs support only basic queries and cannot handle more expressive yet common operations such as conjunctive queries or approximate nearest neighbor (ANN) search. This dissertation addresses these challenges through the following contributions:
Obliviousness: First, we propose a new construction for recursive oblivious RAM that reduces the number of interaction rounds between parties compared to state-of-the-art (SOTA) solutions and guarantees a de-amortized cost. Second, we introduce a novel framework that combines an oblivious hash table with oblivious search trees to create a more efficient oblivious map for key-value stores, achieving both improved asymptotic complexity and greater practical efficiency. We also develop an optimization for oblivious search trees that reduces the overhead of hiding query types. Third, we develop a technique for preserving pointer relationships during oblivious accesses and use it to build a complete system for oblivious graph query processing. All of these constructions, together with existing SOTA methods, are implemented and released as a well-tested, thoroughly documented open-source library.
Query expressiveness: We design new functional encryption schemes that support conjunctive queries, including single- and multi-value filters, column-sum checks, range queries, and equi-join queries. Our schemes enable secure composition across multiple functionalities and ensure that, if any condition fails, the server learns nothing beyond the overall non-match. We further show that access-controlled inner-product functional encryption (ACIPFE) can be used to build a secure outsourced ANN system and we present a more efficient ACIPFE construction that improves upon the prior SOTA methods.
Collectively, these contributions advance EDBs by improving the efficiency of oblivious access mechanisms and expanding the range of supported secure queries.
Advisor:
Adam O'Neill