TorusDB: Fully Homomorphic Encrypted Query Processing over Elliptic Curves

Abstract

We introduce TorusDB, the first database engine supporting practical SQL query processing over ciphertexts using a fully homomorphic encryption scheme derived entirely from elliptic curve cryptography. Unlike prior approaches based on lattice FHE or zero-knowledge proofs, TorusDB preserves the elliptic curve group structure and extends additive homomorphism via a formal multiplicative construction and rational extension, enabling full homomorphic evaluation without decryption. We formalize the underlying EC-based FHE scheme, prove its security under standard elliptic curve assumptions (ECDLP, DDH, BDH), and present a query execution model supporting selection, projection, aggregation, and grouping. Our implementation demonstrates that encrypted query execution incurs only 77% overhead relative to plaintext execution, marking a substantial improvement over existing homomorphic database systems which typically exhibit 10-100× overhead.