Searchable encryption in Rust: querying PII you can’t decrypt

Two query paths over encrypted PII: deterministic AES-SIV for exact match and dedup, a keyed blind index for substring search

Deterministic AES-256-SIV for exact match and dedup, keyed blind indexes for substring search, and an honest accounting of what each one leaks.

Encrypt a user’s email and you can’t look them up by it anymore. That’s not a bug in your crypto. That’s the crypto doing its job.

Good authenticated encryption is supposed to make two encryptions of the same plaintext look completely unrelated. AES-256-GCM with a random nonce does exactly that. It’s also why, the moment you encrypt a column, every query that filtered on it breaks. WHERE email = ? matches nothing, because the ciphertext you stored last week and the ciphertext you’d compute today share no bytes.

So you’re left with two bad options: decrypt every row to find one user, which is slow and pulls all your plaintext into application memory, or don’t encrypt the field at all.

There’s a third way, and it’s what every “encrypted but searchable” PII store is actually built on. Two pieces: deterministic encryption for exact match and dedup, and a blind index for substring search. Neither is exotic. Both leak something, and the leaks are the part nobody explains until you’re already in production. Here’s the build, in Rust, with the tradeoffs written down.

TL;DR

• Random-nonce AEAD (AES-GCM) is correct and unsearchable. That is the entire problem.
• Deterministic AES-256-SIV (RFC 5297) gives you exact-match lookup and cross-record dedup. It leaks equality: which rows hold the same value.
• A keyed blind index (tokenize, then keyed-hash) gives you substring search. Unkeyed hashing of PII is a dictionary attack waiting to happen. Key it.
• Bind field name and tenant into the associated data, so identical values don’t correlate across columns or across customers.
• Derive per-tenant keys with HKDF (RFC 5869) from a KMS-wrapped secret. Version the info string and your normalization, or future-you silently stops matching old rows.

Why the obvious approach fails

Reach for the textbook-correct primitive and you get AES-256-GCM with a fresh random 96-bit nonce per encryption. Encrypt ada@example.com twice and you get two ciphertexts with nothing in common. That is semantic security, and it is the right default for almost everything.

It is also a dead end for lookup. You can’t index it, can’t join on it, can’t GROUP BY it. The only way to answer “which user has this email” is to decrypt the column for every candidate row and compare in plaintext. At a few hundred rows, fine. At ten million, you’ve built an O(n) decrypt into your login path and dragged your entire PII set through application memory to answer one question. That’s slower and a bigger blast radius than the thing you were trying to protect.

The fix is to give up exactly one property, on purpose, for the fields you need to query: indistinguishability of equal plaintexts. Done carelessly that’s how people end up with AES-ECB and a penguin meme. Done deliberately, with the right mode, it’s a feature.

Deterministic encryption with AES-256-SIV

SIV stands for Synthetic IV, specified in RFC 5297. Instead of you supplying a random nonce, SIV derives the IV from the plaintext and the associated data with a PRF (the S2V construction over CMAC). Same key, same associated data, same plaintext gives the same synthetic IV, which gives the same ciphertext. Deterministic by construction.

The reason you want SIV specifically, and not CBC with a fixed IV or some other shortcut, is misuse resistance. With GCM, reusing a nonce is catastrophic: you leak the authentication key and open the door to forgeries. With SIV, the worst thing “nonce reuse” can do is the thing you’re asking for here, which is reveal that two identical inputs produced identical outputs. You get an AEAD that’s safe to run deterministically because it was designed for it.

use aes_siv::aead::generic_array::GenericArray;
use aes_siv::{siv::Aes256Siv, KeyInit};
/// Deterministically encrypt one field value. `aad` carries the context
/// we want bound into the ciphertext: tenant id and field name, so the
/// same value in different columns or tenants never produces the same bytes.
fn encrypt_field(key: &[u8; 64], aad: &[&[u8]], plaintext: &[u8]) -> Vec<u8> {
    let mut siv = Aes256Siv::new(GenericArray::from_slice(key));
    siv.encrypt(aad, plaintext)
        .expect("AES-SIV encryption only fails on absurd input lengths")
}
fn decrypt_field(key: &[u8; 64], aad: &[&[u8]], ciphertext: &[u8]) -> Option<Vec<u8>> {
    let mut siv = Aes256Siv::new(GenericArray::from_slice(key));
    siv.decrypt(aad, ciphertext).ok()
}

Two things worth flagging in that snippet. First, AES-256-SIV takes a 64-byte key, not 32: it splits into a 256-bit key for the S2V PRF and a 256-bit key for the CTR layer. Second, aad is a vector of byte strings, not one blob. That maps cleanly onto “this value, in this field, for this tenant,” and it matters in the next section.

Now lookup is trivial again. To find a user by email, encrypt the query value with the same key and AAD, then byte-compare against the stored column. To dedup, put a unique index on the ciphertext: two signups sharing an SSN collide on identical ciphertext, and you’ve caught it without decrypting either record. That last property is quietly the whole reason to do this. You can detect that two accounts share a value while keeping that value unreadable to your own database admins.

What deterministic encryption leaks

Equality. Anyone who can read the column learns which rows share a value, without decrypting anything. For a dedup field that’s not a leak, it’s the feature. For others it’s real: if one plaintext is ever known, every matching row is unmasked at once, and value frequencies bleed through (a common email domain, a repeated SSN).

You bound the damage with the AAD. Bind the tenant id and the field name into the associated data and the same plaintext encrypts to different ciphertext per tenant and per column. Equality is then only ever observable within one field of one customer. Never across tenants, never across columns. That discipline costs you nothing and it’s the highest-leverage decision in the whole design, so make it on day one, not after you’ve encrypted a billion rows.

Per-tenant keys: HKDF over a KMS-wrapped secret

Per-tenant keys are what make the equality leak survivable. If every tenant shares one key, deterministic ciphertext collides globally and one stolen key unmasks everyone. So each tenant gets its own.

The hierarchy: a per-tenant key in your KMS that never leaves the HSM, used to wrap a random 32-byte master secret that you store next to the tenant. At request time you decrypt the master secret once (cache it for the life of the process so you’re not calling KMS per row), then derive the actual SIV key from it with HKDF.

use hkdf::Hkdf;
use sha2::Sha256;
/// Derive the 64-byte AES-SIV key for one tenant from that tenant's
/// master secret. We never store the derived key, we recompute it.
fn derive_tenant_key(master_secret: &[u8; 32]) -> [u8; 64] {
    let hk = Hkdf::<Sha256>::new(None, master_secret);
    let mut key = [0u8; 64];
    // The info string is a version seam. Bump it to rotate the
    // derivation without rewrapping every master secret.
    hk.expand(b"pii-search/aes256-siv/v1", &mut key)
        .expect("64 is a valid HKDF-SHA256 output length");
    key
}

A salt of None is fine here because the input keying material is already a uniformly random 32 bytes; HKDF’s extract step exists to condition low-entropy or structured inputs, and we don’t have one. The info string does the work that matters: domain separation, plus a version tag you can bump to roll the key derivation forward without touching what’s in KMS. Deterministic derivation also means you don’t persist the data key anywhere; you recompute it from the secret every time, so there’s one fewer secret sitting in your database.

Substring search: the blind index

A substring search never decrypts the whole table — buckets narrow it to a handful of rows, then a plaintext recheck drops the false positives

Deterministic encryption is exact-match only. It encrypts the whole value as one atomic blob, so “find emails containing smith” can’t touch it. For that you need a second structure: a blind index.

The idea is to store, alongside the ciphertext, a set of keyed hashes of the value’s tokens. For substring search the tokens are overlapping trigrams. Normalize first so trivial formatting differences collapse: lowercase, drop non-alphanumeric characters, so John Smith, john smith, and JOHN SMITH all produce the same tokens. Hash each token with a keyed hash. To query, run the search term through the same normalize-then-trigram-then-hash path and AND-match the results.

/// Collapse trivial formatting differences before tokenizing.
fn normalize(value: &str) -> String {
    value
        .chars()
        .filter(|c| c.is_alphanumeric())
        .flat_map(|c| c.to_lowercase())
        .collect()
}
/// Overlapping trigrams of the normalized value.
fn trigrams(normalized: &str) -> impl Iterator<Item = String> + '_ {
    let chars: Vec<char> = normalized.chars().collect();
    (0..chars.len().saturating_sub(2)).map(move |i| chars[i..i + 3].iter().collect())
}
/// One blind-index term: a keyed hash, truncated into a bucket.
fn index_term(index_key: &[u8; 32], token: &str) -> u32 {
    let hash = blake3::keyed_hash(index_key, token.as_bytes());
    // Truncate to 32 bits: fewer bits => more collisions => more false
    // positives in search, but a weaker frequency signal for an attacker.
    let b = hash.as_bytes();
    u32::from_le_bytes([b[0], b[1], b[2], b[3]])
}

At query time you hash the search term’s trigrams, pull rows whose index set contains all of them, then decrypt that small candidate set and run the real substring check in plaintext to drop false positives. The index narrows the search; it doesn’t have to be exact, because the cheap decrypt at the end cleans up what the buckets let through.

What the blind index leaks

This is where most homegrown versions quietly fail, so I’ll be blunt about three things.

Unkeyed hashing of PII is a dictionary attack, full stop. Names, emails, phone numbers, and national IDs carry almost no entropy. If your index is sha256(token) with no secret, anyone who reads that column hashes a wordlist and walks straight back to the plaintext. An SSN is nine digits: the entire space is a billion values, which a laptop chews through in seconds. A keyed hash (HMAC, or blake3::keyed_hash) is the line between “encrypted at rest” and “a rainbow table with extra steps.” Key it. If you take one thing from this post, that’s the one.

Even keyed, the index leaks frequency and co-occurrence. Equal tokens produce equal terms, so an observer sees which records share trigrams and how common each term is. Over a large table that’s enough for statistical inference about the contents. The defense is the truncation in that last snippet: collapse the keyed hash into a smaller bucket space so many distinct tokens map to the same term, which blunts frequency analysis. You pay in false positives, which you were already filtering out after decryption anyway. Tune the bit width to your threat model rather than leaving it at “whatever the hash function returned.”

Normalization is now part of your cryptography, and it is permanent. The day a well-meaning teammate “improves” the normalizer to strip accents, every value indexed under the old rules stops matching. No exception is thrown. Search just silently misses rows, and you find out from a support ticket weeks later. Version your normalization exactly like you version the KDF info string, and re-index when you change it.

The shape of the whole thing

Per encrypted field you end up with two columns. One holds deterministic AES-SIV ciphertext and serves exact lookup plus dedup. The other holds a set of keyed, truncated trigram terms and serves substring search. Keys are per-tenant, derived and not stored. Context lives in the AAD. The plaintext is readable only in process memory, only for the brief candidate-set decrypt, and never by whoever has read access to the database.

What I’d tell you before you build this

• Don’t write the SIV mode yourself. Use the audited aes-siv crate. RFC 5297’s S2V construction has sharp edges, and “I implemented a cipher mode over the weekend” is how you become the cautionary example in someone else’s post.
• Key the blind index. Again, because it’s the mistake I see most.
• Bind tenant and field into the associated data from the first commit. Retrofitting domain separation across an encrypted table is a migration you do not want to schedule.
• Treat normalization and the KDF info string as versioned, breaking interfaces.
• Write down what you accepted: deterministic encryption leaks equality, the blind index leaks bucketed frequency. Those are reasonable tradeoffs for most PII, but they’re choices, and the person running your security review will ask. Have the answer ready.

None of this is novel research. It’s RFC 5297, RFC 5869, and a hash with a key. The engineering is in knowing precisely which leak you signed up for at each step. Get that right and you can hand your support team a working search box over data your own database admins can’t read.