2
$\begingroup$

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)?

$\endgroup$
  • 1
    $\begingroup$ Maybe it's me, but I don't understand what your question is. $\endgroup$ – Maeher Sep 11 at 7:27
  • 1
    $\begingroup$ If I understand correctly, you are talking about the Song works and it's variations. The idea, I think as you know, basically, extract the words from the text, encrypt each of them separately and search over them. With this, at least, you can execute SEARCH in databases as in CryptDB.With FHE, yes you can bu it will be terrible slow. $\endgroup$ – kelalaka Sep 11 at 7:55
  • $\begingroup$ @Maeher I want to ask that is there any paper of seachable encryption don't using keyword set ? $\endgroup$ – Sun_Piao Sep 17 at 2:15
  • $\begingroup$ @kelalaka yes, I am studying Song's paper. Therefore, does the speed is the main problem? My superior want to research on searching keyword on document but not using index. $\endgroup$ – Sun_Piao Sep 17 at 2:23
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. Your explanation is very clear! $\endgroup$ – Sun_Piao Sep 17 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.