Toward Practical Private Access to Data Centers via Parallel ORAM

Jacob R.  Lorch; Bryan Parno; James Mickens; Mariana Raykova; Joshua Schiffman

Paper 2012/133

Toward Practical Private Access to Data Centers via Parallel ORAM

Jacob R. Lorch, Bryan Parno, James Mickens, Mariana Raykova, and Joshua Schiffman

Abstract

Recent events have shown online service providers the perils of possessing private information about users. Encrypting data mitigates but does not eliminate this threat: the pattern of data accesses still reveals information. Thus, we present Shroud, a general storage system that hides data access patterns from the servers running it, protecting user privacy. Shroud functions as a virtual disk with a new privacy guarantee: the user can look up a block without revealing the block's address. Such a virtual disk can be used for many purposes, including map lookup, microblog search, and social networking. Shroud aggressively targets hiding accesses among hundreds of terabytes of data. We achieve our goals by adapting oblivious RAM (ORAM) algorithms to enable large-scale parallelization. Specifically, we show, via new techniques such as oblivious aggregation, how to securely use many inexpensive secure coprocessors acting in parallel to improve request latency. Our evaluation combines large-scale emulation with an implementation on secure coprocessors and suggests that these adaptations bring private data access closer to practicality.

Note: Updated with additional proofs and empirical results.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. An abridged version appears in the Proceedings of the USENIX Conference on File and Storage Technologies (FAST), 2013
Keywords: Oblivious RAM ORAM Parallelism Secure Hardware Implementation
Contact author(s): parno @ microsoft com
History: 2013-01-17: last of 2 revisions; 2012-03-21: received; See all versions
Short URL: https://ia.cr/2012/133
License: CC BY

BibTeX

@misc{cryptoeprint:2012/133,
      author = {Jacob R.  Lorch and Bryan Parno and James Mickens and Mariana Raykova and Joshua Schiffman},
      title = {Toward Practical Private Access to Data Centers via Parallel {ORAM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/133},
      year = {2012},
      url = {https://eprint.iacr.org/2012/133}
}