How to Perform Fuzzy Searches on Encrypted Data: Practical Approaches

How to Perform Fuzzy Queries on Encrypted Data

We often encrypt sensitive fields such as passwords, phone numbers, addresses, and bank details to protect data, but encrypted values are not friendly to fuzzy matching. This article explores three categories of solutions and their trade‑offs.

Classification of Approaches

Naïve (dubbed “沙雕”) : Load all ciphertext into memory, decrypt, then perform fuzzy matching, or maintain a plaintext tag table and query the tags.

Conventional : Implement encryption/decryption functions in the database and modify the LIKE condition, or store tokenized encrypted substrings in an auxiliary column for indexed fuzzy search.

Advanced (“超神”) : Design new algorithms (e.g., order‑preserving encryption, Bloom‑filter‑based schemes) that allow ciphertext to be searched directly without excessive storage growth.

Naïve Approaches

1. Load all data into memory, decrypt each record, and apply a fuzzy‑matching algorithm.

2. Create a plaintext “tag” table that maps ciphertext to its original value, then perform fuzzy queries on the tag table.

Memory Impact Example

Assuming DES encryption of a phone number 13800138000 yields the ciphertext HE9T75xNx6c5yLmS5l4r6Q==, which occupies 24 bytes. For different record counts:

1 million records → ~22.9 MB

10 million records → ~228.9 MB

100 million records → ~2.3 GB

Such memory consumption quickly becomes impractical for large datasets.

Conventional Approaches

Method 1 : Store encrypted values in the database and use a decryption function in the WHERE clause, e.g., decode(key) LIKE '%partial%'. This requires minimal code changes but cannot leverage indexes.

Method 2 : Tokenize the plaintext into fixed‑length substrings, encrypt each token, and store them in an extra column. Queries use key LIKE '%partial%' on the token column, allowing index usage at the cost of additional storage.

Example tokenization: the string “ningyu1” is split into “ning”, “ingy”, “ngyu”, “gyu1”, each encrypted separately. A fuzzy search for “ingy” matches the corresponding token.

Encryption typically expands data size (e.g., DES expands 11‑byte plaintext to 24‑byte ciphertext, a 2.18× increase), so storage overhead must be considered.

Advanced Approaches

These solutions involve algorithmic research such as order‑preserving encryption, Hill cipher variants, FMES, or Bloom‑filter‑based schemes. They aim to keep ciphertext order‑compatible with plaintext and limit size growth, but require deep cryptographic expertise.

References include:

Database fuzzy‑match encryption methods (link omitted)

Bloom‑filter‑enhanced fuzzy search research (link omitted)

Lucene‑based encrypted search (link omitted)

Conclusion

Naïve methods are only viable for very small datasets. Conventional token‑based approaches offer a practical balance of security, storage cost, and query performance, especially the second variant that can use indexes. Advanced cryptographic schemes provide the best theoretical security and performance but demand specialized development effort.