Encrypted Database Queries with FHE:
A Practical Implementation

Databases contain our most sensitive information, yet traditional databases require plaintext access for queries. FHE enables encrypted database queries -- search, filter, and aggregate without ever decrypting the underlying data.

The Encrypted Database Vision

Imagine a database where:

• Data is stored encrypted
• Queries execute on encrypted data
• Results return encrypted
• Database administrator sees nothing

This is possible with FHE — a technology that enables computation on encrypted data — though with important trade-offs. The fundamental insight is that Fully Homomorphic Encryption allows arbitrary computation on ciphertexts. A server holding encrypted records can evaluate query predicates, compute aggregations, and return encrypted results -- all without ever accessing a decryption key. The client who holds the secret key is the only entity that can read the final answer.

Supported Query Types

Equality Queries

Check if encrypted value matches encrypted query:

// Encrypted equality check
SELECT * FROM users WHERE encrypted_email = E(query_email)

Under the hood, an equality check between two BFV ciphertexts is computed by subtracting one from the other and testing whether the result decrypts to zero. With H33's BFV scheme at N=4096 and a single 56-bit modulus, this subtraction is a single polynomial operation -- fast enough to scan thousands of encrypted records per second.

Range Queries

Using comparison circuits (TFHE excels here):

// Encrypted range query
SELECT * FROM orders WHERE encrypted_amount > E(1000)

Range comparisons are more expensive because they require bitwise decomposition of the encrypted values and evaluation of a comparison circuit. Each bit-level operation consumes noise budget, so the depth of the circuit directly determines whether the result remains decryptable. BFV handles moderate-depth comparisons well; for deeper circuits, TFHE's bit-by-bit approach offers more flexibility at the cost of per-operation throughput.

Aggregations

Sum, average, count on encrypted values:

// Encrypted aggregation
SELECT SUM(encrypted_amount) FROM transactions
// Returns encrypted sum -- only the client can decrypt

Homomorphic addition is the cheapest FHE operation. Summing n encrypted values requires n-1 ciphertext additions, each of which adds minimal noise. This makes encrypted aggregation the most practical FHE database operation today. Averages can be computed by returning the encrypted sum alongside a plaintext count, letting the client divide after decryption.

Noise Budget: The Hidden Constraint

Every FHE ciphertext carries a noise budget that decreases with each homomorphic operation. When the budget reaches zero, decryption fails. This is the single most important constraint in designing encrypted database queries.

H33's BFV implementation uses a 56-bit modulus with N=4096, providing roughly 55 bits of noise budget after encryption. This is sufficient for several additions and a small number of multiplications -- exactly the profile needed for encrypted aggregation queries and simple predicate evaluation. For deeper computations, modulus switching (mod_switch) can reclaim budget at the cost of precision, though H33's production pipeline avoids this overhead by keeping operations shallow.

Implementation Approaches

Column-Level Encryption

Encrypt sensitive columns only:

• Non-sensitive columns remain plaintext for indexing
• Sensitive columns use FHE encryption
• Queries combine plaintext filtering with encrypted computation

This hybrid approach is the most practical path to production. A query like SELECT SUM(encrypted_salary) FROM employees WHERE department = 'engineering' filters on the plaintext department column first, reducing the set of ciphertexts that need homomorphic evaluation. The fewer encrypted operations, the faster the query and the more noise budget remains.

Order-Preserving Encryption (OPE)

For range queries on sensitive data:

• Encrypts while preserving order
• Enables efficient range queries
• Weaker security than FHE (reveals ordering)
• Consider hybrid with FHE for sensitive operations

Searchable Encryption

For keyword queries:

• Encrypted indexes enable search
• Trade-off between functionality and leakage
• Combine with FHE for secure aggregation

Architecture Example

// FHE Database Query Flow
class FHEDatabase {
  async query(encryptedQuery) {
    // Scan encrypted records
    const matches = [];
    for (const record of this.encryptedRecords) {
      // Homomorphic comparison
      const matchResult = await fhe.compare(
        record.encryptedField,
        encryptedQuery.searchValue
      );
      // matchResult is encrypted 0 or 1
      matches.push({record, matchResult});
    }

    // Client decrypts to find actual matches
    return matches;
  }
}

The key architectural insight is that the server never learns which records matched. It returns all encrypted match indicators, and only the client -- holding the secret key -- discovers the actual results. This is information-theoretically stronger than any access-pattern-leaking scheme.

Performance Reality

Encrypted database operations are slower than plaintext equivalents, but the gap is narrowing rapidly. The critical question is not "how fast is one operation" but "how many operations fit within the noise budget and latency budget of a real query."

Strategies to improve performance:

• SIMD batching -- H33 packs 32 users into a single ciphertext using BFV's slot structure (N=4096 slots divided by 128 dimensions). This amortizes the cost of every homomorphic operation across 32 independent queries.
• NTT-domain persistence -- Keeping ciphertexts in NTT form eliminates redundant forward and inverse transforms. H33's multiply_plain_ntt() path saves two full NTT transforms per multiplication.
• In-process caching -- H33's DashMap-based ZKP cache delivers 0.085 µs lookups, eliminating the TCP serialization bottleneck that crippled throughput at 96 workers.
• Hardware acceleration -- NEON-accelerated Galois operations and Montgomery-form NTT butterflies with Harvey lazy reduction keep the hot path free of integer division.

Use Cases

FHE databases work well for:

• Medical records -- Hospitals query encrypted patient data for aggregate statistics (average length of stay, treatment outcomes) without exposing individual records to the analytics engine.
• Financial data aggregation -- Multiple institutions contribute encrypted transaction data to a shared database. Regulators compute aggregate risk metrics without seeing individual positions.
• Identity verification -- Biometric templates stored as BFV ciphertexts enable encrypted matching. H33's production pipeline verifies 32 biometric templates simultaneously in a single ~1,109 µs batch operation.
• Secure data warehousing -- Cloud providers host encrypted data lakes where tenants run homomorphic queries without trusting the infrastructure provider.

The Road Ahead

Encrypted databases are an active research area with rapid progress. The combination of SIMD batching, NTT-domain optimizations, and hardware-specific acceleration has already closed much of the performance gap for addition-heavy workloads like aggregation and inner-product queries. As FHE compilers mature and hardware vendors introduce dedicated FHE instruction sets, the overhead for more complex operations -- joins, sorting, multi-depth predicates -- will continue to shrink.

Today's implementations handle many practical workloads. The path forward is not waiting for FHE to become "fast enough" -- it is designing query patterns that play to FHE's strengths: shallow circuits, batched operations, and column-level encryption that minimizes the encrypted surface area.