How to Perform Fuzzy Queries on Encrypted Data

When protecting sensitive fields such as passwords, phone numbers, or credit‑card details, encryption is essential, but it complicates fuzzy searching. This article classifies three broad strategies for fuzzy queries on encrypted data—naïve ("silly"), conventional, and advanced ("god‑level")—and discusses their merits and drawbacks.

Naïve Approaches

These methods ignore performance and security considerations:

Load all encrypted records into memory, decrypt them, and perform fuzzy matching in application code.

Create a clear‑text mapping table (a "tag" table) and query the tags to locate the encrypted rows.

Both are only viable for very small datasets; large volumes cause excessive memory usage and defeat the purpose of encryption.

Conventional Approaches

More practical methods that balance security and queryability:

Implement encryption/decryption functions inside the database and modify fuzzy conditions to use decode(key) like '%partial%' .

Tokenise the plaintext, encrypt each token, store the encrypted tokens in an auxiliary column, and query with key like '%partial%' . This allows index usage but increases storage.

The token‑based method typically groups characters (e.g., four English characters or two Chinese characters) and encrypts each group. For example, the plaintext 13800138000 encrypted with DES becomes HE9T75xNx6c5yLmS5l4r6Q== , expanding from 11 to 24 bytes (≈2.18× growth).

Advanced (Algorithmic) Approaches

These solutions require deep cryptographic research and may involve designing new schemes that preserve order or enable direct ciphertext fuzzy matching. References include Bloom‑filter‑based searchable encryption, Hill‑cipher variants, and encrypted search engines built on Lucene or Elasticsearch.

Typical academic resources: "A Bloom‑Filter‑Based Improved Encrypted Text Fuzzy Search Mechanism" and "Cloud Storage Supporting Verifiable Fuzzy Query Encryption".

Conclusion

Naïve methods are discouraged; conventional token‑based approaches are recommended for most scenarios due to their moderate implementation cost and acceptable performance. When a team has strong cryptographic expertise, exploring advanced algorithmic solutions can yield better security‑performance trade‑offs.