Zhiqiang Wu (Changsha University of Science and Technology), Rui Li (Dongguan University of Technology)

Dynamic searchable encryption (DSE) is a user-cloud protocol for searching over outsourced encrypted data. Many current DSE schemes resort to oblivious RAMs (ORAM) to achieve forward privacy and backward privacy, which is a concept to describe security levels of the protocol. We show that, however, most prior ORAM-based DSE suffers from a new problem: it is inefficient to fetch/insert a large set of data blocks. We call this the large-stash eviction problem. To address the problem, we present OBI, a multi-path Oblivious RAM, which accesses multiple tree paths per query for handling a large set of data blocks. We classify traditional tree-based ORAMs as single-path ORAMs if they access a single path per query. OBI has two new high-throughtput multi-path eviction algorithms that are several orders of magnitude more efficient than the well-known PATH-ORAM eviction algorithm when the stash is large. We prove that the proposed multi-path ORAM outperforms the traditional single-path ORAM in terms of local stash size and insertion efficiency. Security analysis shows that OBI is secure under the strong forward and backward security model. OBI can protect the well-known DSE leakage, such as the search pattern and the size pattern. We also show that OBI can be applied to oblivious file systems and oblivious conjunctive-query DSE schemes. We conduct experiments on the Enron dataset. The experimental results demonstrate that OBI is far more efficient than the state-of-the-art ORAM-based DSE schemes.

View More Papers

dewolf: Improving Decompilation by leveraging User Surveys

Steffen Enders, Eva-Maria C. Behner, Niklas Bergmann, Mariia Rybalka, Elmar Padilla (Fraunhofer FKIE, Germany), Er Xue Hui, Henry Low, Nicholas Sim (DSO National Laboratories, Singapore)

Read More

Analysing Adversarial Threats to Rule-Based Local-Planning Algorithms for Autonomous...

Andrew Roberts (Tallinn University of Technology), Mohsen Malayjerdi (Tallinn University of Technology), Mauro Bellone (Tallinn University of Technology), Olaf Maennel (The University of Adelaide), Ehsan Malayjerdi (Tallinn University of Technology)

Read More

Attacks as Defenses: Designing Robust Audio CAPTCHAs Using Attacks...

Hadi Abdullah (Visa Research), Aditya Karlekar (University of Florida), Saurabh Prasad (University of Florida), Muhammad Sajidur Rahman (University of Florida), Logan Blue (University of Florida), Luke A. Bauer (University of Florida), Vincent Bindschaedler (University of Florida), Patrick Traynor (University of Florida)

Read More

Tag of the Dead: How Terminated SaaS Tags Become...

Takahito Sakamoto, Takuya Murozono (DataSign Inc)

Read More