Paper 2015/668

The Fallacy of Composition of Oblivious RAM and Searchable Encryption

Muhammad Naveed


Oblivious RAM (ORAM) is a tool proposed to hide access pattern leakage, and there has been a lot of progress in the efficiency of ORAM schemes; however, less attention has been paid to study the applicability of ORAM for cloud applications such as symmetric searchable encryption (SSE). Although, searchable encryption is one of the motivations for ORAM research, no in-depth study of the applicability of ORAM to searchable encryption exists as of June 2015. In this work, we initiate the formal study of using ORAM to reduce the access pattern leakage in searchable encryption. We propose four new leakage classes and develop a systematic methodology to study the applicability of ORAM to SSE. We develop a worst-case communication baseline for SSE. We show that completely eliminating leakage in SSE is impossible. We propose single keyword schemes for our leakage classes and show that either they perform worse than streaming the entire outsourced data (for a large fraction of queries) or they do not provide meaningful reduction in leakage. We present detailed evaluation using the Enron email corpus and the complete English Wikipedia corpus.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Oblivious RAMSymmetric Searchable Encryption
Contact author(s)
naveed2 @ illinois edu
2015-07-05: revised
2015-07-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Muhammad Naveed},
      title = {The Fallacy of Composition of Oblivious RAM and Searchable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2015/668},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.