Hiding the Access Pattern is Not Enough: Exploiting Search Pattern\n Leakage in Searchable Encryption

Abstract

Recent Searchable Symmetric Encryption (SSE) schemes enable secure searching\nover an encrypted database stored in a server while limiting the information\nleaked to the server. These schemes focus on hiding the access pattern, which\nrefers to the set of documents that match the client's queries. This provides\nprotection against current attacks that largely depend on this leakage to\nsucceed. However, most SSE constructions also leak whether or not two queries\naim for the same keyword, also called the search pattern.\n In this work, we show that search pattern leakage can severely undermine\ncurrent SSE defenses. We propose an attack that leverages both access and\nsearch pattern leakage, as well as some background and query distribution\ninformation, to recover the keywords of the queries performed by the client.\nOur attack follows a maximum likelihood estimation approach, and is easy to\nadapt against SSE defenses that obfuscate the access pattern. We empirically\nshow that our attack is efficient, it outperforms other proposed attacks, and\nit completely thwarts two out of the three defenses we evaluate it against,\neven when these defenses are set to high privacy regimes. These findings\nhighlight that hiding the search pattern, a feature that most constructions are\nlacking, is key towards providing practical privacy guarantees in SSE.\n