How to Perform Fuzzy Queries on Encrypted Data: Methods and Trade‑offs

In the previous article we discussed data security and the difficulty of performing fuzzy queries on encrypted data; this piece focuses on practical approaches to enable such queries.

The author classifies the solutions into three groups:

Sand‑wich (naïve) approaches : loading all data into memory for decryption and matching, or maintaining a plaintext mapping table (tag table) alongside ciphertext, both of which compromise security and scalability.

Conventional approaches : implementing decryption functions in the database and using decode(key) like '%partial%', or tokenizing the plaintext, encrypting each token, storing them in an auxiliary column, and querying with key like '%partial%'. These methods are easier to adopt but may forfeit index usage and increase storage.

Advanced (super) approaches : algorithm‑level designs such as custom encryption schemes that preserve order, Bloom‑filter‑based methods, or leveraging search engines like Lucene with encrypted tokens. These require deep cryptographic expertise but can offer better performance and security.

Examples illustrate memory consumption when decrypting large datasets (e.g., encrypting 13800138000 with DES yields a 24‑byte ciphertext) and show that naïve in‑memory decryption quickly leads to out‑of‑memory errors for big data volumes.

For conventional method 2, the author describes fixed‑length tokenization (e.g., groups of four ASCII characters or two Chinese characters) and demonstrates how encrypted tokens can be queried with key like "%partial%". The trade‑off includes increased storage due to ciphertext expansion (approximately 2.18× for DES) and a minimum token length requirement for effective fuzzy matching.

The article also lists real‑world implementations from major e‑commerce platforms (Taobao, Alibaba, Pinduoduo, JD) that adopt similar encrypted fuzzy‑search techniques.

In summary, the author recommends avoiding naïve approaches, adopting conventional method 2 as a cost‑effective solution, and considering advanced algorithmic designs only when specialized expertise is available.