PRO-ORAM: Practical Read-Only Oblivious RAM

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.