Building castles out of mud: practical access pattern privacy and correctness on untrusted storage

By P. Williams, Radu Sion, Bogdan Carbunar. Conference on Computer and Communications Security, 2008

300 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems

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

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

In Information Systems

Citations in the corpus

Towards Practical Oblivious RAM (2011, background): “Since their original work, several seminal improvements have been proposed [5, 13, 15, 16].”
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].”
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]).”
Path ORAM: an extremely simple oblivious RAM protocol (2012, methodology): “…core of the Path ORAM algorithm can be described in just 16 lines of pseudocode (see Figure 1) and our construction does not require performing sophisticated deamortized oblivious sorting and oblivious cuckoo hash table construction like many existing ORAM algorithms [4, 7,12–17,22,25–27,35–37].”
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].”
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.”
Oblivious RAM Revisited (2010, methodology): “4 We assume here, as was implicitly assumed by all previous constructions [9,20,21],”
Oblivious RAM with O((logN)3) Worst-Case Cost (2011, unknown): “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)”
Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound (2015, methodology): “Since the original proposal of ORAM [19], it has been studied in various application settings including secure processors [12,14,37,47], cloud outsourced storage [21,49,50, 57] and secure multi-party computation [15,16,25,28,33,53].”
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.”
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].”