Towards a theory of software protection and simulation by oblivious RAMs

By Oded Goldreich. 1987

How researchers see this paper

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

Citations in the corpus

Private Stateful Information Retrieval (2018, background): “To retrieve/overwrite a record, the client performs a protocol with all non-colluding servers to generate an access to the shared ORAM scheme.”
HOP: Hardware makes Obfuscation Practical (2017, methodology): “For performance, our HOP prototype uses a hardwareoptimized Oblivious RAM, on-chip memory and instruction scheduling (our current implementation does not yet support context switching).”
Covert and Side Channels Due to Processor Architecture (2006, background): “The control flow information leakage problem due to the exposure of address traces on the system memory bus is studied in [21][24].”
Oblivious RAM Revisited (2010, methodology): “The original Goldreich-Ostrovsky construction uses a sorting network for this purpose, but this solution has an overhead of O(n log 2 n) comparisons, with a very small constant, using Batcher's network [5], or O(n log n) comparisons, with a constant of about 6100, using the AKS network [2].”
Foundations of Cryptography: Volume 1, Basic Tools (2001, unknown): “First applications of pseudorandom functions were given in [103, 89, 90], and the list of applications has been rapidly growing since.”
Multi-client Oblivious RAM Secure Against Malicious Servers (2017, methodology): “We start by transforming two classical ORAM constructions, the original square-root solution by Goldreich [7] and the hierarchical one by Goldreich and Ostrovsky [8], into multi-client secure versions, retaining the same communication complexity per client.”
Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound (2015, background): “The original ORAM model proposed by Goldreich and Ostrovsky assumes a passive server (or memory) that does not perform computation.”
Path ORAM: an extremely simple oblivious RAM protocol (2012, background): “We consider a client that wishes to store data at a remote untrusted server while preserving its privacy.”
Pseudorandom Functions: Three Decades Later (2017, methodology): “PRFs have been applied to achieve resettable security in protocols [50, 18], to hide memory access patterns in oblivious RAM [62, 68], and to bootstrap fully homomorphic and functional encryption schemes [9, 8].”
Towards Practical Oblivious RAM (2011, methodology): “Oblivious RAM (or O-RAM) [3, 4, 11], first investigated by Goldreich and Ostrovsky, is a primitive intended for hiding storage access patterns.”
Generic Attacks on Secure Outsourced Databases (2016, background): “…can be applied to this problem, ranging from solutions based on tools such as fully homomorphic encryption (FHE) [20, 46] or oblivious RAM (ORAM) [23, 25] to more practical solutions based on weaker primitives such as structural encryption [33] or deterministic and order-preserving encryption…”
What serverless computing is and should become (2021, unknown): “12 Programming languages.”
Private Anonymous Data Access (2019, background): “The square-root ORAM scheme [Gol87,GO96] can be modiﬁed to have this property, but the overall client/server eﬃciency in the ﬁnal solutions would be at least square-7 root of the data size.”
The Melbourne Shuffle: Improving Oblivious Storage in the Cloud (2014, methodology): “In seminal work motivated by a software protection application, Goldreich and Ostrovsky [5, 6] give two oblivious storage solutions for a client with O(1) private memory size: the square root method with O( √ n) overhead and the hierarchical method with O((log n)3) overhead.”
Oblivious RAM with O((logN)3) Worst-Case Cost (2011, methodology): “The standard O-RAM adopted in prior work [5, 7, 14, 18] exports a Read and a Write interfaces.”