Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely
access untrusted memory, such that the access patterns reveal nothing about sensitive data.
ORAM is known to have broad applications in secure processor design and secure multi-party
computation for big data. Unfortunately, due to a well-known logarithmic lower bound by
Goldreich and Ostrovsky (Journal of the ACM, \'96), ORAM is bound to incur a moderate cost
in practice. In particular, with the latest developments in ORAM constructions, we are quickly
approaching this limit, and the room for performance improvement is small.
In this paper, we consider new models of computation in which the cost of obliviousness
can be fundamentally reduced in comparison with the standard ORAM model. We propose
the Oblivious Network RAM model of computation, where a CPU communicates with multiple
memory banks, such that the adversary observes only which bank the CPU is communicating
with, but not the address offset within each memory bank. In other words, obliviousness within
each bank comes for free--either because the architecture prevents a malicious party from ob-
serving the address accessed within a bank, or because another solution is employed to obfuscate
memory accesses within each bank--and hence we only need to obfuscate the communication
patterns between the CPU and the memory banks. We present several new constructions for
obliviously simulating general or parallel programs in the Network RAM model. We describe
applications of the Network RAM model in secure processor design and in distributed storage
applications with a network adversary.