The Melbourne Shuffle: Improving Oblivious Storage in the Cloud
By O. Ohrimenko, Michael T. Goodrich, Roberto Tamassia, Eli Upfal. 2014
77 citations recorded by the source corpus.
We present a simple, efficient, and secure data-oblivious randomized shuffle algorithm. This is the first secure data-oblivious shuffle that is not based on sorting. Our method can be used to improve previous oblivious storage solutions for network-based outsourcing of data.
Subfields: Artificial Intelligence, Information Systems
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
- O. Ohrimenko
- Jonathan Ullman
- Ú. Erlingsson
- Bolin Ding
- Ilya Mironov
- Kunal Talwar
- Ananth Raghunathan
- Badih Ghazi
In Information Systems
- O. Ohrimenko
- Manuel Costa
- Cédric Fournet
- Ú. Erlingsson
- Kapil Vaswani
- Felix Schuster
- David Lie
- Petros Maniatis
Citations in the corpus
- Prochlo: Strong Privacy for Analytics in the Crowd (2017, methodology): “A bit further away from sorting lies the Melbourne Shuffle algorithm [58].”
- VC3: Trustworthy Data Analytics in the Cloud Using SGX (2015, methodology): “We plan to address these attacks with padding, clustering, and distributed shuffle techniques [45].”
- PROCHLO: Strong Privacy for Analytics in the Crowd (2017, methodology): “A bit further away from sorting lies the Melbourne Shuffle algorithm [58].”
- Privacy-Preserving Computation with Trusted Computing via Scramble-then-Compute (2017, methodology): “We implement the scrambler S using the Melbourne shuffle algorithm [29].”
- Observing and Preventing Leakage in MapReduce (2015, methodology): “Instead, for our solutions, we choose the parallel version of the Melbourne Shuffle [20], which offers the same security guarantees, and we implement it as two successive runs of the MapReduce job described below.”
- Oblivious Multi-Party Machine Learning on Trusted Processors (2016, methodology): “Repeatedly, (1) securely shuffle all instances at random, using Batcher’s sort, for example, or an oblivious shuffle [50]; (2) run the learning algorithm on the instances sequentially, rather than randomly, either individually or in small batches.”
- An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors (2018, background): “The Melbourne shuffle [36] is a randomized data-oblivious shuffle that makes O ( cn ) deterministic accesses to external memory, assuming private memory of size c √ n , and fails with negligible probability.”