Why use indexing for searchable encryption?

Question

Searchable encryption can be separated into sequential scan and indexing. Besides increasing search speed, why do we use indexing in searchable encryption?

As an end-user, we do not usually make a keyword list of our document. So, if we don't build an index for our document, is there a method to do searchable encryption (which considers the full text)?

Answer 1

It is mainly to make the search operation more efficient. In searchable encryption, mostly invert index is used. It is a data structure that stores mapping from words to documents or set of documents i.e. directs you from word to document, e.g. something like:

word 1: {doc1, doc2, doc3}

word 2: {doc1, doc3}

word 2: {doc1}

The earliest searchable encryption scheme searches data by sequentially scanning through all encrypted documents. This is not scalable. For example, if you have 10 document and each has 10,000 words in it, then you need to scan through 100,000 encrypted words. For each encrypted word, the comparison operation is cryptographic and is slow (compared to that in plaintext). If you have a large amount of data, you probably will get your results hours later after you submitted your query.

However, the number of distinct words in the documents probably is not very big (say 5,000), and does not increase with the amount of your data. Therefore, using indexes is a natural choice because now you only need to search through the index, and perform comparison operation in the number of distinct words (or even less) to find which entry in the index corresponds to your query, and then you can find the list of documents that contain the word you queried by retrieving and decrypting the list (this part requires additional cryptographic operations, with the number linear in the size of the list). But anyway, this is more scalable and allows searchable encryption to handle very large datasets.

Nowadays, mainstream searchable encryption schemes all use some sort of indexes. Of course, the index structure and cryptographic comparison operation vary greatly from scheme to scheme, but the core idea is to make the search time sublinear in the size of encrypted data.