Secure Acceleration of Aggregation Queries Over Homomorphically Encrypted Databases

Recent advancements in Fully Homomorphic Encryption (FHE) have significantly impacted encrypted database management, particularly in secure data querying. However, FHE poses notable performance challenges, especially in processing aggregation queries. These challenges stem from the need to homomorphically evaluate selection predicates via a linear scan over encrypted rows and from the resultant accumulation of redundant data. Overcoming these limitations necessitates innovative solutions that transcend traditional FHE optimizations. We propose a scheme, named Accelerated Homomorphically Encrypted DataBase (AHEDB), to enhance the efficiency of aggregation queries in homomorphically encrypted databases. In the scheme, we employ Encrypted Multiple Maps (EMM) to reduce the computational load inherent in homomorphic operations, thereby achieving significant improvements over existing encryption schemes. We further introduce Single Range Cover (SRC) algorithm for range and equality indexing to address potential security vulnerabilities. We implement our scheme and conduct comparative analyses with FHE-based database system. Our experiments demonstrate that our scheme offers significant advantages in querying overheads, striking a balance between security and efficiency.