HEDA: Multi-Attribute Unbounded Aggregation over Homomorphically Encrypted Database

Recent years have witnessed the rapid development of the encrypted database, due to the increasing number of data privacy breaches and the corresponding laws and regulations that caused millions of dollars in loss. These encrypted databases may rely on different techniques, such as cryptographic primitives and trusted execution environments. In this work, we investigate the feasibility of utilizing fully homomorphic encryption (FHE) to support unbounded database aggregation queries, which typically involve comparisons as filtering predicates and a final aggregation. These operators are theoretically supported by FHE, but need careful algorithm design to maximize the efficiency and have not been explored before. We creatively use two types of FHE schemes, i.e., one for numerical and one for binary value, to enjoy their advantages respectively. To bridge the encrypted values between these two schemes for seamless query processing without client-server interaction, we propose a novel ciphertext transformation mechanism, which is of independent research interest, to close this gap. We further implement our system and test it over three TPC-H queries and a query over a real social media e-commerce database. Evaluation results show that, to process an aggregation query over 8𝑘 encrypted rows takes about 430 seconds. Although it is slower than plaintext processing in magnitudes and still has much room for improvement, as the very first work in this domain, our system demonstrates the feasibility of using FHE to process OLAP queries.