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

Cybersecurity of COSPAS-SARSAT and EPIRB: threat and attacker models,...

Andrei Costin, Hannu Turtiainen, Syed Khandkher and Timo Hamalainen (Faculty of Information Technology, University of Jyvaskyla, Finland) Presenter: Andrei Costin

Read More

The “Beatrix” Resurrections: Robust Backdoor Detection via Gram Matrices

Wanlun Ma (Swinburne University of Technology), Derui Wang (CSIRO’s Data61), Ruoxi Sun (The University of Adelaide & CSIRO's Data61), Minhui Xue (CSIRO's Data61), Sheng Wen (Swinburne University of Technology), Yang Xiang (Digital Research & Innovation Capability Platform, Swinburne University of Technology)

Read More

The Vulnerabilities Less Exploited: Cyberattacks on End-of-Life Satellites

Frank Lee and Gregory Falco (Johns Hopkins University) Presenter: Frank Lee

Read More

BEAGLE: Forensics of Deep Learning Backdoor Attack for Better...

Siyuan Cheng (Purdue University), Guanhong Tao (Purdue University), Yingqi Liu (Purdue University), Shengwei An (Purdue University), Xiangzhe Xu (Purdue University), Shiwei Feng (Purdue University), Guangyu Shen (Purdue University), Kaiyuan Zhang (Purdue University), Qiuling Xu (Purdue University), Shiqing Ma (Rutgers University), Xiangyu Zhang (Purdue University)

Read More