The value of many cloud services lies in the ability to operate on client's data. Typical examples include data storage, webmail service, advertising, geolocation services, etc. However, the need to access client's data, e.g., files, email, location is often at odds with clients' data privacy needs, which require encryption to protect their data. Reconciling these contradictory requirements, and achieving computation on encrypted data, is an important research and engineering problem.
We focus here on the specific case of indexing and searching on documents. Typically to perform a search on a set of documents, one creates an index of keywords included in the documents and later on performs the search on the index. This does not raise major issues if the querier, who is defined as the one who requests the search, and the storage provider, who is defined as the one who stores the documents and the index and who actually performs the search and returns the result, fully trust each other. The difficulties arise when the querier wants to protect the privacy of its data and store the documents as well as the indexes encrypted, and send encrypted queries as well. In that case, it would be advantageous to be able to perform encrypted searches on a collection of encrypted documents. And more precisely, it would be advantageous to be able to perform all kind of encrypted searches on a collection of encrypted documents, including any Boolean search, such as conjunctive, disjunctive and negative searches.
By “disjunctive search”, we mean a search allowing the user to search for encrypted documents containing word1 or word2 . . . or wordn. By “conjunctive search”, we mean a search allowing the user to search for the encrypted documents containing: “word1 and word2 . . . and wordn”. By “negative search”, we mean a search allowing the user to search for all encrypted documents which do not contain one or several particular words.
Currently, there is no solution enabling to perform Boolean search on encrypted data, i.e. conjunctive, disjunctive and negation search option at the same time.