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(√n) memory to obliviously shuffle an array of size n stored at a server by exchanging O(√n) messages of size O(√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” by Olga Ohrimenko, Michael Goodrich, Roberto Tamassia and Eli Upfal, International Colloquium on Automata, Languages and Programming (ICALP), 2014 (to appear).
Biography: Roberto Tamassia is the Plastech Professor of Computer Science and the Chair of the Department of Computer Science at Brown University. He is also the Director of Brown's Center for Geometric Computing. His research interests include data security and privacy, applied cryptography, analysis, design, and implementation of algorithms, graph drawing and computational geometry. He is an AAAS Fellow, ACM Fellow, and IEEE Fellow, and the recipient of a Technical Achievement Award from the IEEE Computer Society for pioneering the field of graph drawing. Thomson Reuters Highly Cited Research lists him among the most cited computer science authors. He co-founded the Journal of Graph Algorithms and Applications and the Symposium on Graph Drawing. He received a Ph.D. Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign.