Searching encrypted documents: blind indexing

If the server cannot read your files, how can it search them? With most end-to-end encrypted storage the honest answer is that it cannot, so you get search over file names at best, and nothing inside the documents. NomadVault searches names and contents. This article explains how that works without the server learning the words, and, just as important, what it does learn.

Search is a matching problem

Strip search down and it is this: for a word you type, find the documents that contain it. A conventional search engine builds an index, a big table of “word → list of documents”, and looks your word up in it. The index is the plaintext of every document, rearranged. Handing it to the server would undo the encryption.

The trick is to build the same table with every word replaced by a disguised version of itself, in a way that the server cannot reverse but your device can reproduce. If “invoice” always becomes the same unreadable token, the server can still match tokens against tokens. It just does not know which word any token stands for. Cryptographers call this a blind index.

How a word becomes a token

Each user has a secret search key, 256 random bits generated in the browser on first use. It is stored on the server sealed to your own keys, with the same hybrid wrap that protects your files, so the server holds it but cannot open it.

When you upload a document, your browser does the work:

1. It extracts the text. For PDFs, Word, PowerPoint and OpenDocument files, and for plain text formats, that happens on your device, after any content cleaning and before encryption.
2. It splits the text into words, lowercases them, drops anything shorter than three characters, short numbers and a handful of stop words such as “the” and “and”, and removes duplicates. The file name goes through the same rules separately.
3. Each remaining word is passed through HMAC-SHA-256 with your search key. HMAC is a keyed one-way function: the same word and key always give the same output, and without the key the output reveals nothing about the word. The first 16 bytes of each output are the token.
4. The tokens, and only the tokens, are sent to the server and stored next to the file’s identifier, labelled as a name token or a content token.

When you search, your browser applies the same rules to what you typed, computes the same tokens with the same key, and sends them. The server returns every file that has one of those tokens. Your browser decrypts the file names for display. At no point did a word cross the wire.

Because the tokens are keyed to you, the same word in two different users’ indexes produces two unrelated tokens. The server cannot even tell that two people’s documents share a word.

What the server learns anyway

This is the part a careful reviewer will ask about, and the answer is not “nothing”.

How many distinct words each file has. A file with 40 tokens is a short note; one with 4,000 is a long report. Length was already visible from the ciphertext size, so this adds little.

Which files share words. Within your own index, “invoice” is the same token in every file that contains it. The server can see that files A, B and C share a token, without knowing which word it is. Over time, and with outside knowledge, patterns like this can hint at content: a token that appears in nearly every file is probably your company name. This is the known cost of any searchable encryption that is fast enough to use, and the academic literature on it is clear that frequency and co-occurrence leak. We do not pretend otherwise.

What you search for, blinded. The server sees which tokens you queried and which files came back, so it knows you searched for something and what matched. It does not know the something.

Nothing from guests, nothing across users. The key is per user, so there is no index the server could compare across accounts, and someone who later gains access to a file does not automatically inherit the uploader’s tokens.

Compare this with the alternative most products choose, decrypting on the server to build a normal index, and the difference is the difference between a shape and the text itself.

Where it stops

Blind indexing comes with limits that follow from the design, and we would rather list them than have you discover them.

• Whole words only. A token stands for a complete word, so “invoices” and “invoice” are different tokens, and a search for “inv” finds nothing. Prefix search would require storing tokens for every prefix of every word, which multiplies the index and widens the leak. We chose not to.
• Your index is what you indexed. Tokens are created when you upload, create or rename something, under your key. A document a colleague shared with you is not in your index until you touch it, and files that arrive through an anonymous upload link are not indexed at all, because the uploader never had your key.
• Scanned PDFs are pictures. No text, no tokens. Optical character recognition on the device would fix this and is a candidate for the same on-device approach we use for summaries and translation.

Why this trade-off

We could offer no content search and leak nothing, or server-side search and leak everything. Blind indexing sits in between: you get the search people actually use, and the server gets the shape of your vocabulary, not the vocabulary. For an organisation whose threat model is “the provider must not be able to read our documents”, that is the right point, and it is the one every serious encrypted product that offers search ends up at.

What matters is that the shape is documented. The security overview lists blinded search tokens among the things our servers can see, and this article is the longer version of that line.

Questions?

If you want to discuss how search leakage fits your own threat model, or your security team wants the exact tokenisation rules and the index schema, get in touch at hello@nomadvault.de.