Searchable Encryption Supporting General Boolean Expression Queries

Searchable encryption is a mechanism that allows a user to store encrypted documents in an outsourced server, and later on query for some of these documents that match a given keyword. All these operations are performed with encrypted data, meaning both the documents and the queries are encrypted in such a way as to minimize leaked information: the server is considered to be semi-honest or honest-but-curious. Searchable encryption is an active research area and has witnessed several interesting schemes since the beginning of the 2000's, and in particular Curtmola et al. presented a construction which is asymptotically optimal with respect to search complexity. However, most prior works focused only on single keyword query and thus single keyword searches. We target a more general model, which encompasses all basic boolean searches -the disjunction, the conjunction and the negation- over encrypted data. The disjunctive search allows the user to search for encrypted documents containing word1 or word2 ... or wordn. The conjunctive search allows the user to search for the encrypted documents containing: "word1 and ... and wordn" and finally the negative search allows the user to search for all encrypted documents which do not contain a given keyword. To the best of our knowledge, there are no previous solutions in the literature supporting boolean searches on encrypted data, i.e. conjunctive, disjunctive and negation search operations at the same time. We propose a first construction of searchable encryption that supports generic boolean search over encrypted data. It is based on an original idea of considering keywords as vectors and using the Gram-Schmidt process to orthogonalize and then orthonormalize them. It further makes use of a very efficient operation, the inner product, to perform searches at the server side. The inner product indeed leverages the orthonormalized keywords to efficiently test if a boolean expression query matches the label corresponding to an encrypted document or not. The orthonormalized keywords are salted and the queries sent for retrieving encrypted documents are further randomized to guarantee the security of our scheme.