Vivek’s Soapbox

In the wake of the debate over storing all our documents on Google’s servers to enable their “search across computers” feature, I went around digging for cryptographic techniques that enable indexing and searching data on a remote server, without the server learning anything about the documents or the queries.

Here are some links:

A comprehensive survey of secure indexing techniques.

A secure index is a data structure that allows a querier with a “trapdoor” for a word x
to test in O(1) time only if the index contains x; The index reveals no information about its
contents without valid trapdoors, and trapdoors can only be generated with a secret key. Secure
indexes allow a querier to check if a document contains a keyword without having to decrypt the
entire document

Searching Encrypted Data, by Song, Wagner and Perrig

In this paper, we describe our cryptographic schemes
for the problem of searching on encrypted data and provide
proofs of security for the resulting crypto systems. Our
techniques have a number of crucial advantages. They are
provably secure: they provide provable secrecy for encryption,
in the sense that the untrusted server cannot learn
anything about the plaintext when only given the ciphertext;
they provide query isolation for searches, meaning
that the untrusted server cannot learn anything more about
the plaintext than the search result; they provide controlled
searching, so that the untrusted server cannot search for an
arbitrary word without the user’s authorization; they also
support hidden queries, so that the user may ask the untrusted
server to search for a secret word without revealing
the word to the server.

So what’s holding back the application of these techniques in the real world? The scenarios for their use are extremely compelling, more today than ever.

Thanks to our resident database and security expert, Einar Mykletun, for the pointers.