Security of Searchable Encryption

Searchable encryption is a class of encryption schemes that allows the users to store their data on a remote server and search over it securely. Conventional encryption schemes are too strong in terms of their security properties (indistinguishability under chosen plaintext attack) such that searching over encrypted data is inefficient. Researchers have proposed schemes that support searching functionalities at the cost of some security - the adversary in the security model can learn (at most) a function of the database, where the function should not contain any crucial information about the database (e.g. total number of documents, total number of keywords, volumes of queries, etc). Recent attacks have shown that some of the functions that are assumed to be harmless can be exploited to recover important information of the underlying databases. We begin by studying the gap between the security notions and the attacks: why attacks are possible even when the schemes are proven secure under the security notions. Then we propose new security notions that can be used to argue that a scheme is secure against classes of attacks. Finally, we propose efficient constructions of searchable encryption that support various searching functionalities and are secure under our security notions.