Zero-Knowledge Search Index Encryption: Building Searchable Encrypted Stores

Most developers reach for a hosted search service — Elasticsearch, Typesense, Algolia — and accept that the vendor can read every document they index. For consumer apps that's usually fine. For anything storing health records, legal documents, financial data, or personal communications, handing a third party full-text access to your users' data is a liability, not a convenience.

Searchable symmetric encryption (SSE) solves this. It lets a server execute keyword queries against ciphertext without ever learning the underlying plaintext. This post explains how it works, when to use it, and what you lose compared to a standard search stack.

The Core Problem With Encrypting Search Indexes

Encrypting your documents before storage is easy. The hard part is search.

A traditional inverted index maps terms to document IDs. The term "invoice" points to doc IDs [14, 78, 203]. If you encrypt the documents but leave the index in plaintext, the server still sees every word in every document. If you encrypt the index entries with a random key per term, the server can't look anything up without you first decrypting the index client-side — which defeats the purpose of offloading search.

SSE schemes thread this needle with a construction that lets the server match a search token against encrypted index entries, learning only which documents match a given query — nothing else about the query or the documents.

How SSE Schemes Work

The canonical SSE-1 construction (from Curtmola et al., 2006) works like this:

Setup phase (client-side):

1. Derive two keys from a master secret: K1 and K2.
2. For each keyword w, compute a pseudorandom function: PRF(K1, w) to get a chain address, and use PRF(K2, w) to encrypt the document ID list.
3. Store (PRF(K1, w), Enc(K2, w, docIDs)) on the server for each keyword.

Search phase:

1. Client computes the search token: token = PRF(K1, keyword).
2. Client sends only the token to the server.
3. Server looks up the matching entry and returns the encrypted result.
4. Client decrypts the result locally with K2.

The server learns which encrypted entries match (so it learns query access patterns over time) but never learns the keyword itself or the document contents.

Here's a minimal implementation sketch in TypeScript:

import { createHmac, createCipheriv, randomBytes } from "crypto";

function buildIndex(
  masterKey: Buffer,
  documents: Map<string, string[]> // docId -> [keyword, ...]
): Map<string, Buffer> {
  const k1 = createHmac("sha256", masterKey).update("k1").digest();
  const k2 = createHmac("sha256", masterKey).update("k2").digest();
  const index = new Map<string, Buffer>();

  const termDocs = new Map<string, string[]>();
  for (const [docId, keywords] of documents) {
    for (const kw of keywords) {
      if (!termDocs.has(kw)) termDocs.set(kw, []);
      termDocs.get(kw)!.push(docId);
    }
  }

  for (const [kw, docIds] of termDocs) {
    const addr = createHmac("sha256", k1).update(kw).digest("hex");
    const plaintext = Buffer.from(JSON.stringify(docIds), "utf8");
    const iv = randomBytes(12);
    const cipher = createCipheriv("aes-256-gcm", k2, iv);
    const ciphertext = Buffer.concat([
      iv,
      cipher.update(plaintext),
      cipher.final(),
      cipher.getAuthTag(),
    ]);
    index.set(addr, ciphertext);
  }

  return index;
}

function searchToken(masterKey: Buffer, keyword: string): string {
  const k1 = createHmac("sha256", masterKey).update("k1").digest();
  return createHmac("sha256", k1).update(keyword).digest("hex");
}

The server stores the index map. When searching, you send the token, the server returns the ciphertext blob, and you decrypt locally.

The Access Pattern Leakage Problem

SSE-1 is non-adaptive secure: an attacker who only sees the initial index and a single query learns nothing. But it leaks access patterns over time.

If the server sees that query token A returns entries {1, 7, 23} and later token B also returns {1, 7, 23}, it knows A and B retrieved the same document set — without knowing what either keyword was. Over many queries, frequency analysis can reconstruct the underlying keyword distribution.

Two mitigations exist:

Padding and dummy entries. Pad every result set to a fixed bucket size (e.g., the next power of two). Insert dummy encrypted entries so the server can't distinguish a 3-document match from a 4-document match. Cost: 1.5x–2x storage overhead on average.

Oblivious RAM (ORAM). ORAM is a cryptographic protocol that hides access patterns entirely — the server sees random-looking memory accesses regardless of which document you read. The trade-off is bandwidth: Circuit ORAM requires O(log² N) server round-trips per access. For a million-document corpus, that's roughly 400 accesses per query. Fine for a low-QPS compliance use case, prohibitive for a high-volume search product.

Most production SSE deployments accept the access-pattern leakage of SSE-1 and mitigate it with padding. ORAM is reserved for high-security scenarios where the adversary is assumed to be watching all access patterns over a long period.

Practical Trade-offs vs. Standard Search

Feature	Standard (Elasticsearch)	SSE with padding
Full-text ranking	BM25, semantic, hybrid	Keyword match only
Phrase search	Native	Requires n-gram pre-indexing
Fuzzy matching	Native	Requires pre-expanded terms
Aggregations	Native	Not supported without FHE
Query latency	Single digit ms	5–50ms (+ decryption)
Index update cost	Append to posting list	Rebuild affected chains
Server data exposure	Full plaintext	Access patterns only

The ranking gap is the biggest practical limitation. BM25 requires knowing term frequencies across the corpus. With SSE, the server only knows which encrypted entries match — it has no frequency information. You can implement ranked retrieval by computing scores client-side after decryption, but that means fetching more candidate documents than you need (typically the full result set for the keyword) and ranking locally.

For most enterprise document search use cases — "find all invoices containing this vendor name" — keyword precision matters more than ranking. SSE is a good fit. For consumer full-text search where relevance ranking determines the product experience, SSE requires significant compromises.

Dynamic Updates: The Hardest Part

Adding documents to a static SSE index is straightforward. Supporting efficient updates without leaking the structure of your changes is the hard part.

The naive approach: rebuild the entire index on every document add or delete. For a 100k-document corpus, this takes seconds. For a million documents, minutes. Impractical for any real-time use case.

Dynamic SSE (DSSE) schemes (Kamara & Papamanthou, 2013; Stefanov et al., 2014) maintain an append-friendly structure where new documents can be added without rebuilding. The trade-off: forward privacy is harder to guarantee. "Forward private" SSE ensures a server can't link future queries to past updates — without it, an attacker who watches your updates can correlate them with later searches.

Orion (from the academic literature) and practical implementations like Clover achieve forward and backward privacy with O(log N) overhead per update. These are the schemes to reach for in production systems.

What BitAtlas Uses

BitAtlas stores all document metadata encrypted at rest with client-derived keys. Full-text search over encrypted content uses a keyword-based SSE scheme with bucket padding to limit access-pattern leakage. For ranking, we return a configurable result window (default: top 50 candidate documents) and let the client-side agent re-rank using whatever model fits the use case.

For compliance-sensitive customers who need ORAM-level access-pattern hiding, we offer a lower-QPS encrypted search tier that batches queries through a Circuit ORAM layer. Most customers don't need it — but it's there when the threat model demands it.

Getting Started

If you want to experiment with SSE in a Node.js or browser context, the Web Crypto API provides everything you need: SubtleCrypto.importKey for HKDF, SubtleCrypto.sign for HMAC-PRF, and SubtleCrypto.encrypt for AES-GCM. No third-party crypto library required.

For a production deployment, evaluate these open implementations:

• SEAL from Microsoft Research — C++ library for lattice-based FHE that can express SSE patterns.
• OpenSSE — A research implementation of SSE schemes in C++.
• CipherCore — A Rust library with practical DSSE support.

Start with SSE-1 for static or infrequently updated corpora. Move to a DSSE scheme when you need real-time indexing. Add bucket padding from day one — retrofitting it later requires a full index rebuild.

Zero-knowledge search isn't free. You pay in ranking quality, update complexity, and engineering effort. But for the right use case — any application where "the search server must not read user documents" is a hard requirement — it's the only architecture that delivers on that promise.