Can You Search Inside Encrypted Data?

Imagine a customer-support dashboard. Phone numbers must not be stored in plaintext, so the phone column is encrypted and the database holds unreadable bytes. Then a customer who cannot remember the full number wants to find an order using its last four digits. A few days later, the request expands to searching for digits in the middle as well.

The old SQL query no longer works on that column:

SELECT id FROM users WHERE phone LIKE '%0138%';

Randomized field encryption is supposed to hide relationships between plaintext values. A database that cannot read the values cannot simply recognize which ciphertexts contain the same fragment. That loss of visible structure is part of the protection.

Search is still possible. I would keep the original value in ciphertext and build a separate index for a limited set of queries. Blind indexes and some commercial encryption SDKs take this approach. The limit matters: the index provides a capability by exposing relationships that encryption would otherwise hide.

Before implementation, specify which queries are needed and what the database will learn from them.

Last-four-digit lookup, substring search, and typo correction

'Support fuzzy search' is too vague to implement. Several operations may share one search box while requiring quite different designs.

SQL LIKE '%xxx%' here means substring matching, not typo correction. Approximate matching also needs a definition of allowed errors, a distance function, and ranking rules. This article handles literal substrings; it does not implement arbitrary SQL wildcard expressions.

Query semantics determine which indexes are needed and which relationships become visible. Searching the last four digits does not require indexing every four-digit fragment. Exact email lookup does not require indexing every substring of an address. Preparing all searchable features for an unconfirmed future requirement can enlarge the information exposed by the system.

The other question is who the protection is meant to resist. A stolen disk, a leaked database backup, an attacker with query access, and a fully compromised application server are different threats. Disk encryption cannot stop someone who can already query the running database. Conversely, a database's ability to decrypt does not mean an offline backup without the keys can necessarily be decrypted. Choose the encryption layer against the threat model.

The main boundary here is an application that may handle plaintext, with a database that stores only ciphertext and search indexes. An attacker may read the database but does not hold the application's keys. Later sections consider continuous query observation, chosen inputs, and compromise of the application itself.

Scanning, database-side decryption, and plaintext copies

Decrypting a scan can work when its scope is small

The simplest implementation reads records from the database, decrypts them in the application, and runs contains on each value.

An authorized tenant with a few hundred records, or a rare offline investigation, may be a reasonable fit. A cursor or batches also avoid holding every plaintext value in memory at once.

Streaming reduces memory pressure; it does not eliminate the scan. Without a selective preliminary filter, checking ten million records still means reading and processing ten million records. Storage, network transfer, object handling, decryption, and string comparison can all contribute to the cost.

I would assess the scope of the scan, query frequency, and acceptable latency before ruling this option out.

Moving decryption into SQL changes whom you trust

Another option performs decryption inside SQL. This is pseudocode illustrating the idea, not a portable database function:

WHERE decrypt(phone_ciphertext) LIKE '%0138%'

It avoids transferring every ciphertext to the application, but it does not automatically reduce filtering work. An index on the existing ciphertext generally cannot tell the database whether the decrypted value contains a substring.

It would be wrong to claim that expressions can never be indexed, or that every query with a leading wildcard is impossible to optimize. PostgreSQL supports expression indexes, and pg_trgm GIN/GiST indexes support certain LIKE searches with leading wildcards. An ordinary B-tree is not a general solution for arbitrary substring searches.

Materializing decrypted text or directly recoverable plaintext features in an index puts sensitive information back inside the database. That changes the security boundary as well as the query plan.

Giving the database decryption capability also means trusting the execution environment and the parties with the relevant permissions. Plaintext appears there. SQL parameters, diagnostic output, and logging need review. It is inaccurate to say that all plaintext necessarily enters backups or slow-query logs, but each exposure path needs assessment.

The search column belongs in the threat model

One straightforward design encrypts the main field and adds a phone_search column containing the full plaintext number.

If the goal is to protect phone numbers when the database leaks, the attacker can simply read that search column. Decrypting the main field becomes unnecessary.

Even storing just the last four digits deliberately reveals those digits to the database. Encryption of the full number does not protect a separate plaintext suffix.

Security assessment must cover copies, indexes, and execution paths. A column called ciphertext does not establish that the data remains protected after a database leak.

A blind index alongside the ciphertext

I would preserve normal randomized encryption of the original value rather than alter its encryption to make search easier.

A maintained cryptographic library offering AES-GCM is one option for this example; ChaCha20-Poly1305 is another standardized authenticated-encryption construction. Decryption should verify integrity as well as recover the value. A new system has no reason to inherit DES from an old tutorial or invent an algorithm that preserves character patterns for search.

An AES-GCM envelope typically includes an algorithm or format version, a key version, the nonce, and the authentication tag. The nonce need not be secret, but must not repeat under the same key. Random nonces still require appropriate randomness, usage limits, and rotation. 'Generate a random number each time' is not an unlimited guarantee.

Search has its own path. Start with exact matching: the application calculates a deterministic keyed tag over the normalized phone number.

Original phone number --authenticated encryption--> phone_envelope

Normalized phone number --HMAC-SHA-256(K_search, value)--> phone_index

For a full-number lookup, the application generates a query tag using the same rules. The database matches tags for equality; the application then decrypts and checks the candidates.

This auxiliary structure is usually called a blind index. Implementations differ in keyed hashing, key derivation, and truncation. HMAC-SHA-256 here illustrates a deterministic search-tag construction; it is not a complete implementation of any particular library.

The tag is not another decryptable ciphertext or proof of anonymization. Although the database does not know which number a tag represents, it can recognize identical tags within the same index domain.

Unkeyed hashes of four digits are easy to enumerate

There are only ten thousand four-digit inputs, from 0000 to 9999. If the index is SHA256("1380"), someone who obtains the database can hash every input and build a lookup table. A longer hash output does not create more possible inputs.

HMAC introduces a secret key that is not given to the database. If that key remains secret and the attacker has no usable tag-generation oracle, the attacker cannot independently build the same lookup table. A public fixed salt does not provide that property.

Statistics, correlations, and interface feedback may still reveal what tags mean. Preventing direct computation of a lookup table addresses only one route to inference.

A suffix search needs only a suffix tag

Before considering n-grams, narrow the index to the actual requirement. If only the last four digits are needed, generate one tag for that suffix in a separate index domain. For 13800138000, that means one tag corresponding to 8000.

Apply the same rule to the four digits supplied by the user, match tags for equality, and decrypt and verify the candidates.

The database then needs no tags for this number's 1380, 3800, or 0013 fragments. There are fewer index entries to maintain and fewer features exposed than if a full fragment index were added to the same field.

A four-digit suffix is still a low-cardinality feature. Many numbers share it, and it must not serve as an authentication credential. Query scope, returned fields, and protection against bulk enumeration remain necessary.

I would use a full-value index for exact lookup, a suffix index for a fixed suffix, and only the prefix lengths the business needs. Arbitrary-position fragment indexing comes after a confirmed requirement for it.

Building a substring candidate index with 4-grams

Suppose the requirement really is to search for any run of four or more consecutive digits in a phone number. Split the normalized value using a sliding window of length four. For 13800138000, the 4-grams are:

Original: 13800138000

4-grams by position:
1380  3800  8001  0013  0138  1380  3800  8000

Distinct fragments:
1380  3800  8001  0013  0138  8000

Eight window positions produce six distinct fragments. Repeated fragments within one record can be deduplicated for a presence-based candidate filter. Generate an HMAC tag for each fragment and store which records contain each tag. Concatenating every tag into one string and applying LIKE '%tag%' would miss the advantage of equality lookup.

A separate tag table forms a simple inverted index from a tag to record IDs. Searching a concatenated tag string can reintroduce scanning work.

The following minimal PostgreSQL schema illustrates that structure. Business fields and authorization policies are omitted:

CREATE TABLE users (
    tenant_id      BIGINT NOT NULL,
    id             BIGINT NOT NULL,
    phone_envelope BYTEA NOT NULL,
    PRIMARY KEY (tenant_id, id)
);

CREATE TABLE phone_search_tokens (
    tenant_id     BIGINT NOT NULL,
    user_id       BIGINT NOT NULL,
    index_version INTEGER NOT NULL,
    token         BYTEA NOT NULL CHECK (octet_length(token) = 32),
    PRIMARY KEY (tenant_id, index_version, token, user_id),
    FOREIGN KEY (tenant_id, user_id)
        REFERENCES users (tenant_id, id) ON DELETE CASCADE
);

CREATE INDEX phone_search_tokens_by_user
    ON phone_search_tokens (tenant_id, user_id, index_version);

The example stores the full 32-byte HMAC-SHA-256 output. index_version identifies the key version, normalization rules, and fragment rules. The primary key supports tenant/version/tag lookup and prevents duplicate tags for a record. The second index supports maintaining and deleting a record's tags.

For 01380, intersect two tag matches

The query splits into 0138 and 1380. The application generates both query tags and asks for records containing both.

More generally, use this parameterized query. The third parameter must be a deduplicated, nonempty tag array with no NULL elements. It is not the user's plaintext input:

PREPARE search_phone (BIGINT, INTEGER, BYTEA[]) AS
SELECT user_id
FROM phone_search_tokens
WHERE tenant_id = $1
  AND index_version = $2
  AND token = ANY ($3)
GROUP BY user_id
HAVING COUNT(*) = cardinality($3)
ORDER BY user_id;

This uses PostgreSQL prepared statements and array parameters. COUNT(*) works because the primary key prevents duplicate tags per record and the query array is also deduplicated.

The example assumes the caller may search every record in that tenant. Record-level permissions require additional authorization conditions in candidate selection. The tenant ID must come from a verified identity context rather than an arbitrary request parameter.

The output at this point is a set of candidate IDs, not verified search results.

All fragments can be present in the wrong order

Consider these two illustrative digit strings:

A: 13800138000
B: 13801110138

Query: 01380
Query fragments: 0138, 1380

A contains 01380. B does not, but it has 1380 at the beginning and 0138 at the end. An index that stores only fragment presence includes B in the candidate set too.

This is neither an HMAC collision nor failed encryption. Even collision-free tags would produce the same candidates: the index does not retain order or adjacency between fragments.

Multiplicity causes a similar issue. Deduplicating the query 11111 leaves one fragment, 1111. A record containing four consecutive ones does not necessarily contain five.

The full query path therefore needs these steps:

Check query permissions and input
    -> Normalize with the selected rule version
    -> Split, generate tags, and deduplicate
    -> Find candidate IDs within the authorized scope
    -> Fetch, authenticate, and decrypt candidate ciphertext
    -> Check the actual substring against normalized plaintext
    -> Return results permitted by the caller's access

The filter is useful because every n-gram of a real substring must also occur in the field containing that substring.

With a complete and consistent index, identical normalization rules, query length at least n, and no arbitrary candidate truncation, requiring all query fragments does not itself discard true substring matches. The converse does not hold, so candidates still need verification.

A 4-gram index has no query fragments for inputs shorter than four digits. Reject those inputs, ask for more constraints, or route them through another deliberately designed flow. Do not let empty-input handling accidentally become a full scan.

Pagination must account for verification. A hundred candidates may yield fewer than a hundred matches, and candidate counts are not result counts. Capping retrieval at the first hundred candidates cannot justify reporting that no more results exist. Continue verifying batches or explicitly ask the user to narrow the query; the API must describe what it actually did.

How many candidates remain out of ten million records?

Replacing a scan's O(N) with an indexed lookup's O(log N) is an incomplete cost model. The system must also read posting lists, intersect them, fetch candidate ciphertexts, and decrypt and verify them. A B-tree does not remove the work of processing hundreds of thousands of matches for a common tag.

For a deliberately simplified estimate, assume ten million eleven-digit strings, eight four-digit windows per string, and approximately independent uniform digits. A rare-event approximation for the number of records containing one fixed four-digit fragment is:

10,000,000 × 8 ÷ 10,000 ≈ 8,000

This estimates an order of magnitude, not a benchmark on real phone numbers. Actual prefixes, repeated fragments, and business distributions can substantially change it. A diagram claiming that ten million records become twenty-three candidates would need evidence.

Storage also matters. A length-L string has max(L - n + 1, 0) windows for a fixed n. An eleven-digit value yields at most eight 4-gram tags. At 32 bytes each, the tag values alone occupy at most 256 bytes; the repeated number above yields six distinct tags, or 192 bytes. Tenant IDs, record IDs, versions, row overhead, and database indexes add further storage.

Window count and selectivity respond differently to n. Decreasing n does not necessarily make a record's index size explode: changing an eleven-digit string from 4-grams to 2-grams increases its undeduplicated window count from eight to ten. The distinct count depends on the value. Fragment selectivity and candidate volume often change much more.

Indexing several fragment lengths, or every possible substring, can instead generate a number of candidate fragments quadratic in string length. That is a different design from indexing one fixed n.

Before release, I would use appropriately masked or synthetic data that represents the real distribution and measure candidate counts, tail latency, index size, write amplification, and maintenance costs. Those measurements should guide longer fragments, minimum query length, and preliminary tenant or business filters. A generic recommendation to start at four digits is insufficient.

The database still sees frequencies and correlations

An attacker holding a database snapshot may not know whether a tag means 1380 or 8000, but can see which records share it, how many records each tag matches, which tags co-occur, and how many distinct tags each record has.

Continuous query observation can reveal repeated query tags, accessed records, and candidate counts. That exposes a different set of information from a static snapshot.

An attacker who can insert chosen values through normal business operations and observe the resulting database changes may gradually map known inputs to tags. Merely omitting an API named generateHmac does not rule out that capability.

Searchable-encryption research calls attacks that use side information and leakage to recover queries or plaintext leakage-abuse attacks. Cash and colleagues demonstrated such attacks under specified leakage models and attacker-knowledge conditions. Relationships between data can be exploited without breaking the underlying cryptographic algorithm.

I would be cautious about recommending a full HMAC n-gram index for structured values such as phone numbers or short identifiers. Each four-digit fragment has only ten thousand possibilities, fragments overlap, and correlated fields in other tables may help narrow the guesses.

The AWS Database Encryption SDK documentation also describes distribution leakage and risks from skewed or correlated fields. An algorithm name alone cannot establish whether an index fits a dataset.

Fragment length and tag length affect different things

The n in n-gram is the plaintext fragment length. The retained bit count of an HMAC tag is the cryptographic output length. They are separate parameters.

Truncating a tag from 256 bits to 128 bits reduces storage without giving ten thousand four-digit inputs 128 bits of entropy. Random collisions remain negligible for that small domain, so the tags still preserve almost the same equality relationships.

Some implementations truncate more aggressively so that distinct inputs share tags. The resulting false positives reduce distinguishability and are filtered after decryption. This needs dataset-specific analysis of distribution, correlation, and verification costs. Shorter is not automatically safe, and a product's configuration guidance cannot simply be transferred to a custom n-gram index.

Longer n-grams do not deserve a blanket 'more secure' rating. They may improve selectivity while making rare values easier to distinguish. Risk depends on the dataset and the attacker's information, rather than one parameter changing in a single direction.

Calling leakage controlled requires specifying what is exposed, checking what can be inferred by combining those exposures, and deciding whether the remaining risk is acceptable.

Write consistency, key rotation, and search permissions

Version the normalization rules

Removing spaces on writes but retaining them on queries, preserving country codes in one version but dropping them in another, or using different Unicode representations can make equivalent inputs produce different tags.

A full-number normalization function that completes or parses a phone number is not automatically suitable for a partial query. For 0138, validate an allowed search fragment rather than try to interpret a complete number.

Names, addresses, and email addresses need explicit semantics for case, punctuation, and character normalization. Blanket removal or conversion for convenience can change meaning. Index generation and final verification must use the same semantics for the selected version.

Changing these rules requires rebuilding the index, not merely replacing a utility function.

Separate keys by tenant, field, and purpose

Field encryption and all search tags should not share one key. Use independently generated keys or a mature key-derivation scheme to create distinct subkeys for each purpose.

An index domain can include tenant, table, field, query type, fragment length, and normalization version. HKDF's info parameter provides a standard way to bind application context. Encode that context unambiguously rather than concatenate strings without clear boundaries.

The same 1380 then need not have an identical tag across tenants or fields. This reduces direct cross-domain linking; it does not remove correlations inherent in the business data.

A separate random salt per record would also make identical inputs yield different tags across records. That removes the direct single-tag equality lookup described here. Randomization must be designed together with the query procedure.

Key separation limits purposes and some compromise effects, but does not protect everything if the application is fully controlled. A process that can obtain both encryption and search keys can expose both. A leaked search key alone also enables enumeration of low-entropy fragments and inference about original values.

KMS can protect and manage keys, including wrapping data keys through envelope encryption. It does not require a remote KMS call for every fragment tag. Plaintext-key lifetime, caching, permissions, and auditing inside the application still need design.

AAD authenticates ciphertext, not an entire result set

Bind context such as tenant ID, record ID, and field identifier as additional authenticated data, or AAD. It participates in authentication without being encrypted. Moving ciphertext into a different record or field will then normally fail verification under that different context.

The database can still omit index entries so the application misses results, or return a previously valid old ciphertext in the same context. Authenticating one ciphertext does not establish that a query result is complete and current.

Resisting those malicious-server behaviors requires additional integrity, freshness, or verifiable-query mechanisms. The tag table and decryption checks here do not provide those guarantees.

Maintain ciphertext and indexes together

Changing a phone number requires removing old tags, generating new ones, and updating the ciphertext. A transaction in one relational database can commit those changes together. Concurrent searches also need a defined read-consistency model so candidate selection and ciphertext retrieval do not observe incompatible versions.

An external search index introduces asynchronous synchronization, retries, idempotency, and version alignment. Accepting eventual consistency means immediate searchability after an update cannot be guaranteed without further coordination.

Rotating a search key changes the tags. Plan dual writes or another migration strategy, backfill existing records, query the required versions, and safely retire the old index. Normalization changes need a similar migration.

Distinguish replacing actual data or search keys from changing the upper-level key that wraps them. Rewrapping may leave search tags unchanged; replacing a data or search key generally requires migrating ciphertext or indexes.

Deletion must cover indexes, caches, search-engine copies, and backup-retention rules as well as the main table.

The search interface can become an enumeration oracle

Hiding search terms from the database does not hide them from callers. An API allowing unlimited fragment guesses, returning complete customer records, and imposing no business scope can enable bulk enumeration even when every tag uses HMAC.

Design authorization, query scope, rate limits, enumeration detection, and minimal returned fields together. HMAC tags in logs are still stable identifiers linking requests and records, so those logs are not automatically harmless.

These controls do not eliminate index leakage. They reduce the additional exposure created when the system hands out sensitive information through its normal functionality.

What the substring index has not solved

Edit distance cannot recover records that were never retrieved

To match Erci to Eric, the application could calculate edit distance after decryption. That handles candidate verification, but leaves candidate retrieval unresolved.

Requiring all query n-grams is generally too strict for approximate matching. One character change can disrupt several fragments.

Requiring at least one shared fragment is not a complete fix either. abc and axc differ by one substitution, but their unpadded 2-grams are {ab, bc} and {ax, xc}. They share none.

Approximate-search retrieval must be designed against the chosen distance function, length range, and allowed error count. Short strings may need another retrieval path or a scan over a restricted authorized set. State whether full recall is guaranteed and test it. Levenshtein distance counts insertions, deletions, and substitutions; counting adjacent transposition as one error needs a suitable alternative definition.

Edit distance can remove false positives among retrieved candidates. Missing records require changing the retrieval conditions.

Elasticsearch can execute the tag queries

A dedicated search engine may be worth evaluating when tag volume, query concurrency, or combined-search requirements exceed what the relational design handles well.

Store application-generated stable tags in Elasticsearch rather than decrypted phone numbers. Treat them as exact values, typically using keyword, instead of sending them through a normal text analyzer. Exact set-matching queries can express the conditions on several tags.

The engine still exposes tag frequencies, record relationships, query patterns, and result sizes. Ten million records alone do not imply a migration is necessary. Posting-list lengths, tenant partitions, update patterns, and measured load are better inputs to that decision.

Evaluate SSE as a specific protocol

Searchable symmetric encryption, or SSE, is a research area with multiple constructions. It studies search over outsourced encrypted storage and defines and proves security properties in explicit models.

Custom HMAC tags, SSE, and fully homomorphic encryption cannot be ranked with a simple sequence of security stars. Query support, leakage, updates, trust, and interaction requirements vary by protocol. Formal security holds relative to a particular definition and does not imply that remaining leakage cannot be exploited.

Hiding repeated queries or the records they access requires evaluating specialized protocols and their computation, communication, and operational costs. Increasing the hash length of the existing table does not address those requirements.

Choosing a search for the support dashboard

For the original support workflow, I would first check whether full-number lookup is enough. If staff really need the last four digits, build only that suffix index and restrict queries to the required tenant and order scope. For small datasets and infrequent queries, measure a filtered decrypt-and-scan implementation too: it avoids maintaining a persistent search index.

Arbitrary substring search needs a stronger case. Once the requirement is confirmed, measure candidate volumes against real distributions and assess inference from frequencies, correlations, and known inputs. Highly sensitive fields with small domains or strong correlations may call for a revised support workflow.

Randomized authenticated encryption, a minimal search index, authorized candidate retrieval, and decryption-based verification form a design to evaluate. Key isolation, versioned normalization, consistent writes, and API restrictions must hold alongside it. Listing 'AEAD + HMAC + n-gram' does not deliver the whole system.

Encrypted data can support some searches, but indexes leave relationships visible. Alongside verifying decryption and query correctness, I would ask what someone who obtains the database could infer about customers from the search structures.

This article began as a reconsideration of the Chinese post 'How Do You Perform Fuzzy Queries on Encrypted Data?' It uses independently derived tag structures, SQL, and counterexamples rather than adopting that post's algorithm choices or performance estimates. Writing context: original post.

The digit strings are teaching examples, and the candidate-count estimate is not a production benchmark. This is architectural analysis with minimal examples, not a claim that any deployment has passed a cryptographic audit.