Searching Encrypted Data Without Decrypting It

How to index and search encrypted content using character bigrams, CRC32 hashing, and a secret key — no Elasticsearch required.

Imagine you store sensitive financial documents — bank statements, payment orders, IBANs — all encrypted at rest. Your users need to search this content. The naive solution is to decrypt everything on every query, but that’s slow, insecure, and doesn’t scale. The other extreme is storing a plaintext search index, which defeats the purpose of encryption.

There’s a middle ground: ngram-based search with deterministic hashing. You split the text into overlapping character pairs (bigrams), hash each one with a secret key, and store only the hashes alongside your encrypted data. Queries work by hashing the search term the same way and matching against stored hashes. The plaintext never appears on disk.

The Core Idea

An ngram is a contiguous sequence of n items from a text. For search, 2-grams (bigrams) hit a sweet spot — small enough to produce partial matches, specific enough to avoid excessive false positives.

Hash each bigram with a secret key: hash = crc32(bigram . secret_key)

CRC32 is a 32-bit non-cryptographic hash. Combined with a secret key, it becomes a deterministic one-way salted hash. The result is an integer you can store and index in a database — no plaintext ever persists.

Search follows the same hashing process as indexing:

1. Hash the search query using the same NgramStack and secret key.
2. Count how many of the query’s ngram hashes appear in the entity’s index.
3. Require all query ngrams to match — exact count equality.

This approach was built for storing banking data retrieved via the EBICS API Client.

Lessons Learned

Set a maximum query length. Bigram search degrades with very long queries — hundreds of bigrams produce slow COUNT queries. A 40-character limit is a sensible practical cap.

CRC32 collisions are rare but real. With a 32-bit hash space (~4 billion values), collisions between different bigrams in the same document are improbable. For this use case it’s acceptable; for hash-sensitive applications, use a longer hash.

CRC32 is not a cryptographic hash. A determined attacker who obtains the secret key could build a rainbow table of common bigrams in finite time. For high-security environments, consider HMAC-SHA256 truncated to a fixed width instead.