Paper 2015/073

Oblivious Network RAM and Leveraging Parallelism to Achieve Obliviousness

Dana Dachman-Soled, Chang Liu, Charalampos Papamanthou, 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 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 oset within each memory bank. In other words, obliviousness within each bank comes for free either because the architecture prevents a malicious party from observing the address accessed within a bank, or because another solution is used to obfuscate memory accesses within each bank and hence we only need to obfuscate communication patterns between the CPU and the memory banks. We present new constructions for obliviously simulating general or parallel programs in the Network RAM model. We describe applications of our new model in secure processor design and in distributed storage applications with a network adversary.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
Keywords
ORAMparallel computing
Contact author(s)
danadach @ ece umd edu
History
2017-01-13: revised
2015-02-10: received
See all versions
Short URL
https://ia.cr/2015/073
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/073,
      author = {Dana Dachman-Soled and Chang Liu and Charalampos Papamanthou and Elaine Shi and Uzi Vishkin},
      title = {Oblivious Network {RAM} and Leveraging Parallelism to Achieve Obliviousness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/073},
      year = {2015},
      url = {https://eprint.iacr.org/2015/073}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.