Towards Practical Oblivious RAM

By Emil Stefanov, Elaine Shi, Dawn Song. Network and Distributed System Security Symposium, 2011

370 citations recorded by the source corpus.

We take an important step forward in making Oblivious RAM (O-RAM) practical. We propose an O-RAM construction achieving an amortized overhead of 20X-35X (for an O-RAM roughly 1 terabyte in size), about 63 times faster than the best existing scheme. On the theoretic front, we propose a fundamentally novel technique for constructing Oblivious RAMs: specifically, we partition a bigger O-RAM into smaller O-RAMs, and employ a background eviction technique to obliviously evict blocks from the client-side cache into a randomly assigned server-side partition. This novel technique is the key to achieving the gains in practical performance.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/b02ac02e19aa1fe2dca6afde5ca6d2d703a8b995

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors (2018, background): “Existing ORAM constructions incur sublinear overhead by using specialized data structures and re-arranging the external memory [26, 29, 46, 51, 54, 28].”
Privacy and Access Control for Outsourced Personal Records (2015, background): “While a few ORAM constructions guarantee the integrity of user data [46], [47], none of them is suitable to share data with potentially distrustful clients.”
Opaque: An Oblivious and Encrypted Distributed Analytics Platform (2017, background): “Oblivious RAM [13, 37, 38, 36] is a cryptographic construct for protecting against access pattern leakage.”
Blurry-ORAM: A Multi-Client Oblivious Storage Architecture (2016, methodology): “In order to save space, in ORAM constructions that use a position map, such as [16,13,14,15], the position map is stored recursively on the server, in smaller ORAMs, ORAM1, .”
Dynamic Searchable Encryption via Blind Storage (2014, background): “A Blind Storage scheme lets the client keep all information — including the number and size — about files secret from the server storing them, until they are accessed.”
Oblivious RAM with O((logN)3) Worst-Case Cost (2011, methodology): “Apart from this, Stefanov, Shi, and Song also offered another construction geared towards practical performance rather than asymptotics.”
MU-ORAM: Dealing with Stealthy Privacy Attacks in Multi-User Data Outsourcing Services (2016, methodology): “2 Single-user and Multiple-server ORAM As it is popular for a user to utilize multiple cloud servers simultaneously, some ORAM constructions [22, 34, 36] were proposed based on the idea of having two or more cloud servers to store the data and collaborate in performing data shuffling.”
Parallel and Dynamic Searchable Symmetric Encryption (2013, background): “Finally, while a recently introduced ORAM scheme [19] has been shown to be relatively practical, it still requires O( √ n) storage at the client.”
Path ORAM: an extremely simple oblivious RAM protocol (2012, methodology): “We adopt the standard security definition for ORAMs from [29].”
Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound (2015, methodology): “Based on a standard trick [48, 51, 52], we can recursively store the position map on the server.”
Secure two-party computation in sublinear (amortized) time (2012, background): “Oblivious RAM was introduced in [7], and in the past few years several improved constructions have been proposed (c.f. [21, 22, 18, 8, 9, 13, 19, 20]).”
Scalable and Private Media Consumption with Popcorn (2016, background): “Oblivious RAM (ORAM) [49, 69, 71, 94] algorithms allow a client to conceal its access patterns from a storage server.”
Practical Dynamic Searchable Encryption with Small Leakage (2014, background): “, [32], [34], [35] rely on the block sizes being relatively large (e.”
Efficient Private File Retrieval by Combining ORAM and PIR (2014, background): “NDSS ’14, 23-26 February 2014, San Diego, CA, USA Copyright 2014 Internet Society, ISBN 1-891562-35-5 http://dx.doi.org/ of increasing client memory from constant to logarithmic [18] or polynomial [16, 17] in N .”
Data-oblivious graph algorithms for secure computation and outsourcing (2013, background): “There is a renewed interest in ORAM due to the emergence of cloud computing and storage services, and recent results include [39, 40, 34, 1, 17, 27, 7, 36, 37, 29].”
The Melbourne Shuffle: Improving Oblivious Storage in the Cloud (2014, methodology): “Other oblivious storage solutions in [21, 22, 23] allow the user to have o(n) private memory and then by applying the same solution recursively on this private memory bring it to o(1) and adding a log n overhead.”
Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation (2014, background): “RAM move it further towards practicality [11], [20], but it is far from clear that they are competitive with SSE schemes at scale as one must implement the plaintext searching as an abstract RAM program and then run this program underneath the ORAM scheme without leaking information, say, via timing”