Cryptology ePrint Archive: Report 2015/668

The Fallacy of Composition of Oblivious RAM and Searchable Encryption

Muhammad Naveed

Abstract: 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.

Category / Keywords: cryptographic protocols / Oblivious RAM, Symmetric Searchable Encryption

Date: received 3 Jul 2015, last revised 5 Jul 2015

Contact author: naveed2 at illinois edu

Available format(s): PDF | BibTeX Citation

Version: 20150705:185739 (All versions of this report)

Short URL: ia.cr/2015/668

Discussion forum: Show discussion | Start new discussion