Anrin Chakraborti (Stony Brook University), Adam J. Aviv (United States Naval Academy), Seung Geol Choi (United States Naval Academy), Travis Mayberry (United States Naval Academy), Daniel S. Roche (United States Naval Academy), Radu Sion (Stony Brook University)

Oblivious RAM protocols (ORAMs) allow a client to access data from an untrusted storage device without revealing to that device any information about their access pattern. Typically this is accomplished through random shuffling of the data such that the storage device cannot determine where individual blocks are located, resulting in a highly randomized access pattern. Storage devices however, are typically optimized for sequential access. A large number of random disk seeks during standard ORAM operation induce a substantial overhead.

In this paper, we introduce rORAM, an ORAM specifically suited for accessing ranges of sequentially logical blocks while minimizing the number of random physical disk seeks. rORAM obtains significantly better asymptotic efficiency than prior designs (Asharov et al., ePrint 2017, Demertzis et al., CRYPTO 2018) reducing both the number of seeks and communication complexity by a multiplicative factor of $mathbb{O}(log N)$. An rORAM prototype is 30-50x times faster than Path ORAM for similar range-query workloads on local HDDs, 30x faster for local SSDs, and 10x faster for network block devices. rORAM's novel disk layout can also speed up standard ORAM constructions, e.g., resulting in a 2x faster Path ORAM variant. Importantly, experiments demonstrate suitability for real world applications -- rORAM is up to 5x faster running a file server and up to 11x faster running a range-query intensive video server workloads compared to standard Path ORAM.

View More Papers

Measurement and Analysis of Hajime, a Peer-to-peer IoT Botnet

Stephen Herwig (University of Maryland), Katura Harvey (University of Maryland, Max Planck Institute for Software Systems (MPI-SWS)), George Hughey (University of Maryland), Richard Roberts (University of Maryland, Max Planck Institute for Software Systems (MPI-SWS)), Dave Levin (University of Maryland)

Read More

Practical Hidden Voice Attacks against Speech and Speaker Recognition...

Hadi Abdullah (University of Florida), Washington Garcia (University of Florida), Christian Peeters (University of Florida), Patrick Traynor (University of Florida), Kevin R. B. Butler (University of Florida), Joseph Wilson (University of Florida)

Read More

IoTGuard: Dynamic Enforcement of Security and Safety Policy in...

Z. Berkay Celik (Penn State University), Gang Tan (Penn State University), Patrick McDaniel (Penn State University)

Read More

NoDoze: Combatting Threat Alert Fatigue with Automated Provenance Triage

Wajih Ul Hassan (NEC Laboratories America, Inc.; University of Illinois at Urbana–Champaign), Shengjian Guo (Virginia Tech), Ding Li (NEC Laboratories America, Inc.), Zhengzhang Chen (NEC Laboratories America, Inc.), Kangkook Jee (NEC Laboratories America, Inc.), Zhichun Li (NEC Laboratories America, Inc.), Adam Bates (University of Illinois at Urbana–Champaign)

Read More