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, though with important trade-offs.

Supported Query Types

Equality Queries

Check if encrypted value matches encrypted query:

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

Range Queries

Using comparison circuits (TFHE excels here):

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

Aggregations

Sum, average, count on encrypted values:

// Encrypted aggregation
SELECT SUM(encrypted_amount) FROM transactions
// Returns encrypted sum

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

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;
  }
}

Performance Reality

Encrypted database operations are slower:

• Simple equality check: Milliseconds per record
• Range comparison: 10s of milliseconds per record
• Aggregation: Depends on operation count

Strategies to improve performance:

• Pre-filtering with less secure but faster methods
• Parallel query execution
• Hardware acceleration
• Careful index design

Use Cases

FHE databases work well for:

• Medical records with privacy requirements
• Financial data aggregation across institutions
• Identity verification without storing plaintext
• Secure data warehousing

Encrypted databases are an active research area with rapid progress. Today's implementations handle many practical workloads, and performance continues to improve.