How to Enable Fuzzy Search on Encrypted Data: Methods, Pros & Cons

How to Perform Fuzzy Search on Encrypted Data

When data is stored with reversible encryption, plain‑text fuzzy matching cannot be applied directly. The solutions are grouped into three categories and their practicality is evaluated.

1. Naïve approaches

Load‑All‑In‑Memory Decryption – Decrypt every row and run a fuzzy‑match algorithm in application code. Feasible only for very small tables. Example: a DES‑encrypted phone number occupies 24 bytes; 1 M rows ≈ 22.9 MiB, 100 M rows ≈ 2.3 GiB, which quickly exceeds memory limits.

Plain‑Text Tag Table – Keep a separate clear‑text column (tag) alongside the ciphertext and query the tag. This defeats encryption because the tag stores the data in clear.

2. Conventional approaches

Database‑side decryption in the WHERE clause Store ciphertext and use a decryption function inside the query, e.g. WHERE decode(key) LIKE '%partial%' Pros: Minimal code change. Cons: Indexes cannot be used, performance degrades on large tables, and the DB must support the same algorithm as the application.

Encrypted token (tokenisation) columns Split each field into fixed‑length overlapping tokens, encrypt each token, and store them in an auxiliary column. Queries use a LIKE pattern on the encrypted token column. WHERE token_column LIKE '%partial%' Example: the plaintext ningyu1 is tokenised into ning , ingy , ngyu , gyu1 . Searching for ingy translates to an encrypted LIKE query. Pros: Index can be built on the token column, moderate storage overhead. Cons: Minimum token length (≥4 English characters or ≥2 Chinese characters) is required; shorter queries are impractical. Ciphertext size grows (DES ciphertext ≈ 2.18 × plaintext). Reference implementations from major e‑commerce platforms (plain URLs):

https://open.taobao.com/docV3.htm?docId=106213&docType=1

https://jaq-doc.alibaba.com/docs/doc.htm?treeId=1&articleId=106213&docType=1

https://open.pinduoduo.com/application/document/browse?idStr=3407B605226E77F2

https://jos.jd.com/commondoc?listId=345

3. Advanced approaches

These designs introduce new cryptographic primitives that preserve order or enable fuzzy matching with limited ciphertext expansion. Typical research directions include:

Hill‑cipher based fuzzy encryption (FMES)

Bloom‑filter‑enhanced encrypted search

Lucene‑style encrypted indexing (e.g., encrypt tokens and index them in Elasticsearch)

Key papers (plain URLs):

https://www.jiamisoft.com/blog/6542-zifushujumohupipeijiamifangfa.html

http://kzyjc.cnjournals.com/html/2019/1/20190112.htm

https://www.jiamisoft.com/blog/5961-kuaisuchaxunshujukujiami.html

https://www.cnblogs.com/arthurqin/p/6307153.html

http://jeit.ie.ac.cn/fileDZYXXXB/journal/article/dzyxxxb/2017/7/PDF/160971.pdf

Recommendation

For most production systems the token‑based method (Approach 2) offers the best trade‑off: modest implementation effort, index usage for acceptable query performance, and predictable storage increase. Naïve methods should be limited to tiny test datasets, while advanced cryptographic schemes are appropriate only when a dedicated security team can invest in custom algorithm development.

Implementation checklist:

Choose a reversible encryption algorithm (e.g., AES) with known ciphertext expansion factor.

Define token length (≥4 characters for English, ≥2 for Chinese) and generate overlapping tokens for each field.

Encrypt each token and store them in a separate indexed column.

When querying, encrypt the search fragment using the same tokenisation rule and issue a LIKE query on the token column.

Monitor storage growth; ciphertext size is typically about twice the plaintext size for common block ciphers.