How to Perform Fuzzy Searches on Encrypted Data: Practical Methods and Pitfalls

How to Perform Fuzzy Searches on Encrypted Data

Encrypted data is not naturally friendly to fuzzy queries. This article explores the problem and presents several implementation ideas to inspire developers.

Silly Approaches

Load all data into memory, decrypt it, and perform fuzzy matching in the application.

Create a plaintext mapping table (a tag table) for ciphertext and query the tag to associate ciphertext with plaintext.

Silly Approach 1

Decrypting all records in memory works only for tiny datasets; with millions of rows it quickly leads to out‑of‑memory errors.

Silly Approach 2

Maintaining a separate plaintext mapping table defeats the purpose of encryption and introduces serious security risks.

Conventional Approaches

Implement encryption/decryption functions in the database and use decode(key) like '%partial%' for fuzzy matching.

Tokenize the plaintext, encrypt each token, store them in an extra column, and query with key like '%partial%'.

Conventional Approach 1

Decrypting data inside the query allows a low‑cost implementation but cannot use indexes and may suffer from algorithm mismatches between application and database.

Conventional Approach 2

Split the field into fixed‑length groups (e.g., four English characters or two Chinese characters), encrypt each group, and store the ciphertext tokens. Queries search the encrypted tokens with a like pattern. This method increases storage size (e.g., DES encryption expands a 11‑byte phone number to 24 bytes, a 2.18× growth) but enables index usage.

It requires the fuzzy search term to be at least four English characters or two Chinese characters; shorter terms are not recommended due to token explosion.

Advanced (Super‑God) Approaches

These solutions consider algorithmic design, sometimes inventing new schemes to support fuzzy matching on ciphertext without excessive length growth. Examples include:

Hill cipher‑based fuzzy matching ( FMES).

Bloom‑filter‑enhanced encrypted fuzzy search.

Encrypted search in cloud storage with verifiable queries.

Lucene‑style tokenization applied to encrypted fields in relational databases or Elasticsearch.

Such methods often require deep expertise in cryptography and may involve custom algorithms.

Conclusion

Naïve methods are discouraged; conventional approaches—especially the token‑based method—offer a practical balance of security, storage cost, and query performance. When specialized algorithmic talent is available, advanced designs can be explored for optimal results.