International Association
for Cryptologic Research

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.