PhD Dissertation Proposal 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 query processing over encrypted data. Despite substantial progress, existing EDB systems face two key challenges: (1) Practicality constraints: stronger security often comes at the cost of performance. For instance, oblivious query processing suffers from significant performance bottlenecks that hinder its real-world applicability. (2) Limited functionality: many EDBs only support basic query types and are inadequate for more expressive yet common database operations, such as conjunctive queries and approximate nearest neighbor (ANN) search. This dissertation addresses these challenges through the following contributions:
For obliviousness, we first propose a new construction for recursive ORAM that eliminates the large position map requirement of Path ORAM. In contrast to the SOTA Freecursive, which incurs a costly reset phase that leaks access patterns, our construction introduces a de-amortized reset mechanism that ensures uniform performance and stronger security. It also achieves a superior compression ratio. Second, we present a novel framework that combines an oblivious hash table with an oblivious search tree to construct a more efficient oblivious map (OMAP). Third, we introduce a technique called "delayed meta blocks" to enable efficient processing of oblivious graph queries.
For expressive queries, we first demonstrate how access-controlled inner-product functional encryption (ACIPFE) can be used to construct a secure outsourced approximate nearest neighbor (ANN) search system, and we introduce a new ACIPFE scheme that improves performance over prior work. Next, we develop composable functional encryption schemes that efficiently support multiple expressive queries simultaneously, such as equi-joins and column summations checked against a specific value.
Collectively, these contributions advance the state of encrypted databases by improving the efficiency of oblivious access mechanisms and broadening the scope of supported secure queries. All proposed constructions are implemented and released as well-tested and documented open-source libraries.
Advisor
Adam O'Neill