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 and efficient 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: 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 an oblivious search tree to create a more efficient oblivious map for key-value stores, achieving improved asymptotic complexity and greater practical efficiency. 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.
For expressive query: We design new functional encryption schemes that support queries such as equi-joins and summing over columns to compare against specific values. These schemes enable complex queries involving multiple functionalities, while ensuring that if any subset of conditions fails, the server learns nothing beyond the fact that the query did not match. Additionally, we show how access-controlled inner-product functional encryption (ACIPFE) can be used to build a secure outsourced approximate nearest neighbor search system, and we introduce a more efficient ACIPFE construction that outperforms existing SOTA solutions.
Collectively, these contributions advance the state of encrypted databases by improving the efficiency of oblivious access mechanisms and expanding the range of supported secure queries.
Advisor
Adam O'Neill