  Searchable Symmetric Encryption (SSE) allows a data owner to securely
outsource its encrypted data to a cloud server while maintaining the ability to
search over it and retrieve matched documents. Most existing SSE schemes leak
which documents are accessed per query, i.e., the so-called access pattern, and
thus are vulnerable to attacks that can recover the database or the queried
keywords. Current techniques that fully hide access patterns, such as ORAM or
PIR, suffer from heavy communication or computational costs, and are not
designed with search capabilities in mind. Recently, Chen et al. (INFOCOM'18)
proposed an obfuscation framework for SSE that protects the access pattern in a
differentially private way with a reasonable utility cost. However, this scheme
leaks the so-called search pattern, i.e., how many times a certain query is
performed. This leakage makes the proposal vulnerable to certain database and
query recovery attacks.
  In this paper, we propose OSSE (Obfuscated SSE), an SSE scheme that
obfuscates the access pattern independently for each query performed. This in
turn hides the search pattern and makes our scheme resistant against attacks
that rely on this leakage. Under certain reasonable assumptions, our scheme has
smaller communication overhead than ORAM-based SSE. Furthermore, our scheme
works in a single communication round and requires very small constant
client-side storage. Our empirical evaluation shows that OSSE is highly
effective at protecting against different query recovery attacks while keeping
a reasonable utility level. Our protocol provides significantly more protection
than the proposal by Chen et al.~against some state-of-the-art attacks, which
demonstrates the importance of hiding search patterns in designing effective
privacy-preserving SSE schemes.
