Oblivious RAM with O((logN)3) Worst-Case Cost

By Elaine Shi, T-H. Hubert Chan, Emil Stefanov, Mingfei Li. International Conference on the Theory and Application of Cryptology and Information Security, 2011

457 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

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 Computational Theory and Mathematics

Citations in the corpus

Solidus: Confidential Distributed Ledger Transactions via PVORM (2017, methodology): “This definition is an adaptive version of those presented in the ORAM literature [56, 58, 63].”
Efficient Private File Retrieval by Combining ORAM and PIR (2014, methodology): “[12] scheme has client memory independent of the block size, while Stefanov et al.”
Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound (2015, methodology): “4X improvement in terms of number of non-free gates [30] over a straightforward implementation of Path ORAM [52], 31X improvement over the binary-tree ORAM [48], and 5.”
ObliVM: A Programming Framework for Secure Computation (2015, methodology): “add function is a syntactic sugar for the ORAM’s Add interface [29], [42].”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “The probability of an overflow after k ORAM accesses with each node holding O(log( kN )) elements is shown by Shi et al. (2011) to be less than , which”
MU-ORAM: Dealing with Stealthy Privacy Attacks in Multi-User Data Outsourcing Services (2016, methodology): “To address this issue, various oblivious RAM (ORAM) constructions [13–17, 21, 29, 33, 34, 40, 42, 43] have been proposed to protect a user’s data access pattern against a semi-honest remote storage server, who honestly hosts the data and serves the user, but is curious to find out the data access pa”
Practical Dynamic Searchable Encryption with Small Leakage (2014, methodology): “Minimizing the leakage for DSSE can be achieved by using ORAM [3], [10], [13], [15], [17]–[19], [23]–[25], [27], [30], [35], [37], [38] to hide every memory access during searches and updates.”
Multi-client Oblivious RAM Secure Against Malicious Servers (2017, unknown): “[8] and Stefanov et al.”
HOP: Hardware makes Obfuscation Practical (2017, methodology): “If a tree-based ORAM [49] is used, after the first access, the block is remapped to a new path l′ and the new path l′ would be subsequently accessed.”
GraphSC: Parallel Secure Computation Made Easy (2015, background): “Section IV and Figure 5 later in the paper will elaborate on the details of our models and terminology.”
Obliv-C: A Language for Extensible Data-Oblivious Computation (2015, methodology): “Specifically, we show how a library can add ORAM functionalities to Yao's garbled circuits designed for semi-honest adversaries.”
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.”
Efficient, Oblivious Data Structures for MPC (2014, methodology): “[27] does not involve branching, it can be implemented in MPC with asymptotically the same number of memory accesses.”
Secure two-party computation in sublinear (amortized) time (2012, methodology): “[18], and using Yao’s garbled-circuit approach [22] for the secure two-party computation.”
Cloud Programming Simplified: A Berkeley View on Serverless Computing (2019, background): “. While the primary security concern is from external attackers, the network patterns can be protected from employees by adopting oblivious algorithms. Unfortunately, these tend to have high overhead [68]. 4.5 Computer architecture challenges Hardware Heterogeneity, Pricing, and Ease of Management: ”