Obfuscated Access and Search Patterns in Searchable Encryption
Zhiwei Shang, Simon Oya, Peter Andreas, Florian Kerschbaum · 2021
Even though the content of the queries and the documents are encrypted, during this interaction the server learns which documents are accessed, i.e., the access pattern, and which queries are equal, i.e., the search pattern.Most existing SSE schemes [7], [9], [12], [21]-[23], [33] allow such leakage for performance considerations.However, recent studies [8], [20], [39] demonstrated that, with some prior knowledge of the outsourced database or a subset of the queries, an honest-butcurious server can recover the underlying keywords of queries with high accuracy, which violates the client's privacy.There are different techniques that allow enhancing the privacy properties of SSE schemes, but they incur an utility cost which is typically a combination of communication overhead, extra computational complexity, and local client storage requirements.Certain schemes, like those based on Oblivious RAM (ORAM) [19] or Private Information Retrieval (PIR) [11], can fully hide the access pattern when reading a document from a database.However, they incur a large communication and computation overhead, respectively, and are not specifically designed towards securely searching over an encrypted database (except for TWORAM [17]).A recent framework by Chen et al. [10] protects access-pattern leakage in SSE by obfuscating the index of the database before outsourcing it.This way, the server only learns obfuscated access patterns, making it harder to successfully carry out attacks on the client's privacy from such leakage.However, despite its efficiency, this framework cannot hide search patterns since the access pattern for each keyword is determined after outsourcing.This search pattern leakage allows different practical attacks [20], [27], [31] to perform remakably well regardless of the access pattern obfuscation (see Sect.IX).Motivated by this vulnerability of Chen et al.'s scheme [10], in this work we propose OSSE (Obfuscated SSE), a new SSE scheme that protects both the access and search patterns.The main idea behind OSSE is that it produces a fresh obfuscation per query, instead of just once when outsourcing the database, thus making it hard for the server to decide whether or not two queries are for the same keyword.Our scheme allows to perform queries on the encrypted database and receive the matched documents in the same communication round (TWORAM requires at least four rounds [17]).Under some reasonable assumptions on the query and database distribution, OSSE achieves a lower communication overhead than TWORAM (e.g., only a small constant when the keyword distribution is uniform).Our scheme relies on computationheavy cryptographic techniques and thus its computational cost is considerable (e.g., it can require 30 minutes to run a query Abstract-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 always produces the same obfuscated access pattern when querying for the same keyword, and thus 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.Given certain reasonable assumptions on the database and query distribution, 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.