PATHE: A Privacy-Preserving Database Pattern Search Platform with Homomorphic Encryption

Fully Homomorphic Encryption (FHE) enables secure computation on encrypted data without decryption, allowing a great opportunity for privacy-preserving computation. Many companies maintain extensive, high-quality databases to deliver services, making preserving data privacy during the database pattern searches crucial. With FHE, the server can take encrypted queries from clients and search through the reference database on the server without decryption, thus guaranteeing data security for all parties. While FHE provides a promising solution to data privacy, it has severe drawbacks of explosive memory requirements and excessive latency, which amplify the computational and memory inefficiencies for database search applications.

To address these, we propose PATHE that exploits FHE and hyperdimensional computing (HDC), which provides high parallelism, excellent robustness to errors, for high-performance privacy-preserving database search. On the software side, we propose an FHE-friendly PATHE algorithm that leverages efficient FHE-HDC search and a scheme-switching-based argmax to support database search and maintain comparable accuracy to the state-of-the-art. On the hardware side, PATHE proposes an efficient and scalable FHE accelerator system using Compute Express Link (CXL) for large-scale FHE database search, along with a novel, storage-aware dataflow designed to optimize memory and storage transfers for large database workloads. We evaluate PATHE on the large-scale encrypted database of protein mass spectra, PATHE achieves 2.1× speedup and 1.7× better energy efficiency compared to the baseline system.