Searchable encrypted databases: equality and range queries

Four different ideas often share one name

No one mechanism automatically supplies all four properties. Start with the attacker and query requirements, then choose the smallest exposure that works.

Equality search with deterministic tokens

A keyed function can map the same plaintext value to the same token. The database indexes the token and transforms a trusted query value with the same key before lookup. An attacker without the key does not directly read the plaintext, but can still observe that two rows share a value and count how often each token appears.

Low-entropy domains deserve extra caution. A Boolean, U.S. state code, or small status vocabulary leaks more through frequency than a high-entropy random identifier. Keyed tokens prevent a simple public hash dictionary, but they do not erase distribution leakage.

Range search requires more leakage

To answer price BETWEEN 50 AND 100 from encrypted index material, the database needs structure preserving enough order to identify candidates. Order-preserving encryption exposes ordering relationships by design. Depending on the scheme and data distribution, that can reveal more than equality alone.

How MongrelDB scopes searchable columns

MongrelDB encrypts sorted-run pages, encrypted-table WAL frames, and encrypted result-cache entries with AES-256-GCM. Columns marked ENCRYPTED_INDEXABLE derive a per-column key from the database key hierarchy. Equality uses HMAC-derived tokens; range queries use order-preserving tokens.

ColumnDef {
    id: 2,
    name: "account_id".into(),
    ty: TypeId::Bytes,
    flags: ColumnFlags::empty()
        .with(ColumnFlags::ENCRYPTED_INDEXABLE),
}

The page still stores an encrypted value. The extra token supplies the index lookup. Candidate rows can be narrowed before plaintext is required, avoiding a full-table decrypt-first scan for supported equality or range predicates.

Per-run statistics for encrypted columns are kept out of the cleartext directory and travel in an AES-GCM-protected statistics envelope decrypted at open. Structural headers and schema/index metadata are not all encrypted; review the documented storage inventory rather than assuming the entire directory is opaque.

Threat-model checklist

1. Name the attacker: stolen disk, untrusted database operator, compromised application user, or compromised application process.
2. List observable metadata: file sizes, schema, token frequency, ordering, access patterns, and timing.
3. Separate data-at-rest protection from query-time trust.
4. Use searchable indexing only on columns with a real lookup requirement.
5. Apply authorization before returning or ranking candidates.
6. Rotate and back up keys; test interrupted rotation and unavailable KMS behavior.
7. Measure encrypted workloads on deployment hardware.

If the application process is compromised while keys are loaded, storage encryption alone cannot prevent that process from exercising its authorized decryption path.

When not to use searchable encryption

• The field is rarely queried and can be conventionally encrypted.
• The value domain is tiny and frequency leakage is unacceptable.
• Only prefix, fuzzy, or arbitrary full-text search would satisfy the product.
• The requirement is protection from a compromised application process.
• The team cannot operate key storage, rotation, recovery, and audit controls.