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

摘要: Recent Searchable Symmetric Encryption (SSE) schemes enable secure searching over an encrypted database stored in a server while limiting the information leaked to server. These focus on hiding access pattern, which refers set of documents that match client's queries. This provides protection against current attacks largely depend this leakage succeed. However, most SSE constructions also leak whether or not two queries aim for same keyword, called search pattern. In work, we show pattern can severely undermine defenses. We propose attack leverages both and leakage, as well some background query distribution information, recover keywords performed by client. Our follows maximum likelihood estimation approach, is easy adapt defenses obfuscate empirically our efficient, it outperforms other proposed attacks, completely thwarts out three evaluate against, even when these are high privacy regimes. findings highlight feature lacking, key towards providing practical guarantees SSE.