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

Human Drivers' Situation Awareness of Autonomous Driving Under Physical-world...

Katherine S. Zhang (Purdue University), Claire Chen (Pennsylvania State University), Aiping Xiong (Pennsylvania State University)

Read More

POSE: Practical Off-chain Smart Contract Execution

Tommaso Frassetto (Technical University of Darmstadt), Patrick Jauernig (Technical University of Darmstadt), David Koisser (Technical University of Darmstadt), David Kretzler (Technical University of Darmstadt), Benjamin Schlosser (Technical University of Darmstadt), Sebastian Faust (Technical University of Darmstadt), Ahmad-Reza Sadeghi (Technical University of Darmstadt)

Read More

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

Formally Verified Software Update Management System in Automotive

Jaewan Seo, Jiwon Kwak, Seungjoo Kim (Korea University)

Read More