Skip to content
Book Open access

HerreDB: An Encrypted Database Supporting Multi-Result Rapid Retrieval Based on Fully Homomorphic Encryption (FHE)

Nov 2026 · Proceedings of the 14th Workshop on Encrypted Computing & Applied Homomorphic Cryptography · 0 citations · 12 references

Abstract

Fully homomorphic encryption (FHE) enables computation on encrypted data and provides a foundation for protecting outsourced databases. FHE-based databases can evaluate queries without decrypting stored data, but query processing and JOIN operations still incur substantial computation and retrieval overhead. We present HerreDB, an encrypted database framework that uses CKKS and a structured ciphertext-table format to support basic database operations and SQL-style query processing. To improve SELECT processing, HerreDB combines low-depth ciphertext computations with power sums and an algebraic recurrence based on Newton's identities, enabling the client to recover multiple matching record identifiers and retrieve the corresponding records. For JOIN, CKKS packing, extended and cyclic padding, and ciphertext rotations organize record pairs into batches, reducing the number of ciphertext comparisons and additional vector constructions. The framework also provides ciphertext comparison and aggregation operators. Under the tested parameter settings, HerreDB completes TPC-H Query 6 on 16,000 rows in approximately 47 seconds. These results support further optimization of query processing in FHE-based encrypted databases.

Read PDF

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.