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 can take a separate path: ciphertext protects the original value while an auxiliary index supports specific queries. Blind indexes and some commercial encryption SDKs use that division. Each recovered query capability exposes some data relationships through the index. The business should make that tradeoff deliberately, before a database leak makes it visible.

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.

Start with what the attacker can obtain. A stolen disk, leaked offline backup, compromised database account, and controlled application server expose different keys and execution capabilities. Disk encryption addresses physical theft; application-side field encryption can separate an independent database snapshot from its keys. A clear threat model determines the encryption layer.

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.

Three quantities decide whether scanning fits: the authorized record count, query frequency, and acceptable latency. Narrow the set by tenant and order context, then measure it. Maintaining a search index for a few hundred infrequently queried records can be the more expensive choice.

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.

The database has optimization tools of its own. PostgreSQL expression indexes can index computed values, and pg_trgm GIN/GiST indexes support some leading-wildcard searches. Ordinary B-trees serve a different set of query shapes. The security question is what plaintext features the useful index puts back into the database.

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 places trust in the environment authorized to execute it. Plaintext appears there, bringing SQL parameters, diagnostics, and logs into scope. Review exposure along the actual execution path, beyond the ciphertext column.

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.

A blind index is a keyed deterministic label. Matching labels retrieve records and reveal equality within the same index domain. The rest of the design has to account for that extra exposure.

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.

Frequency statistics, record relationships, and API feedback are the next attack surfaces. An attacker can work around direct tag computation by using data distributions and the system's normal functions. The key protects the HMAC operation; relationships exposed by the index carry their own cost.

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.

The false positive comes from order information discarded by the index. A record survives the intersection when both fragments appear somewhere. Verifying the complete 01380 requires decrypting the candidate and checking that the characters occur consecutively.

Multiplicity gets lost too. Deduplicating the query 11111 leaves one fragment, 1111, so a record with four consecutive 1s passes candidate filtering. Final verification still has to find the fifth character required by the query.

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 has to count verified matches. A hundred database candidates may leave only a few results after filtering. Continue fetching and checking batches until a page is filled or candidates are exhausted. Track the candidate cursor, checked count, and verified count separately. Stopping after the first hundred can strand valid results in the next batch.

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

The simplified independent-uniform model gives an initial scale of about eight thousand candidates. Real phone numbers have prefix rules, repeated fragments, and business skew; those distributions belong in the next measurement. The candidate set determines how much decryption the index saves. An arrow from ten million records to twenty-three does not calculate it.

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.

The choice of n strongly affects selectivity. Moving an eleven-character string from 4-grams to 2-grams raises the pre-deduplication window count from eight to ten. The candidate set can grow much more sharply because shorter fragments are shared by more records. Account for window count and selectivity separately in storage and latency measurements.

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.

Phone numbers and short identifiers deserve particular scrutiny before full n-gram indexing. Four-digit fragments have only ten thousand possible inputs and overlap one another. Prefix rules and cross-table relationships give an attacker much more structure than random-looking tags suggest. Saving scans can purchase a long-lived source of correlation.

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 fragments often improve selectivity and can make rare values easier to identify. Shorter fragments raise false positives and verification cost. Parameter selection needs the actual distribution, auxiliary knowledge, and false-positive budget. A “longer is safer” star rating hides those tradeoffs.

Controlled leakage should be an inspectable list: which relationships are exposed, how they combine with other information, and why the business accepts the residual risk. Writing the phrase on an architecture diagram is the beginning of that analysis.

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

Use purpose-separated keys for field encryption and search tags. Generate them independently or derive separate subkeys through an established scheme, with explicit purposes and access controls.

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.

After separating keys, examine who can obtain them together. A process with access to both data and search keys exposes both when compromised. A leaked search key alone enables enumeration of low-entropy fragments. Review key purposes, process permissions, and compromise impact in one picture.

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 result set has another integrity problem. A database can omit an index entry or return an older valid ciphertext under the same context, allowing AAD verification to pass. Establishing a complete and current result set also requires checking retrieval and versions.

For a business that must resist a malicious database, integrity, freshness, and verifiable retrieval need their own requirements and mechanisms. A tag table followed by decryption handles candidate selection and per-record content checking.

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

A search endpoint that permits repeated fragment guesses, returns full customer details, and lacks business scoping is a ready-made enumeration tool. An attacker takes data from its results through a normal application path, regardless of how carefully HMAC is implemented behind it.

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.

Changing search engines addresses execution and scaling of inverted lookups. Index design still determines exposure through tag frequency, record relationships, queries, and result sizes. Posting-list lengths, tenant partitioning, updates, and actual load should drive migration decisions. A ten-million-row label is not a deployment plan.

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.

Evaluate an SSE protocol through its supported queries, leakage function, update behavior, trust assumptions, and interaction cost. Formal proofs state those premises, while leakage-abuse research asks how attackers can combine the exposed information. Custom HMAC indexes, SSE, and homomorphic encryption all have concrete constructions. Ranking their names by safety stars skips the substantive analysis.

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.

The customer-service scenario in the article that prompted this discussion was my starting point. Working through it makes me favor narrowing the search requirement first, then deciding which relationships are worth exposing. More indexes expand what can be searched and what must subsequently be protected and accounted for.