Techniques for Performing Fuzzy Queries on Encrypted Data

Encrypted data is difficult to query with fuzzy matching; this article explores practical ways to enable fuzzy search on encrypted fields while preserving security.

How to Perform Fuzzy Queries on Encrypted Data

The approaches can be grouped into three categories:

Silly methods (quick‑and‑dirty implementations without proper design)

Conventional methods (balanced solutions that consider performance and storage)

Advanced methods (algorithm‑level designs for high‑end scenarios)

Silly Methods

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

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

Silly Example 1

For small datasets, loading everything into memory may work, but the memory cost grows quickly. For example, the phone number 13800138000 encrypted with DES becomes HE9T75xNx6c5yLmS5l4r6Q== , which occupies 24 bytes. Hundreds of megabytes to several gigabytes of data can cause out‑of‑memory failures.

Silly Example 2

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

Conventional Methods

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

Implement encryption/decryption functions in the database and use them in a LIKE clause, e.g., decode(key) LIKE '%partial%' .

Tokenize the plaintext, encrypt each token, store the encrypted tokens in an auxiliary column, and query with key LIKE '%partial%' .

Conventional Example 1

Store the same encryption algorithm in the DB, modify fuzzy‑search conditions to decrypt first and then apply LIKE . This is easy to implement but cannot leverage indexes, and some databases may not guarantee algorithmic consistency.

Conventional Example 2

Split the field into fixed‑length tokens (e.g., every 4 English characters or 2 Chinese characters), encrypt each token, and store them in an extra column. Queries like key LIKE '%partial%' can use indexes on the token column, improving performance at the cost of additional storage.

Typical e‑commerce platforms (Taobao, Alibaba, Pinduoduo, JD) adopt similar token‑based encrypted fuzzy‑search schemes.

This method is recommended for most scenarios because it offers a reasonable trade‑off between implementation complexity, storage overhead, and query speed.

Advanced Methods

These approaches involve deep algorithmic research, such as designing new encryption schemes that preserve order or using Bloom filters, Hill cipher‑based fuzzy encryption (FMES), or other cryptographic constructions to enable fuzzy matching directly on ciphertext.

Research paper: "A Bloom‑Filter‑Based Improved Encrypted Text Fuzzy Search Mechanism".

Study of Hill cipher handling and FMES.

Cloud‑based searchable encryption using Lucene.

These solutions require specialized expertise and are suitable when high security and performance are both critical.

Summary

The article reviewed naïve, conventional, and advanced techniques for fuzzy querying encrypted data, recommending the token‑based conventional method (Approach 2) as the most practical for most applications, while noting that advanced algorithmic solutions may be considered when specialized security requirements exist.