Forward and Backward Private Conjunctive Searchable Symmetric Encryption

Consider, for instance, a client that offloads an encrypted database of (potentially sensitive) emails to an untrusted server. At a later point of time, the client might want to issue a query of the form “retrieve all emails received from xyz@foobar.org or “retrieve all emails with the keyword “research” in the subject field”. Ideally, the client should be able to perform this task without revealing any sensitive information to the server, such as the sources and contents of the emails, the keywords underlying a given query, the distribution of keywords across emails, etc. Unfortunately, techniques such as fully homomorphic encryption [19], that potentially allow achieving such an “ideal” notion of privacy, are unsuitable for practical deployment due to large performance overheads.