INCHE: High-Performance Encoding for Relational Databases through Incrementally Homomorphic Encryption
This addresses the slow encryption rates that hinder database-as-a-service performance, though it is an incremental improvement over existing partially homomorphic schemes.
The paper tackles the performance bottleneck of homomorphic encryption in relational databases by proposing INCHE, an incrementally homomorphic encryption scheme that caches correlations between plaintexts to avoid expensive encryption primitives, achieving linear time complexity and verifying effectiveness on the TPC-H benchmark.
Homomorphic encryption (HE) offers data confidentiality by executing queries directly on encrypted fields in the database-as-a-service (DaaS) paradigm. While fully HE exhibits great expressiveness but prohibitive performance overhead, a better balance between flexibility and efficiency can be achieved by partially HE schemes. Performance-wise, however, the encryption rate of state-of-the-art HE schemes is still orders of magnitude lower than the I/O throughput, rendering the HE scheme the performance bottleneck. This paper proposes INCHE, an incrementally homomorphic encryption scheme, which aims to boost the performance of HE schemes by incrementally encrypting fields in relational databases. The key idea of INCHE is to explore the intrinsic correlation between plaintexts and cache them for future reuse such that expensive HE primitives from plaintexts to ciphertexts are avoided. We prove the semantic security of INCHE under the chosen-plaintext attack (CPA) model and show that its time complexity is linear in the plaintext length. We implement an INCHE prototype by extending the Symmetria cryptosystem and verify its effectiveness on both randomly-generated data and the TPC-H benchmark.