How to Perform Fuzzy Searches on Encrypted Data: Strategies and Trade‑offs

Preface

Encrypted data is not friendly to fuzzy queries; this article explores how to enable fuzzy search on encrypted fields and shares implementation ideas.

During development we often encrypt sensitive data such as passwords, phone numbers, addresses, and bank details. While passwords use irreversible hash functions, other data like phone numbers need reversible encryption and fuzzy search capability.

We categorize three broad approaches for fuzzy searching encrypted data.

How to Perform Fuzzy Queries on Encrypted Data

We identified three main categories:

Naïve ("bad") approaches that ignore proper design.

Conventional approaches that balance performance and storage.

Advanced approaches that consider algorithmic innovations.

Naïve Approaches

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

Create a plaintext mapping table (tag table) for encrypted values and query the tag table.

Naïve Approach 1

Decrypting all records in memory works only for very small datasets; larger volumes quickly cause out‑of‑memory failures.

Example: using DES, the plaintext 13800138000 encrypts to HE9T75xNx6c5yLmS5l4r6Q==, which occupies 24 bytes—over twice the original size.

For datasets of hundreds of megabytes or more, this method is impractical.

Naïve Approach 2

Maintaining a plaintext mapping table defeats the purpose of encryption and introduces severe security risks; therefore it is strongly discouraged.

Conventional Approaches

These are the most widely used methods that balance security and queryability.

Conventional Approach 1

Implement the same encryption/decryption functions in the database and modify fuzzy query conditions to decrypt before applying LIKE '%partial%'. This is easy to adopt but cannot leverage indexes and may suffer from algorithm mismatches between application and database.

Suitable when performance requirements are modest and standard algorithms like AES or DES are acceptable.

Conventional Approach 2

Tokenize the plaintext into fixed‑length segments (e.g., 4 English characters or 2 Chinese characters), encrypt each token, and store them in an auxiliary column. Queries use LIKE '%partial%' on the encrypted tokens.

ningyu1 → tokens: ning , ingy , ngyu , gyu1 … each token is encrypted separately.

Encryption typically expands data size (e.g., DES expands 11‑byte input to 24‑byte ciphertext, a 2.18× increase). The method works well when the fuzzy term length is at least 4 English characters or 2 Chinese characters; shorter terms increase storage overhead and reduce security.

Several e‑commerce platforms (Taobao, Alibaba, Pinduoduo, JD) use similar schemes.

Advanced Approaches

These involve algorithmic research, such as designing new encryption schemes that preserve order or using Bloom filters to enable fuzzy matching without excessive ciphertext growth.

Hill cipher‑based fuzzy matching (FMES).

Bloom‑filter‑enhanced encrypted text search.

Fast query‑supporting encrypted databases.

Lucene‑based encrypted search on cloud storage.

These solutions often require custom algorithm development and deep expertise.

Conclusion

Naïve methods should be avoided; conventional approaches—especially the token‑based method—offer a practical balance of security, performance, and storage cost. Advanced algorithmic solutions are worth exploring when specialized expertise is available.