Techniques for Performing Fuzzy Search on Encrypted Data

We often encrypt sensitive data such as passwords, phone numbers, addresses, and bank details to protect security, but encrypted values are not friendly to fuzzy queries. This article explores how to enable fuzzy search on reversible encrypted data.

How to Perform Fuzzy Search on Encrypted Data

The approaches can be divided into three categories:

Naïve methods (implemented without thoughtful design)

Conventional methods (balance performance and storage)

Advanced methods (algorithm‑level solutions)

Naïve Methods

Load all encrypted records into memory, decrypt them, and perform fuzzy matching in the application.

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

Naïve Example 1

Loading all data into memory works only for small datasets; for large volumes it can cause out‑of‑memory failures. For example, encrypting the phone number 13800138000 with DES yields a 24‑byte ciphertext HE9T75xNx6c5yLmS5l4r6Q== , which quickly scales to hundreds of megabytes or even gigabytes.

Naïve Example 2

Maintaining a plaintext mapping table defeats the purpose of encryption, exposing the data and adding unnecessary complexity.

Conventional Methods

These are the most widely used approaches that still preserve data security while supporting fuzzy queries.

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 auxiliary column, and query with key LIKE '%partial%' .

Conventional Example 1

Store the same encryption algorithm in the DB, modify the fuzzy condition to decrypt first and then apply LIKE . This is easy to implement but cannot leverage indexes and may suffer from algorithm mismatches.

Conventional Example 2

Split the field into fixed‑length tokens (e.g., 4 English characters or 2 Chinese characters), encrypt each token, and store them in an extra column. Queries use key LIKE "%partial%" . This method increases storage (ciphertext length grows, e.g., DES expands 11‑byte plaintext to 24‑byte ciphertext, a 2.18× increase) but allows index usage.

Typical e‑commerce platforms (Taobao, Pinduoduo, JD) adopt similar schemes to enable fuzzy search on encrypted user data.

Advanced Methods

These solutions are algorithm‑centric, often requiring custom designs such as Bloom‑filter‑based encrypted search, FMES, or Hill‑cipher variations. They aim to keep ciphertext orderable or searchable without excessive length growth, but demand deep cryptographic expertise.

Research on Bloom‑filter‑enhanced encrypted fuzzy search.

Fast query‑supporting encrypted databases.

Lucene‑based encrypted fuzzy search.

Summary

Naïve approaches are discouraged; conventional methods—especially the token‑based auxiliary column technique—offer a practical balance of security, storage cost, and query performance. When specialized algorithm talent is available, advanced methods can provide superior performance but require significant research effort.