Oblivious Network RAM∗

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.