Abstract
Searchable encryption (SE) provides a privacy-preserving mechanism for data users to search over encrypted data stored on a remote server. Researchers have designed a number of SE schemes with high efficiency yet allowing some degree of leakage profile to the remote server. The leakage, however, should be further measured to allow us to understand what types of attacks an SE scheme would encounter. This paper considers passive attacks that make inferences based on prior knowledge and observations on queries issued by users. This is in contrast to previously studied active attacks that adaptively inject files and queries. We consider several assumptions on the types or prior knowledge the attacker possessed and propose a few passive attacks. In particular, under the “full-fledged” assumption, the keyword recovery rate of our attack is optimal in the sense that it is equal to the theoretical upper bound. We further present several enhanced attacks under other weaker assumptions on various levels of the prior knowledge that the attacker can obtain, in which the keyword recovery rates are optimal or nearly optimal (i.e., approaching the theoretical upper bound). In addition, we provide extensive experiments to show the “power” of our passive attacks. This paper highlights the importance of minimizing the prior knowledge of a server and the leakage of search queries. It also shows that simply distorting the frequency of the keyword to hold against our passive attacks may not scale well.