How to Perform Fuzzy Searches on Encrypted Data Without Breaking Security

When sensitive information such as passwords, phone numbers, or bank details is stored encrypted, traditional fuzzy search becomes difficult. This article explores how to support fuzzy queries on reversible encrypted data while preserving security.

Classification of Methods

The author groups solutions into three categories:

Naïve approaches that ignore performance and security trade‑offs.

Conventional approaches that balance query speed, storage overhead, and security.

Advanced ("super‑god") approaches that redesign algorithms to enable efficient fuzzy matching on ciphertext.

Naïve Approaches

Approach 1: Load all records into memory, decrypt them, and perform fuzzy matching in application code. This works only for very small datasets; memory consumption grows quickly. For example, encrypting the phone number 13800138000 with DES yields a 24‑byte ciphertext. A table of record counts shows that 1 million rows require about 23 MB, 10 million rows about 229 MB, and 100 million rows exceed 2 GB, leading to out‑of‑memory failures.

Approach 2: Maintain a separate plaintext‑to‑ciphertext mapping table (a "tag" table) and perform fuzzy searches on the tag values. This defeats the purpose of encryption because the plaintext mapping is stored alongside the ciphertext, exposing the data.

Conventional Approaches

These methods are widely used and provide a reasonable trade‑off between security and query performance.

Method 1: Implement the same encryption/decryption algorithm inside the database and modify the fuzzy condition to decode(key) LIKE '%partial%'. This requires low development effort but cannot leverage indexes and may suffer from algorithm mismatches between application and database.

Method 2: Tokenize the plaintext into fixed‑length segments (e.g., four English characters or two Chinese characters), encrypt each token, and store them in an auxiliary column. Queries use key LIKE '%partial%' on the encrypted tokens. The storage overhead depends on the encryption algorithm; for DES, a 11‑byte plaintext becomes a 24‑byte ciphertext, a 2.18× increase.

This method works well when the fuzzy token length is at least four alphanumeric characters or two Chinese characters; shorter tokens cause excessive token explosion and higher storage costs.

Advanced (Algorithm‑Level) Approaches

These solutions require deep algorithmic research and may involve designing new encryption schemes that preserve order or enable direct ciphertext fuzzy matching. Examples from the literature include:

Hill cipher‑based fuzzy matching.

FMES (Fuzzy Matching Encryption Scheme).

Bloom‑filter‑enhanced encrypted text search.

Encrypted search support in databases and search engines such as Lucene or Elasticsearch.

Such approaches aim to keep ciphertext length growth minimal while allowing efficient fuzzy queries, but they typically need custom implementation and expertise.

Conclusion

Among the three categories, the second conventional method (tokenization with encrypted tokens) offers the best balance of implementation complexity, storage overhead, and query performance for most practical scenarios. Naïve methods should be avoided for anything beyond tiny datasets, and advanced algorithmic solutions are recommended only when specialized security requirements justify the additional development effort.