Analysis of Heuristic Based Access Pattern Obfuscation

As cloud computing becomes popular, the security and privacy issues emerge as important hindrances to more widespread adoption of cloud computing. In particular, outsourcing sensitive data to untrusted cloud service providers creates important security and regulatory compliance challenges. Encryption of the outsourced data has been introduced as an alternative to protect privacy and security. In the context of searchable symmetric encryption, many solutions have been proposed to perform efficient search on the encrypted outsourced data. Some of them achieve protecting privacy of outsourced data, but may disclose the access patterns. Recently, it has been shown that such access pattern disclosures could be exploited even further to infer sensitive information about underlying data, even if the data is stored in encrypted form. To address the access pattern disclosures, oblivious RAM and heuristic based techniques are proposed. However, the overhead of oblivious RAM based solutions is too high in many cases, and the security and scalability of heuristic based techniques have not been carefully analyzed yet. In this paper, we provide the first framework to analyze and compare the security and efficiency of such heuristics. In addition, we provide extensive empirical analysis that yields important insights into how to use such heuristics effectively in practice; and we discuss how such heuristics can be combined to improve security and efficiency.