Oblivious RAM Revisited

By Benny Pinkas, Tzachy Reinman. Annual International Cryptology Conference, 2010

343 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/7bf657b1720b751f82d84c06dee119725b7c5369

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

Citations in the corpus

Privacy-Preserving Computation with Trusted Computing via Scramble-then-Compute (2017, methodology): “ORAM techniques [32, 9, 20] trust a CPU with limited internal memory, while storing user programs and data encrypted on the untrusted server.”
Towards Practical Oblivious RAM (2011, methodology): “Pinkas et al. gave an example [13]: if a sequence of data access requests q1, q2, q3 is always followed by a stock exchange operation, the server can gain sensitive information even when the data is encrypted.”
Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound (2015, background): “In addition to the aforementioned lower bound, Goldreich and Ostrovsky were the ﬁrst to propose a poly-logarithmic hierarchical construction, which was subsequently improved in numerous works [6, 16, 18, 20–23, 31, 34, 35, 41–43, 53–56].”
Path ORAM: an extremely simple oblivious RAM protocol (2012, positive): “Since then, there has been much subsequent work [4, 6, 7, 12–16,18,23, 26–28,36,38] devoted to improving ORAM constructions.”
Privacy and Access Control for Outsourced Personal Records (2015, background): “Indeed, as shown in the literature [1], [2], the capability to link consecutive accesses to the same file can be exploited by the server to learn sensitive information: for instance, it has been shown that the access patterns to a DNA sequence allow for determining the patient’s disease.”
Dynamic Searchable Encryption via Blind Storage (2014, background): “However, this solution remains very inefficient for several important applications, despite significant recent improvements [22], [26], [25].”
Oblivious RAM with O((logN)3) Worst-Case Cost (2011, methodology): “OS [13] O((logN) (3)) O((logN)(3)) O(1) O(N logN) (const > 6100) (const > 6100) WS [18] O((logN)(2)) O(N logN) O( √ N) O(N logN) WSC [19] O(logN log logN) O(N log logN) O( √ N) O(N) PR [14] O((logN)(2)) O(N logN) O(1) O(N)”
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.”
Communication-Computation Trade-offs in PIR (2019, methodology): “Unlike PSI and ORAM, we don’t need to provide privacy for the server’s database in PIR.”
Secure two-party computation in sublinear (amortized) time (2012, methodology): “Several more-recent ORAM solutions [18, 8, 9, 13] rely on cuckoo hashing (in addition to also using PRF computations).”
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): “The hierarchical method was recently extended using techniques such as Bloom filters [25, 26] and cuckoo hash tables [9, 13, 18, 20].”
Invertible bloom lookup tables (2011, methodology): “ would either require storing results back with Bob in a way that could reveal selected indices or using yet another server besides Bob. She could use techniques from recent oblivious RAM simulations [19, 20, 31] to obfuscate her access patterns, but doing so would require O(nlog2 n) I/Os. Therefore”
Efficient Private File Retrieval by Combining ORAM and PIR (2014, methodology): “For example, Pinkas and Reinman [14] and Boneh et al. [3] have reduced amortized communication to poly-logarithmic complexity.”
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].”