blindindex
Keyed blind indexes for equality search over encrypted columns, in the
tradition of CipherSweet and
ankane/blind_index: a column stored
encrypted can still be looked up by equality, because each row also stores a
keyed hash — the blind index — of the value. Pure Louise, over
std/crypto's HMAC-SHA-256.
import blindindex
// Once, from a high-entropy root key kept out of the database:
let key = blindindex.derive_key root_key "users" "email"
// On write, store this next to the encrypted column; on lookup, compute it
// from the query and match on it:
blindindex.make ~length: 16 key (blindindex.normalize " Ada@Example.COM ")
API
make ~length: n key value | the index: HMAC-SHA-256 of the already normalized value, truncated to n bytes (1–32, always explicit — n sets the collision rate, so it is never a default) |
derive_key root table column | the (table, column) pair's own 32-byte key, HKDF-expand (RFC 5869) over HMAC-SHA-256 from the root key |
normalize value | trim then lowercase |
normalize_with transforms value | a chain of Transforms of your own |
trim (), lowercase () | the stock Transforms |
full_length () | 32, the untruncated HMAC length |
The leakage model, stated bluntly
A blind index is a deterministic keyed hash in a column anyone with read access can see. That buys equality search and costs exactly this:
- Equality leakage. The index shows which rows share a value, without the key, without any attack. If rows 4, 9, and 31 index alike, their values are alike. Schema design must assume this is public.
- Frequency analysis. The index shows how often each value occurs. When the column's distribution is known — last names, postcodes, diagnoses — the most common index value is the most common plaintext, and so on down. No key needed. This is the attack that actually kills blind-index schemes on low-entropy columns, and truncation only dulls it.
- Guess confirmation. HMAC is fast. Anyone who has the key (or is the server) can index candidate values and match them: a low-entropy field (names, dates of birth, SSNs) is enumerable, so the index confirms guesses at machine speed. Never index a field whose equality is secret — passwords, tokens, answers to security questions. Those get password hashing (argon2), not a blind index.
- Access patterns. Watch which rows a lookup touches and you learn the queried value's equality class. Indexes do not hide access patterns.
Truncation is the deliberate knob: fewer bytes means more distinct values collide into one index entry, so the frequency signal coarsens — and your application gets false-positive rows it must filter after decryption. Approximate row counts at which a collision becomes likely (birthday bound, 50% at ~1.18·2^(bits/2)):
| truncation | collisions likely around |
|---|---|
| 2 bytes (16 bits) | 300 rows |
| 4 bytes (32 bits) | 77,000 rows |
| 8 bytes (64 bits) | 5 × 10⁹ rows |
| 16 bytes (128 bits) | 2.6 × 10¹⁹ rows |
Pick the shortest truncation whose false-positive rate the table size can absorb; 16 bytes is effectively collision-free for any real table, 4–8 bytes buys meaningful ambiguity on small ones.
Key management: the root key is a secret, high-entropy 32 bytes
(random.bytes 32), stored with the application's other secrets, not in
the database. derive_key separates columns, so leaking one index key does
not compound — but the root key is everything: rotating it means
re-indexing every column, and losing it means rebuilding them from the
decrypted data.
Normalization
normalize trims (Unicode whitespace) and lowercases ASCII only:
std/string has no Unicode case folding and no NFC normalization, so "É"
does not fold to "é" and "café" in its two Unicode spellings indexes as
two distinct values. If a column needs more, compose it with
normalize_with and apply it identically on write and on lookup — a
mismatch silently makes rows unfindable, which is worse than a collision.
Tests
Known-answer vectors (RFC 4231 for the HMAC, RFC 5869 HKDF-expand for key
derivation), determinism, key separation, truncation length and prefix
properties — the last via gen (a dev-dependency, ADR 0064):
louise test --locked && louise test --native --locked