Title: Private Access to Remote Data via the Melbourne Shuffle

Abstract:
A shuffle is an algorithm for rearranging an array to achieve a random permutation of its elements. Early shuffle methods were motivated by the problem of shuffling a deck of cards. An oblivious shuffle is a distributed shuffle executed by a client who permutes an array of encrypted data items stored at a server in such a way that the server cannot determine the output permutation with probability better than a random guess. Several private cloud storage solutions that obfuscate the access pattern to the data use an oblivious shuffle as a fundamental building block. We present the Melbourne Shuffle, a simple and efficient oblivious shuffle that allows a client with O(\sqrt{n}) memory to obliviously shuffle an array of size n stored at a server by exchanging O(\sqrt{n}) messages of size O(\sqrt{n}). The Melbourne Shuffle is the first provably secure oblivious shuffle that is not based on sorting.

This talk is based on the paper “The Melbourne Shuffle: Improving Oblivious Storage in the Cloud”, appeared in International Colloquium on Automata, Languages and Programming (ICALP), 2014. Joint work with Michael Goodrich (UC Irvine), Roberto Tamassia (Brown University) and Eli Upfal (Brown University)

Bio:
Olya Ohrimenko is a Postdoctoral Researcher in Constructive Security Group at Microsoft Research, Cambridge, and a research fellow at Darwin College, Cambridge University. Her research interests include privacy, integrity and security issues that emerge in the cloud computing environment. Olya received a Ph.D. degree from Brown University in 2013 and a B.CS. (Hons) degree from The University of Melbourne in 2007. She was an intern at Google, Microsoft Research Redmond and IBM Research Zurich.