PRO-ORAM: Practical Read-Only Oblivious RAM

Authors: 

Shruti Tople, Microsoft; Yaoqi Jia, Ziliqa Research; Prateek Saxena, NUS

Abstract: 

Oblivious RAM is a well-known cryptographic primitive to hide data access patterns. However, the best known ORAM schemes require a logarithmic computation time in the general case which makes it infeasible for use in real-world applications. In practice, hiding data access patterns should incur a constant latency per access.

In this work, we present PRO-ORAM—an ORAM construction that achieves constant latencies per access in a large class of applications. PRO-ORAM theoretically and empirically guarantees this for read-only data access patterns, wherein data is written once followed by read requests. It makes hiding data access pattern practical for read-only workloads, incurring sub-second computational latencies per access for data blocks of 256 KB, over large (gigabyte-sized) datasets. PRO-ORAM supports throughputs of tens to hundreds of MBps for fetching blocks, which exceeds network bandwidth available to average users today. Our experiments suggest that dominant factor in latency offered by PRO-ORAM is the inherent network throughput of transferring final blocks, rather than the computational latencies of the protocol. At its heart, PRO-ORAM utilizes key observations enabling an aggressively parallelized algorithm of an ORAM construction and a permutation operation, as well as the use of trusted computing technique (SGX) that not only provides safety but also offers the advantage of lowering communication costs.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {242036,
author = {Shruti Tople and Yaoqi Jia and Prateek Saxena},
title = {PRO-ORAM: Practical Read-Only Oblivious {RAM}},
booktitle = {22nd International Symposium on Research in Attacks, Intrusions and Defenses ({RAID} 2019)},
year = {2019},
isbn = {978-1-939133-07-6},
address = {Chaoyang District, Beijing},
pages = {197--211},
url = {https://www.usenix.org/conference/raid2019/presentation/tople},
publisher = {{USENIX} Association},
month = sep,
}