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

Encrypted data is not friendly to fuzzy queries; this article explores implementation ideas for fuzzy search on encrypted data.

How to Perform Fuzzy Search on Encrypted Data

The approaches can be grouped into three categories: silly (naïve), conventional, and advanced.

Silly Approaches

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

Create a plaintext mapping table (often called a tag table) and query the tags to associate ciphertext.

Memory consumption grows quickly: about 22.9 MB for 1 million records, 228.9 MB for 10 million, and 2.29 GB for 100 million, leading to possible Out of memory errors for large datasets. The second method also breaks security by storing plaintext mappings.

Conventional Approaches

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

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

The first conventional method is easy to implement but cannot leverage indexes and may suffer from algorithm mismatches between the application and the database.

The second method splits a field into fixed‑length groups (e.g., 4 English characters or 2 Chinese characters), encrypts each group, and stores them. For example, the string ningyu1 is split into ning, ingy, ngyu, gyu1. To search for ingy, use key like "%partial%". Encryption increases length; with DES, an 11‑byte plaintext becomes a 24‑byte ciphertext (2.18× growth). This method requires the fuzzy term to be at least 4 English characters or 2 Chinese characters; shorter terms increase storage cost and reduce security.

Advanced Approaches

Design new algorithms that preserve order and allow fuzzy matching on ciphertext (e.g., decode‑preserving schemes).

Use Hill cipher and FMES‑based encrypted fuzzy matching.

Apply Bloom filter‑based encrypted fuzzy search mechanisms.

Explore databases that support fast encrypted queries.

Implement Lucene‑based cloud search on ciphertext, comparing relational DB storage with Elasticsearch.

Adopt verifiable fuzzy search encryption schemes for cloud storage.

Conclusion

Silly methods are not recommended; the second conventional method offers a good balance of cost, performance, and security, while advanced methods require specialized algorithm expertise.