Cryptology ePrint Archive: Report 2015/073

Oblivious Network RAM

Dana Dachman-Soled and Chang Liu and Charalampos Papamanthou and Elaine Shi and Uzi Vishkin

Abstract: 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.

Category / Keywords: oblivious RAM, parallel computing

Date: received 1 Feb 2015, last revised 2 Feb 2015

Contact author: elaine at cs umd edu

Available format(s): PDF | BibTeX Citation

Version: 20150210:050840 (All versions of this report)

Short URL: ia.cr/2015/073

Discussion forum: Show discussion | Start new discussion