Techniques for Fuzzy Search on Encrypted Data: Approaches, Trade‑offs, and Practical Implementations

When developing applications that store sensitive information (passwords, phone numbers, addresses, bank cards, etc.), different encryption requirements arise: passwords are stored with irreversible hash functions, while fields like phone numbers must remain decryptable and support fuzzy queries.

The author classifies fuzzy‑search solutions for encrypted data into three groups: a "silly" approach that decrypts everything in memory or uses a plain‑text tag table; a "conventional" approach that either runs decryption inside the database and applies LIKE on the plaintext, or tokenises the ciphertext into fixed‑length encrypted tokens stored in extra columns; and a "super" approach that designs new algorithms (e.g., Hill cipher, FMES, Bloom‑filter‑based schemes) to enable order‑preserving, low‑overhead fuzzy matching.

The "silly" methods are easy to implement but become infeasible as data volume grows, often leading to Out of memory errors because the entire dataset must be loaded and decrypted.

The first conventional method adds a decryption function to the DB and modifies the fuzzy condition to decode(key) LIKE '%partial%' . This is simple but cannot leverage indexes and may suffer from algorithm mismatches between application and DB. The second conventional method tokenises the plaintext into fixed‑length groups (e.g., four‑character English or two‑character Chinese segments), encrypts each token (using algorithms such as AES or DES ), stores them in auxiliary columns, and then queries with key LIKE '%partial%' . This method increases storage (ciphertext length grows, e.g., a 11‑byte phone number becomes a 24‑byte ciphertext with DES, a 2.18× increase) but allows index optimisation.

Real‑world e‑commerce platforms (Taobao, Alibaba, Pinduoduo, JD) adopt similar schemes, as shown by the linked documentation.

The "super" approach requires deep algorithmic research, often designing custom order‑preserving encryption or leveraging Bloom filters and Lucene‑based search engines to achieve fuzzy matching without excessive storage growth.

In summary, the author advises avoiding the "silly" methods, prefers the second conventional token‑based technique for its balance of implementation cost, performance, and security, and suggests exploring advanced algorithmic solutions only when specialised expertise is available.