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

The article discusses the challenge of performing fuzzy searches on encrypted data and presents three categories of solutions: naïve “shadiao” approaches that load all data into memory or maintain a plaintext tag table, conventional methods that use database decryption functions or store encrypted tokenized substrings, and advanced “super” techniques that involve custom algorithms such as Bloom‑filter‑based schemes or specialized cipher designs.

Naïve methods are simple but impractical for large datasets due to high memory consumption and security risks. For example, encrypting 13800138000 with DES yields the 24‑byte ciphertext HE9T75xNx6c5yLmS5l4r6Q==, which quickly exhausts memory when many records are loaded.

Conventional approaches, especially the token‑based “regular two” method, balance performance and security by encrypting fixed‑length substrings and leveraging indexable columns, though they increase storage overhead. An illustration uses the string ningyu1 split into 4‑character groups (ning, ingy, ngyu, gyu1) and encrypts each token for later LIKE '%partial%' queries.

Using fixed‑length grouping (e.g., 4 English characters or 2 Chinese characters) and encrypting each group allows partial matches while preserving index usage.

Super methods require deep algorithmic research and may redesign encryption to preserve order and support partial matches without excessive ciphertext expansion; examples include Hill‑cipher variants, FMES, and Bloom‑filter‑enhanced searches.

The author recommends the regular token‑based approach for most scenarios and provides links to implementations from major e‑commerce platforms (Taobao, Alibaba, Pinduoduo, JD) and academic resources for further study.